This is the mail archive of the libstdc++@sourceware.cygnus.com mailing list for the libstdc++ project. See the libstdc++ home page for more information.


[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index] [Subject Index] [Author Index] [Thread Index]

Re: Iterator class for vector and basic_string



Ryszard Kabatek <rysio@rumcajs.chemie.uni-halle.de> wrote:
: I wrote an iterator class for std::vector<> and std::basic_string<>.

: If You mean it's OK I will make a patch.

Let me make some comments. Hopefully it'll spur some useful discussion.
If the general spirit of my comments will be agreed with, I also
volunteer to make the nesessary implementation.

First a general thing:

I think vector and string should have their own iterators. The reason
is that error messages will be far more intelligible. And we should
keep all the names as close to the ones mentioned in the standard as 
possible for the same very reason. For example, vector<int>::const_iterator 
should be a real class, named const_iterator and be a member class of 
vector<int, .......>, not a typedef to 
_Iterator<int, ptrdiff_t, const int*, const int&);

It is also my opinion that const_iterator and iterator should be
separate and unrelated classes. It's much safer and will provide
better error messages. Also see later.

As things stand right now, user-induced error messages from template
code are totally useless. I think the users can use all the help we
can give them. 

Hopefully, these considerations will go away after egcs implements 
typedef-based diagnostics, if ever.

: /*
:  * Written by Ryszard Kabatek
:  */

: # ifndef _ITERATOR_FOR_VECTOR_AND_BASIC_STRING_H
: # define _ITERATOR_FOR_VECTOR_AND_BASIC_STRING_H

: /*******************************************************************
: template<typename _Tp, typename _Dist = ptrdiff_t,
:          typename _Ptr = _Tp*, typename _Ref = _Tp&>
: class _Iterator;

I can't imagine under which circumstances we can possibly use
these default template parameters. Can you give me an example?
If not, I think we should remove them.

: template<typename _Tp, typename _Dist, typename _Ptr, typename _Ref>
: _Iterator<_Tp, _Dist, _Ptr, _Ref>::iterator_category
: iterator_category(const _Iterator<_Tp, _Dist, _Ptr, _Ref>&);

: template<typename _Tp, typename _Dist, typename _Ptr, typename _Ref>
: _Iterator<_Tp, _Dist, _Ptr, _Ref>::value_type*
: value_type(const _Iterator<_Tp, _Dist, _Ptr, _Ref>&);
:  
: template<typename _Tp, typename _Dist, typename _Ptr, typename _Ref>
: _Iterator<_Tp, _Dist, _Ptr, _Ref>::difference_type*
: distance_type(const _Iterator<_Tp, _Dist, _Ptr, _Ref>&);
: *******************************************************************/

I never saw you use any of these three functions. What are they for?

: # include <iterator>

: template<typename _Tp, typename _Dist = ptrdiff_t,
:          typename _Ptr = _Tp*, typename _Ref = _Tp&>
: class _Iterator {
:   public:
:     typedef random_access_iterator_tag                   iterator_category;

Like Nathan Myers already mentioned, we should inherit form
struct iterator<bidirectional_iterator_tag, _Dist, _Ptr, _Ref>
then instead of this

:     typedef _Tp                                           value_type;
:     typedef _Dist                                         difference_type;
:     typedef _Ptr                                          pointer;
:     typedef _Ref                                          reference;

do this:

typedef iterator<bidirectional_iterator_tag, _Dist, _Ptr, _Ref> inherited;

typedef typename inherited::value_type          value_type;
typedef typename inherited::difference_type     difference_type;
typedef typename inherited::pointer             pointer;
typedef typename inherited::reference           reference;
typedef typename inherited::iterator_category   iterator_category;

After that, we should also specialize iterator_traits<> for the newly
defined iterators.

:     typedef _Iterator<_Tp, _Dist, _Tp*, _Tp&>             iterator;
:     typedef _Iterator<_Tp, _Dist, const _Tp*, const _Tp&> const_iterator;

:     typedef _Iterator<_Tp, _Dist, _Ptr, _Ref>             _Self;

I think _Self should be a private typedef.

:   public:
:     _Iterator();

:     explicit _Iterator(pointer __p);

I think _Iterator::_Iterator(pointer __p) should be private. Other then
plain aesthetics, this will also prevent users from writing non-compliant
code like

vector<int>::iterator i (0);


:     // template copy constructor for conversion
:     // iterator <-- const_iterator.

Small typo. It's ``iterator --> const_iterator''

:     template<typename _Up>
:     _Iterator(const _Iterator<_Tp, _Dist, _Up*, _Up&>& __rhs);

That's very unsafe. This will provide a conversion not only
from iterator to const_iterator but many other undesirable
_implicit_ conversions as well. For example, 
vector<Derived>::iterator --> vector<Base>::iterator.

Making iterator and const_iterator separate classes (see above) 
will solve this. 

:     reference operator*() const;

:     pointer   operator->() const;

:     difference_type operator-(const _Self& __rhs) const;

I think operator-() should be a free function, not a member function.
Otherwize, the following will be ill-formed:

vector<int>::iterator        i = v.begin(); 
vector<int>::const_iterator ci = v.end();
i - ci;

Also -- general understanding is that Iterators are typically
designed so that they can be very efficiently passed by value
(ours are). And they are absolutely not supposed to be used
polymorphically. I think we should lose passing by reference 
altogether.

:     _Self& operator++();

:     _Self  operator++(int);

:     _Self& operator--();

:     _Self  operator--(int);

:     _Self& operator+=(difference_type __n);

:     _Self  operator+(difference_type __n) const;

Ditto. Imagine shock of the users, when they find out that
vector<int>::iterator  i = v.begin();
i + 3; // legal
3 + i; // illegal

especially since the Standard requires that the two be equivalent
(Table 76).

Even more dangerous would be some subtle difference in behaviour
we might miss. 

:     _Self& operator-=(difference_type __n);

:     _Self  operator-(difference_type __n) const;

I think having this one as a member, not as a free function,
has a potential to surprize users. Everybody expects these
kinds of operators to be non-members. Imagine somebody
defining his own class A with an implicit conversion to
iterator. Then he would expect that ``A()-3'' be a well-formed
expression, while it is not, if the above operator-() is
a member.

:     reference operator[](difference_type __i) const;

:     // The comparision operators are implemented as member templates
:     // for comparision between iterator and const_iterator.

If we make iterator and const_iterator two unrelated types with
a safe conversion from iterator to const_iterator, then there
would be no need to make these member templates. They would be
free functions. It's much more intuitive and safe (in terms
of symmetry). It will also be much safer in terms of operands.
Just like I mentioned above, as defined, we can compare
things which should not be comparable, like 

