18
ALGORITHMS

And that’s really the essence of programming. By the time you’ve sorted out a complicated idea into little steps that even a stupidmachine can deal with, you’ve learned something about it yourself.
—Douglas Adams, Dirk Gently’s Holistic Detective Agency

An algorithm is a procedure for solving a class of problems. The stdlib and Boost libraries contain a multitude of algorithms that you can use in your programs. Because many very smart people have put a lot of time into ensuring these algorithms are correct and efficient, you should usually not attempt to, for example, write your own sorting algorithm.

Because this chapter covers almost the entire stdlib algorithm suite, it’s lengthy; however, the individual algorithm presentations are succinct. On first reading, you should skim through each section to survey the wide range of algorithms available to you. Don’t try to memorize them. Instead, focus on getting insight into the kinds of problems you can solve with them as you write code in the future. That way, when you need to use an algorithm, you can say, “Wait, didn’t someone already invent this wheel?”

Before you begin working with the algorithms, you’ll need some grounding in complexity and parallelism. These two algorithmic characteristics are the main drivers behind how your code will perform.

Algorithmic Complexity

Algorithmic complexity describes the difficulty of a computational task. One way to quantify this complexity is with Bachmann-Landau or “Big O” notation. Big O notation characterizes functions according to how computation grows with respect to the size of input. This notation only includes the leading term of the complexity function. The leading term is the one that grows most quickly as input size increases.

For example, an algorithm whose complexity increases by roughly a fixed amount for each additional input element has a Big O notation of O(N), whereas an algorithm whose complexity doesn’t change given additional input has a Big O notation of O(1).

This chapter characterizes the stdlib’s algorithms that fall into five complexity classes, as outlined in the list that follows. To give you some idea of how these algorithms scale, each class is listed with its Big O notation and an idea of roughly how many additional operations would be required due to the leading term when input increases from 1,000 elements to 10,000 elements. Each example provides an operation with the given complexity class, where N is the number of elements involved in the operation:

Constant time O(1) No additional computation. An example is determining the size of a std::vector.

Logarithmic time O(log N) About one additional computation. An example is finding an element in a std::set.

Linear time O(N) About 9,000 additional computations. An example is summing all the elements in a collection.

Quasilinear time O(N log N) About 37,000 additional computations. An example is quicksort, a commonly used sorting algorithm.

Polynomial (or quadratic) time O(N²) About 99,000,000 additional computations. An example is comparing all the elements in a collection with all the elements in another collection.

An entire field of computer science is dedicated to classifying computational problems according to their difficulty, so this is an involved topic. This chapter mentions each algorithm’s complexity according to how the size of the target sequence affects the amount of required work. In practice, you should profile performance to determine whether an algorithm has suitable scaling properties. But these complexity classes can give you a sense of how expensive a particular algorithm is.

Execution Policies

Some algorithms, those that are commonly called parallel algorithms, can divide an algorithm so that independent entities can work on different parts of the problem simultaneously. Many stdlib algorithms allow you to specify parallelism with an execution policy. An execution policy indicates the allowed parallelism for an algorithm. From the stdlib’s perspective, an algorithm can be executed either sequentially or in parallel. A sequential algorithm can have only a single entity working on the problem at a time; a parallel algorithm can have many entities working in concert to resolve the problem.

In addition, parallel algorithms can either be vectorized or non-vectorized. Vectorized algorithms allow entities to perform work in an unspecified order, even allowing a single entity to work on multiple portions of the problem simultaneously. For example, an algorithm that requires synchronization among entities is usually non-vectorizable because the same entity could attempt to acquire a lock multiple times, resulting in a deadlock.

Three execution policies exist in the <execution> header:

• std::execution::seq specifies sequential (not parallel) execution.
• std::execution::par specifies parallel execution.
• std::execution::par_unseq specifies parallel and vectorized execution.

For those algorithms that support an execution policy, the default is seq, meaning you have to opt into parallelism and the associated performance benefits. Note that the C++ Standard doesn’t specify the precise meaning of these execution policies because different platforms handle parallelism differently. When you provide a non-sequential execution policy, you’re simply declaring that “this algorithm is safe to parallelize.”

In Chapter 19, you’ll explore execution policies in greater detail. For now, just note that some algorithms permit parallelism.

#include "catch.hpp"
#include <vector>
#include <string>

using namespace std;

Non-Modifying Sequence Operations

A non-modifying sequence operation is an algorithm that performs computation over a sequence but doesn’t modify the sequence in any way. You can think of these as const algorithms. Each algorithm explained in this section is in the <algorithm> header.

all_of

The all_of algorithm determines whether each element in a sequence meets some user-specified criteria.

The algorithm returns true if the target sequence is empty or if pred is true for all elements in the sequence; otherwise, it returns false.

bool all_of([ep], ipt_begin, ipt_end, pred);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of InputIterator objects, ipt_begin and ipt_end, representing the target sequence
• A unary predicate, pred, that accepts an element from the target sequence

Complexity

Linear The algorithm invokes pred at most distance(ipt_begin, ipt_end) times.

Examples

#include <algorithm>

TEST_CASE("all_of") {
  vector<string> words{ "Auntie", "Anne's", "alligator" }; ➊
  const auto starts_with_a =
    [](const auto& word➋) {
      if (word.empty()) return false; ➌
      return word[0] == 'A' || word[0] == 'a'; ➍
    };
  REQUIRE(all_of(words.cbegin(), words.cend(), starts_with_a)); ➎
  const auto has_length_six = [](const auto& word) {
    return word.length() == 6; ➏
  };
  REQUIRE_FALSE(all_of(words.cbegin(), words.cend(), has_length_six)); ➐
}

After constructing a vector containing string objects called words ➊, you construct the lambda predicate starts_with_a, which takes a single object called word ➋. If word is empty, starts_with_a returns false ➌; otherwise, it returns true if word starts with either a or A ➍. Because all of the word elements start with either a or A, all_of returns true when it applies starts_with_a ➎.

In the second example, you construct the predicate has_length_six, which returns true only if word has length six ➏. Because alligator doesn’t have length six, all_of returns false when it applies has_length_six to words ➐.

any_of

The any_of algorithm determines whether any element in a sequence meets some user-specified criteria.

The algorithm returns false if the target sequence is empty or if pred is true for any element in the sequence; otherwise, it returns false.

bool any_of([ep], ipt_begin, ipt_end, pred);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of InputIterator objects, ipt_begin and ipt_end, representing the target sequence
• A unary predicate, pred, that accepts an element from the target sequence

Complexity

Linear The algorithm invokes pred at most distance(ipt_begin, ipt_end) times.

Examples

#include <algorithm>

TEST_CASE("any_of") {
  vector<string> words{ "Barber", "baby", "bubbles" }; ➊
  const auto contains_bar = [](const auto& word) {
    return word.find("Bar") != string::npos;
  }; ➋
  REQUIRE(any_of(words.cbegin(), words.cend(), contains_bar)); ➌

  const auto is_empty = [](const auto& word) { return word.empty(); }; ➍
  REQUIRE_FALSE(any_of(words.cbegin(), words.cend(), is_empty)); ➎
}

After constructing a vector containing string objects called words ➊, you construct the lambda predicate contains_bar that takes a single object called word ➋. If word contains the substring Bar, it returns true; otherwise, it returns false. Because Barber contains Bar, any_of returns true when it applies contains_bar ➌.

In the second example, you construct the predicate is_empty, which returns true only if a word is empty ➍. Because none of the words are empty, any_of returns false when it applies is_empty to words ➎.

none_of

The none_of algorithm determines whether no element in a sequence meets some user-specified criteria.

The algorithm returns true if the target sequence is empty or if pred is true for no element in the sequence; otherwise, it returns false.

bool none_of([ep], ipt_begin, ipt_end, pred);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of InputIterator objects, ipt_begin and ipt_end, representing the target sequence
• A unary predicate, pred, that accepts an element from the target sequence

Complexity

Linear The algorithm invokes pred at most distance(ipt_begin, ipt_end) times.

Examples

#include <algorithm>

TEST_CASE("none_of") {
  vector<string> words{ "Camel", "on", "the", "ceiling" }; ➊
  const auto is_hump_day = [](const auto& word) {
    return word == "hump day";
  }; ➋
  REQUIRE(none_of(words.cbegin(), words.cend(), is_hump_day)); ➌

  const auto is_definite_article = [](const auto& word) {
    return word == "the" || word == "ye";
  }; ➍
  REQUIRE_FALSE(none_of(words.cbegin(), words.cend(), is_definite_article)); ➎
}

After constructing a vector containing string objects called words ➊, you construct the lambda predicate is_hump_day that takes a single object called word ➋. If word equals hump day, it returns true; otherwise, it returns false. Because words doesn’t contain hump day, none_of returns true when it applies is_hump_day ➌.

In the second example, you construct the predicate is_definite_article, which returns true only if word is a definite article ➍. Because the is a definite article, none_of returns false when it applies is_definite_article to words ➎.

for_each

The for_each algorithm applies some user-defined function to each element in a sequence.

The algorithm applies fn to each element of the target sequence. Although for_each is considered a non-modifying sequence operation, if ipt_begin is a mutable iterator, fn can accept a non-const argument. Any values that fn returns are ignored.

If you omit ep, for_each will return fn. Otherwise, for_each returns void.

for_each([ep], ipt_begin, ipt_end, fn);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of InputIterator objects, ipt_begin and ipt_end, representing the target sequence
• A unary function, fn, that accepts an element from the target sequence

Complexity

Linear The algorithm invokes fn exactly distance(ipt_begin, ipt_end) times.

Additional Requirements

• fn must be movable if you omit ep.
• fn must be copyable if you provide ep.

Example

#include <algorithm>

TEST_CASE("for_each") {
  vector<string> words{ "David", "Donald", "Doo" }; ➊
  size_t number_of_Ds{}; ➋
  const auto count_Ds = [&number_of_Ds➌](const auto& word➍) {
    if (word.empty()) return; ➎
    if (word[0] == 'D') ++number_of_Ds; ➏
  };
  for_each(words.cbegin(), words.cend(), count_Ds); ➐
  REQUIRE(3 == number_of_Ds); ➑
}

After constructing a vector containing string objects called words ➊ and a counter variable number_of_Ds ➋, you construct the lambda predicate count_Ds that captures a reference to number_of_Ds ➌ and takes a single object called word ➍. If word is empty, you return ➎; otherwise, if the first letter of word is D, you increment number_of_Ds ➏.

Next, you use for_each to iterate over every word, passing each to count_Ds ➐. The result is that number_of_Ds is three ➑.

for_each_n

The for_each_n algorithm applies some user-defined function to each element in a sequence.

The algorithm applies fn to each element of the target sequence. Although for_each_n is considered a non-modifying sequence operation, if ipt_begin is a mutable iterator, fn can accept a non-const argument. Any values that fn returns are ignored. It returns ipt_begin+n.

InputIterator for_each_n([ep], ipt_begin, n, fn);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• An InputIterator ipt_begin representing the target sequence’s first element
• An integer n representing the desired number of iterations so that the half-open range representing the target sequence is ipt_begin to ipt_begin+n (Size is the templated type of n.)
• A unary function fn that accepts an element from the target sequence

Complexity

Linear The algorithm invokes fn exactly n times.

Additional Requirements

• fn must be movable if you omit ep.
• fn must copyable if you provide ep.
• n must be non-negative.

Example

#include <algorithm>

TEST_CASE("for_each_n") {
  vector<string> words{ "ear", "egg", "elephant" }; ➊
  size_t characters{}; ➋
  const auto count_characters = [&characters➌](const auto& word➍) {
    characters += word.size(); ➎
  };
  for_each_n(words.cbegin(), words.size(), count_characters); ➏
  REQUIRE(14 == characters); ➐
}}

After constructing a vector containing string objects called words ➊ and a counter variable characters ➋, you construct the lambda predicate count_characters that captures a reference to characters ➌ and takes a single object called word ➍. The lambda adds the length of word to characters ➎.

Next, you use for_each_n to iterate over every word, passing each to count_characters ➏. The result is that characters is 14 ➐.

find, find_if, and find_if_not

The find, find_if, and find_if_not algorithms find the first element in a sequence matching some user-defined criteria.

These algorithms return the InputIterator pointing to the target sequence’s first element matching value (find), resulting in a true result when invoked with pred (find_if), or resulting in a false result when invoked with pred (find_if_not).

