Boost logo

Boost :

From: David Abrahams (dave_at_[hidden])
Date: 2004-05-08 05:06:47


"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; }

-- 
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk