boost_range.qbk

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

[section:method_1 Method 1: provide member functions and nested types]

This procedure assumes that you have control over the types that should be made conformant to a Range concept. If not, see [link boost.range.reference.extending.method_2 method 2].

The primary templates in this library are implemented such that standard containers will work automatically and so will __boost_array__. Below is given an overview of which member functions and member types a class must specify to be useable as a certain Range concept.

[table
  [[Member function] [Related concept      ]]
  [[`begin()`      ] [__single_pass_range__]]
  [[`end()`        ] [__single_pass_range__]]
  [[`size()`       ] [__forward_range__    ]]
]

Notice that `rbegin()` and `rend()` member functions are not needed even though the container can support bidirectional iteration.

The required member types are:

[table
  [[Member type     ] [Related concept      ]]
  [[`iterator`      ] [__single_pass_range__]]
  [[`const_iterator`] [__single_pass_range__]]
  [[`size_type`     ] [__forward_range__    ]]
]

Again one should notice that member types `reverse_iterator` and `const_reverse_iterator` are not needed.

[endsect]

[section:method_2 Method 2: provide free-standing functions and specialize metafunctions]

This procedure assumes that you cannot (or do not wish to) change the types that should be made conformant to a Range concept. If this is not true, see [link boost.range.reference.extending.method_1 method 1].

The primary templates in this library are implemented such that certain functions are found via argument-dependent-lookup (ADL). Below is given an overview of which free-standing functions a class must specify to be useable as a certain Range concept. Let `x` be a variable (`const` or `mutable`) of the class in question.

[table
  [[Function              ] [Related concept      ]]
  [[`boost_range_begin(x)`] [__single_pass_range__]]
  [[`boost_range_end(x)`  ] [__single_pass_range__]]
  [[`boost_range_size(x)` ] [__forward_range__    ]]
]

`boost_range_begin()` and `boost_range_end()` must be overloaded for both `const` and `mutable` reference arguments.

You must also specialize 3 metafunctions for your type `X`:

[table
  [[Metafunction                 ] [Related concept      ]]
  [[`boost::range_iterator`      ] [__single_pass_range__]]
  [[`boost::range_const_iterator`] [__single_pass_range__]]
  [[`boost::range_size`          ] [__forward_range__    ]]
]

A complete example is given here:

``
    #include <boost/range.hpp>
    #include <iterator>         // for std::iterator_traits, std::distance()

    namespace Foo
    {
        //
        // Our sample UDT. A 'Pair'
        // will work as a range when the stored
        // elements are iterators.
        //
        template< class T >
        struct Pair
        {
            T first, last;	
        };

    } // namespace 'Foo'

    namespace boost
    {
        //
        // Specialize metafunctions. We must include the range.hpp header.
        // We must open the 'boost' namespace.
        //

    	template< class T >
    	struct range_iterator< Foo::Pair<T> >
    	{
    		typedef T type;
    	};

    	template< class T >
    	struct range_const_iterator< Foo::Pair<T> >
    	{
    		//
    		// Remark: this is defined similar to 'range_iterator'
    		//         because the 'Pair' type does not distinguish
    		//         between an iterator and a const_iterator.
    		//
    		typedef T type;
    	};

    	template< class T >
    	struct range_size< Foo::Pair<T> >
    	{

    		typedef std::size_t type;
    	};

    } // namespace 'boost'

    namespace Foo
    {
    	//
    	// The required functions. These should be defined in
    	// the same namespace as 'Pair', in this case 
    	// in namespace 'Foo'.
    	//
    	
    	template< class T >
    	inline T boost_range_begin( Pair<T>& x )
    	{ 
    		return x.first;
    	}

    	template< class T >
    	inline T boost_range_begin( const Pair<T>& x )
    	{ 
    		return x.first;
    	}

    	template< class T >
    	inline T boost_range_end( Pair<T>& x )
    	{ 
    		return x.last;
    	}

    	template< class T >
    	inline T boost_range_end( const Pair<T>& x )
    	{ 
    		return x.last;
    	}

    	template< class T >
    	inline typename boost::range_size< Pair<T> >::type
    	boost_range_size( const Pair<T>& x )
    	{
    		return std::distance(x.first,x.last);
    	}

    } // namespace 'Foo'

    #include <vector>

    int main()
    {
    	typedef std::vector<int>::iterator  iter;
    	std::vector<int>                    vec;
    	Foo::Pair<iter>                     pair = { vec.begin(), vec.end() };
    	const Foo::Pair<iter>&              cpair = pair; 
    	//
    	// Notice that we call 'begin' etc with qualification. 
    	//
    	iter i = boost::begin( pair );
    	iter e = boost::end( pair );
    	i      = boost::begin( cpair );
    	e      = boost::end( cpair );
    	boost::range_size< Foo::Pair<iter> >::type s = boost::size( pair );
    	s      = boost::size( cpair );
    	boost::range_const_reverse_iterator< Foo::Pair<iter> >::type
    	ri     = boost::rbegin( cpair ),
    	re     = boost::rend( cpair );
    }	
``

[endsect]

[endsect]

[endsect]



[section Utilities]

