boost_range.qbk

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

[article Boost.Range Documentation
    [quickbook 1.3]
    [id boost.range]
    [copyright 2003-2007 Thorsten Ottosen]
    [license
        Distributed under the Boost Software License, Version 1.0.
        (See accompanying file LICENSE_1_0.txt or copy at
        [@http://www.boost.org/LICENSE_1_0.txt])
    ]
]

[/ Converted to Quickbook format by Darren Garvey, 2007]

[def __ranges__                 [link boost.range.concepts Ranges]]
[def __range_concepts__         [link boost.range.concepts Range concepts]]
[def __forward_range__          [link boost.range.concepts.forward_range Forward Range]]
[def __single_pass_range__      [link boost.range.concepts.single_pass_range Single Pass Range]]
[def __bidirectional_range__    [link boost.range.concepts.bidirectional_range Bidirectional Range]]
[def __random_access_range__    [link boost.range.concepts.random_access_range Random Access Range]]

[def __iterator_range__         [link boost.range.utilities.iterator_range `iterator_range`]]
[def __sub_range__              [link boost.range.utilities.sub_range `sub_range`]]
[def __minimal_interface__      [link boost.range.reference.extending minimal interface]]
[def __range_result_iterator__  [link boost.range.reference.semantics.metafunctions `range_result_iterator`]]
[def __implementation_of_metafunctions__ [link boost.range.reference.semantics.metafunctions implementation of metafunctions]]
[def __implementation_of_functions__     [link boost.range.reference.semantics.functions implementation of functions]]

[def __single_pass_iterator__   [@../../libs/iterator/doc/new-iter-concepts.html#singls-pass-iterators-lib-single-pass-iterators Single Pass Iterator]]
[def __forward_traversal_iterator__ [@../../libs/iterator/doc/new-iter-concepts.html#forward-traversal-iterators-lib-forward-traversal-iterators Forward Traversal Iterator]]
[def __bidirectional_traversal_iterator__ [@../../libs/iterator/doc/new-iter-concepts.html#bidirectional-traversal-iterators-lib-bidirectional-traversal-iterators Bidirectional Traversal Iterator]]
[def __random_access_traversal_iterator__ [@../../libs/iterator/doc/new-iter-concepts.html#random-access-traversal-iterators-lib-random-access-traversal-iterators Random Access Traversal Iterator]]
[def __new_style_iterators__    [@../../libs/iterator/doc/new-iter-concepts.html new style iterators]]
[def __iterator_concepts__      [@../../libs/iterator/doc/iterator_concepts.html Iterator concepts]]

[def __container__              [@http://www.sgi.com/Technology/STL/Container.html Container]]
[def __metafunctions__          [@../../libs/mpl/doc/refmanual/metafunction.html metafunctions]]
[def __concept_check__          [@../../libs/concept_check/index.html Boost Concept Check library]]
[def __boost_array__            [@../../libs/array/index.html boost::array]]
[def __the_forwarding_problem__ [@http://std.dkuug.dk/jtc1/sc22/wg21/docs/papers/2002/n1385.htm The Forwarding Problem]]


Boost.Range is a collection of concepts and utilities that are particularly useful for specifying and implementing generic algorithms.


[section Introduction]

Generic algorithms have so far been specified in terms of two or more iterators. Two iterators would together form a range of values that the algorithm could work on. This leads to a very general interface, but also to a somewhat clumsy use of the algorithms with redundant specification of container names. Therefore we would like to raise the abstraction level for algorithms so they specify their interface in terms of __ranges__ as much as possible.

The most common form of ranges we are used to work with is standard library containers. However, one often finds it desirable to extend that code to work with other types that offer enough functionality to satisfy the needs of the generic code if a suitable layer of indirection is applied . For example, raw arrays are often suitable for use with generic code that works with containers, provided a suitable adapter is used. Likewise, null terminated strings can be treated as containers of characters, if suitably adapted.

This library therefore provides the means to adapt standard-like containers, null terminated strings, `std::pairs` of iterators, and raw arrays (and more), such that the same generic code can work with them all. The basic idea is to add another layer of indirection using __metafunctions__ and free-standing functions so syntactic and/or semantic differences can be removed.

The main advantages are

* simpler implementation and specification of generic range algorithms
* more flexible, compact and maintainable client code
* correct handling of null-terminated strings

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

* safe use of built-in arrays (for legacy code; why else would you use built-in arrays?)

Below are given a small example (the complete example can be found [@http://www.boost.org/libs/range/test/algorithm_example.cpp here] ):

``
        //
        // example: extracting bounds in a generic algorithm
        //
        template< class ForwardReadableRange, class T >
        inline typename boost::range_iterator< ForwardReadableRange >::type
        find( ForwardReadableRange& c, const T& value )
        {
           return std::find( boost::begin( c ), boost::end( c ), value );
        }

        template< class ForwardReadableRange, class T >
        inline typename boost::range_const_iterator< ForwardReadableRange >::type
        find( const ForwardReadableRange& c, const T& value )
        {
           return std::find( boost::begin( c ), boost::end( c ), value );
        }

        //
        // replace first value and return its index
        //
        template< class ForwardReadableWriteableRange, class T >
        inline typename boost::range_size< ForwardReadableWriteableRange >::type
        my_generic_replace( ForwardReadableWriteableRange& c, const T& value, const T& replacement )
        {
           typename boost::range_iterator< ForwardReadableWriteableRange >::type found = find( c, value );

           if( found != boost::end( c ) )
               *found = replacement;
           return std::distance( boost::begin( c ), found );
        }

        //
        // usage
        //
        const int N = 5;
        std::vector<int> my_vector;
        int values[] = { 1,2,3,4,5,6,7,8,9 };

        my_vector.assign( values, boost::end( values ) );
        typedef std::vector<int>::iterator iterator;
        std::pair<iterator,iterator>       my_view( boost::begin( my_vector ),
                                                    boost::begin( my_vector ) + N );
        char  str_val[] = "a string";
        char* str       = str_val;

        std::cout << my_generic_replace( my_vector, 4, 2 );
        std::cout << my_generic_replace( my_view, 4, 2 );
        std::cout << my_generic_replace( str, 'a', 'b' );

        // prints '3', '5' and '0'     
``

By using the free-standing functions and __metafunctions__, the code automatically works for all the types supported by this library; now and in the future. Notice that we have to provide two version of `find()` since we cannot forward a non-const rvalue with reference arguments (see this article about __the_forwarding_problem__ ).

[endsect] 



[section:concepts Range Concepts]

[section Overview]

A Range is a ['concept] similar to the STL [@http://www.sgi.com/Technology/STL/Container.html Container] concept. A Range provides iterators for accessing a half-open range `[first,one_past_last)` of elements and provides information about the number of elements in the Range. However, a Range has fewer requirements than a Container.

The motivation for the Range concept is that there are many useful Container-like types that do not meet the full requirements of Container, and many algorithms that can be written with this reduced set of requirements. In particular, a Range does not necessarily

* own the elements that can be accessed through it,
* have copy semantics, 

Because of the second requirement, a Range object must be passed by (const or non-const) reference in generic code.

The operations that can be performed on a Range is dependent on the [@../../iterator/doc/new-iter-concepts.html#iterator-traversal-concepts-lib-iterator-traversal traversal category] of the underlying iterator type. Therefore the range concepts are named to reflect which traversal category its iterators support. See also terminology and style guidelines. for more information about naming of ranges.

The concepts described below specifies associated types as [@../../libs/mpl/doc/refmanual/metafunction.html metafunctions] and all functions as free-standing functions to allow for a layer of indirection.

[endsect]


[section Single Pass Range]

[h4 Notation]

`X` 	A type that is a model of __single_pass_range__.
`a` 	Object of type X.

[h4 Description]

A range `X` where `boost::range_iterator<X>::type` is a model of __single_pass_iterator__.

[h4 Associated types]

[table
  []
  [[Value type         ] [`boost::range_value<X>::type`         ] [The type of the object stored in a Range.]]
  [[Iterator type      ] [`boost::range_iterator<X>::type`      ] [The type of iterator used to iterate through a Range's elements. The iterator's value type is expected to be the Range's value type. A conversion from the iterator type to the `const` iterator type must exist.]]
  [[Const iterator type] [`boost::range_const_iterator<X>::type`] [A type of iterator that may be used to examine, but not to modify, a Range's elements.]]
]

[h4 Valid expressions]

The following expressions must be valid.

[table
  [[Name              ] [Expression       ] [Return type        ]]
  [[Beginning of range] [`boost::begin(a)`] [`boost::range_iterator<X>::type` if `a` is mutable,[br] `boost::range_const_iterator<X>::type` otherwise]]
  [[End of range      ] [`boost::end(a)`  ] [`boost::range_iterator<X>::type` if `a` is mutable,[br] `boost::range_const_iterator<X>::type` otherwise]]
  [[Is range empty?   ] [boost::empty(a)  ] [Convertible to bool]]
]

[h4 Expression semantics]

[table
  [[Expression       ] [Semantics                                                               ] [Postcondition]]
  [[`boost::begin(a)`] [Returns an iterator pointing to the first element in the Range.         ] [`boost::begin(a)` is either dereferenceable or past-the-end. It is past-the-end if and only if `boost::size(a) == 0`.]]
  [[`boost::end(a)`  ] [Returns an iterator pointing one past the last element in the Range.    ] [`boost::end(a)` is past-the-end.]]
  [[`boost::empty(a)`] [Equivalent to `boost::begin(a) == boost::end(a)`. (But possibly faster.)] [-            ]]
]

[h4 Complexity guarantees]

All three functions are at most amortized linear time. For most practical purposes, one can expect `boost::begin(a)`, `boost::end(a)` and `boost::empty(a)` to be amortized constant time.

[h4 Invariants]

[table
  []
  [[Valid range ] [For any Range `a`, `[boost::begin(a),boost::end(a))` is a valid range, that is, `boost::end(a)` is reachable from `boost::begin(a)` in a finite number of increments.]]

  [[Completeness] [An algorithm that iterates through the range `[boost::begin(a),boost::end(a))` will pass through every element of `a`.]]
]

[h4 See also]

__container__

__implementation_of_metafunctions__

__implementation_of_functions__

[endsect]


[section Forward Range]

[h4 Notation]

`X` 	A type that is a model of __forward_range__.
`a` 	Object of type X.

[h4 Description]

A range `X` where `boost::range_iterator<X>::type` is a model of __forward_traversal_iterator__.

[h4 Refinement of]

__single_pass_range__

[h4 Associated types]

[table
  []
  [[Distance type] [`boost::range_difference<X>::type`] [A signed integral type used to represent the distance between two of the Range's iterators. This type must be the same as the iterator's distance type.]]
  [[Size type    ] [`boost::range_size<X>::type`      ] [An unsigned integral type that can represent any nonnegative value of the Range's distance type.]]
]

[h4 Valid expressions]

[table
  [[Name         ] [Expression      ] [Return type                 ]]
  [[Size of range] [`boost::size(a)`] [`boost::range_size<X>::type`]]
]

[h4 Expression semantics]

[table
  [[Expression      ] [Semantics] [Postcondition]]
  [[`boost::size(a)`] [Returns the size of the Range, that is, its number of elements. Note `boost::size(a) == 0u` is equivalent to `boost::empty(a)`.] [`boost::size(a) >= 0`]]
]

[h4 Complexity guarantees]

`boost::size(a)` is at most amortized linear time.

[h4 Invariants]

[table
  []
  [[Range size] [`boost::size(a)` is equal to the distance from `boost::begin(a)` to `boost::end(a)`.]]
]

[h4 See also]

__implementation_of_metafunctions__

__implementation_of_functions__

[endsect]


[section Bidirectional Range]

[h4 Notation]

`X` 	A type that is a model of __bidirectional_range__.
`a` 	Object of type X.

[h4 Description]

This concept provides access to iterators that traverse in both directions (forward and reverse). The `boost::range_iterator<X>::type` iterator must meet all of the requirements of __bidirectional_traversal_iterator__.

[h4 Refinement of]

__forward_range__

[h4 Associated types]

[table
  []
  [[Reverse Iterator type      ] [`boost::range_reverse_iterator<X>::type`      ] [The type of iterator used to iterate through a Range's elements in reverse order. The iterator's value type is expected to be the Range's value type. A conversion from the reverse iterator type to the const reverse iterator type must exist.]]

  [[Const reverse iterator type] [`boost::range_const_reverse_iterator<X>::type`] [A type of reverse iterator that may be used to examine, but not to modify, a Range's elements.]]
]

[h4 Valid expressions]

[table
  [[Name              ] [Expression        ] [Return type] [Semantics]]
  [[Beginning of range] [`boost::rbegin(a)`] [`boost::range_reverse_iterator<X>::type` if `a` is mutable[br] `boost::range_const_reverse_iterator<X>::type` otherwise.] [Equivalent to `boost::range_reverse_iterator<X>::type(boost::end(a))`.]]

  [[End of range      ] [`boost::rend(a)`  ] [`boost::range_reverse_iterator<X>::type` if `a` is mutable,[br] `boost::range_const_reverse_iterator<X>::type` otherwise.] [Equivalent to `boost::range_reverse_iterator<X>::type(boost::begin(a))`.]]
]

[h4 Complexity guarantees]

`boost::rbegin(a)` has the same complexity as `boost::end(a)` and `boost::rend(a)` has the same complexity as `boost::begin(a)` from __forward_range__.

[h4 Invariants]

[table
  []
  [[Valid reverse range] [For any Bidirectional Range a, `[boost::rbegin(a),boost::rend(a))` is a valid range, that is, `boost::rend(a)` is reachable from `boost::rbegin(a)` in a finite number of increments.]]

  [[Completeness       ] [`An algorithm that iterates through the range `[boost::rbegin(a),boost::rend(a))` will pass through every element of `a`.]]
]