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 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.
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_iterators and (2) indirect_iterators. 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:
A range is assume to be noncopyable unless otherwise specified.
We thus talk about the following types of ranges
All expressions rng whose type models a range can be used as arguments to the three freestanding functions
In addition, for an expression whose type models a ForwardRange we can say
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() );
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) );
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:
One might consider supporting additional types like tuples.
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::rng of the form:
template< class Range, ... > return-type algo( Range&& r, ... )which forwards to the algorithm in namespace std using unqualified calls to begin() and end(). (Remark: the return type specified with return-type the 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::rng of the form:
template< class Range, class Range2, ... > return-type algo( Range&& r, Range2&& r2, ... )which forwards to the algorithm in namespace std using unqualified calls to begin() and end().
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() and end().
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() and end().
It is suggested that all algorithms and containers described in tr1 and other proposals adopt the two version approach described above.
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 operator unspecified_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 class range.
- Remarks: The stored iterators are singular.
template< class Iter2 > range( Iter2 begin, Iter2 end );
- Precondition: Iter2 is convertible to Iter.
- Effects: Constructs an object of class range.
template< class Rng > range( Rng&& r );
- Precondition: The iterator type of Rng is convertible to Iter.
- Effects: Constructs an object of class range using unqualified calls to begin(r) and end(r).
template< class Rng > range& operator=( Rng&& r );
- Precondition: The iterator type of Rng is convertible to Iter.
- 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() and end() are not singular.
- Returns: begin() == end().
Convenience:
operator unspecified_bool_type() const;
- Returns: a value convertible to bool indicating whether empty() is true.
bool equal( const range& r ) const;
- Precondition: begin() and end() 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: Iter models 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: l and r are 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: l and r are 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: l and r are 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 Rng is convertible to the value-type of CopyableRng.
- CopyableRng models 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>' };
The last part of this proposal covers range adapters. These little helper classes has the following benefits:
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:
Valid expressions:
- Precondition: The value-type of the range is convertible to the argument type of pred.
- Postcondition: For all elements x in the returned range, pred(x) is true.
- Throws: Whatever the copy-constructor of pred might throw.
- Precondition: The value-type of the range is convertible to the argument types of biPred.
- Postcondition: For all adjacent elements [x,y] in the returned range, biPred(x,y) is true.
- Throws: Whatever the copy-constructor of biPred might throw.
- Precondition: The value-type of the range is convertible to the argument type of fun.
- Postcondition: For all elements x in the returned range, x is the result of fun(y) where y is the corresponding element in the original range.
- Throws: Whatever the copy-constructor of fun might throw.
- Precondition: The value-type of the range defines unary operator*()
- Postcondition: For all elements x in the returned range, x is the result of *y where y is the corresponding element in the original range.
- Returns: A range whose iterators behave as if they were the original iterators wrapped in reverse_iterator.
- Precondition: The value-type of the range is an instantiation of std::pair.
- Postcondition: For all elements x in the returned range, x is the result of y.second where y is the corresponding element in the original range.
- Precondition: The value-type of the range is an instantiation of std::pair.
- Postcondition: For all elements x in the returned range, x is the result of y.first where y is the corresponding element in the original range.
- Returns: A range whose iterators behave as if they were the original iterators wrapped in move_iterator.
- Precondition: The value-type of the range is comparable with operator==().
- Postcondition: For all adjacent elements [x,y] in the returned range, x==y is false.
- 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 T denote typename range_value< decltype(fwdRng) >::type, then regex has the type basic_regex<T> or the type basic_string<T> or is implicitly convertible to one of these types.
- i has the type int.
- the value-type of rndRng is int.
- flags has the type regex_constants::syntax_option_type.
- Returns: A range whose iterators behave as if they were the original iterators wrapped in regex_token_iterator. The first iterator in the range would be constructed by forwarding all the arguments of tokenized() to the regex_token_iterator constructor.
- Throws: Whatever constructing and copying equivalent regex_token_iterators might throw.
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.