STL Algorithms

Contents

Except for the numeric algorithms, all algorithms are declared in the header <algorithm>

Non-range algorithms

Most STL algorithms operate on iterator ranges. These are the exceptions.

swap (x, y);
iter_swap (p, q);
min (x, y);
min (x, y, binary_predicate);
max (x, y);
max (x, y, binary_predicate);

Sequential search

The STL algorithms below search a range for some element or a subrange.

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);
min_element(begin, end);
min_element(begin, end, order_comparison);
max_element(begin, end);
max_element(begin, end, order_comparison);

Comparing ranges

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);

General iteration

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());

Copying

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);

Replacing elements

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);

Filling ranges

fill (begin, end, value);
fill_n (begin, n, value);

A generalization of fill uses a generator (nullary functor) instead of a fixed value.

generate (begin, end, generator);
generate_n (begin, n, generator);

Removing elements

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);

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);

Partitioning

partition (begin, end, predicate);
stable_partition (begin, end, predicate);
partition.png

Permuting elements

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);

Sorting

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);

Merging

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);

Heap operations

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);

Binary search

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

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.

Numeric Algorithms

The following algorithms are defined in the header <numeric>.

accumulate (begin, end, init);
accumulate (begin, end, init, binary_functor);
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);

Algorithms vs. Loops

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:

Algorithms vs. Member Functions

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: