Author: | Thorsten Ottosen |
---|---|

Contact: | nesotto@cs.aau.dk |

organizations: | Dezide Aps and Aalborg University |

Date: | 2005-08-27 |

Number: | WG21/N1871 and J16/05-0131 |

Working Group: | (R)Evolution |

Abstract

This paper proposes the addition of ranges to the C++ standard library to reduce the syntactic burden on programmers. The paper also considers a number of range related utilities that can greatly simplify the use of algorithms and loops.

A range is simply an encapsulation of two iterators. The term range is due to paragraph 24.1/7 from the C++ standard:

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 byiand up to but not including the one pointed to byj. Range[i, j)is valid if and only ifjis reachable fromi. The result of the application of functions in the library to invalid ranges is undefined.

Even though standard algorithms are specified in terms of iterator ranges, they are still somewhat clumsy to use. By combining the two iterators into one object, we can achieve great benefits. This proposal will give standard C++

- a drastic reduction in syntactic overhead,

- an infrastructure for range-based algorithms (which can also be used for the new
for-loop (see n1868)),

- a new concise idiomatic use of algorithms and loops,

- safer use of built-in arrays.

The next example shows how slick and functional the syntax becomes with use of ranges:

vector<int> integers; // old style typedef vector<int>::iterator iterator; pair<iterator,iterator> p = equal_range( integers.begin(), integers.end(), 0 ); for_each( p.first, p.second, some_functor() ); // new style for_each( equal_range(integers, 0), some_functor() );

The latter approach won't give you Cobol-fingers.

The range infrastructure consists of free-standing traits and functions that enable easy support of UDTs. Some of the functions have been separately suggested in Walter Browns proposal (see n1674).

A set of range adapters and overloaded operators make it a dream to use standard algorithms. Just consider the following example:

std::vector<int*> ptr_vec = ...; std::copy( ptr_vec | std::reversed | std::indirected, std::ostream_iterator<int>( std::cout ) );

The expression `ptr_vec | std::reverse | std::indirect`
extracts the `begin()` and `end()` iterators from `ptr_vec`
and then wraps those iterators in (1) `reverse_iterator`s
and (2) `indirect_iterator`s. The result of the expression
is then a range holding these wrapped iterators---that range
is then passed to a new overload of `std::copy()` that
accepts a range as its first argument. Accomplishing the
same without the range abstractions takes quite some
work.

The basic elements of the library consists of typetraits and freestanding functions.

This section briefly introduces range concepts. A range concept has two components:

- the traversal type of its associated iterators

- whether the range is copyable and owns the elements it provides iteration over

A range is assume to be noncopyable unless otherwise specified.

We thus talk about the following types of ranges

- SinglePassRange
- ForwardRange
- BidirectionalRange
- RandomAccessRange

All expressions `rng` whose type models a range
can be used as arguments to the three freestanding
functions

`begin(rng)``end(rng)``empty(rng)`

In addition, for an expression whose type models a ForwardRange we can say

`size(rng)`

A CopyableRange owns the elements in the range and has a deep-copy copy-constructor.

**See also**

Add the following to the `<iterator>` header
(in namespace `std`):

template< class T > auto begin( T&& t ) -> decltype( t.begin() ); template< class T > T begin( const pair<T,T>& p ); template< class T, size_t N > T* begin( T (&a)[N] ); template< class T > auto end( T&& t ) -> decltype( t.end() ); template< class T > T end( const pair<T,T>& p ); template< class T, size_t N > T* end( T (&a)[N] ); template< class T > bool empty( const T& t ); template< class T > auto size( const T& t ) -> decltype( t.size() ); template< class T > typename iterator_traits<T>::size_type size( const pair<T,T>& p ); template< class T, size_t N > size_t size( const T (&a)[N] ); template< class T > struct range_iterator; template< class T > struct range_reverse_iterator; template< class T > struct range_value; template< class T > struct range_difference; template< class T > struct range_size; template< class T > typename range_reverse_iterator<T>::type rbegin( T&& t ); template< class T > auto rend( T&& t ) -> decltype( rbegin(t) ); template< class T > typename range_iterator<const T>::type const_begin( const T& t ); template< class T > auto const_end( const T& t ) -> decltype( const_begin(t) ); template< class T > typename range_reverse_iterator<const T>::type const_rbegin( const T& t ); template< class T > auto const_rend( const T& t ) -> decltype( const_rbegin(t) );

