Copyright © 2003 -2007 Thorsten Ottosen
Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy athttp://www.boost.org/LICENSE_1_0.txt)
Table of Contents
Introduction..........................................................................................................................................................1Range Concepts.....................................................................................................................................................3
Overview......................................................................................................................................................3Single Pass Range..........................................................................................................................................3Forward Range..............................................................................................................................................5Bidirectional Range........................................................................................................................................6Random Access Range....................................................................................................................................7Concept Checking..........................................................................................................................................7Reference.............................................................................................................................................................8
Overview......................................................................................................................................................8Synopsis.......................................................................................................................................................9Semantics...................................................................................................................................................11Extending the library.....................................................................................................................................15Utilities..............................................................................................................................................................18
Class iterator_range................................................................................................................................19Class sub_range.........................................................................................................................................22Terminology and style guidelines............................................................................................................................24Library Headers...................................................................................................................................................25Examples............................................................................................................................................................26Portability...........................................................................................................................................................26FAQ...................................................................................................................................................................26History and Acknowledgement................................................................................................................................27Boost.Range is a collection of concepts and utilities that are particularly useful for specifying and implementing generic algorithms.
Introduction
Generic algorithms have so far been specified in terms of two or more iterators. Two iterators would together form a range of valuesthat the algorithm could work on. This leads to a very general interface, but also to a somewhat clumsy use of the algorithms withredundant specification of container names. Therefore we would like to raise the abstraction level for algorithms so they specifytheir 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 toextend that code to work with other types that offer enough functionality to satisfy the needs of the generic code if a suitable layerof indirection is applied . For example, raw arrays are often suitable for use with generic code that works with containers, provideda 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, andraw arrays (and more), such that the same generic code can work with them all. The basic idea is to add another layer of indirectionusing 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
1
XML to PDFby RenderX XEP XSL-FO Formatter, visit us at http://www.renderx.com/
Boost.Range Documentation
•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 here ):
//
// example: extracting bounds in a generic algorithm//
template inlinetypename boost::range_iterator< ForwardReadableRange >::typefind( ForwardReadableRange& c,const T& value ){ return std::find( boost::begin( c ), boost::end( c ), value );} template inlinetypename boost::range_const_iterator< ForwardReadableRange >::typefind(const ForwardReadableRange& c,const T& value ){ return std::find( boost::begin( c ), boost::end( c ), value );} // // replace first value and return its index// template inlinetypename 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// constint N =5; std::vector int values[]={1,2,3,4,5,6,7,8,9}; my_vector.assign( values, boost::end( values ));typedef std::vector std::pair boost::begin( my_vector )+ N );char str_val[]=\"a string\";char* str = str_val; 2 XML to PDFby RenderX XEP XSL-FO Formatter, visit us at http://www.renderx.com/ Boost.Range Documentation 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 ref-erence arguments (see this article about The Forwarding Problem ). Range Concepts Overview A Range is a concept similar to the STL 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 Rangehas 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 ofContainer, 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 traversal category of the underlying iterator type. Thereforethe range concepts are named to reflect which traversal category its iterators support. See also terminology and style guidelines. formore information about naming of ranges. The concepts described below specifies associated types as metafunctions and all functions as free-standing functions to allow fora layer of indirection. Single Pass Range Notation XA type that is a model of Single Pass Range. a Object of type X. Description A range X where boost::range_iterator 3 XML to PDFby RenderX XEP XSL-FO Formatter, visit us at http://www.renderx.com/ Boost.Range Documentation Associated types Value typeIterator type boost::range_value The type of the object stored in a Range.The type of iterator used to iterate througha Range's elements. The iterator's valuetype is expected to be the Range's valuetype. A conversion from the iterator typeto the const iterator type must exist.A type of iterator that may be used to ex-amine, but not to modify, a Range's ele-ments. Const iterator type boost::range_const_iterat-or Valid expressions The following expressions must be valid.Name Beginning of range Expression boost::begin(a) Return type boost::range_iterator boost::range_const_iterat-or boost::range_iterator boost::range_const_iterat-or End of rangeboost::end(a) Is range empty?boost::empty(a)Convertible to bool Expression semantics Expression boost::begin(a) Semantics Returns an iterator pointing to the firstelement in the Range. Returns an iterator pointing one past thelast element in the Range. Equivalent to boost::begin(a) ==boost::end(a). (But possibly faster.) Postcondition boost::begin(a) is either dereference- able or past-the-end. It is past-the-end ifand only if boost::size(a) == 0. boost::end(a) is past-the-end. boost::end(a) boost::empty(a)- 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. 4 XML to PDFby RenderX XEP XSL-FO Formatter, visit us at http://www.renderx.com/ Boost.Range Documentation Invariants Valid range For any Range a, [boost::begin(a),boost::end(a)) isa valid range, that is, boost::end(a) is reachable fromboost::begin(a) in a finite number of increments.An algorithm that iterates through the range [boost::be-gin(a),boost::end(a)) will pass through every elementof a. Completeness See also Container implementation of metafunctionsimplementation of functions Forward Range Notation XA type that is a model of Forward Range. a Object of type X. Description A range X where boost::range_iterator Refinement of Single Pass Range Associated types Distance type boost::range_differ-ence A signed integral type used to representthe distance between two of the Range'siterators. This type must be the same asthe iterator's distance type. An unsigned integral type that can repres-ent any nonnegative value of the Range'sdistance type. Size typeboost::range_size Valid expressions NameSize of range Expression boost::size(a) Return type boost::range_size 5 XML to PDFby RenderX XEP XSL-FO Formatter, visit us at http://www.renderx.com/ Boost.Range Documentation Expression semantics Expression boost::size(a) Semantics Returns the size of the Range, that is, itsnumber of elements. Noteboost::size(a) == 0u is equivalentto boost::empty(a). Postcondition boost::size(a) >= 0 Complexity guarantees boost::size(a) is at most amortized linear time. Invariants Range size boost::size(a) is equal to the distance from boost::be-gin(a) to boost::end(a). See also implementation of metafunctionsimplementation of functions Bidirectional Range Notation XA type that is a model of Bidirectional Range. a Object of type X. Description This concept provides access to iterators that traverse in both directions (forward and reverse). The boost::range_iterat-or Refinement of Forward Range Associated types Reverse Iterator type boost::range_reverse_iterat-or The type of iterator used to iterate througha Range's elements in reverse order. Theiterator's value type is expected to be theRange's value type. A conversion fromthe reverse iterator type to the const re-verse iterator type must exist. A type of reverse iterator that may be usedto examine, but not to modify, a Range'selements. Const reverse iterator type boost::range_const_reverse_iter-ator 6 XML to PDFby RenderX XEP XSL-FO Formatter, visit us at http://www.renderx.com/ Boost.Range Documentation Valid expressions Name Beginning of range Expression boost::rbegin(a) Return type boost::range_re-verse_iterator boost::range_const_re-verse_iterator Semantics Equivalent to boost::range_re-verse_iterat-or otherwise. End of range boost::rend(a) boost::range_re-verse_iterator boost::range_const_re-verse_iterator Equivalent to boost::range_re-verse_iterat-or otherwise. Complexity guarantees boost::rbegin(a) has the same complexity as boost::end(a) and boost::rend(a) has the same complexity asboost::begin(a) from Forward Range. Invariants Valid reverse range For any Bidirectional Range a, [boost::rbe-gin(a),boost::rend(a)) is a valid range, that is,boost::rend(a) is reachable from boost::rbegin(a) ina finite number of increments. An algorithm that iterates through the range[boost::rbegin(a),boost::rend(a)) will pass through everyelement of a`. Completeness See also implementation of metafunctionsimplementation of functions Random Access Range Description A range X where boost::range_iterator Refinement of Bidirectional Range Concept Checking Each of the range concepts has a corresponding concept checking class in the file boost/range/concepts.hpp. These classesmay be used in conjunction with the Boost Concept Check library to insure that the type of a template parameter is compatible witha range concept. If not, a meaningful compile time error is generated. Checks are provided for the range concepts related to iteratortraversal categories. For example, the following line checks that the type T models the Forward Range concept. 7 XML to PDFby RenderX XEP XSL-FO Formatter, visit us at http://www.renderx.com/ Boost.Range Documentation function_requires An additional concept check is required for the value access property of the range based on the range's iterator type. For example tocheck for a ForwardReadableRange, the following code is required. function_requires ReadableIteratorConcept< typename range_iterator The following range concept checking classes are provided.•Class SinglePassRangeConcept checks for Single Pass Range•Class ForwardRangeConcept checks for Forward Range•Class BidirectionalRangeConcept checks for Bidirectional Range•Class RandomAccessRangeConcept checks for Random Access Range See also Range Terminology and style guidelinesIterator concepts Boost Concept Check library Reference Overview Four types of objects are currently supported by the library:•standard-like containers •std::pair •null terminated strings (this includes char[],wchar_t[], char*, and wchar_t*) Warning: support for null-terminated strings is deprecated and will disappear in the next Boost release(1.34). •built-in arrays Even though the behavior of the primary templates are exactly such that standard containers will be supported by default, the require-ments are much lower than the standard container requirements. For example, the utility class iterator_range implements theminimal interface required to make the class a Forward Range.Please also see Range concepts for more details. 8 XML to PDFby RenderX XEP XSL-FO Formatter, visit us at http://www.renderx.com/ Boost.Range Documentation Synopsis namespace boost{ // // Single Pass Range metafunctions// template struct range_const_iterator;// // Forward Range metafunctions// template struct range_difference;template // // Bidirectional Range metafunctions// template struct range_reverse_iterator;template struct range_const_reverse_iterator;// // Special metafunctions// template struct range_result_iterator; template struct range_reverse_result_iterator;// // Single Pass Range functions// template typename range_iterator template typename range_const_iterator template typename range_iterator 9 XML to PDFby RenderX XEP XSL-FO Formatter, visit us at http://www.renderx.com/ Boost.Range Documentation template typename range_const_iterator empty(const T& c ); // // Forward Range functions// template typename range_size // // Bidirectional Range functions// template typename range_reverse_iterator template typename range_const_reverse_iterator template typename range_reverse_iterator template typename range_const_reverse_iterator // // Special const Range functions// template typename range_const_iterator template typename range_const_iterator template typename range_const_reverse_iterator 10 XML to PDFby RenderX XEP XSL-FO Formatter, visit us at http://www.renderx.com/ Boost.Range Documentation template typename range_const_reverse_iterator Semantics notationType XTP Object xtp Describesany type denotes behavior of the primary templatesdenotes std::pair A[sz]Char* as denotes an array of type A of size szdenotes either char* or wchar_t* Please notice in tables below that when four lines appear in a cell, the first line will describe the primary template, the second linepairs of iterators, the third line arrays and the last line null-terminated strings. 11 XML to PDFby RenderX XEP XSL-FO Formatter, visit us at http://www.renderx.com/ Boost.Range Documentation Metafunctions Expression range_value Return type T::value_type boost::iterat-or_value T::iteratorP::first_typeA*Char* T::const_iteratorP::first_typeconst A*const Char* T::difference_type boost::iterator_differ-ence range_const_iterator range_iterator boost::reverse_iterator< type-name range_result_iterat-or Complexitycompile time range_iterator range_const_iterator range_difference range_size range_result_iterator range_reverse_iterator range_const_reverse_iterat-or range_reverse_result_iterat-or compile time The special metafunctions range_result_iterator and range_reverse_result_iterator are not part of any Range concept,but they are very useful when implementing certain Range classes like sub_range because of their ability to select iterators basedon constness. 12 XML to PDFby RenderX XEP XSL-FO Formatter, visit us at http://www.renderx.com/ Boost.Range Documentation Functions 13 XML to PDFby RenderX XEP XSL-FO Formatter, visit us at http://www.renderx.com/ Boost.Range Documentation Expression begin(x) Return type range_result_iterat-or Returns p.first if p is of typestd::pair s if s is a string literal boost_range_begin(x) if Complexityconstant time that expression would invokea function found by ADLt.begin() otherwise end(x) range_result_iterat-or p.second if p is of typestd::pair a + sz if a is an array of sizeszs + std::char_traits s + sz - 1 if s is a stringliteral of size sz boost_range_end(x) if that linear if X is Char* constanttime otherwise expression would invoke afunction found by ADLt.end() otherwise empty(x) bool begin(x) == end( x ) linear if X is Char*constant time otherwiselinear if X is Char* or ifstd::distance() is linearconstant time otherwise size(x)range_size std::dis-tance(p.first,p.second)if p is of type std::pair boost_range_size(x) if that expression would invokea function found by ADLt.size() otherwise rbegin(x) range_reverse_res-ult_iterator range_reverse_res-ult_iterator range_reverse_res-ult_iterator range_const_iterat-or range_const_iterat-or same as end(x) rend(x) range_reverse_res-ult_iterator same as begin(x) const_begin(x) range_const_iterat-or same as begin(x) const_end(x) range_const_iterat-or same as end(x) 14 XML to PDFby RenderX XEP XSL-FO Formatter, visit us at http://www.renderx.com/ Boost.Range Documentation Expression const_rbegin(x) Return type range_const_re-verse_iterator Returns range_const_re-verse_iterat-or range_const_re-verse_iterat-or Complexitysame as rbegin(x) const_rend(x) range_const_re-verse_iterator same as rend(x) The special const functions are not part of any Range concept, but are very useful when you want to document clearly that your codeis read-only. Extending the library 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 method2. 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 Rangeconcept. Member function begin()end()size() Related conceptSingle Pass RangeSingle Pass RangeForward Range Notice that rbegin() and rend() member functions are not needed even though the container can support bidirectional iteration.The required member types are:Member type iteratorconst_iteratorsize_type Related conceptSingle Pass RangeSingle Pass RangeForward Range Again one should notice that member types reverse_iterator and const_reverse_iterator are not needed. 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 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 xbe a variable (const or mutable) of the class in question. 15 XML to PDFby RenderX XEP XSL-FO Formatter, visit us at http://www.renderx.com/ Boost.Range Documentation Function boost_range_begin(x)boost_range_end(x)boost_range_size(x) Related conceptSingle Pass RangeSingle Pass RangeForward 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:Metafunction boost::range_iteratorboost::range_const_iteratorboost::range_size Related conceptSingle Pass RangeSingle Pass RangeForward Range A complete example is given here: 16 XML to PDFby RenderX XEP XSL-FO Formatter, visit us at http://www.renderx.com/ Boost.Range Documentation #include // 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 T first, last; };}// namespace 'Foo' namespace boost{ // // Specialize metafunctions. We must include the range.hpp header.// We must open the 'boost' namespace.//template struct range_iterator< Foo::Pair typedef T type;}; template struct range_const_iterator< Foo::Pair // 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 struct range_size< Foo::Pair 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 inline T boost_range_begin( Pair return x.first; 17 XML to PDFby RenderX XEP XSL-FO Formatter, visit us at http://www.renderx.com/ Boost.Range Documentation } template inline T boost_range_begin(const Pair return x.first;} template inline T boost_range_end( Pair return x.last;} template inline T boost_range_end(const Pair return x.last;} template inlinetypename boost::range_size< Pair return std::distance(x.first,x.last);} }// namespace 'Foo'#include int main(){ typedef std::vector Foo::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