Range Library Core

Author: Thorsten Ottosen
Contact: tottosen@dezide.com
organizations:Dezide Aps
Date: 2006-09-08
Number:WG21/N2068 J16/06-0138 (revision of WG21/N1871 and J16/05-0131)
Working Group:Evolution

Abstract

This paper proposes the addition of ranges to the C++ standard library to reduce the syntactic burden on programmers. The focus is on the minimal core features that enables enhanced algorithm interfaces.

Table of Contents

Introduction

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.

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,
  1. an infrastructure for range-based algorithms (which can also be used for the new for-loop (see n1868 and n1961)),
  1. a new concise idiomatic use of algorithms and loops,
  1. safer use of built-in arrays.

For more discussion, please refer to n1871.

The new string algorithms in n2059 builds on the core range primitives from this paper and this library component can thus be seen as a prerequisite for the string algorithms.

Each numbered section below describes a new section for the standard or modifications to an existing section. Comments are written in bold and are not part of the wording

Wording

24.2 Header <iterator> synopsis

Add the following to the end of the synopsis:

template< class Range >
auto range_begin( Range&& r ) -> decltype( r.begin() );

template< class Iterator >
Iterator range_begin( const pair<Iterator,Iterator>& p ) ;

template< class T, size_t N >
T* range_begin( T (&array)[N] ) 

template< class Range >
auto begin( Range&& r ) -> decltype( range_begin(r) );

template< class Range >
auto range_end( Range&& r ) -> decltype( r.end() );

template< class Iterator >
Iterator range_end( const pair<Iterator,Iterator>& p );

template< class T, size_t N >
T* range_end( T (&array)[N] );

template< class Range >
auto end( Range&& r ) -> decltype( range_end(r) );

template< class Range >
struct range_iterator; 

template< class BidirectionalRange >
struct range_reverse_iterator;

template< class Range >
struct range_value;

template< class Range >
struct range_reference;

template< class Range >
struct range_pointer;
 
template< class Range >
struct range_difference;

template< class Range >
struct range_category;

template< class Range >
bool empty( const Range& r );

template< class RandomAccessRange >
typename range_difference<RandomAccessRange>::type 
size( const RandomAccessRange& r );

template< class BidirectionalRange >
typename range_reverse_iterator<BidirectionalRange>::type 
rbegin( BidirectionalRange&& r );

template< class BidirectionalRange >
typename range_reverse_iterator<BidirectionalRange>::type
rend( BidirectionalRange&& r );

template< class Range >
typename range_iterator<const Range>::type 
const_begin( const Range& r );

template< class Range >
typename range_iterator<const Range>::type 
const_end( const Range& r );

template< class BidirectionalRange >
typename range_reverse_iterator<const BidirectionalRange>::type 
const_rbegin( const BidirectionalRange& r );

template< class BidirectionalRange >
typename range_reverse_iterator<const BidirectionalRange>::type 
const_rend( const BidirectionalRange& r );

template< class Iterator >
class range;

template< class Range >
class sub_range : public range< typename range_iterator<Range>::type >;

// stream output
template< class Iterator, class T, class Traits >
std::basic_ostream<T,Traits>& 
operator<<( std::basic_ostream<T,Traits>& Os,
            const range<Iterator>& r );

// comparison
template< class Iterator, class Iterator2 >
bool operator==( const range<Iterator>& l, const range<Iterator2>& r );

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

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

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

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

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

template< class Iterator, class Iterator2 >
bool operator<( const range<Iterator>& l, const range<Iterator2>& r );

template< class Iterator, class Range >
bool operator<( const range<Iterator>& l, const Range& r );

template< class Iterator, class Range >
bool operator<( const Range& l, const range<Iterator>& r );

template< class Range, class Range2 >
bool operator==( const sub_range<Range>& l, const sub_range<Range2>& r );

template< class Range, class Range2 >
bool operator!=( const sub_range<Range>& l, const sub_range<Range2>& r )

template< class Range, class Range2 >
bool operator<( const sub_range<Range>& l, const sub_range<Range2>& r );

// external construction
template< class Iterator >
range<Iterator>
make_range( const Iterator& begin, const Iterator& end );
   
