The previous chapter discusses the containers provided by the Standard Library to store data. Orthogonally to these, the library offers numerous algorithms to process this or other data. Algorithms are independent of containers: they do their work solely based on iterators and can therefore be executed on any range of elements as long as suitable iterators are provided.
This chapter starts with a brief definition of input/output iterators, followed by a detailed overview of all available algorithms organized by functionality. The chapter ends with a discussion of iterator adaptors.
Input and Output Iterators
The previous chapter
briefly explains the different categories of iterators offered by containers: forward, bidirectional, and random access. Two more iterator categories are used in the context of algorithms, which have fewer requirements compared to the other three. Essentially:
- Input iterator: Must be dereferenceable to read elements. Other than that, only the ++, ==, and != operators are required.
- Output iterator: Only ++ operators are required, but you must be able to write elements to them after dereferencing.
For both, it also suffices that they provide single-pass access. That is, once incremented, they may in principle invalidate all previous copies of them. Two corresponding iterator tags, as discussed in Chapter 3, are provided for these categories as well: std::input_iterator_tag and output_iterator_tag.
All iterators returned by the standard containers, as well as pointers into C-style arrays, are valid input iterators. They are valid output iterators as well, as long as they do not point to const elements.
Algorithms <algorithm>
This section gives an overview of all available algorithms, organized into subsections according to functionality. All algorithms are defined in the <algorithm> header file unless otherwise noted.
Terminology
The following terms and abbreviations are used for types in the definitions
of algorithms:
- Function: Callable—that is, lambda expression, function object, or function pointer.
- InIt, OutIt, FwIt, BidIt, RanIt: Input, output, forward, bidirectional, or random-access iterator.
- UnaOp, BinOp: Unary or binary operation—that is, a callable accepting one resp. two arguments.
- UnaPred, BinPred: Unary or binary predicate, with a predicate being an operation that returns a Boolean.
- Size: A type representing a size—for example, a number of elements.
- DiffType: A type representing a distance between two iterators.
- T: An element type.
- Compare: A function object to be used to compare elements. If not specified, operator< is used. The function object accepts two parameters and returns true if the first argument is less than the second, false otherwise. The ordering imposed must be a strict weak ordering, just as with the default operator<.
Algorithms often accept a callable as one of their parameters: for example, a unary or binary operation or predicate. This callable can be a lambda expression, a function object, or a function pointer. Lambda expressions and function objects are discussed in Chapter 2.
General Guidelines
First, whenever possible, use standard algorithms instead of self-written loops, because they are often more efficient and are far less error-prone. Also, and especially after the introduction of lambda expressions
, the use of algorithms mostly results in far shorter, readable, self-explanatory code.
Second, for several algorithms, certain containers offer equivalent specialized member functions (see Chapter 3). These are more efficient and should therefore be preferred over the generic algorithms. In the algorithm descriptions that follow, we always list these alternatives.
Finally, many of the algorithms move or swap elements. If no implicit or explicit move and/or swap functions are available, these algorithms fall back to copying elements. For optimal performance, you should therefore always consider implementing specialized move and/or swap functions for nontrivial custom data types. Types offered by the Standard Library always provide these where appropriate. We refer to Chapter 2 for more information regarding move semantics and swap functions.
Applying a Function on a Range
Function for_each(InIt first, InIt last, Function function)
- Calls the given function for each element in the range [first, last), and returns std::move(function). Note that when iterating over an entire container or C-style array, a range-based for loop is more convenient.
OutIt transform(InIt first1, InIt last1, OutIt target, UnaOp operation)
OutIt transform(InIt1 first1, InIt1 last1, InIt2 first2,
OutIt target, BinOp operation)
- Transforms all elements in a range [first1, last1) and stores the results in a range starting at target, which is allowed to be equal to first1 or first2 to perform an in-place transformation. For the first version, a unary operation is performed on each transformed element. For the second, a binary operation is performed on each transformed element with the corresponding element from the second range. Let length = (last1 - first1), then the binary operation is executed on pairs (*(first1 + n ), *(first2 + n )) with 0 ≤ n < length. Returns the end iterator of the target range, so (target + length ).
Example
The following example uses
transform()
to double all the elements in a vector using a lambda expression, then uses transform() to negate the elements using a standard function object, and finally outputs all the elements to the console using for_each(). This code snippet additionally needs <functional>:
std::vector<int> vec{ 1,2,3,4,5,6 };
std::transform(cbegin(vec), cend(vec), begin(vec),
[](auto& element) { return element * 2; });
std::transform(cbegin(vec), cend(vec), begin(vec), std::negate<>());
std::for_each(cbegin(vec), cend(vec),
[](auto& element) { std::cout << element << " "; });
The output is as follows:
-2 -4 -6 -8 -10 -12
Checking for the Presence of Elements
bool all_of(InIt first, InIt last, UnaPred predicate)
bool none_of(InIt first, InIt last, UnaPred predicate)
bool any_of(InIt first, InIt last, UnaPred predicate)
- Returns true if all, none, or respectively at least one of the elements in the range [first, last) satisfies a unary predicate. If the range is empty, all_of() and none_of() return true, and any_of() returns false.
DiffType count(InIt first, InIt last, const T& value)
DiffType count_if(InIt first, InIt last, UnaPred predicate)
- Returns the number of elements in [first, last) that are equal to a given value, or that satisfy a unary predicate.[Alternatives: all ordered and unordered associative containers have a count() member.]
Example
The following example demonstrates the use of all_of() to check whether all elements are even:
Finding Elements
InIt find(InIt first, InIt last, const T& value)
InIt find_if(InIt first, InIt last, UnaPred predicate)
InIt find_if_not(InIt first, InIt last, UnaPred predicate)
- Searches all elements in the range [first, last) for the first element that is equal to a value, satisfies a unary predicate, or does not satisfy a predicate. Returns an iterator to the element found, or last if none is found.[Alternatives: all ordered and unordered associative containers have a find() member.]
InIt find_first_of(InIt first1, InIt last1,
FwIt first2, FwIt last2[, BinPred predicate])
- Returns an iterator to the first element in [first1, last1) that is equal to an element in [first2, last2). Returns last1 if no such element is found or if [first2, last2) is empty. If a binary predicate is given, it is used to decide about equality of elements between the two ranges.
FwIt adjacent_find(FwIt first, FwIt last[, BinPred predicate])
- Returns an iterator to the first element of the first pair of adjacent elements in the range [first, last) that are equal to each other or match a binary predicate. Returns last if no suited adjacent elements are found.
Example
The following code snippet uses the
find_if()
algorithm to find a person called Waldo in a list of people:
auto people = { Person("Wally"), Person("Wilma"), Person("Wenda"),
Person("Odlaw"), Person("Waldo"), Person("Woof") };
auto iter = std::find_if(begin(people), end(people),
[](const Person& p) { return p.GetFirstName() == "Waldo"; });
Binary Search
All of the following algorithms require that the given range [first, last) is sorted or at least partitioned on value (partitioning is explained later). If this precondition is not met, the algorithms’ behavior is undefined.
bool binary_search(FwIt first, FwIt last, const T& value[, Compare comp])
- Returns true if there is an element equal to value in the range [first, last).
FwIt lower_bound(FwIt first, FwIt last, const T& value[, Compare comp])
FwIt upper_bound(FwIt first, FwIt last, const T& value[, Compare comp])
- Returns an iterator to the first element in [first, last) that does not compare less than value for lower_bound() and to the first that compares greater than value for upper_bound(). When inserting in a sorted range, both are suitable positions to insert value, provided insertion happens before the iterator (as with the insert() method of sequential containers; see the next “Example” subsection).[Alternatives: all ordered associative containers have lower_bound() and upper_bound() members.]
pair<FwIt, FwIt> equal_range(FwIt first, FwIt last,
const T& value[, Compare comp])
- Returns a pair containing the lower and upper bounds. [Alternatives: all ordered and unordered associative containers have an equal_range() member.]
Example
The following code snippet demonstrates how to insert a new value into a vector at the correct place to keep the elements sorted:
The next
example uses equal_range() to
find the range of values equal to 2. It returns a pair of iterators. The first one points to the first element equal to 2, and the second points to the element after the last 2:
Subsequence Search
All the subsequence search algorithms accept an optional binary predicate that is used to decide about equality of elements.
FwIt1 search(FwIt1 first1, FwIt1 last1,
FwIt2 first2, FwIt2 last2[, BinPred predicate])
FwIt1 find_end(FwIt1 first1, FwIt1 last1,
FwIt2 first2, FwIt2 last2[, BinPred predicate])
- For search()/find_end(), respectively, returns an iterator to the beginning of the first/last subsequence in [first1, last1) that is equal to the range [first2, last2). Returns first1/last1 if the second range is empty, or last1 if no equal subsequence is found.
FwIt search_n(FwIt first, FwIt last, Size count,
const T& value[, BinPred predicate])
- Returns an iterator to the first subsequence in [first, last) that consists of value repeated count times. Returns first if count is zero, or last if no suitable subsequence is found.
Min/Max
constexpr const T& min(const T& a, const T& b[, Compare comp])
constexpr const T& max(const T& a, const T& b[, Compare comp])
- Returns a reference to the minimum or maximum of two values, or the first value if they are equal.
constexpr T min(initializer_list<T> t[, Compare comp])
constexpr T max(initializer_list<T> t[, Compare comp])
- Returns a copy of the minimum or maximum value in a given initializer_list, or a copy of the leftmost element if there are several elements equal to this extreme.
constexpr pair<const T&, const T&> minmax(
const T& a, const T& b[, Compare comp])
- Returns a pair containing references to the minimum and maximum of two values, in that order. If both values are equal, the pair(a, b) is returned.
constexpr pair<T, T> minmax(initializer_list<T> t[, Compare comp])
- Returns a pair containing a copy of the minimum and maximum values in an initializer_list, in that order. If several elements are equal to the minimum, then a copy of the leftmost one is returned; if several elements are equal to the maximum, then a copy of the rightmost is returned.
FwIt min_element(FwIt first, FwIt last[, Compare comp])
FwIt max_element(FwIt first, FwIt last[, Compare comp])
pair<FwIt, FwIt> minmax_element(FwIt first, FwIt last[, Compare comp])
- Returns an iterator to the minimum, an iterator to the maximum, or, respectively, a pair containing an iterator to both the minimum and maximum element in a range [first, last). Returns last or pair(first, first) if the range is empty.
Sequence Comparison
All the sequence comparison
algorithms accept an optional binary predicate that is used to decide about equality of elements.
bool equal(InIt1 first1, InIt1 last1, InIt2 first2[, BinPred predicate])
- Let n = (last1 - first1), then returns true if all elements in the ranges [first1, last1) and [first2, first2 + n ) pair-wise match. The second range must have at least n elements. The four-argument version discussed later is therefore preferred to avoid out-of-bounds accesses.
pair<InIt1, InIt2> mismatch(InIt1 first1, InIt1 last1,
InIt2 first2[, BinPred predicate])
- Let n = (last1 - first1), then returns a pair of iterators pointing to the first elements in the ranges [first1, last1) and [first2, first2 + n ) that do not pair-wise match. The second range must have at least n elements. The following four-argument version is therefore preferred to avoid out-of-bounds accesses.
bool equal(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2[, BinPred predicate])
pair<InIt1, InIt2> mismatch(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2[, BinPred predicate])
- Safer versions of the earlier three-argument versions that also know the length of the second range. For equal() to be true, both ranges have to be equally long. For mismatch(), if no mismatching pair is found before reaching either last1 or last2, a pair (first1 + m, first2 + m) is returned with m = min(last1 - first1, last2 - first2).
Copy, Move, Swap
OutIt copy(InIt first, InIt last, OutIt targetFirst)
OutIt copy_if(InIt first, InIt last, OutIt targetFirst, UnaPred predicate)
- Copies either all the elements (copy()), or only those that satisfy a unary predicate (copy_if()), from the range [first, last) to a range starting at targetFirst. For copy(), targetFirst is not allowed to be in [first, last): if this is the case, copy_backward() may be an option. For copy_if(), the ranges are not allowed to overlap. For both algorithms, the target range must be big enough to accommodate the copied elements. Returns the end iterator of the resulting range.
BidIt2 copy_backward(BidIt1 first, BidIt1 last, BidIt2 targetLast)
- Copies all the elements in the range [first, last) to a range ending at targetLast, which is not in the range [first, last). The target range must be big enough to accommodate the copied elements. Copying is done backward, starting with copying element (last-1) to (targetLast-1) and going back to first. Returns an iterator to the beginning of the target range, so (targetLast - (last - first)).
OutIt copy_n(InIt start, Size count, OutIt target)
- Copies count elements starting at start to a range starting at target. The target range must be big enough to accommodate the elements. Returns the target end iterator, so (target + count).
OutIt move(InIt first, InIt last, OutIt targetFirst)
BidIt2 move_backward(BidIt1 first, BidIt1 last, BidIt2 targetLast)
- Similar to copy() and copy_backward() but moves the elements instead of copying them.
FwIt2 swap_ranges(FwIt1 first1, FwIt1 last1, FwIt2 first2)
- Swaps the elements in the range [first1, last1) with the elements in the range [first2, first2 + (last1 - first1)). Both ranges are not allowed to overlap, and the second range must be at least as big as the first. Returns an iterator one past the last swapped element in the second range.
void iter_swap(FwIt1 x, FwIt2 y)
- Swaps the element pointed to by x with the element pointed to by y, so swap(*x, *y).
Generating Sequences
void fill(FwIt first, FwIt last, const T& value)
OutIt fill_n(OutIt first, Size count, const T& value)
- Assigns value to all the elements in the range [first, last) or [first, first + count). Nothing happens if count is negative. The range for fill_n() must be big enough to accommodate count elements. fill_n() returns (first + count), or first if count is negative. [Alternatives: array::fill().]
void generate(FwIt first, FwIt last, Generator gen)
OutIt generate_n(OutIt first, Size count, Generator gen)
- The generator is a function without any arguments returning a value. It is called to calculate a value for each element in the range [first, last) or [first, first + count). Nothing happens if count is negative. The range for generate_n() must be big enough to accommodate count elements. generate_n() returns (first + count), or first if count is negative.
void iota(FwIt first, FwIt last, T value)
- This algorithm is defined in the <numeric> header. Each element in the range [first, last) is set to value, after which value is incremented, so:
*first = value++
*(first + 1) = value++
*(first + 2) = value++
...
Example
The following example demonstrates generate() and iota():
Removing and Replacing
FwIt remove(FwIt first, FwIt last, const T& value)
FwIt remove_if(FwIt first, FwIt last, UnaPred predicate)
- Moves all elements in the range [first, last) that are not equal to value, or do not satisfy a unary predicate, toward the beginning of the range, after which [first, result) contains all the elements to keep. The result iterator, pointing to one passed the last element to keep, is returned. The algorithms are stable, which means the retained elements maintain their relative order. The elements in [result, last) should not be used because they could be in an unspecified state due to moves. Usually these algorithms are followed by a call to erase(). This is known as the remove-erase idiom and is discussed in Chapter 3.
[Alternatives: list and
forward_list have remove() and remove_if() members.]
FwIt unique(FwIt first, FwIt last[, BinPred predicate])
- Removes all but one element from consecutive equal elements in the range [first, last). If a binary predicate is given, it is used to decide about equality of elements. Otherwise equivalent to remove(), including the fact that it should normally be followed by an erase(). A typical use of unique() is shown in the next “Example” subsection. [Alternatives: list::unique(), forward_list::unique().]
void replace(FwIt first, FwIt last, const T& oldVal, const T& newVal)
void replace_if(FwIt first, FwIt last, UnaPred predicate, const T& newVal)
- Replaces with newVal all elements in the range [first, last) equal to oldVal, or satisfying a unary predicate.
OutIt remove_copy(InIt first, InIt last, OutIt target, const T& value)
OutIt remove_copy_if(InIt first, InIt last, OutIt target, UnaPred predicate)
OutIt unique_copy(InIt first, InIt last, OutIt target [, BinPred predicate])
OutIt replace_copy(InIt first, InIt last, OutIt target,
const T& oldVal, const T& newVal)
OutIt replace_copy_if(InIt first, InIt last, OutIt target,
UnaPred predicate, const T& newVal)
- Similar to the previous algorithms, but copies the results to a range starting at target. The target range must be big enough to accommodate the copied elements. The input and target ranges are not allowed to overlap. Returns the end iterator of the target range.
Example
The following example demonstrates the use of unique() and the remove-erase idiom to filter out all consecutive equal elements from a vector:
Reversing and Rotating
void reverse(BidIt first, BidIt last)
- Reverses the elements in the range [first, last). [Alternatives: list::reverse(), forward_list::reverse().]
FwIt rotate(FwIt first, FwIt middle, FwIt last)
- Rotates the elements in the range [first, last) to the left in such a way that the element pointed to by middle becomes the first element in the range and the element pointed to by (middle - 1) becomes the last element in the range (see the next “Example” subsection). Returns (first + (last - middle)).
OutIt reverse_copy(BidIt first, BidIt last, OutIt target)
OutIt rotate_copy(FwIt first, FwIt middle, FwIt last, OutIt target)
- Similar to reverse() and rotate(), but copies the results to a range starting at target. The target range must be big enough to accommodate the copied elements. The input and target ranges are not allowed to overlap. Returns the end iterator of the target range.
Example
The next code snippet rotates the elements in the vector. The result is 5,6,1,2,3,4:
std::vector<int> vec{ 1,2,3,4,5,6 };
std::rotate(begin(vec), begin(vec) + 4, end(vec));
Partitioning
bool is_partitioned(InIt first, InIt last, UnaPred predicate)
- Returns true if the elements in the range [first, last) are partitioned such that all elements satisfying a unary predicate are before all elements that do not satisfy the predicate. Also returns true if the range is empty.
FwIt partition(FwIt first, FwIt last, UnaPred predicate)
BidIt stable_partition(BidIt first, BidIt last, UnaPred predicate)
- Partitions the range [first, last) such that all elements satisfying a unary predicate are before all elements that do not satisfy the predicate. Returns an iterator to the first element that does not satisfy the predicate. stable_partition() maintains the relative order of elements in both partitions.
pair<OutIt1, OutIt2> partition_copy(InIt first, InIt last,
OutIt1 outTrue, OutIt2 outFalse, UnaPred predicate)
- Partitions the range [first, last) by copying all elements that satisfy or do not satisfy a unary predicate to an output range starting at outTrue or, respectively, outFalse. Both output ranges must be big enough to accommodate the copied elements. The input and output ranges are not allowed to overlap. Returns a pair containing the end iterator of the two output ranges.
FwIt partition_point(FwIt first, FwIt last, UnaPred predicate)
- Requires the range [first, last) to be partitioned based on a unary predicate. Returns an iterator to the first element of the second partition: that is, the first element that does not satisfy the predicate.
Sorting
void sort(RanIt first, RanIt last[, Compare comp])
void stable_sort(RanIt first, RanIt last[, Compare comp])
- Sorts the elements in the range [first, last). The stable version maintains the order of equal elements. [Alternatives: list::sort(), forward_list::sort().]
void partial_sort(RanIt first, RanIt middle, RanIt last[, Compare comp])
- The (middle - first) smallest elements from the range [first, last) are sorted and moved to the range [first, middle). The unsorted elements are moved to the range [middle, last) in an unspecified order.
RanIt partial_sort_copy(InIt first, InIt last,
RanIt targetFirst, RanIt targetLast[, Compare comp])
- min(last - first, targetLast - targetFirst) elements from the range [first, last) are sorted and copied to the target range. Returns min(targetLast, targetFirst + (last - first)).
void nth_element(RanIt first, RanIt nth, RanIt last[, Compare comp])
- The elements in the range [first, last) are moved in such a way that the given iterator nth, after rearranging, points to the element that would be in that position if the whole range were sorted. The entire range does not actually get sorted, though. It is, however, (non-stably) partitioned on the element nth points to.
bool is_sorted(FwIt first, FwIt last[, Compare comp])
- Returns true if the range [first, last) is a sorted sequence.
FwIt is_sorted_until(FwIt first, FwIt last[, Compare comp])
- Returns the last iterator, iter, such that [first, iter) is a sorted sequence.
bool lexicographical_compare(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2[, Compare comp])
- Returns whether the elements in the range [first1, last1) are lexicographically less than the elements in the range [first2, last2).
Example
The
partial_sort() and partial_sort_copy()
algorithms can be used to find the n biggest, smallest, worst, best, ... elements in a sequence. This is faster than sorting the entire sequence. For example:
std::vector<int> vec{ 9,2,4,7,3,6,1 };
std::vector<int> threeSmallestElements(3);
std::partial_sort_copy(begin(vec), end(vec),
begin(threeSmallestElements), end(threeSmallestElements));
nth_element() is a so-called selection algorithm to find the nth smallest number in a sequence and has on average a linear complexity. It can, for example, be used to calculate the median value of a sequence with an odd number of elements:
Shuffling
void shuffle(RanIt first, RanIt last, UniformRanGen generator)
- Shuffles the elements in the range [first, last) using randomness generated by a uniform random-number generator. The random-number-generation library is explained in Chapter 1.
void random_shuffle(RanIt first, RanIt last[, RNG&& rng])
- Deprecated in favor of shuffle(), but mentioned for completeness. It shuffles the elements in the range [first, last). The random number generator, rng, is a functor whose function call operator accepts an integral parameter n and returns an integral random number in the range [0, n) with n > 0. If no random-number generator is provided, the implementation is free to decide how it generates random numbers.
Example
The following example shuffles the elements in a vector. See Chapter 1 for more information on the random-number-generation library. The code snippet additionally needs <random> and <ctime>:
Operations on Sorted Ranges
All the following operations require that the input ranges are sorted. If this precondition is not met, the algorithms’ behavior is undefined.
OutIt merge(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt target[, Compare comp])
- Merges all the elements from the sorted ranges [first1, last1) and [first2, last2) to a range starting at target in such a way that the target range is sorted as well. The target range must be big enough to accommodate all elements. The input ranges are not allowed to overlap with the target range. Returns the end iterator of the target range. The algorithm is stable; that is, the order of equal elements is maintained. [Alternatives: list::merge(), forward_list::merge().]
void inplace_merge(BidIt first, BidIt middle, BidIt last[, Compare comp])
- Merges the sorted ranges [first, middle) and [middle, last) into one sorted sequence stored in the range [first, last). The algorithm is stable, so the order of equal elements is maintained.
bool includes(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2[, Compare comp])
- Returns true if all elements in the sorted range [first2, last2) are in the sorted range [first1, last1) or if the former is empty, or false otherwise.
OutIt set_union(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt target[, Compare comp])
OutIt set_intersection(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt target[, Compare comp])
OutIt set_difference(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt target[, Compare comp])
OutIt set_symmetric_difference(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt target[, Compare comp])
- Performs set operations (see the following list) on two sorted ranges [first1, last1) and [first2, last2) and stores the results in a range starting at target. The elements in the target range are sorted. The target range must be big enough to accommodate the elements of the set operation. The input and output ranges are not allowed to overlap. Returns the end iterator of the constructed target range.
- Union: All elements of both input ranges. If an element is in both input ranges, it appears only once in the output range.
- Intersection: All elements that are in both input ranges.
- Difference: All elements that are in [first1, last1) and that are not in [first2, last2).
- Symmetric difference: All elements that are in [first1, last1) and that are not in [first2, last2), and all elements that are in [first2, last2) and that are not in [first1, last1).
Permutation
bool is_permutation(FwIt1 first1, FwIt1 last1,
FwIt2 first2[, BinPred predicate])
bool is_permutation(FwIt1 first1, FwIt1 last1,
FwIt2 first2, FwIt2 last2[, BinPred predicate])
- Returns true if the second range is a permutation of the first one. For the three-argument versions, the second range is defined as [first2, first2 + (last1 - first1)), and this range must be at least as large as the first. The four-argument versions are therefore preferred to safeguard against out-of-bounds accesses (they return false if the ranges have different lengths). If a binary predicate is given, it is used to decide about equality of elements between the two ranges.
bool next_permutation(BidIt first, BidIt last[, Compare comp])
bool prev_permutation(BidIt first, BidIt last[, Compare comp])
- Transforms the elements in the range [first, last) into the lexicographically next/previous permutation. Returns true if such a next/previous permutation exists, otherwise returns false and transforms the elements in the lexicographically smallest/largest permutation possible.
Heaps
In this context, the term heap does not refer to the dynamic memory pool of the C++ runtime. In computer science, heaps are also a family of fundamental tree-based data structures (well-known variants include binary, binomial, and Fibonacci heaps). These data structures are key building blocks in the efficient implementation of various graph and sorting algorithms (classic examples include Prim’s algorithm, Dijkstra’s algorithm, and heapsort). It is also a common implementation strategy for a priority queue: in fact, the C++ priority_queue container adapter discussed in the previous chapter is implemented using the heap algorithms defined next.
For the following C++ algorithms, the heap’s tree is flattened into a contiguous sequence of elements that is ordered in a particular way. Although the exact ordering is implementation-specific, it must satisfy the following key properties: no element is greater than its first element, and both removing this greatest element and adding any new element can be done in logarithmic time.
void make_heap(RanIt first, RanIt last[, Compare comp])
- Turns the range [first, last) into a heap (in linear time).
void push_heap(RanIt first, RanIt last[, Compare comp])
- The last element of the range [first, last) is moved to the correct position such that it becomes a heap. The range [first, last - 1) is required to be a heap prior to calling push_heap().
void pop_heap(RanIt first, RanIt last[, Compare comp])
- Removes the greatest element from the heap [first, last) by swapping *first with *(last - 1) and making sure the new range [first, last - 1) remains a heap.
void sort_heap(RanIt first, RanIt last[, Compare comp])
- Sorts all the elements in the range [first, last). The range is required to be a heap prior to calling sort_heap().
bool is_heap(RanIt first, RanIt last[, Compare comp])
- Returns true if the range [first, last) represents a heap.
RanIt is_heap_until(RanIt first, RanIt last[, Compare comp])
- Returns the last iterator, iter, such that [first, iter) represents a heap.
Numeric Algorithms <numeric>
The following algorithms are defined in the <numeric> header:
T accumulate(InIt first, InIt last, T startValue[, BinOp op])
- Returns result, which is calculated by starting with result equal to startValue and then executing result += element or result = op(result, element) for each element in the range [first, last).
T inner_product(InIt1 first1, InIt1 last1, InIt2 first2,
T startValue[, BinOp1 op1, BinOp2 op2])
- Returns result, which is calculated by starting with result equal to startValue and then executing result += (el1 * el2) or result = op1(result, op2(el1, el2)) for each el1 from the range [first1, last1) and each el2 from the range [first2, first2 + (last1 - first1)) in order. The second range must be at least as big as the first.
OutIt partial_sum(InIt first, InIt last, OutIt target[, BinOp op])
- Calculates partial sums of increasing subranges from [first, last), and writes the results to a range starting at target. With the default operator, +, the result is as if calculated as follows:
*(target) = *first
*(target + 1) = *first + *(first + 1)
*(target + 2) = *first + *(first + 1) + *(first + 2)
...
- Returns the end iterator of the target range, so (target + (last - first)). The target range must be big enough to accommodate the results. The calculations can be done in place by specifying target equal to first.
OutIt adjacent_difference(InIt first, InIt last, OutIt target[, BinOp op])
- Calculates differences of adjacent elements in the range [first, last), and writes the results to a range starting at target. For the default operator, -, the result is calculated as follows:
*(target) = *first
*(target + 1) = *(first + 1) - *first
*(target + 2) = *(first + 2) - *(first + 1)
...
- Returns the end iterator of the target range, so (target + (last - first)). The target range must be big enough to accommodate the results. The calculations can be done in place by specifying target equal to first.
Example
The following code snippet uses the
accumulate()
algorithm to calculate the sum of all elements in a sequence:
The inner_product() algorithm can be used to calculate the so-called dot product of two mathematical vectors:
Iterator Adaptors <iterator>
The Standard Library provides the following iterator adaptors:
- reverse_iterator: Reverses the order of the iterator being adapted. Use make_reverse_iterator(Iterator iter) to construct one.
- move_iterator: Dereferences the iterator being adapted as an rvalue. Use make_move_iterator(Iterator iter) to construct one.
- back_insert_iterator: An iterator adaptor that inserts new elements at the back of a container using push_back(). Use back_inserter(Container& cont) to construct one.
- front_insert_iterator: An iterator adaptor that inserts new elements at the front of a container using push_front(). Use front_inserter(Container& cont) to construct one.
- insert_iterator: An iterator adaptor that inserts new elements in a container using insert(). To construct one, use inserter(Container& cont, Iterator iter), where iter is the insertion position.
The following example copies all elements from a vector to a deque in reverse order by using a front_insert_iterator adaptor on the deque. Next, it concatenates all strings in the vector using accumulate() (whose default combining operator, +, performs concatenation for strings). Because move_iterator adaptors are used here, the strings are moved rather than copied from the vector: