boost_range.qbk

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

    make_iterator_range( const Range& r, 
                         typename range_difference<Range>::type advance_begin,
                         typename range_difference<Range>::type advance_end );
    
    // convenience
    template< class Sequence, class ForwardRange >
    Sequence copy_range( const ForwardRange& r );
    
} // namespace 'boost'
``    

If an instance of `iterator_range` is constructed by a client with two iterators, the client must ensure that the two iterators delimit a valid closed-open range [begin,end).

It is worth noticing that the templated constructors and assignment operators allow conversion from `iterator_range<iterator>` to `iterator_range<const_iterator>`. Similarly, since the comparison operators have two template arguments, we can compare ranges whenever the iterators are comparable; for example when we are dealing with const and non-const iterators from the same container.

[h4 Details member functions]

`operator unspecified_bool_type() const;`

[:['[*Returns]] `!empty();`]

`bool equal( iterator_range& r ) const;`

[:['[*Returns]] `begin() == r.begin() && end() == r.end();`]

[h4 Details functions]

`bool operator==( const ForwardRange1& l, const ForwardRange2& r );`

[:['[*Returns]] `size(l) != size(r) ? false : std::equal( begin(l), end(l), begin(r) );`]

`bool operator!=( const ForwardRange1& l, const ForwardRange2& r );`

[:['[*Returns]] `!( l == r );`]

`bool operator<( const ForwardRange1& l, const ForwardRange2& r );`

[:['[*Returns]] `std::lexicographical_compare( begin(l), end(l), begin(r), end(r) );`]

``
iterator_range make_iterator_range( Range& r,
                                    typename range_difference<Range>::type advance_begin, 
                                    typename range_difference<Range>::type advance_end );
``

[:['[*Effects:]]]

``
    iterator new_begin = begin( r ),
    iterator new_end   = end( r );
    std::advance( new_begin, advance_begin );
    std::advance( new_end, advance_end );
    return make_iterator_range( new_begin, new_end );
``

`Sequence copy_range( const ForwardRange& r );`

[:['[*Returns]] `Sequence( begin(r), end(r) );`]

[endsect]

[section:sub_range Class `sub_range`]

The `sub_range` class inherits all its functionality from the __iterator_range__ class. The `sub_range` class is often easier to use because one must specify the __forward_range__ template argument instead of an iterator. Moreover, the sub_range class can propagate constness since it knows what a corresponding `const_iterator` is.

[h4 Synopsis]

``
namespace boost
{
    template< class ForwardRange >
    class sub_range : public iterator_range< typename range_result_iterator<ForwardRange>::type >
    {
    public: 
        typedef typename range_result_iterator<ForwardRange>::type iterator;
        typedef typename range_const_iterator<ForwardRange>::type  const_iterator;
    
    public: // construction, assignment
        template< class ForwardTraversalIterator >
        sub_range( ForwardTraversalIterator Begin, ForwardTraversalIterator End );

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

        template< class ForwardRange2 >
        sub_range& operator=( const ForwardRange2& 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;
    
    public:
        // rest of interface inherited from iterator_range
    };
    
} // namespace 'boost'
``

The class should be trivial to use as seen below. Imagine that we have an algorithm that searches for a sub-string in a string. The result is an iterator_range, that delimits the match. We need to store the result from this algorithm. Here is an example of how we can do it with and without `sub_range`

``
std::string str("hello");
iterator_range<std::string::iterator> ir = find_first( str, "ll" );
sub_range<std::string>               sub = find_first( str, "ll" );
``

[endsect]

[endsect]



[section:style_guide Terminology and style guidelines]

The use of a consistent terminology is as important for __ranges__ and range-based algorithms as it is for iterators and iterator-based algorithms. If a conventional set of names are adopted, we can avoid misunderstandings and write generic function prototypes that are ['self-documenting].

Since ranges are characterized by a specific underlying iterator type, we get a type of range for each type of iterator. Hence we can speak of the following types of ranges:

* ['Value access] category:
  * Readable Range
  * Writeable Range
  * Swappable Range
  * Lvalue Range 
* ['Traversal] category:
  * __single_pass_range__
  * __forward_range__
  * __bidirectional_range__
  * __random_access_range__

Notice how we have used the categories from the __new_style_iterators__.

Notice that an iterator (and therefore an range) has one ['traversal] property and one or more properties from the ['value access] category. So in reality we will mostly talk about mixtures such as

* Random Access Readable Writeable Range
* Forward Lvalue Range 

By convention, we should always specify the ['traversal] property first as done above. This seems reasonable since there will only be one ['traversal] property, but perhaps many ['value access] properties.

It might, however, be reasonable to specify only one category if the other category does not matter. For example, the __iterator_range__ can be constructed from a Forward Range. This means that we do not care about what ['value access] properties the Range has. Similarly, a Readable Range will be one that has the lowest possible ['traversal] property (Single Pass).

As another example, consider how we specify the interface of `std::sort()`. Algorithms are usually more cumbersome to specify the interface of since both traversal and value access properties must be exactly defined. The iterator-based version looks like this:

``
   template< class RandomAccessTraversalReadableWritableIterator >
   void sort( RandomAccessTraversalReadableWritableIterator first,
              RandomAccessTraversalReadableWritableIterator last );
`` 

For ranges the interface becomes

``
   template< class RandomAccessReadableWritableRange >
   void sort( RandomAccessReadableWritableRange& r );
``
 
[endsect]



[section Library Headers]

[table
    [[Header                              ] [Includes                   ] [Related Concept         ]]
    [[`<boost/range.hpp>`                 ] [everything                 ] [-                       ]]
    [[`<boost/range/metafunctions.hpp>`   ] [every metafunction         ] [-                       ]]
    [[`<boost/range/functions.hpp>`       ] [every function             ] [-                       ]]
    [[`<boost/range/value_type.hpp>`      ] [`range_value`              ] [__single_pass_range__   ]]
    [[`<boost/range/iterator.hpp>`        ] [`range_iterator`           ] [__single_pass_range__   ]]
    [[`<boost/range/const_iterator.hpp>`  ] [`range_const_iterator`     ] [__single_pass_range__   ]]
    [[`<boost/range/difference_type.hpp>` ] [`range_difference`         ] [__forward_range__       ]]
    [[`<boost/range/size_type.hpp>`       ] [`range_size`               ] [__forward_range__       ]]
    [[`<boost/range/result_iterator.hpp>` ] [`range_result_iterator`    ] [-                       ]]
    [[`<boost/range/reverse_iterator.hpp>`] [`range_reverse_iterator`   ] [__bidirectional_range__ ]]
    [[`<boost/range/const_reverse_iterator.hpp>`]
                                            [`range_const_reverse_iterator`]
                                                                          [_bidirectional_range__  ]]
    [[`<boost/range/reverse_result_iterator.hpp>`]
                                            [`range_reverse_result_iterator`]
                                                                          [-                       ]]
    [[`<boost/range/begin.hpp>`           ] [`begin` and `const_begin`  ] [__single_pass_range__   ]]
    [[`<boost/range/end.hpp>`             ] [`end` and `const_end`      ] [__single_pass_range__   ]]
    [[`<boost/range/empty.hpp>`           ] [`empty`                    ] [__single_pass_range__   ]]
    [[`<boost/range/size.hpp>`            ] [`size`                     ] [__forward_range__       ]]
    [[`<boost/range/rbegin.hpp>`          ] [`rbegin` and `const_rbegin`] [__bidirectional_range__ ]]
    [[`<boost/range/rend.hpp>`            ] [`rend` and `const_rend`    ] [__bidirectional_range__ ]]
    [[`<boost/range/iterator_range.hpp>`  ] [`iterator_range`           ] [-                       ]]
    [[`<boost/range/sub_range.hpp>`       ] [`sub_range`                ] [-                       ]]
    [[`<boost/range/concepts.hpp>`        ] [`concept checks`           ] [-                       ]]
]

[endsect]



[section Examples]

Some examples are given in the accompanying test files:

* [@http://www.boost.org/libs/range/test/string.cpp string.cpp][br]
shows how to implement a container version of `std::find()` that works with `char[]`,`wchar_t[]`,`char*`,`wchar_t*`.

[:[*Warning: ['support for null-terminated strings is deprecated and will disappear in the next Boost release (1.34).]]]

* [@http://www.boost.org/libs/range/test/algorithm_example.cpp algorithm_example.cpp][br]shows the replace example from the introduction.

* [@http://www.boost.org/libs/range/test/iterator_range.cpp iterator_range.cpp]

* [@http://www.boost.org/libs/range/test/sub_range.cpp sub_range.cpp]

* [@http://www.boost.org/libs/range/test/iterator_pair.cpp iterator_pair.cpp]

* [@http://www.boost.org/libs/range/test/reversible_range.cpp reversible_range.cpp]

* [@http://www.boost.org/libs/range/test/std_container.cpp std_container.cpp]

* [@http://www.boost.org/libs/range/test/array.cpp array.cpp]

[endsect]



[section Portability]

A huge effort has been made to port the library to as many compilers as possible.

Full support for built-in arrays require that the compiler supports class template partial specialization. For non-conforming compilers there might be a chance that it works anyway thanks to workarounds in the type traits library.
Visual C++ 6/7.0 has a limited support for arrays: as long as the arrays are of built-in type it should work.

Notice also that some compilers cannot do function template ordering properly. In that case one must rely of __range_result_iterator__ and a single function definition instead of overloaded versions for const and non-const arguments. So if one cares about old compilers, one should not pass rvalues to the functions.

For maximum portability you should follow these guidelines:

# do not use built-in arrays,
# do not pass rvalues to `begin()`, `end()` and `iterator_range` Range constructors and assignment operators,
# use `const_begin()` and `const_end()` whenever your code by intention is read-only; this will also solve most rvalue problems,
# do not rely on ADL:
  * if you overload functions, include that header before the headers in this library,
  * put all overloads in namespace boost. 



[endsect]



[section FAQ]

1. ['[*Why is there no difference between `range_iterator<C>::type`  and `range_const_iterator<C>::type` for `std::pair<iterator, iterator>`?]]

[:In general it is not possible nor desirable to find a corresponding `const_iterator`. When it is possible to come up with one, the client might choose to construct a `std::pair<const_iterator,const_iterator>` object.]

[:Note that an __iterator_range__ is somewhat more convenient than a `pair` and that a __sub_range__ does propagate const-ness.]

2. ['[*Why is there not supplied more types or more functions?]]

[:The library has been kept small because its current interface will serve most purposes. If and when a genuine need arises for more functionality, it can be implemented.]

3. ['[*How should I implement generic algorithms for ranges?]]

[:One should always start with a generic algorithm that takes two iterators (or more) as input. Then use Boost.Range to build handier versions on top of the iterator based algorithm. Please notice that once the range version of the algorithm is done, it makes sense not to expose the iterator version in the public interface.]

4. ['[*Why is there no Incrementable Range concept?]]

[:Even though we speak of incrementable iterators, it would not make much sense for ranges; for example, we cannot determine the size and emptiness of a range since we cannot even compare its iterators.]

[:Note also that incrementable iterators are derived from output iterators and so there exist no output range.]

[endsect]

[section:history_ack History and Acknowledgement]

The library have been under way for a long time. Dietmar Kühl originally intended to submit an `array_traits` class template which had most of the functionality present now, but only for arrays and standard containers.

Meanwhile work on algorithms for containers in various contexts showed the need for handling pairs of iterators, and string libraries needed special treatment of character arrays. In the end it made sense to formalize the minimal requirements of these similar concepts. And the results are the Range concepts found in this library.

The term Range was adopted because of 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. 

Special thanks goes to

* Pavol Droba for help with documentation and implementation
* Pavel Vozenilek for help with porting the library
* Jonathan Turkanis and John Torjo for help with documentation
* Hartmut Kaiser for being review manager
* Jonathan Turkanis for porting the lib (as far sa possible) to vc6 and vc7. 

The concept checks and their documentation was provided by Daniel Walker. 

[endsect]