template< class Range >
range<typename range_iterator<Range>::type> 
make_range( Range&& r );

template< class Range >
range<typename range_iterator<Range>::type> 
make_range( Range&& r, typename range_difference<Range>::type advance_begin,
                       typename range_difference<Range>::type advance_end );
           
template< class CopyableRange, class Range >      
CopyableRange copy_range( const Range& r );

template< class ForwardRange >
typename range_difference<ForwardRange>::type
distance( const ForwardRange& r );

24.6 Range primitives

Add the following new section:

To support ranges and range-based algorithms, the library provides free-standing functions that enable the range abstraction as well as several utilities.

A type T conforms to a range concept if the free-standing functions range_begin(T&) and range_begin(T&) have been defined in the namespace of T or if T has member functions named begin() and end(). Furthermore, built-in arrays conforms to the range concept. All these functions must return iterators in amortized constant time, and the type of these iterators may vary with the constness of the range object. If the iterators of a range are mutable, we say the range is mutable, and if the iterators of a range are constant, we say the range is constant.

Each possible category of the associated iterator type of a range leads to a range category; we therefore have the concept of input ranges, forward ranges, bidirectional ranges and random access ranges. There is no notion of an output range. A range is singular if any of its associated iterators are singular.

If a range T owns its associated values (like containers do) and has a deep-copy constructor that takes two iterator parameters, T is called a copyable range.

24.6.1 Range operations

The functions range_begin() and range_end() are intended to be overloaded for a user-defined type T in the namespace of T.

The functions begin() and end() are intended to be called qualified with the std namespace, and they are always called qualified within the standard library. From these two functions the call to range_begin() and range_end(), respectively, is without namespace qualification to enable argument dependent lookup.

template< class Range > auto range_begin( Range&& r ) -> decltype( r.begin() );

  • Returns: r.begin()

template< class Iterator > Iterator range_begin( const pair<Iterator,Iterator>& p );

  • Returns: p.first

template< class T, size_t N > T* range_begin( T (&array)[N] )

  • Returns: array

template< class Range > auto begin( Range&& r ) -> decltype( range_begin(r) );

  • Returns: range_begin(r)

template< class Range > auto range_end( Range&& r ) -> decltype( r.end() );

  • Returns: r.end()

template< class Iterator > Iterator range_end( const pair<Iterator,Iterator>& p );

  • Returns: p.second

template< class T, size_t N > T* range_end( T (&array)[N] );

  • Returns: array + N

template< class Range > auto end( Range&& r ) -> decltype( range_end(r) );

  • Returns: range_end(r)

template< class RandomAccessRange > typename range_difference<RandomAccessRange>::type size( const RandomAccessRange& r );

  • Returns: std::end(r) - std::begin(r)

template< class BidirectionalRange > typename range_reverse_iterator<BidirectionalRange>::type rbegin( BidirectionalRange&& r );

  • Returns: typename range_reverse_iterator<BidirectionalRange>::type(std::end(r))

template< class BidirectionalRange > typename range_reverse_iterator<BidirectionalRange>::type rend( BidirectionalRange&& r );

  • Returns: typename range_reverse_iterator<BidirectionalRange>::type(std::begin(r))

template< class Range > typename range_iterator<const Range>::type const_begin( const Range& r );

  • Returns: std::begin(r)

template< class Range > typename range_iterator<const Range>::type const_end( const Range& r );

  • Returns: std::end(r)

template< class BidirectionalRange > typename range_reverse_iterator<const BidirectionalRange>::type const_rbegin( const BidirectionalRange& r );

  • Returns: std::rbegin(r)

template< class BidirectionalRange > typename range_reverse_iterator<const BidirectionalRange>::type const_rend( const BidirectionalRange& r );

  • Returns: std::rend(r)

24.6.2 Range traits

For convenience the type and properties of an associated iterator type of a range can be queried by range traits. Each trait is a TransformationTrait and so define a nested type called type.

template< class Range > struct range_iterator;

  • Definition of type: Let ptr be a variable of type Range*, then the nested type is typedef decltype( begin(*ptr) ) type;

template< class BidirectionalRange > struct range_reverse_iterator;

  • Definition of type: typedef reverse_iterator< typename range_iterator<BidirectionalRange>:type > type;

template< class Range > struct range_value;

  • Definition of type: typedef typename iterator_traits< typename range_iterator<Range>::type >::value_type type;

template< class Range > struct range_reference;

  • Definition of type: typedef typename iterator_traits< typename range_iterator<Range>::type >::reference type;

template< class Range > struct range_pointer;

  • Definition of type: typedef typename iterator_traits< typename range_iterator<Range>::type >::pointer type;

template< class Range > struct range_difference;

  • Definition of type: typedef typename iterator_traits< typename range_iterator<Range>::type >::difference_type type;

template< class Range > struct range_category;

  • Definition of type: typedef typename iterator_traits< typename range_iterator<Range>::type >::iterator_category type;

24.6.3 Range utilities

For convenience the library provides two iterator-view helper classes. These two classes make comparison between view-objects and container-objects easy and provide a safer and more convenient encapsulation of iterator-views.

namespace std
{
        template< class Iterator >
        class range
        {
        public: // types
                typedef typename iterator_traits<Iterator>::value_type       value_type;
                typedef typename iterator_traits<Iterator>::reference        reference;
                typedef typename iterator_traits<Iterator>::difference_type  difference_type;
                typedef Iterator                                             iterator;
                typedef Iterator                                             const_iterator;
        
        public: // construction, assignment
                range();
                
                template< class Iterator2 >
                range( const Iterator2& begin, const Iterator2& end );
                        
                template< class Range >
                range( Range&& r );
        
                template< class Range >
                range& operator=( Range&& r );
        
        public: // forward range functions
                iterator        begin() const;
                iterator        end() const;
                difference_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[]( difference_type at ) const;
                range&      advance_begin( difference_type n );
                range&      advance_end( difference_type n );
        
        private:
                Iterator first; // exposition only
                Iterator last;  // exposition only    
        }; 

        template< class Range >
        class sub_range : public range< typename range_iterator<Range>::type >
        {
        public: 
                typedef range< typename range_iterator<Range>::type >        base_type
                typedef typename range_iterator<Range>::type                 iterator;
                typedef typename range_iterator<const Range>::type           const_iterator;
                typedef typename iterator_traits<const_iterator>::reference  const_reference;
                using base_type::value_type;
                using base_type::reference;
                using base_type::difference_type;
                
        public: // construction, assignment
                sub_range();
                
                template< class Iterator >
                sub_range( const Iterator& begin, const Iterator& end );
                
                template< class Range2 >
                sub_range( Range2&& r );
                 
                template< class Range2 >
                sub_range& operator=( Range2&& r );
                
        public:  // forward range functions 
                iterator        begin();
                const_iterator  begin() const;
                iterator        end();
                const_iterator  end() const;    
                
        public: // convenience 
                reference        front();
                const_reference  front() const;
                reference        back();
                const_reference  back() const;
                reference        operator[]( difference_type at );
                const_reference  operator[]( difference_type at ) const;   
                sub_range&       advance_begin( difference_type n );
                sub_range&       advance_end( difference_type n );
        };
}

[Example: An efficient way to find and manipulate a substring may be done with sub_range:

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

-- end example]

range();

  • Effects: Initializes its members as if implemented by: range() : first(), last() {}
  • Remarks: The stored iterators are singular.

template< class Iterator2 > range( const Iterator2& begin, const Iterator2& end );

  • Effects: Initializes first with begin and last with end.

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

  • Effects: Initializes first with std::begin(r) and last with std::end(r).

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

  • Effects: assigns std::begin(r) to first and std::end(r) to last.
  • Returns: *this

iterator begin() const;

  • Returns: first.

iterator end() const;

  • Returns: last.

difference_type size() const;

  • Returns: end() - begin();

bool empty() const;

  • Returns: begin() == end();
operator unspecified_bool_type() const;
  • Returns: a value convertible to bool indicating whether empty() is true.

bool equal( const range& ) const;

  • Returns: begin() == r.begin() && end() == r.end().

reference front() const;

  • Returns: *begin().

