[boost] Re: What is the status of Container algorithms in sandbox

From: Thorsten Ottosen (nesotto_at_[hidden])
Date: 2003-05-11 16:19:31

> > Likewise, for me a container is simply one form of range, but I can
> > imagine many others.  Perhaps I should take a look at the Views
> > library?  To phrase the library in terms of containers seems to limit
> > it, to me.
>
> I like your approach, FWIW.  It's easy enough to get an iterator out
> of a sequence when you need one.  It can be harder to come up with a
> sequence given an iterator.

ok, I thought a little about it and I tend to agree that there is an
underlying range abstraction. I remember Pavol Dropa wrote a class called
iterator_range for his string lib...and that is maybe what we've got, not a
range, but an iterator range concept:

Concept:  IteratorRange

Description:
A type is an IteratorRange if objects of that type can be used to construct
iterators (denoting ranges) that can be passes to iterator-based algorithms.

Associated types:

Name                     |                        Type
|    Requirements
----------------------------------------------------------------------------
------------
iterator type            | iterator_range_traits<X>::iterator              |
The type of iterator used to iterate through an iterator range's elements.
const iterator type   | iterator_range_traits<X>::const_iterator    |  A
type of iterator that may be used to examine, but not to modify, an iterator
range's elements
distance type           | iterator_range_traits<X>::difference_type | bla
bla
size_type                | iterator_range_traits<X>::size_type           |
bla bla

Notation:
      X  A type that is a model of IteratorRange
      x, y, z  Object of type X

Valid expressions:

Name                          |     Expression            |   Type
requirements             | Return type
----------------------------------------------------------------------------
--------------
beginning of range        |  begin( x )                 |
|  iterator_range_traits<X>::iterator if a is mutable,

iterator_range_traits<X>::const_iterator otherwise
 end of range               |  end( x )                    |
|  iterator_range_traits<X>::iterator if a is mutable,

iterator_range_traits<X>::const_iterator otherwise
 size of range               |  size( x )                    |
|  iterator_range_traits<X>::isize_type

Complexity guarantess:
begin() and end() are amortized constant time. size() is linear in the
iterator range's size or better

Invariants
same as on http://www.sgi.com/tech/stl/Container.html

Concept: ReversibleIteratorRange

Description:
A type is an IteratorRange if objects of that type can be used to construct
iterators (at least bidirectional) (denoting ranges) that can be passes to
iterator-based algorithms.

Associated types:

Name                                  |                        Type
|    Requirements
----------------------------------------------------------------------------
------------
Reverse iterator type            |
iterator_range_traits<X>::reverse_iterator              |  The type of
iterator used to iterate through a reversible

iterator range's elements.
const reverse iterator type    |
iterator_range_traits<X>::const_reverse_iterator    |  A type of iterator
that may be used to examine, but not to modify,

a reversible iterator range's elements
Valid expressions:

Name                                      |     Expression            |
Type requirements             | Return type
----------------------------------------------------------------------------
--------------
beginning of reverse range        |  rbegin( x )                 |
|  iterator_range_traits<X>::reverse_iterator if a is mutable,

iterator_range_traits<X>::const_reverse_iterator otherwise
 end of reverse range               |  rend( x )                    |
|  bla bla

So could this be a way to go?

regards

Thorsten