In the following `ptr` is a variable
of type `T*`.

`template< class T >
auto begin( T&& t ) -> decltype( t.begin() );`

- returns:
`t.begin()`

`template< class T >
T begin( const pair<T,T>& p );`

- returns:
`p.first`

`template< class T, size_t N >
T* begin( T (&a)[N] );`

- returns:
`a`

`template< class T >
auto end( T&& t ) -> decltype( t.end() );`

- returns:
`t.end()`

`template< class T >
T end( const pair<T,T>& p );`

- returns:
`p.second`

`template< class T, size_t N >
T* end( T (&a)[N] );`

- returns:
`a + N`

`template< class T >
bool empty( const T& t );`

- returns:
`begin(t) == end(t)`

`template< class T >
auto size( const T& t ) -> decltype( t.size() );`

- returns:
`t.size()`

`template< class T >
typename iterator_traits<T>::size_type size( const pair<T,T>& p );`

- returns:
`distance(p.first,p.second)`

`template< class T, size_t N >
size_t size( const T (&a)[N] );`

- returns:
`N`

`template< class T >
struct range_iterator;`

- description: A TransformationTrait that defines the iterator of a range
- definition of
`type`:`typedef decltype( begin(*ptr) ) type;`

`template< class T >
struct range_reverse_iterator;`

- description: A TransformationTrait that defines the reverse iterator of a range
- definition of
`type`:`typedef reverse_iterator< typename range_iterator<T>:type > type;`

`template< class T >
struct range_value;`

- description: A TransformationTrait that defines the value type of the iterators of a range
- definition of
`type`:`typedef typename iterator_traits< typename range_iterator<T>::type >::value_type type;`

`template< class T >
struct range_difference;`

- description: A TransformationTrait that defines the difference type of the iterators of a range
- definition of
`type`:`typedef typename iterator_traits< decltype( begin(*ptr) ) >::difference_type type;`

`template< class T >
struct range_size;`

- description: A TransformationTrait that defines the size type of the iterators of a range
- definition of
`type`:`typedef decltype( size(*ptr) ) type;`

`template< class T >
typename range_reverse_iterator<T>::type rbegin( T&& t );`

- returns:
`decltype( rbegin(t) )(end(t))`

`template< class T >
auto rend( T&& t ) -> decltype( rbegin(t) );`

- returns:
`decltype( rbegin(t) )(begin(t))`

`template< class T >
typename range_iterator<const T>::type const_begin( const T& t );`

- returns:
`begin(t)`

`template< class T >
auto const_end( const T& t ) -> decltype( const_begin(t) );`

- returns:
`end(t)`

`template< class T >
typename range_reverse_iterator<const T>::type const_rbegin( const T& t );`

- returns:
`rbegin(t)`

`template< class T >
auto const_rend( const T& t ) -> decltype( const_rbegin(t) );`

- returns:
`rend(t)`

The above TransformationTraits differ slightly from those currently in Boost.Range. In particular, Boost.Range had both

`range_iterator`and`range_const_iterator`which were*unaffected*by the const-ness of the template argument. Expericence showed, however, that you rarely want the iterator not to follow the constness of the argument and so the two traits have been combined into one. (The same comment applies to`reverse_iterator`).Boost.Range currently treats arrays and character arrays differently, but that functionality has been deprecated and is therefore not part of this proposal. After lengthy discussion on the Boost Dev. list, it was decided that this functionality was actually a problem in generic code.

In a discussion on the Boost Dev. list, the names

`const_begin()/const_end()`and`const_rbegin()/const_rend()`were preferred to the names`cbegin()/cend()`and`crbegin()/crend()`suggested by Walter Brown in n1674.The core functionality means that the following types conforms to the range concept:

