Re: [boost] Re: [Formal review] Collection Traits library

From: Pavol Droba (droba_at_[hidden])
Date: 2004-05-08 07:48:14

On Sat, May 08, 2004 at 06:06:47AM -0400, David Abrahams wrote:
> "Thorsten Ottosen" <nesotto_at_[hidden]> writes:
> 
> > | > hm...empty() is O(N) for strings if implemented as end() - begin(), but
> > | > O(1) currently.
> > |
> > | What kind of string doesn't have random-access iterators? Or are you
> > | talking about C-strings which would have an O(N) end() function?
> >
> > yes.
> >
> > | I am leery of performance discontinuities like O(N) for end(char
> > | const*).  Maybe it just shouldn't be provided (or something).
> >
> > Pavol uses it havily in his string library. The "dangerous" thing would be not to put
> > computation of the end-iterator out-side the loop, eg.
> >
> > for( iterator_type_of<T>::type i = begin( c ); i != end( c ); ... )
> >                                                                   ^^^^^^^^^^  ^
> > is not good. But one wouldn't do that anyway. And if one did it, what are the chances of
> > the argument being a char*?
> 
> Too many chances are being taken here, IMO.  It doesn't feel right.
> STL's end is guaranteed O(1) and I'm really concerned about anything
> that violates that expectation.
> 
> Maybe the string algorithm library ought to use a different name for
> this; for example:
> 
>   sentinel_type_of<T>::type f = finish( c );
>   for (iterator_type_of<T>::type i = begin( c ); i != f; ++i)
>       ...
> 
> In that case, the same mistake
> 
>   for (iterator_type_of<T>::type i = begin( c ); i != finish(c); ++i)
>       ...
> 
> wouldn't hurt at all.
> 
>   struct sentinel_ {};
> 
>   template <class T>
>   sentinel_ finish(T*) { return sentinel_(); }
> 
>   template <class T>
>   typename iterator_type_of<T>::type finish(T& x)
>   { return x.end(); }
> 
>   template <class T>
>   typename iterator_type_of<const T>::type finish(T const& x)
>   { return x.end(); }
> 
>   template <class 
>   template <class T>
>   bool operator==(T* x, sentinel_) { return !*x; }
> 
>   template <class T>
>   bool operator==(sentinel_, T* x) { return !*x; }
> 
>   template <class T>
>   bool operator!=(T* x, sentinel_) { return *x; }
> 
>   template <class T>
>   bool operator!=(sentinel_, T* x) { return *x; }
> 

This is an elegant solution for this particular problem. However iteration is not the
only construct, that uses iterators. 
If you would have a look into the implementaion of the string_algo library, you will see,
that there are very few constructs like this. I'm using collection traits
facility mostly to extract begin() and end() iterators, that are later forwarded to
the iterator based function. This is clearly not possible with "finish".
(you cannot, for instance, do following
   std::copy(begin(c), finish(c), it) 
)

Strong requirement that end() have complexity of O(N) rules out C-Strings. This is very unfortunate,
because this is one of the best use-cases for the collection_traits library.

Special threatment of char[] arrays is needed, so thay bahave in the same way as they char* conterparts.
(and std::string too). When I used the collection traits for the first time, I was very surprised,
that end(char[]) was pointing after the terminating 0. This is definitely not the expected behaviour,
therefor it was changed.

Regards,

Pavol