Except for the numeric algorithms, all algorithms are declared in the header <algorithm>
Most STL algorithms operate on iterator ranges. These are the exceptions.
swap (x, y);
Swap two values.
Swaps by copying with the help of temporary.
Should be overloaded for types that can be swapped more efficiently.
namespace gadget { struct widget { void swap(widget&); // ... } void swap (widget& x, widget& y) { x.swap(y); } }
iter_swap (p, q);
min (x, y); min (x, y, binary_predicate); max (x, y); max (x, y, binary_predicate);
The STL algorithms below search a range for some element or a subrange.
All iterators are input or forward iterators.
The return value is an iterator to the element or to the beginning of the subrange if found, and the end iterator if not found.
The optional binary_predicate of many algorithms is used for comparing two elements.
// find first decrease in values string s("abcdcba"); string::iterator i; i = adjacent_find(begin, end, greater<char>()); assert(*i=='d');
Here are the search algorithms:
find (begin, end, value); find_if (begin, end, unary_predicate);
count (begin, end, value); count_if (begin, end, unary_predicate);
find_first_of (begin, end, set_begin, set_end); find_first_of (begin, end, set_begin, set_end, binary_predicate);
adjacent_find (begin, end); adjacent_find (begin, end, binary_predicate);
search_n (begin, end, n, value); search_n (begin, end, n, value, binary_predicate);
search (begin, end, begin2, end2); search (begin, end, begin2, end2, binary_predicate); find_end (begin, end, begin2, end2); find_end (begin, end, begin2, end2, binary_predicate);
Finds the first or the last matching subrange.
string s("first matching subrange"); string p("match"); string::iterator i; i = search(s.begin(), s.end(), p.begin(), p.end()); assert(*i == 'm');
min_element(begin, end); min_element(begin, end, order_comparison); max_element(begin, end); max_element(begin, end, order_comparison);
The following algorithms compare the two ranges [begin1,end1) and [begin2,begin2+(end1-begin1)).
equal (begin1, end1, begin2); equal (begin1, end1, begin2, binary_predicate);
mismatch (begin1, end1, begin2); mismatch (begin1, end1, begin2, binary_predicate);
lexicographic_compare (begin1, end1, begin2); lexicographic_compare (begin1, end1, begin2, order_comparison);
for_each is a powerful algorithm for iterating over all elements of a range doing something with them.
for_each(begin, end, unary_functor);
For example:
struct mean_value : unary_function<int,void> { mean_value() : count(0), sum(0) {} void operator() (int x) { ++count; sum+=x; } operator double() { return static_cast<double>(sum) / static_cast<double>(count); } private: long count; long sum; }; vector<int> v; // ... double mean = for_each(begin, end, mean_value());
The following algorithms copy a range into another.
copy (begin, end, result);
copy_backward (begin, end, result);
The differences between the two are
Either algorithm can be used (but copy should be preferred) except when the two ranges overlap.
Two ranges can also be swapped using element-by-element swaps.
swap_ranges (begin1, end1, begin2);
Many of the following algorithms have a version with copy in the name.
copy and other algorithms writing to an output iterator range return an iterator to the end of the output range (result+(end-begin)). Writing can continue using that iterator.
vector<int> v1; vector<int> v2; // fill v1 and v2 vector<int> v3; back_insert_iterator <vector<int> > i(v3); i = copy(v1.begin(), v1.end(), i); i = fill_n(i, 10, 0); i = copy(v2.begin(), v2.end(), i);
The following algorithms replace matching elements with a new value.
replace (begin, end, old_value, new_value); replace_if (begin, end, predicate, new_value); replace_copy (begin, end, result, old_value, new_value); replace_copy_if (begin, end, result, predicate, new_value);
A more powerful algorithm for replacing elements is transform.
transform (begin, end, result, unary_functor);
There is also a variant that combines two ranges.
transform (begin1, end1, begin2, result, binary_functor);
fill (begin, end, value);
fill_n (begin, n, value);
Fills [begin,begin+n) with copies of value.
vector<double> v(10, 1.0); fill_n (back_inserter(v), 10, 2.0);
A generalization of fill uses a generator (nullary functor) instead of a fixed value.
generate (begin, end, generator); generate_n (begin, n, generator);
For example, the following fills a vector with the first 100 Fibonacci numbers.
struct fibonacci_generator { typedef int result_type; fibonacci_generator() : current(0), next(1) {} int operator() () { int tmp = current; current = next; next += tmp; return tmp; } private: int current; int next; }; vector<int> v; v.reserve(100); generate_n(back_inserter(v), 100, fibonacci_generator());
The following algorithms remove all matching elements from a range.
remove (begin, end, value); remove_if (begin, end, predicate); remove_copy (begin, end, result, value); remove_copy_if (begin, end, result, predicate);
The copy versions copy the unremoved elements leaving the original range untouched.
The non-copy versions place the unremoved elements to the beginning of the range [begin,end).
new_end = remove_if (begin, end, even());
The elements could not truely be erased, because the algorithm does not know enough about the container to do that. The container's erase member function can be called to perform the actual erasure using this standard idiom.
c.erase(remove(c.begin(), c.end(), value), c.end());
Here's another example of removing all 1's and 2's from a vector.
vector<int> v; // fill v vector<int>::iterator new_end; new_end = remove(v.begin(), v.end(), 1); new_end = remove(v.begin(), new_end, 2); v.erase(new_end, v.end());
There are also algorithms for removing duplicates:
unique (begin, end); unique (begin, end, binary_predicate); unique_copy (begin, end, result); unique_copy (begin, end, result, binary_predicate);
partition (begin, end, predicate); stable_partition (begin, end, predicate);
Places all elements satisfying predicate in the beginning. If n is the number of satisfying elements, then after the call:
mid = partition (begin, end, even());
The following algorithms change the order of elements in the range.
reverse (begin, end); reverse_copy (begin, end, result);
rotate (begin, middle, end); rotate_copy (begin, middle, end, result);
next_permutation(begin, end); prev_permutation(begin, end); next_permutation(begin, end, order_comparison); prev_permutation(begin, end, order_comparison);
random_suffle (begin, end); random_suffle (begin, end, random_number_generator);
sort (begin, end); sort (begin, end, order_comparison);
stable_sort (begin, end); stable_sort (begin, end, order_comparison);
partial_sort (begin, middle, end); partial_sort (begin, middle, end, order_comparison);
partial_sort_copy (begin, end, result_begin, result_end); partial_sort_copy (begin, end, result_begin, result_end, order_comparison);
nth_element (begin, middle, end); nth_element (begin, middle, end, order_comparison);
After the call:
iterator middle = begin + (end-begin) / 2; nth_element(begin, middle, end); median = *middle;
merge (begin1, end1, begin2, end2, result); merge (begin1, end1, begin2, end2, result, order_comparison);
inplace_merge (begin, middle, end); inplace_merge (begin, middle, end, order_comparison);
These operations implement the standard binary heap.
make_heap(begin, end); make_heap(begin, end, order_comparison); push_heap(begin, end); push_heap(begin, end, order_comparison); pop_heap(begin, end); pop_heap(begin, end, order_comparison); sort_heap(begin, end); sort_heap(begin, end, order_comparison);
The following algorithms perform a binary search on a sorted range.
binary_search (begin, end, value); binary_search (begin, end, value, order_comparison);
lower_bound (begin, end, value); lower_bound (begin, end, value, order_comparison);
upper_bound (begin, end, value); upper_bound (begin, end, value, order_comparison);
equal_range (begin, end, value); equal_range (begin, end, value, order_comparison);
Set operations on sorted ranges representing sets:
includes (begin1, end1, begin2, end2); includes (begin1, end1, begin2, end2, order_comparison); set_union (begin1, end1, begin2, end2, result); set_union (begin1, end1, begin2, end2, result, order_comparison); set_intersection (begin1, end1, begin2, end2, result); set_intersection (begin1, end1, begin2, end2, result, order_comparison); set_difference (begin1, end1, begin2, end2, result); set_difference (begin1, end1, begin2, end2, result, order_comparison); set_symmetric_difference (begin1, end1, begin2, end2, result); set_symmetric_difference (begin1, end1, begin2, end2, result, order_comparison);
Can be used on associative containers.
The following algorithms are defined in the header <numeric>.
accumulate (begin, end, init); accumulate (begin, end, init, binary_functor);
Computes the sum of the elements.
struct size_sum : binary_function<size_t, string, size_t> { size_t operator() (size_t sum, const string& s) const { return sum + s.size(); } }; vector<string> v; // ... size_t total_length = accumulate(v.begin(), v.end(), 0, size_sum());
inner_product (begin1, end1, begin2, init); inner_product (begin1, end1, begin2, init, binary_function1, binary_function2);
partial_sum (begin, end, result); partial_sum (begin, end, result, binary_function);
adjacent_difference (begin, end, result); adjacent_difference (begin, end, result, binary_function);
Computes differences of adjacent elements.
// [ 1 2 3 4 ] partial_sum (begin, end, begin); // [ 1 3 6 10 ] adjacent_difference (begin, end, begin); // [ 1 2 3 4 ]
Often a call to an algorithms could be replaced with a simple loop.
iterator i = find (c.begin(), c.end(), value); // is the same as iterator i; for ( i=c.begin(); i!=c.end(); ++i ) { if (*i==value) break; }
Algorithms have several advantages over loops:
Sometimes a loop may be clearer. For example, to replace
iterator i; for ( i=begin; i!=end; ++i ) { if ( x<*i && *i<y ) break; }
with find_if there are several possibilities:
Use bind from TR1/Boost:
iterator i; i = find_if (begin, end, bind(logical_and<bool>(), bind(less<int>(), x, _1), bind(less<int>(), _1, y)));
which looks confusing.
Write a separate functor:
struct between_values : unary_function<int,bool> { between_values(int x, int y) : lo(x), hi(y) {} bool operator() (int n) const { lo<n && n<hi; } private: int lo; int hi; }; // ... iterator i; i = find_if (begin, end, between_values(x,y));
which moves the details away from the call point.
Use boost::lambda
iterator i; i = find_if (begin, end, x<_1 && _1<y);
which uses a non-standard library and an exotic technique (expression templates) that may confuse some.
The standard containers do not contain member functions for operations that can be implemented just as well using standard algorithms:
The member functions that exist are there for a reason: