Range Library Proposal

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.

Table of Contents

1   Motivation

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

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

3.1   Range concepts

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

  1. the traversal type of its associated iterators
  1. 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

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   Additions to existing library components (Part 2)

4.1   Overloaded algorithms

4.1.1   <algorithm> and <numeric>

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.

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.
  1. 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.
  1. 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   Range utilities (Part 3)

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

5.1   Range

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

5.1.1   Synopsis

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.1.2   Specification

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

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.

5.2.1   Synopsis

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.2.2   Specification

Rng must model a ForwardRange.

All the functions are like the ones from range.

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   Range adapters (Part 4)

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.

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.
  1. The return-type of operator|() is otherwise unspecified.
  1. operator|() is found by ADL because a range adapter is implemented in namespace std.
  1. operator|() is used to add new behavior lazily and never modifies its left argument.
  1. All iterators extracted from the left argument are extracted using unqualified calls to begin() and end().
  1. 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.
  1. 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.
  1. 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.
  1. biRng | std::reversed
  • Returns: A range whose iterators behave as if they were the original iterators wrapped in reverse_iterator.
  1. 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.
  1. 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.
  1. fwdRng | std::moved
  • Returns: A range whose iterators behave as if they were the original iterators wrapped in move_iterator.
  1. 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.
  1. fwdRng | std::sliced(n,m)
  • Precondition: 0<=n && n <= m && m < size(fwdRng).
  • Returns: make_range(fwdRng,n,m).
  1. 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?

7   Acknowledgements

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.