RE: [boost] Re: iterator ranges; eliminating private member

From: Aleksey Gurtovoy (alexy_at_[hidden])
Date: 2001-11-05 02:30:48

Dave Harris wrote:
>     template <typename in_sequence, typename out_iterator>
>     out_iterator copy( in_sequence src, out_iterator dest ) [
>         for ( ; !src.at_end(); src.advance())
>             *dest++ = src.current();
>         return dest;
>     }
> 
> Just the names have been changed. The idea is to model a data 
> source like a sequential file. We can get the current item, advance 
> to the next, and test for no more items. It is not really like a range. 
> Stroustrup called it an input sequence in C++PL.

'input_seq' in C++PL has an iterator range interface. IMO it would be a
mistake for input sequences to have an interface different from all other
types of sequences (forward, bidirectonal, random access) STL algorithms
already, although implicitly, operate on. Sure, as it has discussed by
participants of this thread elsewhere, the notion of sequences is a key
concept of the STL, which obviously needs a more explicit support from the
library interface level, but let's make sure that we don't go too far in our
attempt to improve things. In my opinion, rewriting/duplicating all existing
STL algorithms in terms of 'src.at_end()', 'src.advance()' and
'src.current()' calls instead of itor != end, ++itor, *itor just for a sake
of different naming conventions (instead of building a wrapping interface
that just makes the implicit things explicit) is too far. For one, as others
already noted, marking input sequences as a special case just doesn't scale;
there are many algorithms that do operate on sequences, but impose more
demanding traversal requirements on them than simple "iterate forward until
you hit the end" ('unique', 'reverse', 'rotate', 'lower_bound', 'sort', just
to name several); the sequence concept's interface you propose just doesn't
fit there, and having such special interface for something that is a part of
more broad domain just isn't practical. Currently, the iterator concepts are
hierarchical - e.g. everything that is a forward iterator is also an input
iterator, and you can pass a former one to a function that requires the
latter. That's important. Citing a famous (in our circles :) posting of
Dietmar Kuehl to comp.std.c++
(http://groups.google.com/groups?selm=[e-mail]
ogle.com), "This provides a common interface, making the use, interface
design, and implementation of algorithms/functions operating on sequences
more simpler". Breaking this commonality would just unnecessary complicate
things both for users and implementors of the library without providing any
real value.

On the other hand, giving sequences iterator range interface is a natural
extension of the existing library framework, works well with the whole
hierarchy of sequence concepts, and is proved to be very practical and
useful.

> There seems to be a lot of overlap between the roles of 
> a range, and a container.

Any standard container is a model of (SGI STL) Container concept, that is a
refinement of (hypothetical) Sequence concept; iterator range is a model of
Sequence concept too, and a Sequence is (see
http://groups.yahoo.com/group/boost/message/15353):

"... anything to that you can apply begin/end operations in order
to get iterators for accessing the range of its elements. Any Container is a
model of Sequence, but Sequence is not necessary a container. In particular,
Sequence is not required to "own" its elements, i.e. the lifetime of an
element in a Sequence does not have to match the lifetime of the Sequence
object. Also, Sequence is not required to actually store its elements
somewhere, i.e. there is no guarantee that elements of a Sequence do all
exist at the same time - they might be created on the fly while you are
iterating the sequence. Nor is there a guarantee that more than one iterator
into a Sequence may be active at any one time. ..."

> > Any container or array type can be used to construct a range.
> 
> Are you suggesting that we pass a std::vector to copy(), by 
> value? That sounds expensive. I think we need to extract the range from 
> the vector before calling copy(). 

This has been discussed here before, please see "Boost algorithm library"
thread, and, more specifically,
http://groups.yahoo.com/group/boost/message/15360. In short, sequence
algorithms should take their arguments by reference ;).

Aleksey