1[/ 2 Copyright 2010 Neil Groves 3 Distributed under the Boost Software License, Version 1.0. 4 (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 5/] 6[section:adaptors Range Adaptors] 7 8[section:introduction Introduction and motivation] 9 10A [*Range Adaptor] is a class that wraps an existing Range to provide a new Range with different behaviour. Since the behaviour of Ranges is determined by their associated iterators, a Range Adaptor simply wraps the underlying iterators with new special iterators. In this example 11 12`` 13#include <boost/range/adaptors.hpp> 14#include <boost/range/algorithm.hpp> 15#include <iostream> 16#include <vector> 17 18std::vector<int> vec; 19boost::copy( vec | boost::adaptors::reversed, 20 std::ostream_iterator<int>(std::cout) ); 21`` 22 23the iterators from `vec` are wrapped `reverse_iterator`s. The type of the underlying Range Adapter is not documented because you do not need to know it. All that is relevant is that the expression 24 25`` 26vec | boost::adaptors::reversed 27`` 28 29returns a Range Adaptor where the iterator type is now the iterator type of the range `vec` wrapped in `reverse_iterator`. The expression `boost::adaptors::reversed` is called an *Adaptor Generator*. 30 31There are two ways of constructing a range adaptor. The first is by using `operator|()`. This is my preferred technique, however while discussing range adaptors with others it became clear that some users of the library strongly prefer a more familiar function syntax, so equivalent functions of the present tense form have been added as an alternative syntax. The equivalent to `rng | reversed` is `adaptors::reverse(rng)` for example. 32 33Why do I prefer the `operator|` syntax? The answer is readability: 34 35`` 36std::vector<int> vec; 37boost::copy( boost::adaptors::reverse(vec), 38 std::ostream_iterator<int>(std::cout) ); 39`` 40 41This might not look so bad, but when we apply several adaptors, it becomes much worse. Just compare 42 43`` 44std::vector<int> vec; 45boost::copy( boost::adaptors::unique( boost::adaptors::reverse( vec ) ), 46 std::ostream_iterator<int>(std::cout) ); 47`` 48 49to 50 51`` 52std::vector<int> vec; 53boost::copy( vec | boost::adaptors::reversed 54 | boost::adaptors::uniqued, 55 std::ostream_iterator<int>(std::cout) ); 56`` 57 58Furthermore, some of the adaptor generators take arguments themselves and these arguments are expressed with function call notation too. In those situations, you will really appreciate the succinctness of `operator|()`. 59 60[heading Composition of Adaptors] 61 62Range Adaptors are a powerful complement to Range algorithms. The reason is that adaptors are ['*orthogonal*] to algorithms. For example, consider these Range algorithms: 63 64* `boost::copy( rng, out )` 65* `boost::count( rng, pred )` 66 67What should we do if we only want to copy an element `a` if it satisfies some predicate, say `pred(a)`? And what if we only want to count the elements that satisfy the same predicate? The naive answer would be to use these algorithms: 68 69* `boost::copy_if( rng, pred, out )` 70* `boost::count_if( rng, pred )` 71 72These algorithms are only defined to maintain a one to one relationship with the standard library algorithms. This approach of adding algorithm suffers a combinatorial explosion. Inevitably many algorithms are missing `_if` variants and there is redundant development overhead for each new algorithm. The Adaptor Generator is the design solution to this problem. It is conceivable that some algorithms are capable of optimization by tightly coupling the filter with the algorithm. The adaptors provide a more general solution with superior separation of orthogonal concerns. 73 74[heading Range Adaptor alternative to copy_if algorithm] 75`` 76boost::copy_if( rng, pred, out ); 77`` 78can be expressed as 79`` 80boost::copy( rng | boost::adaptors::filtered(pred), out ); 81`` 82 83[heading Range Adaptor alternative to count_if algorithm] 84`` 85boost::count_if( rng, pred ); 86`` 87can be expressed as 88`` 89boost::size( rng | boost::adaptors::filtered(pred) ); 90`` 91 92What this means is that many algorithms no longer require nor benefit from an optimized implementation with an `_if` suffix. Furthermore, it turns out that algorithms with the `_copy` suffix are often not needed either. Consider `replace_copy_if()` which may be used as 93 94`` 95std::vector<int> vec; 96boost::replace_copy_if( rng, std::back_inserter(vec), pred, new_value ); 97`` 98 99With adaptors and algorithms we can express this as 100 101`` 102std::vector<int> vec; 103boost::push_back(vec, rng | boost::adaptors::replaced_if(pred, new_value)); 104`` 105 106The latter code has several benefits: 107 1081. it is more ['*efficient*] because we avoid extra allocations as might happen with `std::back_inserter` 109 1102. it is ['*flexible*] as we can subsequently apply even more adaptors, for example: `` 111boost::push_back(vec, rng | boost::adaptors::replaced_if(pred, new_value) 112 | boost::adaptors::reversed); 113`` 114 1153. it is ['*safer*] because there is no use of an unbounded output iterator. 116 117In this manner, the ['*composition*] of Range Adaptors has the following consequences: 118 1191. we no longer need many of the `_if`, `_copy`, `_copy_if` and `_n` variants of algorithms. 120 1212. we can generate a multitude of new algorithms on the fly, for example, above we generated `reverse_replace_copy_if()` 122 123In other words: 124 125[*Range Adaptors are to algorithms what algorithms are to containers] 126 127[endsect] 128 129[section:general_requirements General Requirements] 130 131In the description of generator expressions, the following notation is used: 132 133* `fwdRng` is an expression of a type `R` that models `ForwardRange` 134* `biRng` is an expression of a type `R` that models `BidirectionalRange` 135* `rndRng` is an expression of a type `R` that models `RandomAccessRange` 136* `pred` is an expression of a type that models `UnaryPredicate` 137* `bi_pred` is an expression of a type that models `BinaryPredicate` 138* `fun` is an expression of a type that models `UnaryFunction` 139* `value`, `new_value` and `old_value` are objects convertible to `boost::range_value<R>::type` 140* `n,m` are integer expressions convertible to `range_difference<R>::type` 141 142Also note that `boost::range_value<R>::type` must be implicitly convertible to the type arguments to `pred`, `bi_pred` and `fun`. 143 144Range Category in the following adaptor descriptions refers to the minimum range concept required by the range passed to the adaptor. The resultant range is a model of the same range concept as the input range unless specified otherwise. 145 146Returned Range Category is the concept of the returned range. In some cases the returned range is of a lesser category than the range passed to the adaptor. For example, the `filtered` adaptor returns only a `ForwardRange` regardless of the input. 147 148Furthermore, the following rules apply to any expression of the form 149`` 150rng | boost::adaptors::adaptor_generator 151`` 152 1531. Applying `operator|()` to a range `R` (always left argument) and a range adapter `RA` (always right argument) yields a new range type which may not conform to the same range concept as `R`. 154 1552. The return-type of `operator|()` is otherwise unspecified. 156 1573. `operator|()` is found by Argument Dependent Lookup (ADL) because a range adaptor is implemented in namespace `boost::adaptors`. 158 1594. `operator|()` is used to add new behaviour ['*lazily*] and never modifies its left argument. 160 1615. All iterators extracted from the left argument are extracted using qualified calls to `boost::begin()` and `boost::end()`. 162 1636. In addition to the `throw`-clauses below, `operator|()` may throw exceptions as a result of copying iterators. If such copying cannot throw an exception, then neither can the whole expression. 164 165[endsect] 166 167[section:reference Reference] 168[include adaptors/adjacent_filtered.qbk] 169[include adaptors/copied.qbk] 170[include adaptors/filtered.qbk] 171[include adaptors/indexed.qbk] 172[include adaptors/indirected.qbk] 173[include adaptors/map_keys.qbk] 174[include adaptors/map_values.qbk] 175[include adaptors/ref_unwrapped.qbk] 176[include adaptors/replaced.qbk] 177[include adaptors/replaced_if.qbk] 178[include adaptors/reversed.qbk] 179[include adaptors/sliced.qbk] 180[include adaptors/strided.qbk] 181[include adaptors/type_erased.qbk] 182[include adaptors/tokenized.qbk] 183[include adaptors/transformed.qbk] 184[include adaptors/uniqued.qbk] 185[endsect] 186 187[endsect] 188 189