vector<Base>::iterator() == vector<Derived>::iterator(); 

:     template<typename _Up>
:     bool operator==(const _Iterator<_Tp, _Dist, _Up*, _Up&>& __rhs) const;

:     template<typename _Up>
:     bool operator!=(const _Iterator<_Tp, _Dist, _Up*, _Up&>& __rhs) const;

:     template<typename _Up>
:     bool operator<(const _Iterator<_Tp, _Dist, _Up*, _Up&>& __rhs) const;

:     template<typename _Up>
:     bool operator<=(const _Iterator<_Tp, _Dist, _Up*, _Up&>& __rhs) const;

:     template<typename _Up>
:     bool operator>(const _Iterator<_Tp, _Dist, _Up*, _Up&>& __rhs) const;

:     template<typename _Up>
:     bool operator>=(const _Iterator<_Tp, _Dist, _Up*, _Up&>& __rhs) const;

:   private:
:     pointer _M_data;
: };


: ///////////////////
: // inline functions
: ///////////////////

: template<typename _Tp, typename _Dist, typename _Ptr, typename _Ref>
: inline
: _Iterator<_Tp, _Dist, _Ptr, _Ref>::_Iterator()
: : _M_data(0) 
: {
: }

: template<typename _Tp, typename _Dist, typename _Ptr, typename _Ref>
: inline
: _Iterator<_Tp, _Dist, _Ptr, _Ref>::_Iterator(pointer __p) 
: : _M_data(__p) 
: {
: }

: template<typename _Tp, typename _Dist, typename _Ptr, typename _Ref>
: template<typename _Up>
: inline
: _Iterator<_Tp, _Dist, _Ptr, _Ref>::
: _Iterator(const _Iterator<_Tp, _Dist, _Up*, _Up&>& __rhs) 
: : _M_data(__rhs.operator->()) 
: {
: }

: template<typename _Tp, typename _Dist, typename _Ptr, typename _Ref>
: inline _Iterator<_Tp, _Dist, _Ptr, _Ref>::reference
: _Iterator<_Tp, _Dist, _Ptr, _Ref>::operator*() const 
: {
:   return *_M_data;
: }

This is somewhat controvercial, but I think we should prepend `this->'' 
in front of all member variables and functions, like this:

    return *(this->_M_data);

This will reduce the risk great deal. Imagine somebody doing
#define _M_data 0      

On the other hand, there is absolutely no downside that I know of.

Also, for consistency with the rest of your code, you might
want to rewrite it like this:

   return *(this->operator->());

However, I would define a private accessor _M_data() (this would
require renaming of the data member ``_M_data'' into ``_M_data_''
or something)  and use that, instead of operator->(). And I would 
implement operator->() in terms of _M_data_(). As coded right now,
there is a too tight coupling between the implementation of
operator->() and the rest of the code. 

[......]

I never noticed any need for the three functions below.
Where are they used?

: template<typename _Tp, typename _Dist, typename _Ptr, typename _Ref>
: inline _Iterator<_Tp, _Dist, _Ptr, _Ref>::iterator_category
: iterator_category(const _Iterator<_Tp, _Dist, _Ptr, _Ref>&)
: {
:   return _Iterator<_Tp, _Dist, _Ptr, _Ref>::iterator_category();
: }

: template<typename _Tp, typename _Dist, typename _Ptr, typename _Ref>
: inline _Iterator<_Tp, _Dist, _Ptr, _Ref>::value_type*
: value_type(const _Iterator<_Tp, _Dist, _Ptr, _Ref>&)
: {
:   return 0;
: }

: template<typename _Tp, typename _Dist, typename _Ptr, typename _Ref>
: inline _Iterator<_Tp, _Dist, _Ptr, _Ref>::difference_type*
: distance_type(const _Iterator<_Tp, _Dist, _Ptr, _Ref>&)
: {
:   return 0;
: }

: # endif // _ITERATOR_FOR_VECTOR_AND_BASIC_STRING_H

Oleg.