If the algorithm finds no match, it returns ipt_end.

InputIterator find([ep], ipt_begin, ipt_end, value);
InputIterator find_if([ep], ipt_begin, ipt_end, pred);
InputIterator find_if_not([ep], ipt_begin, ipt_end, pred);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of InputIterator objects, ipt_begin and ipt_end, representing the target sequence
• A const reference value that is equality comparable to the target sequence’s underlying type (find) or a predicate that accepts a single argument with the target sequence’s underlying type (find_if and find_if_not)

Complexity

Linear The algorithm makes at most distance(ipt_begin, ipt_end) comparisons (find) or invocations of pred (find_if and find_if_not).

Examples

#include <algorithm>

TEST_CASE("find find_if find_if_not") {
  vector<string> words{ "fiffer", "feffer", "feff" }; ➊
  const auto find_result = find(words.cbegin(), words.cend(), "feff"); ➋
  REQUIRE(*find_result == words.back()); ➌

  const auto defends_digital_privacy = [](const auto& word) {
    return string::npos != word.find("eff"); ➍
  };

  const auto find_if_result = find_if(words.cbegin(), words.cend(),
                                      defends_digital_privacy); ➎
  REQUIRE(*find_if_result == "feffer"); ➏

  const auto find_if_not_result = find_if_not(words.cbegin(), words.cend(),
                                              defends_digital_privacy); ➐
  REQUIRE(*find_if_not_result == words.front()); ➑
}

After constructing a vector containing string objects called words ➊, you use find to locate feff ➋, which is at the end of words ➌. Next, you construct the predicate defends_digital_privacy, which returns true if word contains the letters eff ➍. You then use find_if to locate the first string in words that contains eff ➎, feffer ➏. Finally, you use find_if_not to apply defends_digital_privacy to words ➐, which returns the first element fiffer (because it doesn’t contain eff) ➑.

find_end

The find_end algorithm finds the last occurrence of a subsequence.

If the algorithm finds no such sequence, it returns fwd_end1. If find_end does find a subsequence, it returns a ForwardIterator pointing to the first element of the last matching subsequence.

InputIterator find_end([ep], fwd_begin1, fwd_end1,
                       fwd_begin2, fwd_end2, [pred]);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• Two pairs of ForwardIterators, fwd_begin1 / fwd_end1 and fwd_begin2 / fwd_end2, representing the target sequences 1 and 2
• An optional binary predicate pred to compare whether two elements are equal

Complexity

Quadratic The algorithm makes at most the following number of comparisons or invocations of pred:

distance(fwd_begin2, fwd_end2) * (distance(fwd_begin1, fwd_end1) -
                                  distance(fwd_begin2, fwd_end2) + 1)

Examples

#include <algorithm>

TEST_CASE("find_end") {
  vector<string> words1{ "Goat", "girl", "googoo", "goggles" }; ➊
  vector<string> words2{ "girl", "googoo" }; ➋
  const auto find_end_result1 = find_end(words1.cbegin(), words1.cend(),
                                         words2.cbegin(), words2.cend()); ➌
  REQUIRE(*find_end_result1 == words1[1]); ➍

  const auto has_length = [](const auto& word, const auto& len) {
    return word.length() == len; ➎
  };
  vector<size_t> sizes{ 4, 6 }; ➏
  const auto find_end_result2 = find_end(words1.cbegin(), words1.cend(),
                                         sizes.cbegin(), sizes.cend(),
                                         has_length); ➐
  REQUIRE(*find_end_result2 == words1[1]); ➑
}

After constructing a vector containing string objects called words1 ➊ and another called words2 ➋, you invoke find_end to determine which element in words1 begins the subsequence equal to words2 ➌. The result is find_end_result1, which equals the element girl ➍.

Next, you construct the lambda has_length, which takes two arguments, word and len, and returns true if word.length() equals len ➎. You construct a vector of size_t objects called sizes ➏ and invoke find_end with words1, sizes, and has_length ➐. The result, find_end_result2, points to the first element in words1 that has length 4 with the subsequent word having length 6. Because girl has length 4 and googoo has length 6, find_end_result2 points to girl ➑.

find_first

The find_first_of algorithm finds the first occurrence in sequence 1 equal to some element in sequence 2.

If you provide pred, the algorithm finds the first occurrence i in sequence 1 where, for some j in sequence 2, pred (i, j) is true.

If find_first_of finds no such sequence, it returns ipt_end1. If find_first_of does find a subsequence, it returns an InputIterator pointing to the first element of the first matching subsequence. (Note that if ipt_begin1 is also a ForwardIterator, find_first_of instead returns a ForwardIterator.)

InputIterator find_first_of([ep], ipt_begin1, ipt_end1,
                            fwd_begin2, fwd_end2, [pred]);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of InputIterator objects, ipt_begin1 / ipt_end1, representing the target sequence 1
• A pair of ForwardIterators, fwd_begin2 / fwd_end2, representing the target sequence 2
• An optional binary predicate, pred, to compare whether two elements are equal

Complexity

Quadratic The algorithm makes at most the following number of comparisons or invocations of pred:

distance(ipt_begin1, ipt_end1) * distance(fwd_begin2, fwd_end2)

Example

#include <algorithm>

TEST_CASE("find_first_of") {
  vector<string> words{ "Hen", "in", "a", "hat" }; ➊
  vector<string> indefinite_articles{ "a", "an" }; ➋
  const auto find_first_of_result = find_first_of(words.cbegin(),
                                                  words.cend(),
                                                  indefinite_articles.cbegin(),
                                                  indefinite_articles.cend()); ➌
  REQUIRE(*find_first_of_result == words[2]); ➍
}

After constructing a vector containing string objects called words ➊ and another called indefinite_articles ➋, you invoke find_first_of to determine which element in words begins the subsequence equal to indefinite_articles ➌. The result is find_first_of_result, which equals the element a ➍.

adjacent_find

The adjacent_find algorithm finds the first repeat in a sequence.

The algorithm finds the first occurrence in the target sequence where two adjacent elements are equal or where, if you provide pred, the algorithm finds the first occurrence element i in the sequence where pred (i, i+1) is true.

If adjacent_find finds no such element, it returns fwd_end. If adjacent_find does find such an element, it returns a ForwardIterator pointing to it.

ForwardIterator adjacent_find([ep], fwd_begin, fwd_end, [pred]);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of ForwardIterators, fwd_begin / fwd_end, representing the target sequence
• An optional binary predicate pred to compare whether two elements are equal

Complexity

Linear When no execution policy is given, the algorithm makes at most the following number of comparisons or invocations of pred:

 min(distance(fwd_begin, i)+1, distance(fwd_begin, fwd_end)-1)

where i is the index of the return value.

Example

#include <algorithm>
TEST_CASE("adjacent_find") {
  vector<string> words{ "Icabod", "is", "itchy" }; ➊
  const auto first_letters_match = [](const auto& word1, const auto& word2) { ➋
    if (word1.empty() || word2.empty()) return false;
    return word1.front() == word2.front();
  };
  const auto adjacent_find_result = adjacent_find(words.cbegin(), words.cend(),
                                                  first_letters_match); ➌
  REQUIRE(*adjacent_find_result == words[1]); ➍
}

After constructing a vector containing string objects called words ➊, you construct a lambda called first_letters_match, which takes two words and evaluates whether they start with the first letter ➋. You invoke adjacent_find to determine which element has the same first letter as the subsequent letter ➌. The result, adjacent_find_result ➍, equals is because it shares a first letter with itchy ➍.

count

The count algorithm counts the elements in a sequence matching some user-defined criteria.

The algorithm returns the number of elements i in the target sequence where pred (i) is true or where value == i. Usually, DifferenceType is size_t, but it depends on the implementation of InputIterator. You use count when you want to count the occurrences of a particular value, and you use count_if when you have a more complicated predicate you want to use for comparison.

DifferenceType count([ep], ipt_begin, ipt_end, value);
DifferenceType count_if([ep], ipt_begin, ipt_end, pred);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of InputIterator objects, ipt_begin / ipt_end, representing the target sequence
• Either a value or a unary predicate pred to evaluate whether an element x in the target sequence should be counted

Complexity

Linear When no execution policy is given, the algorithm makes distance (ipt_begin, ipt_end) comparisons or invocations of pred.

Examples

#include <algorithm>
TEST_CASE("count") {
  vector<string> words{ "jelly", "jar", "and", "jam" }; ➊
  const auto n_ands = count(words.cbegin(), words.cend(), "and"); ➋
  REQUIRE(n_ands == 1); ➌

  const auto contains_a = [](const auto& word) { ➍
    return word.find('a') != string::npos;
  };
  const auto count_if_result = count_if(words.cbegin(), words.cend(),
                                        contains_a); ➎
  REQUIRE(count_if_result == 3); ➏
}

After constructing a vector containing string objects called words ➊, you use it to invoke count with the value and ➋. This returns 1, because a single element equals and ➌. Next, you construct a lambda called contains_a, which takes a word and evaluates whether it contains a ➍. You invoke count_if to determine how many words contain a ➎. The result equals 3 because three elements contain a ➏.

mismatch

The mismatch algorithm finds the first mismatch in two sequences.

The algorithm finds the first mismatched element pair i, j from sequence 1 and sequence 2. Specifically, it finds the first index n such that i = (ipt_begin1 + n); j = (ipt_begin2 + n); and i != j or pred(i, j) == false.

The types of the iterators in the returned pair equal the types of ipt_begin1 and ipt_begin2.

pair<Itr, Itr> mismatch([ep], ipt_begin1, ipt_end1,
                        ipt_begin2, [ipt_end2], [pred]);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq).
• Two pairs of InputIterators, ipt_begin1 / ipt_end1 and ipt_begin2 / ipt_end2, representing the target sequences 1 and 2. If you don’t provide ipt_end2, sequence 1’s length implies sequence 2’s length.
• An optional binary predicate pred to compare whether two elements are equal.

Complexity

Linear When no execution policy is given, at worst the algorithm makes the following number of comparisons or invocations of pred:

min(distance(ipt_begin1, ipt_end1), distance(ipt_begin2, ipt_end2))

Examples

#include <algorithm>

TEST_CASE("mismatch") {
  vector<string> words1{ "Kitten", "Kangaroo", "Kick" }; ➊
  vector<string> words2{ "Kitten", "bandicoot", "roundhouse" }; ➋
  const auto mismatch_result1 = mismatch(words1.cbegin(), words1.cend(),
                                         words2.cbegin()); ➌
  REQUIRE(*mismatch_result1.first == "Kangaroo"); ➍

  REQUIRE(*mismatch_result1.second == "bandicoot"); ➎
  const auto second_letter_matches = [](const auto& word1,
                                        const auto& word2) { ➏
    if (word1.size() < 2) return false;
    if (word2.size() < 2) return false;
    return word1[1] == word2[1];
  };
  const auto mismatch_result2 = mismatch(words1.cbegin(), words1.cend(),
                                     words2.cbegin(), second_letter_matches); ➐
  REQUIRE(*mismatch_result2.first == "Kick"); ➑
  REQUIRE(*mismatch_result2.second == "roundhouse"); ➒
}

After constructing two vectors of strings called words1 ➊ and words2 ➋, you use them as the target sequences for mismatch ➌. This returns a pair pointing to the elements Kangaroo and bandicoot ➍ ➎. Next, you construct a lambda called second_letter_matches, which takes two words and evaluates whether their second letters match ➏. You invoke mismatch to determine the first pair of elements with mismatched second letters ➐. The result is the pair Kick ➑ and roundhouse ➒.

equal

The equal algorithm determines whether two sequences are equal.

The algorithm determines whether sequence 1’s elements equal sequence 2’s.

bool equal([ep], ipt_begin1, ipt_end1, ipt_begin2, [ipt_end2], [pred]);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq) .
• Two pairs of InputIterators, ipt_begin1 / ipt_end1 and ipt_begin2 / ipt_end2, representing the target sequences 1 and 2. If you don’t provide ipt_end2, sequence 1’s length implies sequence 2’s length.
• An optional binary predicate pred to compare whether two elements are equal.

Complexity

Linear When no execution policy is given, at worst the algorithm makes the following number of comparisons or invocations of pred:

min(distance(ipt_begin1, ipt_end1), distance(ipt_begin2, ipt_end2))

Examples

#include <algorithm>

TEST_CASE("equal") {
  vector<string> words1{ "Lazy", "lion", "licks" }; ➊
  vector<string> words2{ "Lazy", "lion", "kicks" }; ➋
  const auto equal_result1 = equal(words1.cbegin(), words1.cend(),
                                    words2.cbegin()); ➌
  REQUIRE_FALSE(equal_result1); ➍

  words2[2] = words1[2]; ➎
  const auto equal_result2 = equal(words1.cbegin(), words1.cend(),
                                    words2.cbegin()); ➏
  REQUIRE(equal_result2); ➐
}

After constructing two vectors of strings called words1 and words2 ➊ ➋, you use them as the target sequences for equal ➌. Because their last elements, lick and kick, aren’t equal, equal_result1 is false ➍. After setting the third element of words2 to the third element of words1 ➎, you again invoke equal with the same arguments ➏. Because the sequences are now identical, equal_result2 is true ➐.

is_permutation

The is_permutation algorithm determines whether two sequences are permutations, meaning they contain the same elements but potentially in a different order.

The algorithm determines whether some permutation of sequence 2 exists such that sequence 1’s elements equal the permutation’s.

bool is_permutation([ep], fwd_begin1, fwd_end1, fwd_begin2, [fwd_end2], [pred]);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq) .
• Two pairs of ForwardIterators, fwd_begin1 / fwd_end1 and fwd_begin2 / fwd_end2, representing the target sequences 1 and 2. If you don’t provide fwd_end2, sequence 1’s length implies sequence 2’s length.
• An optional binary predicate pred to compare whether two elements are equal.

Complexity

Quadratic When no execution policy is given, at worst the algorithm makes the following number of comparisons or invocations of pred:

distance(fwd_begin1, fwd_end1) * distance(fwd_begin2, fwd_end2)

Example

#include <algorithm>

TEST_CASE("is_permutation") {
  vector<string> words1{ "moonlight", "mighty", "nice" }; ➊
  vector<string> words2{ "nice", "moonlight", "mighty" }; ➋
  const auto result = is_permutation(words1.cbegin(), words1.cend(),
                                     words2.cbegin()); ➌
  REQUIRE(result); ➍
}

After constructing two vectors of strings called words1 and words2 ➊ ➋, you use them as the target sequences for is_permutation ➌. Because words2 is a permutation of words1, is_permutation returns true ➍.

search

The search algorithm locates a subsequence.

The algorithm locates sequence 2 within sequence 1. In other words, it returns the first iterator i in sequence 1 such that for each non-negative integer n, *(i + n) equals *(ipt_begin2 + n), or if you provide a predicate pred(*(i + n), *(ipt_begin2 + n)) is true. The search algorithm returns ipt_begin1 if sequence 2 is empty or ipt_begin2 if no subsequence is found. This is different from find because it locates a subsequence rather than a single element.

ForwardIterator search([ep], fwd_begin1, fwd_end1,
                             fwd_begin2, fwd_end2, [pred]);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• Two pairs of ForwardIterators, fwd_begin1 / fwd_end1 and fwd_begin2 / fwd_end2, representing the target sequences 1 and 2
• An optional binary predicate pred to compare whether two elements are equal

Complexity

Quadratic When no execution policy is given, at worst the algorithm makes the following number of comparisons or invocations of pred:

distance(fwd_begin1, fwd_end1) * distance(fwd_begin2, fwd_end2)

Examples

#include <algorithm>

TEST_CASE("search") {
  vector<string> words1{ "Nine", "new", "neckties", "and",
                         "a", "nightshirt" }; ➊
  vector<string> words2{ "and", "a", "nightshirt" }; ➋
  const auto search_result_1 = search(words1.cbegin(), words1.cend(),
                                      words2.cbegin(), words2.cend()); ➌
  REQUIRE(*search_result_1 == "and"); ➍

  vector<string> words3{ "and", "a", "nightpant" }; ➎
  const auto search_result_2 = search(words1.cbegin(), words1.cend(),
                                      words3.cbegin(), words3.cend()); ➏
  REQUIRE(search_result_2 == words1.cend()); ➐
}

After constructing two vectors of strings called words1 ➊ and words2 ➋, you use them as the target sequences for search ➌. Because words2 is a subsequence of words1, search returns an iterator pointing to and ➍. The vector containing string objects words3 ➎ contains the word nightpant instead of nightshirt, so invoking search with it instead of words2 ➏ yields the end iterator of words1 ➐.

search_n

The search_n algorithm locates a subsequence containing identical, consecutive values.

The algorithm searches for count consecutive values in the sequence and returns an iterator pointing to the first value, or it returns fwd_end if no such subsequence is found. This is different from adjacent_find because it locates a subsequence rather than a single element.

ForwardIterator search([ep], fwd_begin, fwd_end, count, value, [pred]);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of ForwardIterators, fwd_begin / fwd_end, representing the target sequence
• An integral count value representing the number of consecutive matches you want to find
• A value representing the element you want to find
• An optional binary predicate pred to compare whether two elements are equal

Complexity

Linear When no execution policy is given, at worst the algorithm makes distance(fwd_begin, fwd_end) comparisons or invocations of pred.

Example

#include <algorithm>

TEST_CASE("search_n") {
  vector<string> words{ "an", "orange", "owl", "owl", "owl", "today" }; ➊
  const auto result = search_n(words.cbegin(), words.cend(), 3, "owl"); ➋
  REQUIRE(result == words.cbegin() + 2); ➌
}

After constructing a vector of strings called words ➊, you use it as the target sequence for search_n ➋. Because words contains three instances of the word owl, it returns an iterator pointing to the first instance ➌.

Mutating Sequence Operations

A mutating sequence operation is an algorithm that performs computation over a sequence and is allowed to modify the sequence in some way. Each algorithm explained in this section is in the <algorithm> header.

copy

The copy algorithm copies one sequence into another.

The algorithm copies the target sequence into result and returns the receiving sequence’s end iterator. It’s your responsibility to ensure that result represents a sequence with enough space to store the target sequence.

OutputIterator copy([ep], ipt_begin, ipt_end, result);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of InputIterator objects, ipt_begin and ipt_end, representing the target sequence
• An OutputIterator, result, that receives the copied sequence

Complexity

Linear The algorithm copies elements from the target sequence exactly distance(ipt_begin, ipt_end) times.

Additional Requirements

Sequences 1 and 2 must not overlap unless the operation is a copy to the left. For example, for a vector v with 10 elements, std::copy(v.begin()+3, v.end(), v.begin()) is well defined, but std::copy(v.begin(), v.begin()+7, v.begin()+3) is not.

Example

#include <algorithm>

TEST_CASE("copy") {
  vector<string> words1{ "and", "prosper" }; ➊
  vector<string> words2{ "Live", "long" }; ➋
  copy(words1.cbegin(), words1.cend(), ➌
       back_inserter(words2)➍);
  REQUIRE(words2 == vector<string>{ "Live", "long", "and", "prosper" }); ➎
}

After constructing two vectors of string objects ➊ ➋, you invoke copy with words1 as the sequence to copy ➌ and words2 as the destination sequence ➍. The result is that words2 contains the contents of words1 appended to the original contents ➎.

copy_n

The copy_n algorithm copies one sequence into another.

The algorithm copies the target sequence into result and returns the receiving sequence’s end iterator. It’s your responsibility to ensure that result represents a sequence with enough space to store the target sequence and that n represents the correct length of the target sequence.

OutputIterator copy_n([ep], ipt_begin, n, result);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A begin iterator, ipt_begin, representing the beginning of the target sequence
• The size of the target sequence, n
• An OutputIterator result that receives the copied sequence

Complexity

Linear The algorithm copies elements from the target sequence exactly distance(ipt_begin, ipt_end) times.

Additional Requirements

Sequences 1 and 2 must not contain the same objects unless the operation is a copy to the left.

Example

#include <algorithm>

TEST_CASE("copy_n") {
  vector<string> words1{ "on", "the", "wind" }; ➊
  vector<string> words2{ "I'm", "a", "leaf" }; ➋
  copy_n(words1.cbegin(), words1.size(), ➌
         back_inserter(words2)); ➍
  REQUIRE(words2 == vector<string>{ "I'm", "a", "leaf",
                                    "on", "the", "wind" }); ➎
}

After constructing two vectors of string objects ➊➋, you invoke copy_n with words1 as the sequence to copy_n ➌ and words2 as the destination sequence ➍. The result is that words2 contains the contents of words1 appended to the original contents ➎.

copy_backward

The copy_backward algorithm copies the reverse of one sequence into another.

The algorithm copies sequence 1 into sequence 2 and returns the receiving sequence’s end iterator. Elements copy backward but will appear in the target sequence in the original order. It’s your responsibility to ensure that sequence 1 represents a sequence with enough space to store sequence 2.

OutputIterator copy_backward([ep], ipt_begin1, ipt_end1, ipt_end2);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of InputIterator objects, ipt_begin1 and ipt_end1, representing sequence 1
• An InputIterator, ipt_end2, representing 1 past the end of sequence 2

Complexity

Linear The algorithm copies elements from the target sequence exactly distance(ipt_begin1, ipt_end1) times.

Additional Requirements

Sequences 1 and 2 must not overlap.

Example

#include <algorithm>

TEST_CASE("copy_backward") {
  vector<string> words1{ "A", "man", "a", "plan", "a", "bran", "muffin" }; ➊
  vector<string> words2{ "a", "canal", "Panama" }; ➋
  const auto result = copy_backward(words2.cbegin(), words2.cend(), ➌
                                    words1.end()); ➍
  REQUIRE(words1 == vector<string>{ "A", "man", "a", "plan",
                                    "a", "canal", "Panama" }); ➎
}

After constructing two vectors of strings ➊ ➋, you invoke copy_backward with words2 as the sequence to copy ➌ and words1 as the destination sequence ➍. The result is that the contents of word2 replace the last three words of words1 ➎.

move

The move algorithm moves one sequence into another.

The algorithm moves the target sequence and returns the receiving sequence’s end iterator. It’s your responsibility to ensure that the target sequence represents a sequence with at least as many elements as the source sequence.

OutputIterator move([ep], ipt_begin, ipt_end, result);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of InputIterator objects, ipt_begin and ipt_end, representing the target sequence
• An InputIterator, result, representing the beginning of the sequence to move into

Complexity

Linear The algorithm moves elements from the target sequence exactly distance(ipt_begin, ipt_end) times.

Additional Requirements

• Sequences must not overlap unless moving to the left.
• Types must be moveable but not necessarily copyable.

Example

#include <algorithm>

struct MoveDetector { ➊
  MoveDetector() : owner{ true } {} ➋
  MoveDetector(const MoveDetector&) = delete;
  MoveDetector& operator=(const MoveDetector&) = delete;
  MoveDetector(MoveDetector&& o) = delete;
  MoveDetector& operator=(MoveDetector&&) { ➌
    o.owner = false;
    owner = true;
    return *this;
  }
  bool owner;
};

TEST_CASE("move") {
  vector<MoveDetector> detectors1(2); ➍
  vector<MoveDetector> detectors2(2); ➎
  move(detectors1.begin(), detectors1.end(), detectors2.begin()); ➏
  REQUIRE_FALSE(detectors1[0].owner); ➐
  REQUIRE_FALSE(detectors1[1].owner); ➑
  REQUIRE(detectors2[0].owner); ➒
  REQUIRE(detectors2[1].owner); ➓
}

First, you declare the MoveDetector’s class ➊, which defines a default constructor setting its only member owner to true ➋. It deletes the copy and move constructor and the copy assignment operator but defines a move assignment operator that swaps owner ➌.

After constructing two vectors of MoveDetector objects ➍ ➎, you invoke move with detectors1 as the sequence to move and detectors2 as the destination sequence ➏. The result is that the elements of detector1 are in a moved from state ➐➑ and the elements of detector2 are moved into detectors2 ➒➓.

move_backward

The move_backward algorithm moves the reverse of one sequence into another.

The algorithm moves sequence 1 into sequence 2 and returns an iterator pointing to the last moved element. Elements move backward but will appear in the target sequence in the original order. It’s your responsibility to ensure that the target sequence represents a sequence with at least as many elements as the source sequence.

