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

From: David Abrahams (dave_at_[hidden])
Date: 2004-05-06 07:32:32

Pavol Droba <droba_at_[hidden]> writes:

> On Thu, May 06, 2004 at 04:33:54AM -0500, Aleksey Gurtovoy wrote:
>
> [snip]
>  
>> I wasn't suggesting to re-define the standard's Sequence concept to
>> mean what we want (although that's not entirely impossible). Rather, I
>> was saying that "Collection" is a bad substitute for the occupied
>> term.
>> 
>
>
>> > I found collection easy to understand. I don't understand what is
>> > wrong with it.
>>
>  
>> There is nothing wrong with the word per se. It just has a commonly
>> accepted meaning that is in conflict with the definition we are giving
>> to the identically named concept. In particular, like I said earlier,
>> "Collection" commonly implies storage, while the concept in question
>> specifically aims to represent sequences that don't have any.
>> Compare, for instance, http://tinyurl.com/32fmb and
>> http://tinyurl.com/3h23s.
>> 
>> > It very well fits into the standard concept hierarchy
>> >
>> > Collection < Container < Sequence
>> >                        < Associative container
>> 
>> Looks like a total mess to me. If anything, it should be
>> 
>>     Sequence < Collection < Container
>>                           < Associative Container
>>              < View
>> 
>>
>
> I don't agree, that sequence is a good candidate for this concept as
> you're suggestion. Sequence directlu implies that elements are
> sequentialy organized. 

Anything with iterators is sequentially organized.

> 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.
______________________________________________________________________________

> There is nothing like front() for map, yet it can be enumarated,
>
> Maybe the best name for the concept should be "Enumerable". That
> designates, the primar goal of this conceps, i.e. to be able to
> enumerate the elementes of an arbitrary collection/container or
> what ever you name it.

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.

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