Having an abstraction that encapsulates a pair of iterators is very useful. The standard library uses `std::pair` in some circumstances, but that class is cumbersome to use because we need to specify two template arguments, and for all range algorithm purposes we must enforce the two template arguments to be the same. Moreover, `std::pair<iterator,iterator>` is hardly self-documenting whereas more domain specific class names are. Therefore these two classes are provided:

* Class `iterator_range`
* Class `sub_range`

The `iterator_range` class is templated on an __forward_traversal_iterator__ and should be used whenever fairly general code is needed. The `sub_range` class is templated on an __forward_range__ and it is less general, but a bit easier to use since its template argument is easier to specify. The biggest difference is, however, that a `sub_range` can propagate constness because it knows what a corresponding `const_iterator` is.

Both classes can be used as ranges since they implement the __minimal_interface__ required for this to work automatically.

[section:iterator_range Class `iterator_range`]

The intention of the `iterator_range` class is to encapsulate two iterators so they fulfill the __forward_range__ concept. A few other functions are also provided for convenience.

If the template argument is not a model of __forward_traversal_iterator__, one can still use a subset of the interface. In particular, `size()` requires Forward Traversal Iterators whereas `empty()` only requires Single Pass Iterators.

Recall that many default constructed iterators are singular and hence can only be assigned, but not compared or incremented or anything. However, if one creates a default constructed `iterator_range`, then one can still call all its member functions. This means that the `iterator_range` will still be usable in many contexts even though the iterators underneath are not.

[h4 Synopsis]

``
namespace boost
{
    template< class ForwardTraversalIterator >
    class iterator_range
    {
    public: // Forward Range types
        typedef ...                        value_type;
        typedef ...                        difference_type;
        typedef ...                        size_type;
        typedef ForwardTraversalIterator   iterator;
        typedef ForwardTraversalIterator   const_iterator;

    public: // construction, assignment
        template< class ForwardTraversalIterator2 >
        iterator_range( ForwardTraversalIterator2 Begin, ForwardTraversalIterator2 End );
                    
        template< class ForwardRange >
        iterator_range( ForwardRange& r );
  
        template< class ForwardRange >
        iterator_range( const ForwardRange& r );
        
        template< class ForwardRange >
        iterator_range& operator=( ForwardRange& r );

        template< class ForwardRange >
        iterator_range& operator=( const ForwardRange& 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 iterator_range& ) const;
        value_type& front() const;
        value_type& back() const;
        // for Random Access Range only: 
        value_type& operator[]( size_type at ) const;
    };
    
    // stream output
    template< class ForwardTraversalIterator, class T, class Traits >
    std::basic_ostream<T,Traits>& 
    operator<<( std::basic_ostream<T,Traits>& Os,
                const iterator_range<ForwardTraversalIterator>& r );

    // comparison
    template< class ForwardTraversalIterator, class ForwardTraversalIterator2 >
    bool operator==( const iterator_range<ForwardTraversalIterator>& l, 
                     const iterator_range<ForwardTraversalIterator2>& r );

    template< class ForwardTraversalIterator, class ForwardRange >
    bool operator==( const iterator_range<ForwardTraversalIterator>& l, 
                     const ForwardRange& r );

    template< class ForwardTraversalIterator, class ForwardRange >
    bool operator==( const ForwardRange& l,
                     const iterator_range<ForwardTraversalIterator>& r );

    template< class ForwardTraversalIterator, class ForwardTraversalIterator2 >
    bool operator!=( const iterator_range<ForwardTraversalIterator>& l, 
                     const iterator_range<ForwardTraversalIterator2>& r );

    template< class ForwardTraversalIterator, class ForwardRange >
    bool operator!=( const iterator_range<ForwardTraversalIterator>& l, 
                     const ForwardRange& r );

    template< class ForwardTraversalIterator, class ForwardRange >
    bool operator!=( const ForwardRange& l,
                     const iterator_range<ForwardTraversalIterator>& r );

    template< class ForwardTraversalIterator, class ForwardTraversalIterator2 >
    bool operator<( const iterator_range<ForwardTraversalIterator>& l, 
                    const iterator_range<ForwardTraversalIterator2>& r );

    template< class ForwardTraversalIterator, class ForwardRange >
    bool operator<( const iterator_range<ForwardTraversalIterator>& l, 
                    const ForwardRange& r );

    template< class ForwardTraversalIterator, class ForwardRange >
    bool operator<( const ForwardRange& l,
                    const iterator_range<ForwardTraversalIterator>& r );
 
    // external construction
    template< class ForwardTraversalIterator >
    iterator_range< ForwardTraversalIterator >
    make_iterator_range( ForwardTraversalIterator Begin, 
                         ForwardTraversalIterator End );
       
    template< class ForwardRange >
    iterator_range< typename iterator_of<ForwardRange>::type >
    make_iterator_range( ForwardRange& r );

    template< class ForwardRange >
    iterator_range< typename const_iterator_of<ForwardRange>::type >
    make_iterator_range( const ForwardRange& r );
    
    template< class Range >
    iterator_range< typename range_iterator<Range>::type >
    make_iterator_range( Range& r,
                         typename range_difference<Range>::type advance_begin,
                         typename range_difference<Range>::type advance_end );
    
    template< class Range >
    iterator_range< typename range_const_iterator<Range>::type >