OutputIterator move_backward([ep], ipt_begin, ipt_end, result);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of InputIterator objects, ipt_begin and ipt_end, representing the target sequence
• An InputIterator, result, representing the sequence to move into

Complexity

Linear The algorithm moves elements from the target sequence exactly distance(ipt_begin, ipt_end) times.

Additional Requirements

• Sequences must not overlap.
• Types must be moveable but not necessarily copyable.

Example

#include <algorithm>

struct MoveDetector { ➊
--snip--
};

TEST_CASE("move_backward") {
  vector<MoveDetector> detectors1(2); ➋
  vector<MoveDetector> detectors2(2); ➌
  move_backward(detectors1.begin(), detectors1.end(), detectors2.end()); ➍
  REQUIRE_FALSE(detectors1[0].owner); ➎
  REQUIRE_FALSE(detectors1[1].owner); ➏
  REQUIRE(detectors2[0].owner); ➐
  REQUIRE(detectors2[1].owner); ➑
}

First, you declare the MoveDetector class ➊ (see “move” back on page 595 for the implementation).

After constructing two vectors of MoveDetector objects ➋ ➌, you invoke move with detectors1 as the sequence to move and detectors2 as the destination sequence ➍. The result is that the elements of detector1 are in a moved from state ➎➏ and the elements of detector2 are moved into ➐➑.

swap_ranges

The swap_ranges algorithm exchanges elements from one sequence into another.

The algorithm calls swap on each element of sequence 1 and sequence 2, and it returns the receiving sequence’s end iterator. It’s your responsibility to ensure that the target sequence represents a sequence with at least as many elements as the source sequence.

OutputIterator swap_ranges([ep], ipt_begin1, ipt_end1, ipt_begin2);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of ForwardIterators, ipt_begin1 and ipt_end1, representing sequence 1
• A ForwardIterator, ipt_begin2, representing the beginning of sequence 2

Complexity

Linear The algorithm calls swap exactly distance(ipt_begin1, ipt_end1) times.

Additional Requirements

The elements contained in each sequence must be swappable.

Example

#include <algorithm>

TEST_CASE("swap_ranges") {
  vector<string> words1{ "The", "king", "is", "dead." }; ➊
  vector<string> words2{ "Long", "live", "the", "king." }; ➋
  swap_ranges(words1.begin(), words1.end(), words2.begin()); ➌
  REQUIRE(words1 == vector<string>{ "Long", "live", "the", "king." }); ➍
  REQUIRE(words2 == vector<string>{ "The", "king", "is", "dead." }); ➎
}

After constructing two vectors of strings ➊ ➋, you invoke swap with words1 and words2 as the sequences to swap ➌. The result is that words1 and words2 swap contents ➍ ➎.

transform

The transform algorithm modifies the elements of one sequence and writes them into another.

The algorithm invokes unary_op on each element of the target sequence and outputs it into the output sequence, or it invokes binary_op on corresponding elements of each target sequence.

OutputIterator transform([ep], ipt_begin1, ipt_end1, result, unary_op);
OutputIterator transform([ep], ipt_begin1, ipt_end1, ipt_begin2,
                         result, binary_op);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq).
• A pair of InputIterator objects, ipt_begin1 and ipt_end1, representing the target sequence.
• An optional InputIterator, ipt_begin2, representing a second target sequence. You must ensure that this second target sequence has at least as many elements as the first target sequence.
• An OutputIterator, result, representing the beginning of the output sequence.
• A unary operation, unary_op, that transforms elements of the target sequence into elements of the output sequence. If you supply two target sequences, you instead provide a binary operation, binary_op, which accepts an element from each target sequence and transforms each into an element of the output sequence.

Complexity

Linear The algorithm invokes unary_op or binary_op exactly distance(ipt_begin1, ipt_end1) times.

Examples

#include <algorithm>
#include <boost/algorithm/string/case_conv.hpp>

TEST_CASE("transform") {
  vector<string> words1{ "farewell", "hello", "farewell", "hello" }; ➊
  vector<string> result1;
  auto upper = [](string x) { ➋
    boost::algorithm::to_upper(x);
    return x;
  };
  transform(words1.begin(), words1.end(), back_inserter(result1), upper); ➌
  REQUIRE(result1 == vector<string>{ "FAREWELL", "HELLO",
                                     "FAREWELL", "HELLO" }); ➍

  vector<string> words2{ "light", "human", "bro", "quantum" }; ➎
  vector<string> words3{ "radar", "robot", "pony", "bit" }; ➏
  vector<string> result2;
  auto portmantize = [](const auto &x, const auto &y) { ➐
    const auto x_letters = min(size_t{ 2 }, x.size());
    string result{ x.begin(), x.begin() + x_letters };
    const auto y_letters = min(size_t{ 3 }, y.size());
    result.insert(result.end(), y.end() - y_letters, y.end() );
    return result;
  };
  transform(words2.begin(), words2.end(), words3.begin(),
            back_inserter(result2), portmantize); ➑
  REQUIRE(result2 == vector<string>{ "lidar", "hubot", "brony", "qubit" }); ➒
}

After constructing a vector containing string objects ➊, you construct a lambda called upper, which takes a string by value and converts it to uppercase using the Boost to_upper algorithm discussed in Chapter 15 ➋. You invoke transform with words1 as the target sequence, a back_inserter for an empty results1 vector, and upper as the unary operation ➌. After transform, results1 contains the uppercase version of words1 ➍.

In the second example, you construct two vectors of string objects ➎➏. You also construct a lambda called portmantize that accepts two string objects ➐. The lambda returns a new string containing up to two letters from the beginning of the first argument and up to three letters from the end of the second argument. You pass the two target sequences, a back_inserter to an empty vector called results2 and portmantize ➑. The result2 contains portmanteaus of the contents of words1 and words2 ➒.

replace

The replace algorithm replaces certain elements of a sequence with some new element.

The algorithm searches for target sequence elements x for which either x == old_ref or pred(x) == true and assigns them to new_ref.

void replace([ep], fwd_begin, fwd_end, old_ref, new_ref);
void replace_if([ep], fwd_begin, fwd_end, pred, new_ref);
void replace_copy([ep], fwd_begin, fwd_end, result, old_ref, new_ref);
void replace_copy_if([ep], fwd_begin, fwd_end, result, pred, new_ref);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of ForwardIterators, fwd_begin and fwd_end, representing the target sequence
• An OutputIterator, result, representing the beginning of the output sequence
• An old const reference representing the element to find
• A unary predicate, pred, that determines whether an element meets the criteria for replacement
• A new_ref const reference that represents the element to replace

Complexity

Linear The algorithm invokes pred exactly distance(fwd_begin, fwd_end) times.

Additional Requirements

The elements contained in each sequence must be comparable to old_ref and assignable to new_ref.

Examples

#include <algorithm>
#include <string_view>

TEST_CASE("replace") {
  using namespace std::literals; ➊
  vector<string> words1{ "There", "is", "no", "try" }; ➋
  replace(words1.begin(), words1.end(), "try"sv, "spoon"sv); ➌
  REQUIRE(words1 == vector<string>{ "There", "is", "no", "spoon" }); ➍

  const vector<string> words2{ "There", "is", "no", "spoon" }; ➎
  vector<string> words3{ "There", "is", "no", "spoon" }; ➏
  auto has_two_os = [](const auto& x) { ➐
    return count(x.begin(), x.end(), 'o') == 2;
  };
  replace_copy_if(words2.begin(), words2.end(), words3.begin(), ➑
                  has_two_os, "try"sv);
  REQUIRE(words3 == vector<string>{ "There", "is", "no", "try" }); ➒
}

You first bring in the std::literals namespace ➊ so you can employ the string_view literal later on. After constructing a vector containing string objects ➋, you invoke replace with the vector ➌ to replace all instances of try with spoon ➍.

In the second example, you construct two vectors of string objects ➎➏ and a lambda called has_two_os, which accepts a string and returns true if it contains exactly two os ➐. You then pass words2 as the target sequence and words3 as the destination sequence to replace_copy_if, which applies has_two_os to each element of words2 and replaces elements that evaluate to true with try ➑. The result is that words2 is unaffected and words3 has the element spoon replaced with try ➒.

fill

The fill algorithm fills a sequence with some value.

The algorithm writes a value into each element of the target sequence. The fill_n function returns opt_begin+n.

void fill([ep], fwd_begin, fwd_end, value);
OutputIterator fill_n([ep], opt_begin, n, value);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A ForwardIterator, fwd_begin, representing the target sequence’s beginning
• A ForwardIterator, fwd_end, representing one past the sequence’s end
• A Size n representing the number of elements
• A value to write into each element of the target sequence

Complexity

Linear The algorithm assigns value exactly distance(fwd_begin, fwd_end) or n times.

Additional Requirements

• The value parameter must be writable into the sequence.
• Objects of type Size must be convertible into an integral type.

Examples

#include <algorithm>

// If police police police police, who polices the police police?
TEST_CASE("fill") {
  vector<string> answer1(6); ➊
  fill(answer1.begin(), answer1.end(), "police"); ➋
  REQUIRE(answer1 == vector<string>{ "police", "police", "police",
                                     "police", "police", "police" }); ➌

  vector<string> answer2; ➍
  fill_n(back_inserter(answer2), 6, "police"); ➎
  REQUIRE(answer2 == vector<string>{ "police", "police", "police",
                                     "police", "police", "police" }); ➏
}

You first initialize a vector containing string objects containing six empty elements ➊. Next, you invoke fill using this vector as the target sequence and police as the value ➋. The result is that your vector contains six police ➌.

In the second example, you initialize an empty vector containing string objects ➍. You then invoke fill_n with a back_inserter pointing to the empty vector, a length of 6, and police as the value ➎. The result is the same as before: your vector contains six police ➏.

generate

The generate algorithm fills a sequence by invoking a function object.

The algorithm invokes generator and assigns the result into the target sequence. The generate_n function returns opt_begin+n.

void generate([ep], fwd_begin, fwd_end, generator);
OutputIterator generate_n([ep], opt_begin, n, generator);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A ForwardIterator, fwd_begin, representing the target sequence’s beginning
• A ForwardIterator, fwd_end, representing 1 past the sequence’s end
• A Size n representing the number of elements
• A generator that, when invoked with no arguments, produces an element to write into the target sequence

Complexity

Linear The algorithm invokes generator exactly distance(fwd_begin, fwd_end) or n times.

Additional Requirements

• The value parameter must be writable into the sequence.
• Objects of type Size must be convertible into an integral type.

Examples

#include <algorithm>

TEST_CASE("generate") {
  auto i{ 1 }; ➊
  auto pow_of_2 = [&i]() { ➋
    const auto tmp = i;
    i *= 2;
    return tmp;
  };
  vector<int> series1(6); ➌
  generate(series1.begin(), series1.end(), pow_of_2); ➍
  REQUIRE(series1 == vector<int>{ 1, 2, 4, 8, 16, 32 }); ➎

  vector<int> series2; ➏
  generate_n(back_inserter(series2), 6, pow_of_2); ➐
  REQUIRE(series2 == vector<int>{ 64, 128, 256, 512, 1024, 2048 }); ➑
}

You first initialize an int called i to 1 ➊. Next, you create a lambda called pow_of_2, which takes i by reference ➋. Each time you invoke pow_of_2, it doubles i and returns its value just before the doubling. Next, you initialize a vector of int objects with six elements ➌. You then invoke generate with the vector as the target sequence and pow_of_2 as the generator ➍. The result is that the vector contains the first six powers of two ➎.

In the second example, you initialize an empty vector of int objects ➏. Next, you invoke generate_n using a back_inserter to your empty vector, a size of 6, and pow_of_2 as your generator ➐. The result is the next six powers of two ➑. Notice that pow_of_2 has state because it captures i by reference.

remove

The remove algorithm removes certain elements from a sequence.

The algorithm moves all elements where pred evaluates to true or where the element equals value in such a way that the remaining elements’ order is preserved, and it returns an iterator pointing to the first moved element. This iterator is called the resulting sequence’s logical end. The sequence’s physical size remains unchanged, and a call to remove is typically followed by a call to a container’s erase method.