reference back() const;

  • Returns: *--end().

reference operator[]( difference_type at ) const;

  • Precondition: 0 <= at < size().
  • Returns: *(begin() + at).

range& advance_begin( difference_type n );

  • Effects: std::advance(first,n).
  • Returns: *this

range& advance_end( difference_type n );

  • Effects: std::advance(last,n).
  • Returns: *this

sub_range();

template< class Iterator > sub_range( const Iterator& begin, const Iterator& end );

template< class Range2 > sub_range( Range2&& r );

  • Effects: Calls corresponding base class constructor.

template< class Range2 > sub_range& operator=( Range2&& r );

  • Effects: base_type::operator=(r);
  • Returns: *this

iterator begin();

  • Returns: base_type::begin();

const_iterator begin() const;

  • Returns: base_type::begin();

iterator end();

  • Returns: base_type::end();

const_iterator end() const;

  • Returns: base_type::end();

reference front();

  • Returns: base_type::front();

const_reference front() const;

  • Returns: base_type::front();

reference back();

  • Returns: base_type::back();

const_reference back() const;

  • Returns: base_type::back();

reference operator[]( difference_type at );

  • Returns: base_type::operator[](at);

const_reference operator[]( difference_type at ) const;

  • Returns: base_type::operator[](at);

sub_range& advance_begin( difference_type n );

  • Effects: base_type::advance_begin(n);
  • Returns: *this

sub_range& advance_end( difference_type n );

  • Effects: base_type::advance_end(n);
  • Returns: *this

template< class Iterator, class T, class Traits > std::basic_ostream<T,Traits>& operator<<( std::basic_ostream<T,Traits>& Os, const range<Iterator>& r );

  • Effects: std::copy( r.begin(), r.end(), std::ostream_iterator< typename iterator_traits<Iterator>::value_type,T,Traits>(os)); return Os;.

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

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

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

  • Returns: std::equal( std::begin(l), std::end(l), std::begin(r) );.
  • Remarks: For random access ranges the function compares the size of the ranges first via std::size().

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

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

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

  • Returns: !( l == r ).

template< class Iterator, class Iterator2 > bool operator<( const range<Iterator>& l, const range<Iterator2>& r );

template< class Iterator, class Range > bool operator<( const range<Iterator>& l, const Range& r );

template< class Iterator, class Range > bool operator<( const Range& l, const range<Iterator>& r );

  • Returns: std::lexicographical_compare(std::begin(l),std::end(l),std::begin(r), std::end(r)).

template< class Range, class Range2 > bool operator==( const sub_range<Range>& l, const sub_range<Range2>& r );

template< class Range, class Range2 > bool operator!=( const sub_range<Range>& l, const sub_range<Range2>& r )

template< class Range, class Range2 > bool operator<( const sub_range<Range>& l, const sub_range<Range2>& r );

  • Effects: forwards to range version via static casts to a reference to the base class
  • Remarks: these functions are needed to avoid ambiguity during overload resolution.

template< class Iterator > range<Iterator> make_range( const Iterator& begin, const Iterator& end );

  • Returns: range<Iterator>(begin,end).

template< class Range > range<typename range_iterator<Range>::type> make_range( Range&& r );

  • Returns: range<typename range_iterator<Range>::type>(r).

template< class Range > range<typename range_iterator<Range>::type> make_range( Range&& r, typename range_difference<Range>::type N, typename range_difference<Range>::type M );

  • Effects: range<typename range_iterator<Range>::type> tmp(r); tmp.advance_begin(N); tmp.advance_end(M); return tmp;

template< class CopyableRange, class Range > CopyableRange copy_range( const Range& r );

  • Returns: CopyableRange(std::begin(r),std::end(r)).

template< class ForwardRange > typename range_difference<ForwardRange>::type distance( const ForwardRange& r );

  • Returns: std::distance(std::begin(r),std::end(r))

Acknowledgements

Thanks to Pavol Droba for our many discussions. Thanks to Howard Hinnant, Dietmar Kuehl and Walter Brown for feedback on the earlier version of this paper. Thanks to the Boost community for their feedback on Boost.Range over the years.