- standard containers (including
`tr1::array`) - pairs of iterators
- built-in arrays

One might consider supporting additional types like tuples.

- standard containers (including
If the use of the TransformationTraits seems to verbose, we might consider abbreviation like:

namespace rng { template< class T > using iterator = typename range_iterator<T>::type; }

using template aliases.

Should we add a

`range_category`TransformationTrait?

For all iterator-based
algorithms it is proposed to add additional
overloads that take a range whenever two
iterators is expected. For quite some algorithms
(e.g. `adjacent_find()`, `mismatch()`, `equal()`, `search_n()` etc.)
this will lead to ambiguities in a language
without concepts. Therefore it is suggested that the
overloaded algorithms are provided in namespace `std::rng`
(see also this discussion).

The following should be added to chapter 17:

For all iterator based algorithms described in 20.4.4, 25.1-3 and 26.4 it holds that

for all algorithms of the form:

template< class Iterator, ... > return-type algo( Iterator first, Iterator last, ... )a range-based version is placed in namespace

std::rngof the form:template< class Range, ... > return-type algo( Range&& r, ... )which forwards to the algorithm in namespace

stdusing unqualified calls tobegin()andend(). (Remark: the return type specified withreturn-typethe same in both the iterator-based and the range-based functions.)

for all algorithms of the form:

template< class Iterator, class Iterator2, ... > return-type algo( Iterator first, Iterator last, Iterator2 first2, Iterator2 last2, ... )a range-based version is placed in namespace

std::rngof the form:template< class Range, class Range2, ... > return-type algo( Range&& r, Range2&& r2, ... )which forwards to the algorithm in namespace

stdusing unqualified calls tobegin()andend().For range-based algorithms described above it holds that

for all algorithms taking an output iterator of the form

template< ..., class OutIter, ... > return-type algo( ..., OutIter, ... )a range-based version of the form:

template< class Sequence, ... > CopyableRange algo( ... )is added.

For the classes `basic_string`,
`deque`, `list`, `vector`, `map`, `multimap`, `set`
and `multiset` it holds that

the following new members are added:

const_iterator const_begin() const; const_iterator const_end() const; const_reverse_iterator const_rbegin() const; const_reverse_iterator const_rend() const;for all member-functions of the form:

template< class Iterator > return-type fun( Iterator first, Iterator last )a range-based version is added of the form:

template< class Range > return-type fun( const Range& r )which forwards to the iterator-based version via unqualified calls to

begin()andend().for all member-functions of the form:

template< class Iterator > return-type fun( ..., Iterator first, Iterator last )a range-based version is added of the form:

template< class Range > return-type fun( ..., const Range& r )which forwards to the iterator-based version via unqualified calls to

begin()andend().

It is suggested that all algorithms and containers described in tr1 and other proposals adopt the two version approach described above.

- Should constructers that take two iterators also be accompanied
by a range-based constructor? This will make it easy to copy
eg. a
`vector`to a`deque`. Making the constructor do the right thing is getting complicated, though.

- Putting every algorithm in namespace
`std::rng`is somewhat controversial. Maybe we should consider`enable_if`-like disambiguiting instead to give users the easiest-to-use library. Of course, with concepts in the language, there is no problem anymore.

- We might one to reconsider on a case-by-case basis if the return type
of range-based algothms can be changed for the better. For example,
`remove()`might return the removed range so it is easy to pass this to`erase()`in a container.

Outside the core functionality, Boost.Range supplies a few handy utility-classes for using iterator views:

Overloaded operators are provided s.t. comparisons between view-objects and container-objects are easy. For example:

string s = ...; sub_range<string> sub = find( s, ... ); if( sub == string("foo") ) { sub[0] = 'b'; assert( sub == string("boo") ); }

The class template `range` is templated on
an iterator and hence very generic.

namespace std { template< class Iter > class range { public: // Forward Range types typedef typename iterator_traits<Iter>::value_type value_type; typedef typename iterator_traits<Iter>::reference reference; typedef typename iterator_traits<Iter>::difference_type difference_type; typedef typename iterator_traits<Iter>::size_type size_type; typedef Iter iterator; typedef Iter const_iterator; public: // construction, assignment range(); template< class Iter2 > range( Iter2 begin, Iter2 end ); template< class Rng > range( Rng&& r ); template< class Rng > range& operator=( Rng&& r ); public: // Forward Range functions iterator begin() const; iterator end() const; size_type size() const; bool empty() const; public: // convenience operatorunspecified_bool_type()const; bool equal( const range& ) const; reference front() const; reference back() const; reference operator[]( size_type at ) const; void advance_begin( difference_type n ); void advance_end( difference_type n ); private: Iter first; // exposition only Iter last; // exposition only }; // stream output template< class Iter, class T, class Traits > std::basic_ostream<T,Traits>& operator<<( std::basic_ostream<T,Traits>& Os, const range<ForwardTraversalIterator>& r ); // comparison template< class Iter, class Iter2 > bool operator==( const range<Iter>& l, const range<Iter2>& r ); template< class Iter, class Rng > bool operator==( const range<Iter>& l, const Rng& r ); template< class Iter, class Rng > bool operator==( const Rng& l, const range<Iter>& r ); template< class Iter, class Iter2 > bool operator!=( const range<Iter>& l, const range<Iter2>& r ); template< class Iter, class Rng > bool operator!=( const range<Iter>& l, const Rng& r ); template< class Iter, class Rng > bool operator!=( const Rng& l, const range<Iter>& r ); template< class Iter, class Iter2 > bool operator<( const range<Iter>& l, const range<Iter2>& r ); template< class Iter, class Rng > bool operator<( const range<Iter>& l, const Rng& r ); template< class Iter, class Rng > bool operator<( const Rng& l, const range<Iter>& r ); // external construction template< class Iter > range< Iter > make_range( Iter Begin, Iter End ); template< class Rng > auto make_range( Rng&& r ) -> range< decltype( begin(r) ) >; template< class Rng > auto make_range( Rng&& r, typename range_difference<Range>::type advance_begin, typename range_difference<Range>::type advance_end ) -> range< decltype( begin(r) ) >; template< class CopyableRng, class Rng > CopyableRng copy_range( const Rng& r ); }

The template argument `Iter` must be a model of `ForwardTraversalIterator`.

**Construction, assignment**:

range()

Effects: Constructs an object of classrange.Remarks: The stored iterators are singular.

template< class Iter2 > range( Iter2 begin, Iter2 end );

Precondition:Iter2is convertible toIter.Effects: Constructs an object of classrange.

template< class Rng > range( Rng&& r );

Precondition: The iterator type ofRngis convertible toIter.Effects: Constructs an object of classrangeusing unqualified calls tobegin(r)andend(r).

template< class Rng > range& operator=( Rng&& r );

Precondition: The iterator type ofRngis convertible toIter.Postcondition:begin() == begin(r) && end() == end(r).

**Forward Range functions**:

iterator begin() const;

Returns:first.

iterator end() const;

Returns:last.

size_type size() const;

Precondition:[begin(),end())is a valid range.Returns:std::distance(begin(),end()).

bool empty() const;

Precondition:begin()andend()are not singular.Returns:begin() == end().

**Convenience**:

operatorunspecified_bool_type()const;

Returns: a value convertible toboolindicating whetherempty()is true.

bool equal( const range& r ) const;

Precondition:begin()andend()are not singular.Returns:begin() == r.begin() && end() == r.end().

reference front() const;

Precondition:begin()is dereferenceable.Returns:*begin().

reference back() const;

Precondition:--end()is dereferenceable.Returns:*--end().

reference operator[]( size_type at ) const;

Precondition:Itermodels a RandomAccessIterator.Precondition:at < size().Returns:*(begin() + at).

void advance_begin( difference_type n );

Effects:advance(first,n).

void advance_end( difference_type n );

Effects:advance(last,n).

**Stream output**:

template< class Iter, class T, class Traits > std::basic_ostream<T,Traits>&

operator<<( std::basic_ostream<T,Traits>& os, const range<Iter>& r );

Effects:copy( r.begin(), r.end(), std::ostream_iterator<Elem>(os)); return Os;.

**Comparison**:

template< class Iter, class Iter2 > bool operator==( const range<Iter>& l, const range<Iter2>& r );

template< class Iter, class Rng > bool operator==( const range<Iter>& l, const Rng& r );

template< class Iter, class Rng > bool operator==( const Rng& l, const range<Iter>& r );

Precondition:landrare valid ranges.Returns:equal(l,r).

template< class Iter, class Iter2 > bool operator!=( const range<Iter>& l, const range<Iter2>& r );

template< class Iter, class Rng > bool operator!=( const range<Iter>& l, const Rng& r );

template< class Iter, class Rng > bool operator!=( const Rng& l, const range<Iter>& r );

Precondition:landrare valid ranges.Returns:!( l == r ).

template< class Iter, class Iter2 > bool operator<( const range<Iter>& l, const range<Iter2>& r );

template< class Iter, class Rng > bool operator<( const range<Iter>& l, const Rng& r );

template< class Iter, class Rng > bool operator<( const Rng& l, const range<Iter>& r );

Precondition:landrare valid ranges.Returns:lexicographical_compare(l,r).

**External construction**:

template< class Iter > range<Iter> make_range( Iter begin, Iter end );

Returns:range<Iter>(begin,end).

template< class Rng > auto make_range( Rng&& r ) -> range< decltype( begin(r) ) >;

Returns:range< decltype( begin(r) ) >(r).

template< class Rng > auto make_range( Rng&& r, typename range_difference<Rng>::type N, typename range_difference<Rng>::type M ) -> range< decltype( begin(r) ) >;

Effects:range< decltype( begin(r) ) > tmp(r); tmp.advance_begin(N); tmp.advance_end(M); return tmp;

template< class CopyableRng, class Rng > CopyableRng copy_range( const Rng& r );

Precondition:

- The value-type of
Rngis convertible to the value-type ofCopyableRng.CopyableRngmodels a CopyableRange.Returns:CopyableRng(begin(r),end(r)).

The class template `sub_range` is templated on
another Range and so can propagate constness because
it can infer what the associated `const_iterator` is.
Besides that it is exactly like `range`.

template< class Rng > class sub_range { public: typedef typename range_iterator<Rng>::type iterator; typedef typename range_iterator<const Rng>::type const_iterator;The remaining typedefs as in 'range<iterator>'public: // construction, assignment template< class Iter > sub_range( Iter begin, Iter end ); template< class Rng2 > sub_range( Rng2&& r ); template< class Rng2 > sub_range& operator=( Rng2&& r ); public: // Forward Range functions iterator begin(); const_iterator begin() const; iterator end(); const_iterator end() const; public: // convenience value_type& front(); const value_type& front() const; value_type& back(); const value_type& back() const; // for Random Access Range only: value_type& operator[]( size_type at ); const value_type& operator[]( size_type at ) const;rest of interface as if inherited from 'range<iterator>'};

- In Boost
`range`is called`iterator_range`, but it seems unnecessary to say we are dealing with iterators.

- The Boost versions of
`range`and`sub_range`gives well-defined behavior even when the stored iterators are singular. This behavior have been removed from the proposal as it means an object is 3 words instead of 2 words. Furthermore, it seems of little use to make the singularity of a range be different than singularity of its iterators.

- The helper function
`copy_range()`is useful generic libraries when a third-party type does not provide a constructor that takes two iterators. A version of`copy_range()`may then be found via ADL.

The last part of this proposal covers range adapters. These little helper classes has the following benefits:

- adapters are easily composable via
`operator|()`,

- the user can completely avoid naming the types of iterators and ranges---everything is deduced in function calls.

The adapters can all be build on top off iterator adapters although
the exact nature of these have been left unspecified. `operator|()`
is simply a short name for what would normally be called
a `make_XX()` function, though `operator|()` is much easier
to read---especially when applied several times.

Eric Niebler's range_ex code implements some of these adapters.

In the following `fwdRng` is an expression of a type that models
ForwardRange, `biRng` is an expression of a type that models
BidirectionalRange, `rndRng` is an expression of a type that models
RandomAccessRange, `pred` is an expression of a type that models
UnaryPredicate, `biPred` is an expression of a type that models
BinaryPredicate, `fun` is an expression of type that models
UnaryFunction. Furthermore, `n` and `m` are
integer expressions corresponding in type to the
size-type of the range in question.

General requirements:

- Applying
`operator|()`to a range`R`(always left argument) and a range adapter`RA`(always right argument) yields a new range type conforming to the same range concept as`R`.

- The return-type of
`operator|()`is otherwise unspecified.

`operator|()`is found by ADL because a range adapter is implemented in namespace`std`.

`operator|()`is used to add new behavior lazily and never modifies its left argument.

- All iterators extracted from the left argument are extracted using
unqualified calls to
`begin()`and`end()`.

- In addition to the throw-clauses below,
`operator|()`may throw exceptions as a result of copying iterators.

Valid expressions:

`fwdRng | std::filtered( pred )`

Precondition: The value-type of the range is convertible to the argument type ofpred.Postcondition: For all elementsxin the returned range,pred(x)is true.Throws: Whatever the copy-constructor ofpredmight throw.

`fwdRng | std::adjacent_filtered( biPred )`

Precondition: The value-type of the range is convertible to the argument types ofbiPred.Postcondition: For all adjacent elements[x,y]in the returned range,biPred(x,y)is true.Throws: Whatever the copy-constructor ofbiPredmight throw.

`fwdRng | std::transformed( fun )`

Precondition: The value-type of the range is convertible to the argument type offun.Postcondition: For all elementsxin the returned range,xis the result offun(y)whereyis the corresponding element in the original range.Throws: Whatever the copy-constructor offunmight throw.

`fwdRng | std::indirected`

Precondition: The value-type of the range defines unaryoperator*()Postcondition: For all elementsxin the returned range,xis the result of*ywhereyis the corresponding element in the original range.

`biRng | std::reversed`

Returns: A range whose iterators behave as if they were the original iterators wrapped inreverse_iterator.

`fwdRng | std::map_values`

Precondition:The value-type of the range is an instantiation ofstd::pair.Postcondition: For all elementsxin the returned range,xis the result ofy.secondwhereyis the corresponding element in the original range.

`fwdRng | std::map_keys`

Precondition:The value-type of the range is an instantiation ofstd::pair.Postcondition: For all elementsxin the returned range,xis the result ofy.firstwhereyis the corresponding element in the original range.

`fwdRng | std::moved`

Returns: A range whose iterators behave as if they were the original iterators wrapped inmove_iterator.

`fwdRng | std::uniqued`

Precondition: The value-type of the range is comparable withoperator==().Postcondition: For all adjacent elements[x,y]in the returned range,x==yis false.

`fwdRng | std::sliced(n,m)`

Precondition:0<=n && n <= m && m < size(fwdRng).Returns:make_range(fwdRng,n,m).

`fwdRng | std::tokenized( regex )``fwdRng | std::tokenized( regex, i )``fwdRng | std::tokenized( regex, rndRng )``fwdRng | std::tokenized( regex, i, flags )``fwdRng | std::tokenized( regex, rndRng, flags )`

Precondition:

- Let
Tdenotetypename range_value< decltype(fwdRng) >::type, thenregexhas the typebasic_regex<T>or the typebasic_string<T>or is implicitly convertible to one of these types.ihas the typeint.- the value-type of
rndRngisint.flagshas the typeregex_constants::syntax_option_type.Returns: A range whose iterators behave as if they were the original iterators wrapped inregex_token_iterator. The first iterator in the range would be constructed by forwarding all the arguments oftokenized()to theregex_token_iteratorconstructor.Throws: Whatever constructing and copying equivalentregex_token_iterators might throw.

- Should we provide additional range adapters? Can anybody come up with more?

- Would
`adjacent_transformed()`be a candidate?

Thanks to Howard Hinnant, Dietmar Kuehl and Walter Brown for their constructive and brutally honest feedback. The range adapters presented in this proposal is based on ideas developed by Eric Niebler.