Re: Iterators for basic_string/vector

[Benjamin Kosnik <bkoz@cygnus.com>]

My apologies for the delay in responding to this email, and also for not
paying closer attention to the debate/discussion last month. I'm not
particularly enamored with the ammount of code duplication that has been
in both Oleg's and your current proposals. There has got to be a better
way.

Although I believe these iterator classes are useful, I would like to
figure out a way to implement them that involves the least ammount of code
duplication, both between the interator and const_iterator classes, and
between string and vector (where the classes will eventually be used.) 

Here are some (divergent) thoughts:

 
// string::iterator

// 21.3 [lib.basic.string]
// p 6

// typedef implementation defined iterator // 23.1
// typedef implementation defined const_iterator // 23.1


// 23.1 container requirements

// p 5
X::iterator	
return: 	iterator type pointing to T. 	
conditions: 	any iter_categ except output_iterator. 
		convertible to X::const_iterator. 

X::const_iterator	
return: 	iterator type pointing to const T.	
conditions: 	any iter_categ except output_iterator. 

// p 9 
// If the iterator type of a container belongs to the
// bidirectional or random access iterator categories (24.1) the
// container is called reversible and satisfies additional
// requirements, noted on (p. 461).

I don't really see any real reason to have separate classes for
const_iterator and iterator. In particular, it is not required by the
standard. Deque, vector, and string currently do not use this
convention. The only advantage to this approach that I can see is
readability of error messages. The possible disadvantages that I can
see are at bit more compelling, and include: needless duplication of
code, which will result in less comprehensible header files, the
duplicity in revamping this approach when compiler behavior WRT
diagnostics changes, etc. As this is a standard library, one that
other C++ library designers will hopefully look at for design ideas
and advice, I believe that the collective efforts would be most
efficiently used creating the most well-designed library, period,
regardless of particular compiler limitations. If all libraries work
around this problem in similar ways, then there will never be any
pressure on g++ to improve its admittedly poor diagnostics.


// what is vector::iterator?
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef value_type* iterator;
  typedef const value_type* const_iterator;

// what is string::iterator?
    typedef typename _Alloc::pointer pointer;
    typedef typename _Alloc::const_pointer const_pointer;
    typedef pointer iterator;
    typedef const_pointer const_iterator;
 
It seems to me that vector, deque, and string want to use iterators
that meet the standard requirement for random_access_iterators, yet
none exist as a standard library component. Deque's iterator class is
seemingly specialized for deques. The most elegant and conforming
solution that I can see is to make a templatized class, and stick it
in some kind of standard namespace for extensions to the standard
library, and use this one piece of code for both container classes
that need it, yet allows other code to reuse this component. As this
namespace doesn't exist, perhaps we could start with "ext" or
"__std_ext" or something along those lines.

// NB--why did vector and string not get designed with iterator as a
// class? Does SGI have a reason besides expedience for the current
// implementation with vector? Nathan or Matt, can you weigh in here?

Looking at stl_iterator.h and the standard, it looks like we'll need:

template <typename _T>
struct random_access_iterator: public iterator<random_access_iterator_tag, 
iterator_traits<_T*>::value_type, iterator_traits<_T*>::difference_type, 
iterator_traits<_T*>::pointer, iterator_traits<_T*>::reference
{ };

Then in string you could typedef

 typedef random_access_iterator<char_type> iterator;
 typedef random_access_iterator<const char_type> const_iterator;

??

-Benjamin