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:algorithms Range Algorithms] 7[section:introduction Introduction and motivation] 8In its most simple form a [*Range Algorithm] (or range-based algorithm) is simply an iterator-based algorithm where the /two/ iterator arguments have been replaced by /one/ range argument. For example, we may write 9 10`` 11#include <boost/range/algorithm.hpp> 12#include <vector> 13 14std::vector<int> vec = ...; 15boost::sort(vec); 16`` 17 18instead of 19 20`` 21std::sort(vec.begin(), vec.end()); 22`` 23 24However, the return type of range algorithms is almost always different from that of existing iterator-based algorithms. 25 26One group of algorithms, like `boost::sort()`, will simply return the same range so that we can continue to pass the range around and/or further modify it. Because of this we may write 27`` 28boost:unique(boost::sort(vec)); 29`` 30to first sort the range and then run `unique()` on the sorted range. 31 32Algorithms like `boost::unique()` fall into another group of algorithms that return (potentially) narrowed views of the original range. By default `boost::unique(rng)` returns the range `[boost::begin(rng), found)` where `found` denotes the iterator returned by `std::unique(boost::begin(rng), boost::end(rng))` 33 34Therefore exactly the unique values can be copied by writing 35`` 36boost::copy(boost::unique(boost::sort(vec)), 37 std::ostream_iterator<int>(std::cout)); 38`` 39 40Algorithms like `boost::unique` usually return the range: `[boost::begin(rng), found)`. 41However, this behaviour may be changed by supplying a `range_return_value` 42as a template parameter to the algorithm: 43 44[table 45 [[Expression] [Return]] 46 [[`boost::unique<boost::return_found>(rng)`] [returns a single iterator like `std::unique`]] 47 [[`boost::unique<boost::return_begin_found>(rng)`] [returns the range `[boost::begin(rng), found)` (this is the default)]] 48 [[`boost::unique<boost::return_begin_next>(rng)`] [returns the range `[boost::begin(rng), boost::next(found))`]] 49 [[`boost::unique<boost::return_found_end>(rng)`] [returns the range `[found, boost::end(rng))`]] 50 [[`boost::unique<boost::return_next_end>(rng)`] [returns the range `[boost::next(found),boost::end(rng))`]] 51 [[`boost::unique<boost::return_begin_end>(rng)`] [returns the entire original range.]] 52] 53 54This functionality has the following advantages: 55 56# it allows for ['*seamless functional-style programming*] where you do not need to use named local variables to store intermediate results 57# it is very ['*safe*] because the algorithm can verify out-of-bounds conditions and handle tricky conditions that lead to empty ranges 58 59For example, consider how easy we may erase the duplicates in a sorted container: 60 61`` 62std::vector<int> vec = ...; 63boost::erase(vec, boost::unique<boost::return_found_end>(boost::sort(vec))); 64`` 65 66Notice the use of `boost::return_found_end`. What if we wanted to erase all the duplicates except one of them? In old-fashioned STL-programming we might write 67 68`` 69// assume 'vec' is already sorted 70std::vector<int>::iterator i = std::unique(vec.begin(), vec.end()); 71 72// remember this check or you get into problems 73if (i != vec.end()) 74 ++i; 75 76vec.erase(i, vec.end()); 77`` 78 79The same task may be accomplished simply with 80`` 81boost::erase(vec, boost::unique<boost::return_next_end>(vec)); 82`` 83and there is no need to worry about generating an invalid range. Furthermore, if the container is complex, calling `vec.end()` several times will be more expensive than using a range algorithm. 84 85[endsect] 86 87[section:mutating Mutating algorithms] 88[include algorithm/copy.qbk] 89[include algorithm/copy_backward.qbk] 90[include algorithm/fill.qbk] 91[include algorithm/fill_n.qbk] 92[include algorithm/generate.qbk] 93[include algorithm/inplace_merge.qbk] 94[include algorithm/merge.qbk] 95[include algorithm/nth_element.qbk] 96[include algorithm/partial_sort.qbk] 97[include algorithm/partition.qbk] 98[include algorithm/random_shuffle.qbk] 99[include algorithm/remove.qbk] 100[include algorithm/remove_copy.qbk] 101[include algorithm/remove_copy_if.qbk] 102[include algorithm/remove_if.qbk] 103[include algorithm/replace.qbk] 104[include algorithm/replace_copy.qbk] 105[include algorithm/replace_copy_if.qbk] 106[include algorithm/replace_if.qbk] 107[include algorithm/reverse.qbk] 108[include algorithm/reverse_copy.qbk] 109[include algorithm/rotate.qbk] 110[include algorithm/rotate_copy.qbk] 111[include algorithm/sort.qbk] 112[include algorithm/stable_partition.qbk] 113[include algorithm/stable_sort.qbk] 114[include algorithm/swap_ranges.qbk] 115[include algorithm/transform.qbk] 116[include algorithm/unique.qbk] 117[include algorithm/unique_copy.qbk] 118[endsect] 119 120[section:non_mutating Non-mutating algorithms] 121[include algorithm/adjacent_find.qbk] 122[include algorithm/binary_search.qbk] 123[include algorithm/count.qbk] 124[include algorithm/count_if.qbk] 125[include algorithm/equal.qbk] 126[include algorithm/equal_range.qbk] 127[include algorithm/for_each.qbk] 128[include algorithm/find.qbk] 129[include algorithm/find_end.qbk] 130[include algorithm/find_first_of.qbk] 131[include algorithm/find_if.qbk] 132[include algorithm/lexicographical_compare.qbk] 133[include algorithm/lower_bound.qbk] 134[include algorithm/max_element.qbk] 135[include algorithm/min_element.qbk] 136[include algorithm/mismatch.qbk] 137[include algorithm/search.qbk] 138[include algorithm/search_n.qbk] 139[include algorithm/upper_bound.qbk] 140[endsect] 141 142[section:set Set algorithms] 143[include algorithm/includes.qbk] 144[include algorithm/set_union.qbk] 145[include algorithm/set_intersection.qbk] 146[include algorithm/set_difference.qbk] 147[include algorithm/set_symmetric_difference.qbk] 148[endsect] 149 150[section:heap Heap algorithms] 151[include algorithm/push_heap.qbk] 152[include algorithm/pop_heap.qbk] 153[include algorithm/make_heap.qbk] 154[include algorithm/sort_heap.qbk] 155[endsect] 156 157[section:permutation Permutation algorithms] 158[include algorithm/next_permutation.qbk] 159[include algorithm/prev_permutation.qbk] 160[endsect] 161 162[section:new New algorithms] 163[include algorithm_ext/copy_n.qbk] 164[include algorithm_ext/erase.qbk] 165[include algorithm_ext/for_each.qbk] 166[include algorithm_ext/insert.qbk] 167[include algorithm_ext/iota.qbk] 168[include algorithm_ext/is_sorted.qbk] 169[include algorithm_ext/overwrite.qbk] 170[include algorithm_ext/push_back.qbk] 171[include algorithm_ext/push_front.qbk] 172[include algorithm_ext/remove_erase.qbk] 173[include algorithm_ext/remove_erase_if.qbk] 174[endsect] 175 176[section:numeric Numeric algorithms] 177[include numeric/accumulate.qbk] 178[include numeric/adjacent_difference.qbk] 179[include numeric/inner_product.qbk] 180[include numeric/partial_sum.qbk] 181[endsect] 182[endsect] 183