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

From: Pavol Droba (droba_at_[hidden])
Date: 2004-05-06 09:23:08

On Thu, May 06, 2004 at 08:32:32AM -0400, David Abrahams wrote:
> Pavol Droba <droba_at_[hidden]> writes:
> 

[snip]
 
> > There are operations that are natural only to
> > sequences like push_front/back() front/back() pop_front()/back.
> 
> Those are not sequence operations.  Alex Stepanov defined "Sequence"
> for us long before this library:
> 
>   http://www.sgi.com/tech/stl/Sequence.html
> 
> and the standard contains this definition:
> 
> Table 67---Sequence requirements (in addition to container)
> ______________________________________________________________________________
> expression              return type                        pre/post-condition
>                                                              assertion/note  
> ______________________________________________________________________________
> ______________________________________________________________________________
> X(n, t)                                                     post: size() == n.
> X a(n, t);                           constructs a sequence with n copies of t.
> ______________________________________________________________________________
> X(i, j)                              post: size() == distance between i and j.
> X a(i, j);                     constructs a sequence equal to the range [i,j).
> ______________________________________________________________________________
> a.insert(p,t)           iterator                 inserts a copy of t before p.
> ______________________________________________________________________________
> a.insert(p,n,t)         void                   inserts n copies of t before p.
> ______________________________________________________________________________
> a.insert(p,i,j)         void                pre: i,j are not iterators into a.
>                                  inserts copies of elements in [i,j) before p.
> ______________________________________________________________________________
> a.erase(q)              iterator           erases the element pointed to by q.
> ______________________________________________________________________________
> a.erase(q1,q2)          iterator     erases the elements in the range [q1,q2).
> ______________________________________________________________________________
> a.clear()               void                             erase(begin(), end())
>                                                             post: size() == 0.
> ______________________________________________________________________________
> 
>

Actualy they are: Std 23.1.1 Table 68: Optional Sequence Operation. 
Sure, not every sequence must have them, but for non-sequencial containers, 
they have no sense and that's what I wanted to say.

 
> I'd say "Iterable" if we have to use an "-able" term.  24.1/7
> suggests to me that "Range" might be OK:
> 
>   Most of the library's algorithmic templates that operate on data
>   structures have interfaces that use ranges.  A range is a pair of
>   iterators that designate the beginning and end of the computation. A
>   range [i, i) is an empty range; in general, a range [i, j) refers to
>   the elements in the data structure starting with the one pointed to
>   by i and up to but not including the one pointed to by j. Range [i,
>   j) is valid if and only if j is reachable from i. The result of the
>   application of functions in the library to invalid ranges is
>   undefined.
> 

So it seems, that Range is the clear winner here. 

Regards,

Pavol