1.1   What is a range?

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.

1.2   Advantages

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++

1. a drastic reduction in syntactic overhead,

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

3. a new concise idiomatic use of algorithms and loops,

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

3.1   Range concepts

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

1. the traversal type of its associated iterators

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

• Boost.Range concepts
• n1640 (new iterator concepts)

3.2   Synopsis (1)

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) );

3.3   Specification (1)

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)

3.4   Discussion

1. 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).

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

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

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

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

6. Should we add a range_category TransformationTrait?

4.1   Overloaded algorithms

4.2   New member functions

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().

4.3   Tr1 and other proposals

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

4.4   Discussion

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

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

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

5.1   Range

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 );

}

5.2   Sub_range

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>'
};

5.3   Discussion

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

6.1   Specification

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:

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

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

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

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

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

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

Valid expressions:

1. fwdRng | std::filtered( pred )

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

1. fwdRng | std::adjacent_filtered( biPred )

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

2. fwdRng | std::transformed( fun )

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

3. fwdRng | std::indirected

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

4. biRng | std::reversed

• Returns: A range whose iterators behave as if they were the original iterators wrapped in reverse_iterator.

5. fwdRng | std::map_values

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

6. fwdRng | std::map_keys

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

7. fwdRng | std::moved

• Returns: A range whose iterators behave as if they were the original iterators wrapped in move_iterator.

8. fwdRng | std::uniqued

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

9. fwdRng | std::sliced(n,m)

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

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

6.2   Discussion

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

• Would adjacent_transformed() be a candidate?