ForwardIterator remove([ep], fwd_begin, fwd_end, value);
ForwardIterator remove_if([ep], fwd_begin, fwd_end, pred);
ForwardIterator remove_copy([ep], fwd_begin, fwd_end, result, value);
ForwardIterator remove_copy_if([ep], fwd_begin, fwd_end, result, pred);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of ForwardIterators, fwd_begin and fwd_end, representing the target sequence
• An OutputIterator, result, representing the destination sequence (if copying)
• A value representing the element to remove
• A unary predicate, pred, that determines whether an element meets the criteria for removal

Complexity

Linear The algorithm invokes pred or compares with value exactly distance(fwd_begin, fwd_end) times.

Additional Requirements

• The elements of the target sequence must be moveable.
• If copying, the elements must be copyable, and the target and destination sequences must not overlap.

Examples

#include <algorithm>

TEST_CASE("remove") {
  auto is_vowel = [](char x) { ➊
    const static string vowels{ "aeiouAEIOU" };
    return vowels.find(x) != string::npos;
  };
  string pilgrim = "Among the things Billy Pilgrim could not change "
                   "were the past, the present, and the future."; ➋
  const auto new_end = remove_if(pilgrim.begin(), pilgrim.end(), is_vowel); ➌
  REQUIRE(pilgrim == "mng th thngs Blly Plgrm cld nt chng wr th pst, "
                     "th prsnt, nd th ftr.present, and the future."); ➍

  pilgrim.erase(new_end, pilgrim.end()); ➎
  REQUIRE(pilgrim == "mng th thngs Blly Plgrm cld nt chng wr th "
                     "pst, th prsnt, nd th ftr."); ➏
}

You first create a lambda called is_vowel that returns true if the given char is a vowel ➊. Next, you construct a string called pilgrim containing a sentence ➋. You then invoke remove_if with pilgrim as the target sentence and is_vowel as the predicate ➌. This eliminates all the vowels in the sentence by shifting the remaining characters to the left each time remove_if encounters a vowel. The result is that pilgrim contains the original sentence with vowels removed plus the phrase present, and the future. ➍. This phrase contains 24 characters, which is exactly the number of vowels that remove_if removed from the original sentence. The phrase present, and the future. is the detritus from shifting the remaining string during removal.

To eliminate these leftovers, you save the iterator new_end, which remove_if returns. This points to 1 past the last character in the new target sequence, the p in present, and the future. To eliminate, you simply use the erase method on pilgrim, which has an overload that accepts a half-open range. You pass the logical end returned by remove_if, new_end, as the begin iterator. You also pass pilgrim.end() as the end iterator ➎. The result is that pilgrim is now equal to the original sentence with vowels removed ➏.

This combination of remove (or remove_if) and the erase method, which is called the erase-remove idiom, is widely used.

unique

The unique algorithm removes redundant elements from a sequence.

The algorithm moves all repeat elements where pred evaluates to true or where the elements are equal such that the remaining elements are unique from their neighbors and original ordering is preserved. It returns an iterator pointing to the new logical end. As with std::remove, the physical storage doesn’t change.

ForwardIterator unique([ep], fwd_begin, fwd_end, [pred]);
ForwardIterator unique_copy([ep], fwd_begin, fwd_end, result, [pred]);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of ForwardIterators, fwd_begin and fwd_end, representing the target sequence
• An OutputIterator, result, representing the destination sequence (if copying)
• A binary predicate, pred, that determines whether two elements are equal

Complexity

Linear The algorithm invokes pred exactly distance(fwd_begin, fwd_end) - 1 times.

Additional Requirements

• The elements of the target sequence must be moveable.
• If copying, elements of the target sequence must by copyable, and the target and destination ranges cannot overlap.

Example

#include <algorithm>

TEST_CASE("unique") {
  string without_walls = "Wallless"; ➊
  const auto new_end = unique(without_walls.begin(), without_walls.end()); ➋
  without_walls.erase(new_end, without_walls.end()); ➌
  REQUIRE(without_walls == "Wales"); ➍
}

You first construct a string containing a word with multiple repeated characters ➊. You then invoke unique with the string as the target sequence ➋. This returns the logical end, which you assign to new_end. Next, you erase the range beginning with new_end and ending with without_walls.end() ➌. This is a corollary to the erase-remove idiom: you’re left with the contents Wales, which contains consecutively unique characters ➍.

reverse

The reverse algorithm reverses the order of a sequence.

The algorithm reverses a sequence by either swapping its elements or copying them into a target sequence.

void reverse([ep], bi_begin, bi_end);
OutputIterator reverse_copy([ep], bi_begin, bi_end, result);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of BidirectionalIterators, bi_begin and bi_end, representing the target sequence
• An OutputIterator, result, representing the destination sequence (if copying)

Complexity

Linear The algorithm invokes swap exactly distance(bi_begin, bi_end)/2 times.

Additional Requirements

• The elements of the target sequence must be swappable.
• If copying, elements of the target sequence must by copyable, and the target and destination ranges cannot overlap.

Example

#include <algorithm>

TEST_CASE("reverse") {
  string stinky = "diaper"; ➊
  reverse(stinky.begin(), stinky.end()); ➋
  REQUIRE(stinky == "repaid"); ➌
}

You first construct a string containing the word diaper ➊. Next, you invoke reverse with this string as the target sequence ➋. The result is the word repaid ➌.

sample

The sample algorithm generates random, stable subsequences.

The algorithm samples min(pop_end - pop_begin, n) elements from the population sequence. Somewhat unintuitively, the sample will be sorted if and only if ipt_begin is a forward iterator. It returns the resulting destination sequence’s end.

OutputIterator sample([ep], ipt_begin, ipt_end, result, n, urb_generator);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of InputIterator objects, ipt_begin and ipt_end, representing the population sequence (the sequence to sample from)
• A OutputIterator, result, representing the destination sequence
• A Distance n representing the number of elements to sample
• A UniformRandomBitGenerator urb_generator, such as the Mersenne Twister std::mt19937_64 introduced in Chapter 12

Complexity

Linear The algorithm’s complexity scales with distance(ipt_begin, ipt_end).

Example

#include <algorithm>
#include <map>
#include <string>
#include <iostream>
#include <iomanip>
#include <random>

using namespace std;

const string population = "ABCD"; ➊
const size_t n_samples{ 1'000'000 }; ➋
mt19937_64 urbg; ➌

void sample_length(size_t n) { ➍
  cout << "-- Length " << n << " --
";
  map<string, size_t> counts; ➎
  for (size_t i{}; i < n_samples; i++) {
    string result;
    sample(population.begin(), population.end(),
           back_inserter(counts), n, urbg); ➏
    counts[result]++;
  }
  for (const auto[sample, n] : counts) { ➐
    const auto percentage = 100 * n / static_cast<double>(n_samples);
    cout << percentage << " '" << sample << "'
"; ➑
  }
}

int main() {
  cout << fixed << setprecision(1); ➒
  sample_length(0); ➓
  sample_length(1);
  sample_length(2);
  sample_length(3);
  sample_length(4);
}
-----------------------------------------------------------------------
-- Length 0 --
100.0 ''
-- Length 1 --
25.1 'A'
25.0 'B'
25.0 'C'
24.9 'D'
-- Length 2 --
16.7 'AB'
16.7 'AC'
16.6 'AD'
16.6 'BC'
16.7 'BD'
16.7 'CD'
-- Length 3 --
25.0 'ABC'
25.0 'ABD'
25.0 'ACD'
25.0 'BCD'
-- Length 4 --
100.0 'ABCD'

You first construct a const string called population containing the letters ABCD ➊. You also initialize a const size_t called n_samples equal to a million ➋ and a Mersenne Twister called urbg ➌. All of these objects have static storage duration.

In addition, you initialize the function sample_length, which takes a single size_t argument called n ➍. Within the function, you construct a map of string to size_t objects ➎ that will count the frequency of each sample invocation. Within a for loop, you invoke sample with population as the population sequence, a back_inserter to a result string as the destination sequence, n as the sample length, and urbg as the random bit generator ➏.

After a million iterations, you iterate over each element of counts ➐ and print the probability distribution of each sample for the given length n ➑.

Within main, you configure floating-point formatting with fixed and setprecision ➒. Finally, you invoke sample_length with each value from 0 to 4 inclusive ➓.

Because string provides random access iterators, sample provides stable (sorted) samples.

shuffle

The shuffle algorithm generates random permutations.

The algorithm randomizes the target sequence such that each possible permutation of those elements has equal probability of appearance.

void shuffle(rnd_begin, rnd_end, urb_generator);

Arguments

• A pair of RandomAccessIterators, rnd_begin and rnd_end, representing the target sequence
• A UniformRandomBitGenerator urb_generator, such as the Mersenne Twister std::mt19937_64 introduced in Chapter 12

Complexity

Linear The algorithm swaps exactly distance(rnd_begin, rnd_end) - 1 times.

Additional Requirements

The elements of the target sequence must be swappable.

Example

#include <algorithm>
#include <map>
#include <string>
#include <iostream>
#include <random>
#include <iomanip>

using namespace std;

int main() {
  const string population = "ABCD"; ➊
  const size_t n_samples{ 1'000'000 }; ➋
  mt19937_64 urbg; ➌
  map<string, size_t> samples; ➍
  cout << fixed << setprecision(1); ➎
  for (size_t i{}; i < n_samples; i++) {
    string result{ population }; ➏
    shuffle(result.begin(), result.end(), urbg); ➐
    samples[result]++; ➑
  }
  for (const auto[sample, n] : samples) { ➒
    const auto percentage = 100 * n / static_cast<double>(n_samples);
    cout << percentage << " '" << sample << "'
"; ➓
  }
}
-----------------------------------------------------------------------
4.2 'ABCD'
4.2 'ABDC'
4.1 'ACBD'
4.2 'ACDB'
4.2 'ADBC'
4.2 'ADCB'
4.2 'BACD'
4.2 'BADC'
4.1 'BCAD'
4.2 'BCDA'
4.1 'BDAC'
4.2 'BDCA'
4.2 'CABD'
4.2 'CADB'
4.1 'CBAD'
4.1 'CBDA'
4.2 'CDAB'
4.1 'CDBA'
4.2 'DABC'
4.2 'DACB'
4.2 'DBAC'
4.1 'DBCA'
4.2 'DCAB'
4.2 'DCBA'

You first construct a const string called population containing the letters ABCD ➊. You also initialize a const size_t called n_samples equal to a million ➋, a Mersenne Twister called urbg ➌, and a map of string to size_t objects ➍ that will count the frequencies of each shuffle sample. In addition, you configure floating-point formatting with fixed and setprecision ➎.

Within a for loop, you copy population into a new string called sample because shuffle modifies the target sequence ➏. You then invoke shuffle with result as the target sequence and urbg as the random bit generator ➐, and you record the result within samples ➑.

Finally, you iterate over each element in samples ➒ and print the probability distribution of each sample ➓.

Notice that, unlike with sample, shuffle always produces an unordered distribution of elements.

Sorting and Related Operations

A sorting operation is an algorithm that reorders a sequence in some desired way.

Each sorting algorithm has two versions: one that takes a function object called a comparison operator and one that uses operator<. A comparison operator is a function object that is invokable with two objects to compare. It returns true if the first argument is less than the second argument; otherwise, it returns false. The sort interpretation of x < y is that x is sorted before y. All the algorithms explained in this section are in the <algorithm> header.

Comparison operators must be transitive. This means that for any elements a, b, and c the comparison operator comp must preserve the following relationship: if comp(a, b) and comp(b, c), then comp(a, c). This should make sense: if a is ordered before b and b is ordered before c, then a must be ordered before c.

sort

The sort algorithm sorts a sequence (unstably).

The algorithm sorts the target sequence in place.

void sort([ep], rnd_begin, rnd_end, [comp]);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of RandomAccessIterators, rnd_begin and rnd_end, representing the target sequence
• An optional comparison operator, comp

Complexity

Quasilinear O(N log N) where N = distance(rnd_begin, rnd_end)

Additional Requirements

The elements of the target sequence must be swappable, move constructible, and move assignable.

Example

#include <algorithm>

TEST_CASE("sort") {
  string goat_grass{ "spoilage" }; ➊
  sort(goat_grass.begin(), goat_grass.end()); ➋
  REQUIRE(goat_grass == "aegilops"); ➌
}

You first construct a string containing the word spoilage ➊. Next, you invoke sort with this string as the target sequence ➋. The result is that goat_grass now contains the word aegilops (a genus of invasive weeds) ➌.

stable_sort

The stable_sort algorithm sorts a sequence stably.

The algorithm sorts the target sequence in place. Equal elements retain their original ordering.

void stable_sort([ep], rnd_begin, rnd_end, [comp]);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of RandomAccessIterators, rnd_begin and rnd_end, representing the target sequence
• An optional comparison operator, comp

Complexity

Polylog-linear O(N log² N) where N = distance(rnd_begin, rnd_end). If additional memory is available, complexity reduces to quasilinear.

Additional Requirements

The elements of the target sequence must be swappable, move constructible, and move assignable.

Example

#include <algorithm>

enum class CharCategory { ➊
  Ascender,
  Normal,
  Descender
};

CharCategory categorize(char x) { ➋
  switch (x) {
    case 'g':
    case 'j':
    case 'p':
    case 'q':
    case 'y':
      return CharCategory::Descender;
    case 'b':
    case 'd':
    case 'f':
    case 'h':
    case 'k':
    case 'l':
    case 't':
      return CharCategory::Ascender;
  }
  return CharCategory::Normal;
}

bool ascension_compare(char x, char y) { ➌
  return categorize(x) < categorize(y);
}

TEST_CASE("stable_sort") {
  string word{ "outgrin" }; ➍
  stable_sort(word.begin(), word.end(), ascension_compare); ➎
  REQUIRE(word == "touring"); ➏
}

This example sorts a string using the ascenders and descenders. In typography, an ascender is a letter with a portion that extends above what is known as the mean line of a font. A descender is a letter with a portion that extends below what is known as the baseline. Letters commonly typed with descenders are g, j, p, q, and y. Letters commonly typed with ascenders are b, d, f, h, k, l, and t. This example seeks a stable_sort so that all letters with ascenders appear before all other letters and letters with descenders appear after all other letters. Letters with neither an ascender nor a descender lie in the middle. As a stable_sort, the relative ordering of letters with common ascender/descender categorization must not change.

You first define an enum class called CharCategory that takes on three possible values: Ascender, Normal, or Descender ➊. Next, you define a function that categorizes a given char into a CharCategory ➋. (Recall from “Switch Statements” on page 50 that labels “fall through” if you don’t include a break.) You also define an ascension_compare function that converts two given char objects into CharCategory objects and compares them with operator< ➌. Because enum class objects convert implicitly to int objects and because you define CharCategory with its values in the intended order, this will sort letters with ascenders ahead of normal letters ahead of letters with descenders.

Within the test case, you initialize a string containing the word outgrin ➍. Next, you invoke stable_sort with this string as the target sequence and ascension_compare as the comparison operator ➎. The result is that word now contains touring ➏. Notice that t, the only ascender, appears before all the normal characters (which are in the same order as in outgrin), which appear before g, the only descender.

partial_sort

The partial_sort algorithm sorts a sequence into two groups.

If modifying, the algorithm sorts the first (rnd_middle – rnd_first) elements in the target sequence so all elements in rnd_begin to rnd_middle are less than the rest of the elements. If copying, the algorithm places the first min(distance(ipt_begin, ipt_end), distance(rnd_begin, rnd_end)) sorted elements into the destination sequence, and it returns an iterator pointing to the end of the destination sequence.

Basically, a partial sort allows you to find the first few elements of a sorted sequence without having to sort the entire sequence. For example, if you had the sequence D C B A, you could partial sort the first two elements and obtain the result A B D C. The first two elements are the same as if you’d sorted the entire sequence, but the remaining elements aren’t.

void partial_sort([ep], rnd_begin, rnd_middle, rnd_end, [comp]);
RandomAccessIterator partial_sort_copy([ep], ipt_begin, ipt_end,
                                       rnd_begin, rnd_end, [comp]);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• If modifying, a trio of RandomAccessIterators, rnd_begin, rnd_middle, and rnd_end, representing the target sequence
• If copying, a pair ipt_begin and ipt_end representing the target sequence and a pair rnd_begin and rnd_end representing the destination sequence
• An optional comparison operator, comp

Complexity

Quasilinear O(N log N) where N = distance(rnd_begin, rnd_end) * log(distance(rnd_begin, rnd_middle) or distance(rnd_begin, rnd_end) * log(min(distance(rnd_begin, rnd_end), distance(ipt_begin, ipt_end)) for the copy variant

Additional Requirements

The elements of the target sequence must be swappable, move constructible, and move assignable.

Examples

#include <algorithm>

bool ascension_compare(char x, char y) {
--snip--
}

TEST_CASE("partial_sort") {
  string word1{ "nectarous" }; ➊
  partial_sort(word1.begin(), word1.begin() + 4, word1.end()); ➋
  REQUIRE(word1 == "acentrous"); ➌

  string word2{ "pretanning" }; ➍
  partial_sort(word2.begin(), word2.begin() + 3, ➎
               word2.end(), ascension_compare);
  REQUIRE(word2 == "trepanning"); ➏
}

You first initialize a string containing the word nectarous ➊. Next, you invoke partial_sort with this string as the target sequence and the fifth letter (a) as the second argument to partial_sort ➋. The result is that the sequence now contains the word acentrous ➌. Notice that the first four letters of acentrous are sorted and that they’re less than the remaining characters in the sequence.

In the second example, you initialize a string containing the word pretanning ➍, which you use as the target sequence for partial_sort ➎. In this example, you specify the fourth character (t) as the second argument to partial_sort, and you use the ascension_compare function from the stable_sort example as the comparison operator. The result is that the sequence now contains the word trepanning ➏. Notice that the first three letters are sorted according to ascension_compare and none of the remaining characters in the second argument to partial_sort to z is less than the first three characters.

is_sorted

The is_sorted algorithm determines whether a sequence is sorted.

The algorithm returns true if the target sequence is sorted according to operator< or comp, if given. The is_sorted_until algorithm returns an iterator pointing to the first unsorted element or rnd_end if the target sequence is sorted.

bool is_sorted([ep], rnd_begin, rnd_end, [comp]);
ForwardIterator is_sorted_until([ep], rnd_begin, rnd_end, [comp]);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of RandomAccessIterators, rnd_begin and rnd_end, representing the target sequence
• An optional comparison operator, comp

Complexity

Linear The algorithm compares distance(rnd_begin, rnd_end) times.

Examples

#include <algorithm>

bool ascension_compare(char x, char y) {
--snip--
}

TEST_CASE("is_sorted") {
  string word1{ "billowy" }; ➊
  REQUIRE(is_sorted(word1.begin(), word1.end())); ➋

  string word2{ "floppy" }; ➌
  REQUIRE(word2.end() == is_sorted_until(word2.begin(), ➍
                                         word2.end(), ascension_compare));
}

You first construct a string containing the word billowy ➊. Next, you invoke is_sort with this string as the target sequence, which returns true ➋.

In the second example, you construct a string containing the word floppy ➌. You then invoke is_sorted_until with this string as the target sequence, which returns rnd_end because the sequence is sorted ➍.

nth_element

The nth_element algorithm places a particular element in a sequence into its correct sorted position.

This partial sorting algorithm modifies the target sequence in the following way: the element in the position pointed to by rnd_nth is in that position as if the whole range were sorted. All elements from rnd_begin to rnd_nth-1 will be less than rnd_nth. If rnd_nth == rnd_end, the function performs no operation.

bool nth_element([ep], rnd_begin, rnd_nth, rnd_end, [comp]);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A trio of RandomAccessIterators, rnd_begin, rnd_nth, and rnd_end, representing the target sequence
• An optional comparison operator, comp

Complexity

Linear The algorithm compares distance(rnd_begin, rnd_end) times.

Additional Requirements

The elements of the target sequence must be swappable, move constructible, and move assignable.

Example

#include <algorithm>

TEST_CASE("nth_element") {
  vector<int> numbers{ 1, 9, 2, 8, 3, 7, 4, 6, 5 }; ➊
  nth_element(numbers.begin(), numbers.begin() + 5, numbers.end()); ➋
  auto less_than_6th_elem = [&elem=numbers[5]](int x) { ➌
    return x < elem;
  };
  REQUIRE(all_of(numbers.begin(), numbers.begin() + 5, less_than_6th_elem)); ➍
  REQUIRE(numbers[5] == 6 ); ➎
}

You first construct a vector of int objects containing the number sequence 1 to 10 inclusive ➊. Next, you invoke nth_element with this vector as the target sequence ➋. You then initialize a lambda named less_than_6th_elem, which compares an int with the sixth element of numbers with operator< ➌. This allows you to check that all elements before the sixth element are less than the sixth element ➍. The sixth element is 6 ➎.

Binary Search

Binary search algorithms assume that a target sequence is already sorted. These algorithms have desirable complexity characteristics compared with generic search over an unspecified sequence. Each algorithm explained in this section is in the <algorithm> header.

lower_bound

The lower_bound algorithm finds a partition in a sorted sequence.

The algorithm returns an iterator corresponding to the element result, which partitions the sequence so the elements before result are less than value, whereas result and all elements after it aren’t less than value.

ForwardIterator lower_bound(fwd_begin, fwd_end, value, [comp]);

Arguments

• A pair of ForwardIterators, fwd_begin and fwd_end, representing the target sequence
• A value to partition the target sequence with
• An optional comparison operator, comp

Complexity

Logarithmic If you provide a random iterator, O(log N) where N = distance (fwd_begin, fwd_end); otherwise, O(N)

Additional Requirements

The target sequence must be sorted according to operator< or comp if provided.

Example

#include <algorithm>

TEST_CASE("lower_bound") {
  vector<int> numbers{ 2, 4, 5, 6, 6, 9 }; ➊
  const auto result = lower_bound(numbers.begin(), numbers.end(), 5); ➋
  REQUIRE(result == numbers.begin() + 2); ➌
}

You first construct a vector of int objects ➊. Next, you invoke lower_bound with this vector as the target sequence and a value of 5 ➋. The result is the third element, 5 ➌. The elements 2 and 4 are less than 5, whereas the elements 5, 6, 6, and 9 are not.

upper_bound

The upper_bound algorithm finds a partition in a sorted sequence.

The algorithm returns an iterator corresponding to the element result, which is the first element in the target sequence greater than value.

ForwardIterator upper_bound(fwd_begin, fwd_end, value, [comp]);

Arguments

• A pair of ForwardIterators, fwd_begin and fwd_end, representing the target sequence
• A value to partition the target sequence with
• An optional comparison operator, comp

Complexity

Logarithmic If you provide a random iterator, O(log N) where N = distance (fwd_begin, fwd_end); otherwise, O(N)

Additional Requirements

The target sequence must be sorted according to operator< or comp if provided.

Example

#include <algorithm>

TEST_CASE("upper_bound") {
  vector<int> numbers{ 2, 4, 5, 6, 6, 9 }; ➊
  const auto result = upper_bound(numbers.begin(), numbers.end(), 5); ➋
  REQUIRE(result == numbers.begin() + 3); ➌
}

You first construct a vector of int objects ➊. Next, you invoke upper_bound with this vector as the target sequence and a value of 5 ➋. The result is the fourth element, 6, which is the first element in the target sequence greater than value ➌.

equal_range

The equal_range algorithm finds a range of certain elements in a sorted sequence.

The algorithm returns a std::pair of iterators corresponding to the half-open range equal to value.

ForwardIteratorPair equal_range(fwd_begin, fwd_end, value, [comp]);

Arguments

• A pair of ForwardIterators, fwd_begin and fwd_end, representing the target sequence
• A value to seek
• An optional comparison operator, comp

Complexity

Logarithmic If you provide a random iterator, O(log N) where N = distance (fwd_begin, fwd_end); otherwise, O(N)

Additional Requirements

The target sequence must be sorted according to operator< or comp if provided.

Example

#include <algorithm>

TEST_CASE("equal_range") {
  vector<int> numbers{ 2, 4, 5, 6, 6, 9 }; ➊
  const auto[rbeg, rend] = equal_range(numbers.begin(), numbers.end(), 6); ➋
  REQUIRE(rbeg == numbers.begin() + 3); ➌
  REQUIRE(rend == numbers.begin() + 5); ➍
}

You first construct a vector of int objects ➊. Next, you invoke equal_range with this vector as the target sequence and a value of 6 ➋. The result is an iterator pair representing the matching range. The begin iterator points to the fourth element ➌, and the second iterator points to the sixth element ➍.

binary_search

The binary_search algorithm finds a particular element in a sorted sequence.

The algorithm returns true if the range contains value. Specifically, it returns true if the target sequence contains an element x such that neither x < value nor value < x. If comp is provided, it returns true if the target sequence contains an element x such that neither comp(x, value) nor comp(value, x).

bool binary_search(fwd_begin, fwd_end, value, [comp]);

Arguments

• A pair of ForwardIterators, fwd_begin and fwd_end, representing the target sequence
• A value to seek
• An optional comparison operator, comp

Complexity

Logarithmic If you provide a random iterator, O(log N) where N = distance (fwd_begin, fwd_end); otherwise, O(N)

Additional Requirements

The target sequence must be sorted according to operator< or comp if provided.

Example

#include <algorithm>

TEST_CASE("binary_search") {
  vector<int> numbers{ 2, 4, 5, 6, 6, 9 }; ➊
  REQUIRE(binary_search(numbers.begin(), numbers.end(), 6)); ➋
  REQUIRE_FALSE(binary_search(numbers.begin(), numbers.end(), 7)); ➌
}

You first construct a vector of int objects ➊. Next, you invoke binary_search with this vector as the target sequence and a value of 6. Because the sequence contains 6, binary_search returns true ➋. When you invoke binary_search with 7, it returns false because the target sequence doesn’t contain 7 ➌.

Partitioning Algorithms

A partitioned sequence contains two contiguous, distinct groups of elements. These groups don’t mix, and the first element of the second distinct group is called the partition point. The stdlib contains algorithms to partition sequences, determine whether a sequence is partitioned, and find partition points. Each algorithm explained in this section is in the <algorithm> header.

is_partitioned

The is_partitioned algorithm determines whether a sequence is partitioned.

The algorithm returns true if every element in the target sequence for which pred evaluates to true appears before the other elements.

bool is_partitioned([ep], ipt_begin, ipt_end, pred);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of InputIterator objects, ipt_begin and ipt_end, representing the target sequence
• A predicate, pred, that determines group membership

Complexity

Linear At most distance(ipt_begin, ipt_end) evaluations of pred

Examples

#include <algorithm>

TEST_CASE("is_partitioned") {
  auto is_odd = [](auto x) { return x % 2 == 1; }; ➊

  vector<int> numbers1{ 9, 5, 9, 6, 4, 2 }; ➋
  REQUIRE(is_partitioned(numbers1.begin(), numbers1.end(), is_odd)); ➌

  vector<int> numbers2{ 9, 4, 9, 6, 4, 2 }; ➍
  REQUIRE_FALSE(is_partitioned(numbers2.begin(), numbers2.end(), is_odd)); ➎
}

You first construct a lambda called is_odd, which returns true if the given number is odd ➊. Next, you construct a vector of int objects ➋ and invoke is_partitioned with this vector as the target sequence and is_odd as the predicate. Because the sequence contains all its odd numbers placed before its even numbers, is_partitioned returns true ➌.

You then construct another vector of int objects ➍ and again invoke is_partitioned with this vector as the target sequence and is_odd as the predicate. Because the sequence doesn’t contain all its odd numbers placed before its even numbers (4 is even and before the second 9), is_partitioned returns false ➎.

partition

The partition algorithm partitions a sequence.

The algorithm mutates the target sequence so it’s partitioned according to pred. It returns the partition point. The elements’ original ordering isn’t necessarily preserved.

ForwardIterator partition([ep], fwd_begin, fwd_end, pred);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of ForwardIterators, fwd_begin and fwd_end, representing the target sequence
• A predicate, pred, that determines group membership

Complexity

Linear At most distance(fwd_begin, fwd_end) evaluations of pred

Additional Requirements

The target sequence’s elements must be swappable.

Example

#include <algorithm>

TEST_CASE("partition") {
  auto is_odd = [](auto x) { return x % 2 == 1; }; ➊
  vector<int> numbers{ 1, 2, 3, 4, 5 }; ➋
  const auto partition_point = partition(numbers.begin(),
                                         numbers.end(), is_odd); ➌
  REQUIRE(is_partitioned(numbers.begin(), numbers.end(), is_odd)); ➍
  REQUIRE(partition_point == numbers.begin() + 3); ➎
}

You first construct a lambda called is_odd, which returns true if the given number is odd ➊. Next, you construct a vector of int objects ➋ and invoke partition with this vector as the target sequence and is_odd as the predicate. You assign the resulting partition point into partition_point ➌.

When you invoke is_partitioned on the target sequence with is_odd as the predicate, it returns true ➍. Per the specification of the algorithm, you cannot rely on the ordering within the groups, but the partition_point will always be the fourth element, because the target sequence contains three odd numbers ➎.

partition_copy

The partition_copy algorithm partitions a sequence.

The algorithm partitions the target sequence by evaluating pred on each element. All true elements copy into opt_true, and all false elements copy into opt_false.

ForwardIteratorPair partition_copy([ep], ipt_begin, ipt_end,
                                         opt_true, opt_false, pred);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of InputIterator objects, ipt_begin and ipt_end, representing the target sequence
• An OutputIterator, opt_true, to receive copies of true elements
• An OutputIterator, opt_false, to receive copies of false elements
• A predicate, pred, that determines group membership

Complexity

Linear Exactly distance(ipt_begin, ipt_end) evaluations of pred

Additional Requirements

• The target sequence’s elements must be copy assignable.
• The input and output ranges must not overlap.

Example

#include <algorithm>

TEST_CASE("partition_copy") {
  auto is_odd = [](auto x) { return x % 2 == 1; }; ➊
  vector<int> numbers{ 1, 2, 3, 4, 5 }, odds, evens; ➋
  partition_copy(numbers.begin(), numbers.end(),
                 back_inserter(odds), back_inserter(evens), is_odd); ➌
  REQUIRE(all_of(odds.begin(), odds.end(), is_odd)); ➍
  REQUIRE(none_of(evens.begin(), evens.end(), is_odd)); ➎
}

You first construct a lambda called is_odd, which returns true if the given number is odd ➊. Next, you construct a vector of int objects containing the numbers from 1 to 5 and two empty vector objects called odds and evens ➋. Next, you invoke partition_copy with numbers as the target sequence, a back_inserter to odds as the output for true elements, a back_inserter to evens as the output for false elements, and is_odd as the predicate ➌. The result is that all of the elements in odds are odd ➍ and none of the elements in evens are odd ➎.

stable_partition

The stable_partition algorithm partitions a sequence stably.

The algorithm mutates the target sequence so it’s partitioned according to pred. It returns the partition point. The elements’ original ordering is preserved.

BidirectionalIterator partition([ep], bid_begin, bid_end, pred);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of BidirectionalIterators, bid_begin and bid_end, representing the target sequence
• A predicate, pred, that determines group membership

Complexity

Quasilinear O(N log N) swaps where N = distance(bid_begin, bid_end), or O(N) swaps if sufficient memory is available.

Additional Requirements

The target sequence’s elements must be swappable, move constructible, and move assignable.

Example

#include <algorithm>

TEST_CASE("stable_partition") {
  auto is_odd = [](auto x) { return x % 2 == 1; }; ➊
  vector<int> numbers{ 1, 2, 3, 4, 5 }; ➋
  stable_partition(numbers.begin(), numbers.end(), is_odd); ➌
  REQUIRE(numbers == vector<int>{ 1, 3, 5, 2, 4 }); ➍
}

You first construct a lambda called is_odd, which returns true if the given number is odd ➊. Next, you construct a vector of int objects ➋ and invoke stable_partition with this vector as the target sequence and is_odd as the predicate ➌. The result is that the vector contains the elements 1, 3, 5, 2, 4 because this is the only way to partition these numbers while preserving their original within-group order ➍.

Merging Algorithms

Merging algorithms merge two sorted target sequences such that the resulting sequence contains copies of both target sequences and is also sorted. Each algorithm explained in this section is in the <algorithm> header.

merge

The merge algorithm merges two sorted sequences.

The algorithm copies both target sequences into the destination sequence. The destination sequence is sorted according to operator< or comp if provided.

OutputIterator merge([ep], ipt_begin1, ipt_end1,
                     ipt_begin2, ipt_end2, opt_result, [comp]);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• Two pairs of InputIterators, ipt_begin and ipt_end, representing the target sequences
• An OutputIterator, opt_result, representing the destination sequence
• A predicate, pred, that determines group membership

Complexity

Linear At most N-1 comparisons where N = distance(ipt_begin1, ipt_end1) + distance(ipt_begin2, ipt_end2)

Additional Requirements

The target sequences must be sorted according to operator< or comp if provided.

Example

#include <algorithm>

TEST_CASE("merge") {
  vector<int> numbers1{ 1, 4, 5 }, numbers2{ 2, 3, 3, 6 }, result; ➊
  merge(numbers1.begin(), numbers1.end(),
        numbers2.begin(), numbers2.end(),
        back_inserter(result)); ➋
  REQUIRE(result == vector<int>{ 1, 2, 3, 3, 4, 5, 6 }); ➌
}

You construct three vector objects: two containing sorted int objects and another that is empty ➊. Next, you merge the non-empty vector and use the empty vector as the destination sequence via a back_inserter ➋. The result contains copies of all the elements from the original sequences, and it too is sorted ➌.

Extreme-Value Algorithms

Several algorithms, called extreme-value algorithms, determine minimum and maximum elements or place limits on the minimum or maximum value of an element. Each algorithm explained in this section is in the <algorithm> header.

min and max

The min or max algorithm determines a sequence’s extrema.

The algorithms use operator< or comp and return the minimum (min) or maximum (max) object. The minmax algorithm returns both as a std::pair with first as the minimum and second as the maximum.

T min(obj1, obj2, [comp]);
T min(init_list, [comp]);
T max(obj1, obj2, [comp]);
T max(init_list, [comp]);
Pair minmax(obj1, obj2, [comp]);
Pair minmax(init_list, [comp]);

Arguments

• Two objects, obj1 and obj2, or
• An initializer list, init_list, representing the objects to compare
• An optional comparison function, comp

Complexity

Constant or Linear For the overloads taking obj1 and obj2, exactly one comparison. For the initializer list, at most N-1 comparisons where N is the length of the initializer list. In the case of minmax, given an initializer list, this grows to 3/2 N.

Additional Requirements

The elements must be copy constructible and comparable using the given comparison.

Examples

#include <algorithm>

TEST_CASE("max and min") {
  using namespace std::literals;
  auto length_compare = [](const auto& x1, const auto& x2) { ➊
    return x1.length() < x2.length();
  };

  REQUIRE(min("undiscriminativeness"s, "vermin"s,
              length_compare) == "vermin"); ➋

  REQUIRE(max("maxim"s, "ultramaximal"s,
              length_compare) == "ultramaximal"); ➌

  const auto result = minmax("minimaxes"s, "maximin"s, length_compare); ➍
  REQUIRE(result.first == "maximin"); ➎
  REQUIRE(result.second == "minimaxes"); ➏
}

You first initialize a lambda called length_compare, which uses operator< to compare the lengths of two inputs ➊. Next, you use min to determine whether undiscriminativeness or vermin has lesser length ➋, and you use max to determine whether maxim or ultramaximal has greater length ➌. Finally, you use minmax to determine which of minimaxes and maximin has minimum and maximum length ➍. The result is a pair ➎➏.

min_element and max_element

The min_element or max_element algorithm determines a sequence’s extrema.

The algorithms use operator< or comp and return an iterator pointing to the minimum (min_element) or maximum (max_element) object. The minimax_element algorithm returns both as a std::pair with first as the minimum and second as the maximum.

ForwardIterator min_element([ep], fwd_begin, fwd_end, [comp]);
ForwardIterator max_element([ep], fwd_begin, fwd_end, [comp]);
Pair minmax_element([ep], fwd_begin, fwd_end, [comp]);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of ForwardIterators, fwd_begin and fwd_end, representing the target sequence
• An optional comparison function, comp

Complexity

Linear For max and min, at most N-1 comparisons where N=distance(fwd_begin, fwd_end); for minmax, 3/2 N

Additional Requirements

The elements must be comparable using the given operation.

Examples

#include <algorithm>

TEST_CASE("min and max element") {
  auto length_compare = [](const auto& x1, const auto& x2) { ➊
    return x1.length() < x2.length();
  };

  vector<string> words{ "civic", "deed", "kayak",  "malayalam" }; ➋

  REQUIRE(*min_element(words.begin(), words.end(),
                       length_compare) == "deed"); ➌
  REQUIRE(*max_element(words.begin(), words.end(),
                       length_compare) == "malayalam"); ➍

  const auto result = minmax_element(words.begin(), words.end(),
                                     length_compare); ➎
  REQUIRE(*result.first == "deed"); ➏
  REQUIRE(*result.second == "malayalam"); ➐
}

You first initialize a lambda called length_compare, which uses operator< to compare the lengths of two inputs ➊. Next, you initialize a vector of string objects called words containing four words ➋. You use min_element to determine the smallest of these words by passing it as the target sequence and length_compare as the comparison function (deed) ➌, and you use max_element to determine the largest (malayalam) ➍. Finally, you use minmax_element, which returns both as a std::pair ➎. The first element refers to the shortest word ➏, and second refers to the longest ➐.

clamp

The clamp algorithm bounds a value.

The algorithm uses operator< or comp to determine whether obj is inside the bounds from low to high. If it is, the algorithm simply returns obj; otherwise, if obj is less than low, it returns low. If obj is greater than high, it returns high.

T& clamp(obj, low, high, [comp]);

Arguments

• An object, obj
• A low and high object
• An optional comparison function, comp

Complexity

Constant At most two comparisons

Additional Requirements

The objects must be comparable using the given operation.

Examples

#include <algorithm>

TEST_CASE("clamp") {
  REQUIRE(clamp(9000, 0, 100) == 100); ➊
  REQUIRE(clamp(-123, 0, 100) == 0); ➋
  REQUIRE(clamp(3.14, 0., 100.) == Approx(3.14)); ➌
}

In the first example, you clamp 9000 to the interval from 0 to 100 inclusive. Because 9,000 > 100, the result is 100 ➊. In the second example, you clamp -123 to the same interval. Because −123 < 0, the result is 0 ➋. Finally, you clamp 3.14 and because it’s within the interval, the result is 3.14 ➌.

Numeric Operations

The <numeric> header was discussed in Chapter 12 when you learned about its mathematical types and functions. It also provides algorithms well suited to numeric operations. This section introduces many of them. Each algorithm explained in this section is in the <numeric> header.

Useful Operators

Some stdlib numeric operations permit you to pass an operator to customize behavior. For convenience, the <functional> header provides the following class templates that expose various binary arithmetic operations through operator(T x, T y):

• plus<T> implements addition x + y.
• minus<T> implements subtraction x - y.
• multiplies<T> implements multiplication x * y.
• divides<T> implements division x / y.
• modulus<T> implements addition x % y.

For example, you could add two numbers using the plus template, like this:

#include <functional>

TEST_CASE("plus") {
  plus<short> adder; ➊
  REQUIRE(3 == adder(1, 2)); ➋
  REQUIRE(3 == plus<short>{}(1,2)); ➌
}

You first instantiate a plus called adder ➊, and then you invoke it with the values 1 and 2, which yields 3 ➋. You can also skip the variable entirely and simply use a newly constructed plus directly to achieve the same result ➌.

iota

The iota algorithm fills a sequence with incremental values.

The algorithm assigns incremental values beginning with start to the target sequence.

void iota(fwd_begin, fwd_end, start);

Arguments

• A pair of iterators, fwd_begin and fwd_end, representing the target sequence
• A start value

Complexity

Linear N increments and assignments, where N=distance(fwd_begin, fwd_end)

Additional Requirements

The objects must be assignable to start.

Example

#include <numeric>
#include <array>

TEST_CASE("iota") {
  array<int, 3> easy_as; ➊
  iota(easy_as.begin(), easy_as.end(), 1); ➋
  REQUIRE(easy_as == array<int, 3>{ 1, 2, 3 }); ➌
}

You first initialize an array of int objects with length 3 ➊. Next, you invoke iota with the array as the target sequence and 1 as the start value ➋. The result is that array contains the elements 1, 2, and 3 ➌.

accumulate

The accumulate algorithm folds a sequence (in order).

The algorithm applies op to start and the target sequence’s first element. It takes the result and the target sequence’s next element and again applies op, proceeding in this fashion until it visits each element in the target sequence. Loosely, this algorithm adds the target sequence elements and the start value, and it returns the result.

T accumulate(ipt_begin, ipt_end, start, [op]);

Arguments

• A pair of iterators, ipt_begin and ipt_end, representing the target sequence
• A start value
• An optional binary operator, op, that defaults to plus

Complexity

Linear N applications of op, where N=distance(ipt_begin, ipt_end)

Additional Requirements

The target sequence’s elements must be copyable.

Examples

#include <numeric>

TEST_CASE("accumulate") {
  vector<int> nums{ 1, 2, 3 }; ➊
  const auto result1 = accumulate(nums.begin(), nums.end(), -1); ➋
  REQUIRE(result1 == 5); ➌

  const auto result2 = accumulate(nums.begin(), nums.end(),
                                  2, multiplies<>()); ➍
  REQUIRE(result2 == 12); ➎
}

You first initialize a vector of int objects with length 3 ➊. Next, you invoke accumulate with the vector as the target sequence and -1 as the start value ➋. The result is −1 + 1 + 2 + 3 = 5 ➌.

In the second example, you use the same target sequence but a start value of 2 and the multiplies operator instead ➍. The result is 2 * 1 * 2 * 3 = 12 ➎.

reduce

The reduce algorithm folds a sequence (not necessarily in order).

The algorithm is identical to accumulate except it accepts an optional execution and doesn’t guarantee the order of operator applications.

T reduce([ep], ipt_begin, ipt_end, start, [op]);

Arguments

• An optional std::execution execution policy, ep (default: std::execution::seq)
• A pair of iterators, ipt_begin and ipt_end, representing the target sequence
• A start value
• An optional binary operator, op, that defaults to plus

Complexity

Linear N applications of op, where N=distance(ipt_begin, ipt_end)

Additional Requirements

• Elements must be movable if you omit ep.
• Elements must copyable if you provide ep.

Examples

#include <numeric>

TEST_CASE("reduce") {
  vector<int> nums{ 1, 2, 3 }; ➊
  const auto result1 = reduce(nums.begin(), nums.end(), -1); ➋
  REQUIRE(result1 == 5); ➌

  const auto result2 = reduce(nums.begin(), nums.end(),
                                  2, multiplies<>()); ➍
  REQUIRE(result2 == 12); ➎
}

You first initialize a vector of int objects with length 3 ➊. Next, you invoke reduce with the vector as the target sequence and -1 as the start value ➋. The result is −1 + 1 + 2 + 3 = 5 ➌.

In the second example, you use the same target sequence but a start value of 2 and the multiplies operator instead ➍. The result is 2 * 1 * 2 * 3 = 12 ➎.

inner_product

The inner_product algorithm computes the inner product of two sequences.

The algorithm applies op2 to each pair of corresponding elements in the target sequence and sums them together with start using op1.

T inner_product([ep], ipt_begin1, ipt_end1, ipt_begin2, start, [op1], [op2]);

Arguments

• A pair of iterators, ipt_begin1 and ipt_end1, representing target sequence 1
• An iterator, ipt_begin2, representing target sequence 2
• A start value
• Two optional binary operators, op1 and op2, that default to plus and multiply

Complexity

Linear N applications of op1 and op2, where N=distance(ipt_begin1, ipt_end1)

Additional Requirements

Elements must be copyable.

Example

#include <numeric>

TEST_CASE("inner_product") {
  vector<int> nums1{ 1, 2, 3, 4, 5 }; ➊
  vector<int> nums2{ 1, 0,-1, 0, 1 }; ➋
  const auto result = inner_product(nums1.begin(), nums1.end(),
                                    nums2.begin(), 10); ➌
  REQUIRE(result == 13); ➍
}

You first initialize two vectors of int objects ➊ ➋. Next, you invoke inner_product with the two vector objects as the target sequences and 10 as the start value ➌. The result is 10 + 1 * 1 + 2 * 0 + 3 * 1 + 4 * 0 + 4 * 1 = 13 ➍.

adjacent_difference

The adjacent_difference algorithm generates adjacent differences.

The algorithm sets the first element of the destination sequence equal to the first element of the target sequence. For each subsequent element, it applies op to the prior element and the current element and writes the return value into result. The algorithm returns the end of the destination sequence.

OutputIterator adjacent_difference([ep], ipt_begin, ipt_end, result, [op]);

Arguments

• A pair of iterators, ipt_begin and ipt_end, representing target sequence
• An iterator, result, representing the destination sequence
• An optional binary operator, op, that defaults to minus

Complexity

Linear N-1 applications of op, where N=distance(ipt_begin, ipt_end)

Additional Requirements

• Elements must be movable if you omit ep.
• Elements must copyable if you provide ep.

Example

#include <numeric>

TEST_CASE("adjacent_difference") {
  vector<int> fib{ 1, 1, 2, 3, 5, 8 }, fib_diff; ➊
  adjacent_difference(fib.begin(), fib.end(), back_inserter(fib_diff)); ➋
  REQUIRE(fib_diff == vector<int>{ 1, 0, 1, 1, 2, 3 }); ➌
}

You first two initialize a vector of int objects, one containing the first six numbers of the Fibonacci sequence and another that is empty ➊. Next, you invoke adjacent_difference with the two vector objects as the target sequences ➋. The result is as expected: the first element equals the first element of the Fibonacci sequence, and the following elements are the adjacent differences (1 – 1 = 0), (2 – 1 = 1), (3 – 2 = 1), (5 – 3 = 2), (8 – 5 = 3) ➌.

partial_sum

The partial_sum algorithm generates partial sums.

The algorithm sets an accumulator equal to the first element of the target sequence. For each subsequent element of the target sequence, the algorithm adds that element to the accumulator and then writes the accumulator into the destination sequence. The algorithm returns the end of the destination sequence.

OutputIterator partial_sum(ipt_begin, ipt_end, result, [op]);

Arguments

• A pair of iterators, ipt_begin and ipt_end, representing the target sequence
• An iterator, result, representing the destination sequence
• An optional binary operator, op, that defaults to plus

Complexity

Linear N-1 applications of op, where N=distance(ipt_begin, ipt_end)

Example

#include <numeric>

TEST_CASE("partial_sum") {
  vector<int> num{ 1, 2, 3, 4 }, result; ➊
  partial_sum(num.begin(), num.end(), back_inserter(result)); ➋
  REQUIRE(result == vector<int>{ 1, 3, 6, 10 }); ➌
}

You first initialize two vector of int objects, one called num containing the first four counting and an empty one called result ➊. Next, you invoke partial_sum with num as the target sequence and result as the destination ➋. The first element equals the first element of the target sequence, and the following elements are the partial sums (1 + 2 = 3), (3 + 3 = 6), (6 + 4 = 10) ➌.

Other Algorithms

To keep a long chapter from getting much longer, many algorithms are omitted. This section provides a survey of them.

(Max) Heap Operations

A range of length N is a max heap if for all 0 < i < N, the -th element (rounded down) doesn’t compare less than the i-th element. These structures have strong performance properties in situations where maximum element lookup and insertions must be fast.

The <algorithm> header contains functions that are useful for handling such ranges, such as those in Table 18-1. See [alg.heap.operations] for details.

Table 18-1: Heap-Related Algorithms in the <algorithm> Header

Set Operations on Sorted Ranges

The <algorithm> header contains functions that perform set operations on sorted ranges, such as those in Table 18-2. See [alg.set.operations] for details.

Table 18-2: Set-Related Algorithms in the <algorithm> Header

Other Numeric Algorithms

The <numeric> header contains several more functions in addition to those introduced in the “Numeric Operations” section. Table 18-3 lists them. See [numeric.ops] for details.

Table 18-3: Additional Numerical Algorithms in the <numeric> Header

Memory Operations

The <memory> header contains a number of low-level functions for handling uninitialized memory. Table 18-4 lists them. See [memory.syn] for details.

Table 18-4: Operations for Uninitialized Memory in the <memory> Header

Boost Algorithm

Boost Algorithm is a large algorithm library that overlaps partially with the standard library. For space reasons, Table 18-5 lists only a quick reference to those algorithms not already contained in the standard library. Refer to the Boost Algorithm documentation for further information.

Table 18-5: Additional Algorithms Available in Boost Algorithm