Mastering Standard Library Algorithms

WHAT’S IN THIS CHAPTER?

• What Standard Library algorithms are and what principles they are built on
• Details of the algorithms provided by the Standard Library
• How to execute algorithms in parallel to improve performance
• What constrained algorithms are

WILEY.COM DOWNLOADS FOR THIS CHAPTER

Please note that all the code examples for this chapter are available as part of this chapter’s code download on the book’s website at www.wiley.com/go/proc++6e on the Download Code tab.

As Chapter 18, “Standard Library Containers,” shows, the Standard Library provides an impressive collection of generic data structures. Most libraries stop there. The Standard Library, however, contains an additional assortment of generic algorithms that can, with some exceptions, be applied to elements from any container. Using these algorithms, you can find, sort, and process elements in containers and perform a host of other operations. The beauty of the algorithms is that they are independent not only of the types of the underlying elements, but also of the types of the containers on which they operate. Algorithms perform their work using only the iterator or ranges interfaces, discussed in Chapter 17, “Understanding Iterators and the Ranges Library.”

The Standard Library comes with a large set of unconstrained algorithms, all working solely with iterators. These algorithms don’t have any constraints in the form of concepts; see Chapter 12, “Writing Generic Code with Templates,” attached to them. The Standard Library additionally has a large collection of constrained algorithms, sometimes called range-based algorithms. These are able to work with iterators and ranges and are properly constrained, so the compiler can produce more readable error messages when an algorithm is used wrongly. This chapter focuses first on the unconstrained algorithms, as these are the ones used in most existing and legacy code bases; hence, you need to know how they work. Once you know how they work, it will be refreshing to see how the constrained algorithms make things easier.

Chapter 16, “Overview of the C++ Standard Library,” gives a high-level overview of all the Standard Library algorithms, but without any coding details. Combined with the knowledge of Chapter 19, “Function Pointers, Function Objects, and Lambda Expressions,” now it’s time to look at how those algorithms can be used in practice and discover their true power.

OVERVIEW OF ALGORITHMS

The “magic” behind the unconstrained algorithms is that they work on iterator intermediaries instead of on the containers themselves. In that way, they are not tied to specific container implementations. All the Standard Library algorithms are implemented as function templates, where the template type parameters are usually iterator types. The iterators themselves are specified as arguments to the function. Function templates can usually deduce the template types from the function arguments, so you can generally call the algorithms as if they were normal functions, not templates.

Most algorithms require a source sequence on which to apply the algorithm. For the unconstrained algorithms, a source sequence is specified as an iterator pair, a begin and end iterator, which is called a common range. As Chapter 17 explains, common ranges are half-open for most containers such that they include the first element in the range but exclude the last. The end iterator is really a “past-the-end” marker.

Algorithms pose certain requirements on iterators passed to them. For instance, copy_backward(), which copies elements from one sequence to another, starting with the last element, is an example of an algorithm that requires a bidirectional iterator. Similarly, stable_sort(), which sorts elements in place while preserving the order of duplicate elements, is an example of an algorithm requiring random access iterators. This means that such algorithms cannot work on containers that do not provide the necessary iterators. forward_list is an example of a container supporting only forward iterators, no bidirectional or random-access iterators; thus, copy_backward() and stable_sort() cannot work on forward_list.

The majority of the algorithms are defined in <algorithm>, with some numerical algorithms defined in <numeric>. All of them are in the std namespace.

Most algorithms are constexpr, which means they can be used in the implementation of constexpr functions. Consult a Standard Library Reference (see Appendix B, “Annotated Bibliography”) to discover exactly which algorithms are constexpr.

The best way to understand the algorithms is to look at some examples in detail first. After you’ve seen how a few of them work, it’s easy to pick up the others. This section describes the find(), find_if(), and accumulate() algorithms in detail. The subsequent sections discuss each of the classes of algorithms with representative samples.

The find and find_if Algorithms

find() looks for a specific element in a common range. You can use it on elements in any container type. It returns an iterator referring to the element found or the end iterator of the range in case the element is not found. Note that the range specified in the call to find() need not be the entire range of elements in a container; it could be a subset.

If find() fails to find an element, it returns an iterator equal to the end iterator specified in the function call, not the end iterator of the underlying container.

Before looking at find(), let’s define a function template to populate a container with integers. This function template is used throughout this chapter. It’s a function template parameterized on the type of container. A constraint enforces that the given container type supports push_back(int).

template <typename Container>
    requires requires(Container& c, int i) { c.push_back(i); }
void populateContainer(Container& cont)
{
    while (true) {
        print("Enter a number (0 to stop): ");
        int value;
        cin >> value;
        if (value == 0) { break; }
        cont.push_back(value);
    }
}

Now we can look at how to use std::find(). This example and the populateContainer() function template assume that the user plays nice and enters valid numbers; it does not perform any error checking on the user input. Performing error checking on stream input is discussed in Chapter 13, “Demystifying C++ I/O.”

vector<int> myVector;
populateContainer(myVector);

while (true) {
    print("Enter a number to lookup (0 to stop): ");
    int number;
    cin >> number;
    if (number == 0) { break; }
    auto endIt { cend(myVector) };
    auto it { find(cbegin(myVector), endIt, number) };
    if (it == endIt) {
        println("Could not find {}", number);
    } else {
        println("Found {}", *it);
    }
}

To search all the elements of the vector, find() is called with cbegin(myVector) and endIt as iterator arguments, where endIt is defined as cend(myVector). If you want to search in a subrange, you can change these two iterators.

Here is a sample run of the program:

Enter a number (0 to stop): 3
Enter a number (0 to stop): 4
Enter a number (0 to stop): 5
Enter a number (0 to stop): 6
Enter a number (0 to stop): 0
Enter a number to lookup (0 to stop): 5
Found 5
Enter a number to lookup (0 to stop): 8
Could not find 8
Enter a number to lookup (0 to stop): 0

With initializers for if statements, the call to find() and checking the result can be done with one statement as follows:

if (auto it { find(cbegin(myVector), endIt, number) }; it == endIt) {
    println("Could not find {}", number);
} else {
    println("Found {}", *it);
}

Some containers, such as map and set, provide their own versions of find() as class member functions, as demonstrated with examples during the discussion of those containers in Chapter 18.

If a container provides a member function with the same functionality as a generic algorithm, you should use the member function instead, because it’s faster. For example, the generic find() algorithm runs in linear time, even on a map, while the find() member function on a map runs in logarithmic time.

find_if() is similar to find(), except that it accepts a predicate function callback returning true or false, instead of a simple element to match. The find_if() algorithm calls the predicate on each element in the range until the predicate returns true, in which case find_if() returns an iterator referring to that element. The following program reads test scores from the user, then checks whether any of the scores are “perfect.” A perfect score is a score of 100 or higher. The program is similar to the previous example. Only the major differences are highlighted:

bool perfectScore(int num) { return num >= 100; }

int main()
{
    vector<int> myVector;
    populateContainer(myVector);

    auto endIt { cend(myVector) };
    auto it { find_if(cbegin(myVector), endIt, perfectScore) };
    if (it == endIt) {
        println("No perfect scores");
    } else {
        println("Found a \"perfect\" score of {}", *it);
    }
}

This program passes a pointer to the perfectScore() function to find_if(), which the algorithm then calls on each element until it returns true.

Instead of passing a function pointer to find_if(), you can also pass a functor. Chapter 15, “Overloading C++ Operators,” explains that, starting with C++23, the function call operator of a functor can be marked as static if it doesn’t need access to any non-static data members and member functions of the functor class. The perfectScore() function could be changed to a PerfectScore functor with a static function call operator as follows:

class PerfectScore
{
    public:
        static bool operator()(int num) { return num >= 100; }
};

The call to find_if() then needs to change as follows:

auto it { find_if(cbegin(myVector), endIt, &PerfectScore::operator()) };

Finally, instead of a perfectScore() function or a PerfectScore functor, you can use a lambda expression, discussed in Chapter 19.

auto it { find_if(cbegin(myVector), endIt, [](int i){ return i >= 100; }) };

The accumulate Algorithm

It’s often useful to calculate the sum, or some other arithmetic quantity, of elements in a container. The accumulate() function—defined in <numeric>, not in <algorithm>—does just that. In its most basic form, it calculates the sum of the elements in a specified range. For example, the following function calculates the arithmetic mean of a sequence of integers given as a span. The arithmetic mean is simply the sum of all the elements divided by the number of elements:

double arithmeticMean(span<const int> values)
{
    double sum { accumulate(cbegin(values), cend(values), 0.0) };
    return sum / values.size();
}

The accumulate() algorithm takes as its third parameter an initial value for the sum, which in this case should be 0.0 (the identity for addition) to start a fresh sum.

A second overload of accumulate() allows the caller to specify an operation to perform instead of the default addition. This operation takes the form of a binary callback. Suppose that you want to calculate the geometric mean, which is the product of all the numbers in the sequence to the power of the inverse of the size. In that case, you would want to use accumulate() to calculate the product instead of the sum. You could write it like this:

int product(int value1, int value2) { return value1 * value2; }

double geometricMean(span<const int> values)
{
    int mult { accumulate(cbegin(values), cend(values), 1, product) };
    return pow(mult, 1.0 / values.size());  // pow() is defined in <cmath>
}

Note that the product() function is passed as a callback to accumulate() and that the initial value for the accumulation is 1 (the identity for multiplication).

Instead of a separate product() function, you could use a lambda expression:

double geometricMeanLambda(span<const int> values)
{
    int mult { accumulate(cbegin(values), cend(values), 1,
        [](int value1, int value2) { return value1 * value2; }) };
    return pow(mult, 1.0 / values.size());
}

You could also use the transparent multiplies<> function object, discussed in Chapter 19, to implement the geometricMean() function:

double geometricMeanFunctor(span<const int> values)
{
    int mult { accumulate(cbegin(values), cend(values), 1, multiplies<>{}) };
    return pow(mult, 1.0 / values.size());
}

Move Semantics with Algorithms

Just like Standard Library containers, Standard Library algorithms are also optimized to use move semantics at appropriate times; that is, they can move objects instead of performing potential expensive copy operations. This can greatly speed up certain algorithms, for example, remove(), discussed in detail later in this chapter. For this reason, it is highly recommended that you implement move semantics in your custom element classes that you want to store in containers. Move semantics can be added to any class by implementing a move constructor and a move assignment operator. As discussed in Chapter 18, both should be marked as noexcept, otherwise they won’t be used by Standard Library containers and algorithms. Consult the “Implementing Move Semantics” section in Chapter 9, “Mastering Classes and Objects,” for details on how to add move semantics to your classes.

Algorithm Callbacks

The algorithms are allowed to make multiple copies of given callbacks, such as functors and lambda expressions, and call different copies for different elements.

The fact that multiple copies of a callback can be made places strong restrictions on the side effects of such callbacks. Basically, the callbacks must be stateless. For functors, this means that the function call operator needs to be const; thus, you cannot write functors such that they count on any internal state of the object being consistent between calls. Similar for lambda expressions, they cannot be marked as mutable.

There are some exceptions. The generate() and generate_n() algorithms can accept stateful callbacks, but even these make one copy of the callback. On top of that, they don’t return that copy, so you don’t have access to the changes made to the state once the algorithm is finished. The only exception is for_each(). It copies the given predicate once into the for_each() algorithm and returns that copy when finished. You can access the changed state through this returned value.

To prevent callbacks from getting copied by algorithms, you can use the std::ref() helper function to pass a callback reference to the algorithm instead. This ensures that the algorithm always uses the same callback. For example, the following code snippet is based on an earlier example in this chapter but uses a lambda expression stored in a variable named isPerfectScore. The lambda expression counts how often it gets called and writes that to standard output. isPerfectScore is passed to the find_if() algorithm, not yet using ref(). The last statement of the snippet explicitly calls isPerfectScore one additional time.

auto isPerfectScore { [tally = 0] (int i) mutable {
    println("{}", ++tally);  return i >= 100; } };

auto endIt { cend(myVector) };
auto it { find_if(cbegin(myVector), endIt, isPerfectScore) };
if (it != endIt) { println("Found a \"perfect\" score of {}", *it); }
println("---");
isPerfectScore(1);

The output can be as followed:

Enter a number (0 to stop): 11
Enter a number (0 to stop): 22
Enter a number (0 to stop): 33
Enter a number (0 to stop): 0
1
2
3
---
1

The output shows that the find_if() algorithm calls isPerfectScore three times producing the output 1, 2, 3. The last line shows that the explicit call to isPerfectScore occurs on a different instance of isPerfectScore as it starts again at 1.

Now, change the call to find_if() as follows:

auto it { find_if(cbegin(myVector), endIt, ref(isPerfectScore)) };

The output now will be 1, 2, 3, 4, showing that no copies of isPerfectScore are made.

ALGORITHM DETAILS

Chapter 16 lists all available Standard Library algorithms, divided into different categories. Most of the algorithms are defined in <algorithm>, but a few are located in <numeric>. They are all in the std namespace.

The goal of this chapter is not to provide a reference-style overview of all available algorithms. Instead, I have picked a number of categories and provided examples for them. Once you know how to use these algorithms, you should have no problems with other algorithms. Consult a Standard Library Reference (see Appendix B) for a full reference of all the algorithms.

Non-modifying Sequence Algorithms

Non-modifying sequence algorithms are algorithms that do not modify the sequence of elements they operate on. These include algorithms for searching elements in a range and for comparing two ranges to each other; they also include a number of counting algorithms.

Search Algorithms

You’ve already seen examples of two search algorithms earlier in this chapter: find() and find_if(). The Standard Library provides several other variations of the basic find() algorithm that work on sequences of elements. The section “Search Algorithms” in Chapter 16 describes the different search algorithms that are available, including their complexity.

All the algorithms use operator== or < as the default comparison operator, but also provide overloaded versions that allow you to specify a different comparison callback.

Here are examples of some of the search algorithms in action:

// The list of elements to be searched.
vector myVector { 5, 6, 9, 8, 8, 3 };
auto beginIter { cbegin(myVector) };
auto endIter { cend(myVector) };

// Find the first element that does not satisfy the given lambda expression.
auto it { find_if_not(beginIter, endIter, [](int i){ return i < 8; }) };
if (it != endIter) {
    println("First element not < 8 is {}", *it);
}

// Find the first pair of matching consecutive elements.
it = adjacent_find(beginIter, endIter);
if (it != endIter) {
    println("Found two consecutive equal elements with value {}", *it);
}

// Find the first of two values.
vector targets { 8, 9 };
it = find_first_of(beginIter, endIter, cbegin(targets), cend(targets));
if (it != endIter) {
    println("Found one of 8 or 9: {}", *it);
}

// Find the first subsequence.
vector sub { 8, 3 };
it = search(beginIter, endIter, cbegin(sub), cend(sub));
if (it != endIter) {
    println("Found subsequence {{8,3}}");
} else {
    println("Unable to find subsequence {{8,3}}");
}

// Find the last subsequence (which is the same as the first in this example).
auto it2 { find_end(beginIter, endIter, cbegin(sub), cend(sub)) };
if (it != it2) {
    println("Error: search and find_end found different subsequences "
         "even though there is only one match.");
}

// Find the first subsequence of two consecutive 8s.
it = search_n(beginIter, endIter, 2, 8);
if (it != endIter) {
    println("Found two consecutive 8s");
} else {
    println("Unable to find two consecutive 8s");
}

Here is the output:

First element not < 8 is 9
Found two consecutive equal elements with value 8
Found one of 8 or 9: 9
Found subsequence {8,3}
Found two consecutive 8s

Note

Remember that some of the containers have member functions equivalent to generic algorithms. If that’s the case, it’s recommended to use those member functions instead of the generic algorithms, because the member functions are more efficient. An example is the find() member function of std::set and std::map.

Specialized Searchers

An optional parameter to the search() algorithm allows you to specify which search algorithm to use. You have three options—default_searcher, boyer_moore_searcher, or boyer_moore_horspool_searcher—all defined in <functional>. The last two options implement the well-known Boyer-Moore and Boyer-Moore-Horspool search algorithms. These are more efficient than the default searcher and can be used to find a substring in a larger piece of text. The complexity of the Boyer-Moore searchers is as follows (N is the size of the sequence to search in, the haystack, and M is the size of the pattern to find, the needle):

• If the pattern is not found, the worst-case complexity is O(N+M).
• If the pattern is found, the worst-case complexity is O(N*M).

These are the theoretical worst-case complexities. In practice, these specialized searchers are sublinear, better than O(N), which means they are much faster than the default one! They are sublinear because they are able to skip characters instead of looking at each single character in the haystack. They also have an interesting property that the longer the needle is, the faster they work, as they will be able to skip more characters in the haystack. The difference between the Boyer-Moore and the Boyer-Moore-Horspool algorithm is that the latter has less constant overhead for its initialization and in each loop iteration of its algorithm; however, its worst-case complexity can be significantly higher than for the Boyer-Moore algorithm. So, which one to choose depends on your specific use case.

Here is an example of using a Boyer-Moore searcher:

string text { "This is the haystack to search a needle in." };
string toSearchFor { "needle" };
boyer_moore_searcher searcher { cbegin(toSearchFor), cend(toSearchFor) };
auto result { search(cbegin(text), cend(text), searcher) };
if (result != cend(text)) {
    println("Found the needle.");
} else {
    println("Needle not found.");
}

Comparison Algorithms

You can compare entire ranges of elements in several different ways: equal(), mismatch(), lexicographical_compare(), and lexicographical_compare_three_way(). These algorithms have the advantage that you can compare sequences from different containers. For example, you can compare the contents of a vector with the contents of a list. In general, these algorithms work best with sequential containers. They work by comparing the values in corresponding positions of the two collections to each other. The following list describes how each algorithm works:

• equal() returns true if all corresponding elements are equal. Originally, equal() accepted three iterators: begin and end iterators for the first range, and a begin iterator for the second range. This version required both ranges to have the same number of elements. Since C++14, there is an overload accepting four iterators: begin and end iterators for the first range, and begin and end iterators for the second range. This version can cope with ranges of different sizes. It’s recommended to always use the four-iterator version because it’s safer!
• mismatch() returns iterators, one iterator for each range, to indicate where in the range the corresponding elements mismatch. There are three-iterator and four-iterator versions available, just as with equal(). It’s again recommended to use the four-iterator version, because of safety!
• lexicographical_compare() compares the elements that have the same position in both supplied ranges against each other (sequentially). It returns true if the first unequal element in the first range is less than its corresponding element in the second range, or if the first range has fewer elements than the second and all elements in the first range are equal to their corresponding initial subsequence in the second set. lexicographical_compare() gets its name because it resembles the rules for comparing strings in dictionaries, but extends this set of rules to deal with objects of any type.
• lexicographical_compare_three_way() is similar to lexicographical_compare() except that it performs a three-way comparison and returns a comparison category type (strong_ordering, weak_ordering, or partial_ordering, discussed in Chapter 1, “A Crash Course in C++ and the Standard Library”) instead of a Boolean.

Note

If you want to compare all elements of two containers of the same type, you can just use operators such as operator== or operator< instead of one of these algorithms. The algorithms are useful for comparing subranges, C-style arrays, sequences of elements from different container types, and so on.

Here are some examples of these algorithms in action:

vector<int> myVector;
list<int> myList;

println("Populate the vector:");
populateContainer(myVector);
println("Populate the list:");
populateContainer(myList);

// Compare the two containers
if (equal(cbegin(myVector), cend(myVector),
          cbegin(myList), cend(myList))) {
    println("The two containers have equal elements");
} else {
    // If the containers were not equal, find out why not
    auto miss { mismatch(cbegin(myVector), cend(myVector),
                         cbegin(myList), cend(myList)) };
    println("The following initial elements are the same in "
        "the vector and the list:");
    for (auto iter { cbegin(myVector) }; iter != miss.first; ++iter) {
        print("{}\t", *iter);
    }
    println("");
}

// Now order them.
if (lexicographical_compare(cbegin(myVector), cend(myVector),
                            cbegin(myList), cend(myList))) {
    println("The vector is lexicographically first.");
} else {
    println("The list is lexicographically first.");
}

Here is a sample run of the program:

Populate the vector:
Enter a number (0 to stop): 5
Enter a number (0 to stop): 6
Enter a number (0 to stop): 7
Enter a number (0 to stop): 0
Populate the list:
Enter a number (0 to stop): 5
Enter a number (0 to stop): 6
Enter a number (0 to stop): 9
Enter a number (0 to stop): 8
Enter a number (0 to stop): 0
The following initial elements are the same in the vector and the list:
5      6
The vector is lexicographically first.

Additionally, the following comparison algorithms work on a single range: all_of(), any_of(), and none_of(). Here are some examples:

// all_of()
vector vec2 { 1, 1, 1, 1 };
if (all_of(cbegin(vec2), cend(vec2), [](int i){ return i == 1; })) {
    println("All elements are == 1");
} else {
    println("Not all elements are == 1");
}

// any_of()
vector vec3 { 0, 0, 1, 0 };
if (any_of(cbegin(vec3), cend(vec3), [](int i){ return i == 1; })) {
    println("At least one element == 1");
} else {
    println("No elements are == 1");
}

// none_of()
vector vec4 { 0, 0, 0, 0 };
if (none_of(cbegin(vec4), cend(vec4), [](int i){ return i == 1; })) {
    println("All elements are != 1");
} else {
    println("Some elements are == 1");
}

The output is as follows:

All elements are == 1
At least one element == 1
All elements are != 1

Counting Algorithms

The non-modifying counting algorithms are count() and count_if(). The following example uses the count_if() algorithm to count the number of elements in a vector that satisfy a certain condition. The condition is given in the form of a lambda expression, which captures the value variable from its enclosing scope by value:

vector values { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int value { 3 };
auto tally { count_if(cbegin(values), cend(values),
    [value](int i){ return i > value; }) };
println("Found {} values > {}.", tally, value);

The output is as follows:

Found 6 values> 3

The example can be extended to demonstrate capturing variables by reference. The following lambda expression counts the number of times it is called by incrementing a variable in the enclosing scope that is captured by reference:

vector values { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int value { 3 };
int callCounter { 0 };
auto tally { count_if(cbegin(values), cend(values),
    [value, &callCounter](int i){ ++callCounter; return i > value; }) };
println("The lambda expression was called {} times.", callCounter);
println("Found {} values > {}.", tally, value);

The output is as follows:

The lambda expression was called 9 times.
Found 6 values > 3

Modifying Sequence Algorithms

The Standard Library provides a variety of modifying sequence algorithms that perform tasks such as copying elements from one range to another, removing elements, or reversing the order of elements in a range.

Some modifying algorithms use the concept of a source and a destination range. The elements are read from the source range and modified in the destination range. An example of such an algorithm is copy().

Other algorithms perform their work in-place; that is, they require only one range, for example the generate() algorithm.

The modifying algorithms cannot insert elements into a destination. They can only overwrite/modify whatever elements are in the destination already. Chapter 17 describes how iterator adapters can be used to really insert elements into a destination.

Note

Ranges from maps and multimaps cannot be used as destinations of modifying algorithms. These algorithms overwrite entire elements, which in a map consist of key/value pairs. However, maps and multimaps mark the key as const, so it cannot be assigned to. The same holds for set and multiset. Your alternative is to use an insert iterator, described in Chapter 17.

The section “Modifying Sequence Algorithms” in Chapter 16 lists all available modifying algorithms with a description of each one. This section provides code examples for a selection of those algorithms. If you understand how to use the algorithms explained in this section, you should not have any problems using the other algorithms for which no examples are given.

generate

The generate() algorithm requires a common range and replaces the values in that range with the values returned from the function callback given as third argument. The following example uses the generate() algorithm together with a lambda expression to put the numbers 2, 4, 8, 16, and so on, in a vector:

vector<int> values(10); // Create a vector of 10 elements.
int value { 1 };
generate(begin(values), end(values), [&value]{ value *= 2; return value; });
println("{:n}", values);

The output is as follows:

2, 4, 8, 16, 32, 64, 128, 256, 512, 1024

transform

There are multiple overloads of the transform() algorithm. One overload applies a callback to each element in a range and expects the callback to generate a new element, which it stores in the specified destination range. The source and destination ranges can be the same if you want transform() to work in-place. The parameters are a begin and end iterator of the source sequence, a begin iterator of the destination sequence, and the callback. For example, the following code snippet adds 100 to each element in a vector. The populateContainer() function is the same as defined earlier in this chapter.

vector<int> myVector;
populateContainer(myVector);

println("The vector contains: {:n}", myVector);
transform(begin(myVector), end(myVector), begin(myVector),
    [](int i){ return i + 100;});
println("The vector contains: {:n}", myVector);

A possible output is as follows:

Enter a number (0 to stop): 1
Enter a number (0 to stop): 11
Enter a number (0 to stop): 0
The vector contains: 1, 11
The vector contains: 101, 111

Another overload of transform() calls a binary function on pairs of elements from two ranges. It requires a begin and end iterator of the first range, a begin iterator of the second range, and a begin iterator of the destination range. The following example creates two vectors and uses transform() to calculate the sum of pairs of elements and to store the result back in the first vector:

vector<int> vec1, vec2;
println("Vector1:"); populateContainer(vec1);
println("Vector2:"); populateContainer(vec2);
if (vec2.size() < vec1.size())
{
    println("Vector2 should be at least the same size as vector1.");
    return 1;
}

println("Vector1: {:n}", vec1);
println("Vector2: {:n}", vec2);
transform(begin(vec1), end(vec1), begin(vec2), begin(vec1),
    [](int a, int b){ return a + b; });
println("Vector1: {:n}", vec1);
println("Vector2: {:n}", vec2);

The output could look like this:

Vector1:
Enter a number (0 to stop): 1
Enter a number (0 to stop): 2
Enter a number (0 to stop): 0
Vector2:
Enter a number (0 to stop): 11
Enter a number (0 to stop): 22
Enter a number (0 to stop): 33
Enter a number (0 to stop): 0
Vector1: 1, 2
Vector2: 11, 22, 33
Vector1: 12, 24
Vector2: 11, 22, 33

Note

transform() and the other modifying algorithms often return an iterator referring to the past-the-end value of the destination range. The examples in this book usually ignore that return value.

copy

The copy() algorithm allows you to copy elements from one range to another, starting with the first element and proceeding to the last element in the range. The source and destination ranges must be different, but, with restrictions, they can overlap. The restrictions are as follows: for copy(b,e,d), overlapping is fine if d is before b; however, if d is within [b,e), then the behavior is undefined. As with all modifying algorithms, copy() cannot insert elements into the destination. It just overwrites whatever elements are there already. Chapter 17 describes how to use iterator adapters to insert elements into a container or stream with copy().

Here is a simple example of copy() that uses the resize() member function on a vector to ensure that there is enough space in the destination container. It copies all elements from vec1 to vec2.

vector<int> vec1, vec2;
populateContainer(vec1);
vec2.resize(size(vec1));
copy(cbegin(vec1), cend(vec1), begin(vec2));
println("{:n}", vec2);

There is also a copy_backward() algorithm, which copies the elements from the source backward to the destination. In other words, it starts with the last element of the source, puts it in the last position in the destination range, and then moves backward after each copy. Also for copy_backward(), the source and destination ranges must be different, but, with restrictions, they can again overlap. The restrictions this time are as follows: for copy_backward(b,e,d), overlapping is fine if d is after e, however, if d is within (b,e], then the behavior is undefined. The preceding example can be modified to use copy_backward() instead of copy(), as follows. Note that you need to specify end(vec2) as the third argument instead of begin(vec2). The output is the same as the version using copy().

copy_backward(cbegin(vec1), cend(vec1), end(vec2));

copy_if() works by having an input range specified by two iterators, an output destination specified by one iterator, and a predicate (for example, a function or lambda expression). The algorithm copies all elements that satisfy the given predicate to the destination. Remember, copy does not create or extend containers; it merely replaces existing elements, so the destination should be big enough to hold all elements to be copied. Of course, after copying the elements, it might be desirable to remove the space “beyond” where the last element was copied to. To facilitate this, copy_if() returns an iterator to the one-past-the-last-copied element in the destination range. This can be used to determine how many elements should be removed from the destination container. The following example demonstrates this by copying only the even numbers to vec2:

vector<int> vec1, vec2;
populateContainer(vec1);
vec2.resize(size(vec1));
auto endIterator { copy_if(cbegin(vec1), cend(vec1),
         begin(vec2), [](int i){ return i % 2 == 0; }) };
vec2.erase(endIterator, end(vec2));
println("{:n}", vec2);

copy_n() copies n elements from the source to the destination. The first parameter of copy_n() is the start iterator. The second parameter is an integer specifying the number of elements to copy, and the third parameter is the destination iterator. The copy_n() algorithm does not perform any bounds checking, so you must make sure that the start iterator, incremented by the number of elements to copy, does not exceed the end() of the source collection or your program will have undefined behavior. Here is an example:

vector<int> vec1, vec2;
populateContainer(vec1);
size_t tally { 0 };
print("Enter number of elements you want to copy: ");
cin >> tally;
tally = min(tally, size(vec1));
vec2.resize(tally);
copy_n(cbegin(vec1), tally, begin(vec2));
println("{:n}", vec2);

move

There are two move-related algorithms: move() and move_backward(). They both use move semantics, discussed in Chapter 9. You have to provide a move assignment operator in your element classes if you want to use these algorithms on containers with elements of your own types, as demonstrated in the following example. The main() function creates a vector with three MyClass objects and then moves those elements from vecSrc to vecDst. Note that the code includes two different uses of move(). The move() function accepting a single argument converts an lvalue into an rvalue and is defined in <utility>, while move() accepting three arguments is the Standard Library move() algorithm to move elements between containers. Consult Chapter 9 for details on implementing move assignment operators and the use of the single parameter version of std::move().

class MyClass
{
    public:
        MyClass() = default;
        MyClass(const MyClass& src) = default;
        explicit MyClass(string str) : m_str { move(str) } {}
        virtual ˜MyClass() = default;

        // Move assignment operator
        MyClass& operator=(MyClass&& rhs) noexcept {
            if (this == &rhs) { return *this; }
            m_str = move(rhs.m_str);
            println("Move operator= (m_str={})", m_str);
            return *this;
        }

        void setString(string str) { m_str = move(str); }
        const string& getString() const { return m_str; }
    private:
        string m_str;
};

int main()
{
    vector<MyClass> vecSrc { MyClass { "a" }, MyClass { "b" }, MyClass { "c" } };
    vector<MyClass> vecDst(vecSrc.size());
    move(begin(vecSrc), end(vecSrc), begin(vecDst));
    for (const auto& c : vecDst) { print("{} ", c.getString()); }
}

The output is as follows:

Move operator= (m_str=a)
Move operator= (m_str=b)
Move operator= (m_str=c)
a b c

Note

Chapter 9 explains that source objects in a move operation are left in some valid but otherwise indeterminate state. For the previous example, this means you should not use the elements from vecSrc anymore after the move operation, unless you bring them back to a determinate state, for example by calling a member function on them without any preconditions, such as setString().

move_backward() uses the same move mechanism as move(), but it moves the elements starting from the last to the first element. For both move() and move_backward(), the source and destination ranges are allowed to overlap with the same restrictions as for copy() and copy_backward().

replace

The replace() and replace:if() algorithms replace elements in a range matching a value or predicate, respectively, with a new value. Take replace:if() as an example. Its first and second parameters specify the range of elements to process. The third parameter is a callback that returns true or false. If it returns true, the value in the container is replaced with the value given for the fourth parameter; if it returns false, it leaves the original value.

For example, you might want to replace all odd values in a container with the value zero:

vector<int> values;
populateContainer(values);
replace:if(begin(values), end(values), [](int i){ return i % 2 != 0; }, 0);
println("{:n}", values);

There are also variants of replace() and replace:if() called replace:copy() and replace:copy_if() that copy the results to a different destination range. They are similar to copy(), in that the destination range must already be large enough to hold the copied elements.

erase

As introduced in Chapter 18, std::erase() and std::erase_if() support almost all Standard Library containers. Officially, these operations are called uniform container erasure. The erase() function deletes all elements matching a given value from a container, while erase_if() deletes all elements matching a given predicate. These algorithms require a reference to a container, instead of a common range, and are the preferred way to erase elements from containers.

For example, the following code snippet removes all empty strings from a vector of strings and uses erase_if() to do all the work:

vector<string> values {"", "one", "", "two", "three", "four"};
println("{:n}", values);
erase_if(values, [](const string& str){ return str.empty(); });
println("{:n}", values);

The output is as follows:

"", "one", "", "two", "three", "four"
"one", "two", "three", "four"

Note

std::erase() does not work with ordered and unordered associative containers, because these containers have a member function called erase(key), which is much more performant and should be used instead. On the other hand, the erase_if() function works with all containers.

remove

The erase() and erase_if() algorithms discussed in the previous section have been available since C++20. Still, let’s look at your options before C++20, as you will encounter them in legacy code. A first solution that you might think of is to check the documentation to see whether your container has an erase() member function and then iterate over all the elements and call erase() for each element that matches the condition. The vector is an example of a container that has such an erase() member function. However, if applied to the vector container, this solution is extremely inefficient as it will cause a lot of memory operations to keep the vector contiguous in memory, resulting in a quadratic complexity. This solution is also error-prone, because you need to be careful that you keep your iterators valid after a call to erase(). For example, here is a function that removes empty strings from a vector of strings without using algorithms. Note how iter is carefully manipulated inside the for loop.

void removeEmptyStringsWithoutAlgorithms(vector<string>& strings)
{
    for (auto iter { begin(strings) }; iter != end(strings); ) {
        if (iter->empty()) {
            iter = strings.erase(iter);
        } else {
            ++iter;
        }
    }
}

Note

Quadratic complexity means that the running time is a function of the square of the input size, O(n2).

This solution is inefficient and not recommended. A much better solution for this problem is the remove-erase-idiom, which runs in linear time and is explained next.

The remove algorithms have access only to the iterator abstraction, not to the container. Thus, they cannot really remove elements from the underlying container. Instead, the algorithms work by replacing the elements that match a given value or predicate with the next element that does not match the given value or predicate. It does so using move assignments. The result is that all elements to be kept are moved toward the beginning of the range. The range becomes partitioned into two sets: the elements to be kept and the elements to be erased. An iterator is returned that points to the first element of the range of elements to be erased. Take care not to use any of the elements in that range, as they might have been moved. The only thing you must do with the returned iterator is to actually erase these elements from the container. So you first use the remove() or remove_if() algorithm, and then you must call erase() on the container to erase all the elements from the returned iterator up to the end of the range. This process is called the remove-erase-idiom. Here is an implementation of a removeEmptyStrings() function using this idiom:

void removeEmptyStrings(vector<string>& strings)
{
    auto it { remove_if(begin(strings), end(strings),
        [](const string& str){ return str.empty(); }) };
    // Erase the removed elements.
    strings.erase(it, end(strings));
}

When using the remove-erase-idiom, make sure not to forget the second argument to erase()! If you forget this second argument, erase() will erase only a single element from the container, that is, the element referred to by the iterator passed as the first argument.

The remove_copy() and remove_copy_if() variations of remove() and remove_if() do not change the source range. Instead, they copy all kept elements to a different destination range. They are similar to copy(), in that the destination range must already be large enough to hold the new elements.

Note

The remove() family of functions are stable; i.e., they maintain the order of elements remaining in the container even while moving the retained elements toward the beginning.

Note

It’s recommended to use the std::erase_if() and std::erase() algorithms (or the erase(key) member function for associative containers) over the remove-erase-idiom, and definitely over handwritten loops.

unique

The unique() algorithm is a special case of remove() that removes all duplicate contiguous elements. The list container provides its own unique() member function that implements the same semantics. You should generally use unique() on sorted sequences, but nothing prevents you from running it on unsorted sequences.

unique() works in a similar way as remove(): it moves all elements to be kept to the front of the range and returns an iterator that points to the first element of the range of elements to be erased. As with the remove-erase-idiom, calling unique() must be followed by a call to erase().

The basic form of unique() runs in place, but there is also a variant of the algorithm called unique_copy() that copies its results to a new destination range.

Chapter 18 shows an example of the list::unique() algorithm in the section “list Example: Determining Enrollment,” so an example of the general form is omitted here.

shuffle

shuffle() rearranges the elements of a range in a random order with a linear complexity. It’s useful for implementing tasks like shuffling a deck of cards. shuffle() requires a start and end iterator for the range that you want to shuffle and a uniform random number generator object that specifies how random numbers should be generated. Here is an example (details on how to use random number generation engines and how to “seed” them are explained in Chapter 23, “Random Number Facilities”):

vector values { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

random_device seeder;
default_random_engine generator { seeder() };

for (int i { 0 }; i < 6; ++i) {
    shuffle(begin(values), end(values), generator);
    println("{:n}", values);
}

Here is some possible output: The output is as follows:

8, 6, 7, 5, 4, 1, 2, 9, 3
4, 1, 6, 2, 3, 7, 5, 9, 8
1, 4, 2, 5, 6, 8, 7, 3, 9
8, 4, 2, 7, 5, 9, 1, 6, 3
8, 9, 1, 7, 4, 5, 2, 6, 3
1, 7, 8, 5, 4, 3, 9, 6, 2

sample

The sample() algorithm returns a selection of n randomly chosen elements from a given source range and stores them in a destination range. It requires five parameters:

• A begin and end iterator of the range to sample
• A begin iterator of the destination range where to store the randomly selected elements
• The number of elements to select
• A random number generation engine

Here is an example (details on how to use random number generation engines and how to “seed” them are explained in Chapter 23):

vector values { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
const size_t numberOfSamples { 5 };
vector<int> samples(numberOfSamples);

random_device seeder;
default_random_engine generator { seeder() };

for (int i { 0 }; i < 6; ++i) {
    sample(cbegin(values), cend(values), begin(samples),
        numberOfSamples, generator);
    println("{:n}", samples);
}

Here is some possible output: The output is as follows:

1, 4, 7, 8, 9
1, 3, 4, 7, 9
2, 3, 4, 5, 7
3, 5, 6, 7, 9
1, 2, 3, 6, 7
1, 2, 4, 5, 8

reverse

The reverse() algorithm reverses the order of the elements in a range. The first element in the range is swapped with the last, the second with the second-to-last, and so on.

The basic form of reverse() runs in place and requires two arguments: a start and end iterator for the range. There is also a variant of the algorithm called reverse_copy() that copies its results to a new destination range and requires three arguments: a start and end iterator for the source range, and a start iterator for the destination range. The destination range must already be large enough to hold the new elements.

Here is an example using reverse():

vector<int> values;
populateContainer(values);
reverse(begin(values), end(values));
println("{:n}", values);

Shifting Elements

The shift_left() and shift_right() algorithms shift elements in a given range by moving them to their new position. shift_left() returns an iterator to the end of the new range, while shift_right() returns an iterator to the beginning of the new range. After calling either algorithm, you must use the returned iterator in a call to erase() to delete elements that fell off either end of the range. Here is an example:

vector values { 11, 22, 33, 44, 55 };
println("{:n}", values);

// Shift elements to the left by 2 positions.
auto newEnd { shift_left(begin(values), end(values), 2) };
// Resize the vector to its proper size.
values.erase(newEnd, end(values));
println("{:n}", values);

// Shift elements to the right by 2 positions.
auto newBegin { shift_right(begin(values), end(values), 2) };
// Resize the vector to its proper size.
values.erase(begin(values), newBegin);
println("{:n}", values);

The output is as follows:

11, 22, 33, 44, 55
33, 44, 55
33

Operational Algorithms

There are only two algorithms in this category: for_each() and for_each_n(). They execute a callback on each element of a range, for_each(), or on the first n elements of a range, for_each_n(). The callback can modify elements in the range if the given iterator type is non-const. The algorithms are mentioned here so you know they exist; however, it’s often easier and more readable to use a simple range-based for loop instead.

for_each

The following is an example using a generic lambda expression, printing the elements from a map:

map<int, int> myMap { { 4, 40 }, { 5, 50 }, { 6, 60 } };
for_each(cbegin(myMap), cend(myMap), [](const auto& p)
    { println("{} -> {}", p.first, p.second); });

The type of p is const pair<int, int>&. The output is as follows:

4 -> 40
5 -> 50
6 -> 60

The following example shows how to use the for_each() algorithm and a lambda expression to calculate the sum and the product of a range of elements at the same time. The lambda expression explicitly captures only those variables it needs. It captures them by reference; otherwise, changes made to sum and product in the lambda expression would not be visible outside the lambda.

vector<int> myVector;
populateContainer(myVector);

int sum { 0 };
int product { 1 };
for_each(cbegin(myVector), cend(myVector),
    [&sum, &product](int i){
        sum += i;
        product *= i;
});
println("The sum is {}", sum);
println("The product is {}", product);

This example can also be written with a functor in which you accumulate information that you can retrieve after for_each() has finished processing all the elements. For example, you can calculate both the sum and product of the elements in one pass by writing a functor SumAndProduct that tracks both at the same time:

class SumAndProduct
{
    public:
        void operator()(int value)
        {
            m_sum += value;
            m_product *= value;
        }

        int getSum() const { return m_sum; }
        int getProduct() const { return m_product; }
    private:
        int m_sum { 0 };
        int m_product { 1 };
};

int main()
{
    vector<int> myVector;
    populateContainer(myVector);

    SumAndProduct calculator;
    calculator = for_each(cbegin(myVector), cend(myVector), calculator);
    println("The sum is {}", calculator.getSum());
    println("The product is {}", calculator.getProduct());
}

You might be tempted to ignore the return value of for_each() yet still try to read information from calculator after the algorithm is finished. However, that doesn’t work because for_each() copies the functor, and at the end, this copy is returned from the call. You must capture the return value to ensure correct behavior.

Another option is to pass calculator by reference using std::ref(), see earlier in this chapter:

for_each(cbegin(myVector), cend(myVector), ref(calculator));

A final point about for_each() (that also applies to for_each_n() discussed in the next section) is that the callback is allowed to have a reference-to-non-const as parameter and modify it. That has the effect of changing values in the actual range. Here is an example:

vector values { 11, 22, 33, 44 };
// Double each element in the values vector.
for_each(begin(values), end(values), [](auto& value) { value *= 2; });
println("{:n}", values);

for_each_n

The for_each_n() algorithm requires a begin iterator of the range, the number of elements to iterate over, n, and a callback. It returns an iterator equal to begin + n. As usual, it does not perform any bounds checking. Here is an example that only iterates over the first two elements of a map:

map<int, int> myMap { { 4, 40 }, { 5, 50 }, { 6, 60 } };
for_each_n(cbegin(myMap), 2, [](const auto& p)
    { println("{} -> {}", p.first, p.second); });

Partition Algorithms

partition_copy() copies elements from a source to two different destinations. The destination for each element is selected based on the result of a predicate, either true or false. The value returned by partition_copy() is a pair of iterators: iterators referring to one-past-the-last-copied element in the first and second destination range. These returned iterators can be used in combination with erase() to remove excess elements from the two destination ranges, just as in the earlier copy_if() example. The following code snippet asks the user to enter a number of integers, which are then partitioned into two destination vectors: one for the even numbers and one for the odd numbers:

vector<int> values, vecOdd, vecEven;
populateContainer(values);
vecOdd.resize(size(values));
vecEven.resize(size(values));

auto pairIters { partition_copy(cbegin(values), cend(values),
    begin(vecEven), begin(vecOdd),
    [](int i){ return i % 2 == 0; }) };

vecEven.erase(pairIters.first, end(vecEven));
vecOdd.erase(pairIters.second, end(vecOdd));

println("Even numbers: {:n}", vecEven);
println("Odd numbers: {:n}", vecOdd);

The output can be as follows:

Enter a number (0 to stop): 11
Enter a number (0 to stop): 22
Enter a number (0 to stop): 33
Enter a number (0 to stop): 44
Enter a number (0 to stop): 0
Even numbers: 22, 44
Odd numbers: 11, 33

The partition() algorithm sorts a sequence such that all elements for which a predicate returns true are before all elements for which it returns false, without preserving the original order of the elements within each partition. The following example demonstrates how to partition a vector into all even numbers followed by all odd numbers:

vector<int> values;
populateContainer(values);
partition(begin(values), end(values), [](int i){ return i % 2 == 0; });
println("Partitioned result: {:n}", values);

The output can be as follows:

Enter a number (0 to stop): 55
Enter a number (0 to stop): 44
Enter a number (0 to stop): 33
Enter a number (0 to stop): 22
Enter a number (0 to stop): 11
Enter a number (0 to stop): 0
Partitioned result: 22, 44, 33, 55, 11

A few more partition algorithms are available as well. See Chapter 16 for a list.

Sorting Algorithms

The Standard Library provides several variations of sorting algorithms. A sorting algorithm reorders the contents of a container such that an ordering is maintained between sequential elements of the collection. Thus, it applies only to sequential collections. Sorting is not relevant for ordered associative containers because they already maintain elements in a sorted order. Sorting is not relevant for the unordered associative containers either, because they have no concept of ordering. Some containers, such as list and forward_list, provide their own sorting member functions, because these member functions can be implemented more efficiently than a generic sorting mechanism. Consequently, the generic sorting algorithms are most useful for vectors, deques, arrays, and C-style arrays.

The sort() algorithm sorts a range of elements in O(N log N) time in general. Following the application of sort() to a range, the elements in the range are in nondecreasing order (lowest to highest), according to operator<. If you don’t like that order, you can specify a different comparator, such as greater.

A variant of sort(), called stable_sort(), maintains the relative order of equal elements in a range, but it is less efficient than sort().

Here is an example of sort() using a transparent greater<> comparator:

vector<int> values;
populateContainer(values);
sort(begin(values), end(values), greater<>{});

There is also is_sorted(), returning true if a given range is sorted, and is_sorted_until(), returning an iterator such that everything before this iterator is sorted.

nth_element() is a powerful selection algorithm. Given a range of elements and an iterator to the nth element in that range, the algorithm rearranges the elements in the range such that the element in the position pointed to by nth is the element that would be in that position if the whole range were sorted. Additionally, it rearranges all elements such that all elements preceding the nth element are less than the new nth element, and the ones following it are greater than the new nth element. The interesting thing about this algorithm is that it does all this in linear time, O(n). Instead of using nth_element(), you could also just sort the whole range and then retrieve the data you are interested in, but that would result in a complexity that is linear logarithmic, O(n log n).

All this sounds complicated, so let’s see this algorithm in action. A first example is to find the third largest element in a given range. It assumes the user enters at least three values.

vector<int> values;
populateContainer(values);
// Find the third largest value.
nth_element(begin(values), begin(values) + 2, end(values), greater<>{});
println("3rd largest value: {}", values[2]);

Another example is to get the five largest elements from a range in sorted order. It assumes the user enters at least five values.

vector<int> values;
populateContainer(values);
// Get the 5 largest elements in sorted order.
nth_element(begin(values), begin(values) + 4, end(values), greater<>{});
// nth_element() has partitioned the elements, now sort the first subrange.
sort(begin(values), begin(values) + 5);
// And finally, output the sorted subrange.
for_each_n(begin(values), 5, [](const auto& element) { print("{}  ", element); });

Binary Search Algorithms

There are several search algorithms that work only on sequences that are sorted or that are at least partitioned on the element that is searched for. These algorithms are binary_search(), lower_bound(), upper_bound(), and equal_range(). Note that the associative containers, such as map and set, have equivalent member functions that you should use instead. See Chapter 18 for an example on how to use these member functions on such containers.

The lower_bound() algorithm finds the first element in a sorted range not less than (greater or equal to) a given value. It is often used to find at which position in a sorted vector a new value should be inserted so that the vector remains sorted. Here is an example:

vector<int> values;
populateContainer(values);

// Sort the container
sort(begin(values), end(values));
println("Sorted vector: {:n}", values);

while (true) {
    int number;
    print("Enter a number to insert (0 to stop): ");
    cin >> number;
    if (number == 0) { break; }

    auto iter { lower_bound(begin(values), end(values), number) };
    values.insert(iter, number);
    println("New vector: {:n}", values);
}

The binary_search() algorithm finds a matching element in logarithmic time instead of linear time. It requires a start and end iterator specifying the range to search in, a value to search, and optionally a comparator callback. It returns true if the value is found in the specified range, false otherwise. Binary search requires the range to be sorted and works by first comparing the middle element of the range. Depending on whether that middle element is greater than or less than the value to search, it continues by comparing the middle element of the left or right half of the range, respectively. This continues until the element is found. Basically, on each iteration, the range is halved, hence the logarithmic complexity. The following example demonstrates this algorithm:

vector<int> values;
populateContainer(values);

// Sort the container
sort(begin(values), end(values));

while (true) {
    print("Enter a number to find (0 to stop): ");
    int number;
    cin >> number;
    if (number == 0) { break; }
    if (binary_search(cbegin(values), cend(values), number)) {
        println("That number is in the vector.");
    } else {
        println("That number is not in the vector.");
    }
}

Set Algorithms

The set algorithms work on any sorted range. The includes() algorithm implements standard subset determination, checking whether all the elements of one sorted range are included in another sorted range, in any order.

The set_union(), set_intersection(), set_difference(), and set_symmetric_difference() algorithms implement the standard semantics of those operations. In set theory, the result of a union is all the elements in either set. The result of an intersection is all the elements that are in both sets. The result of a difference is all the elements in the first set but not the second. The result of a symmetric difference is the “exclusive or” of sets: all the elements in one, but not both, sets.

Make sure that your result range is large enough to hold the result of the operations. For set_union() and set\_symmetric_difference(), the result is at most the sum of the sizes of the two input ranges. For set_intersection(), the result is at most the size of the smallest input range, and for set_difference() it’s at most the size of the first range.

You can’t use common ranges from associative containers, including sets, to store the results because they don’t allow changes to their keys.

Let’s look at these set algorithms in action. First, a constrained DumpRange() function template is defined to write elements of a given range to the standard output stream; it is implemented as follows. ranges::subrange() converts a common range, given as a pair of iterators, to a range, which can then be passed to println().

template <forward_iterator Iterator>
void DumpRange(string_view message, Iterator begin, Iterator end)
{
    println("{}{:n}", message, ranges::subrange(begin, end));
}

With this helper function defined, here are examples on using the set algorithms:

vector<int> vec1, vec2, result;
println("Enter elements for set 1:");
populateContainer(vec1);
println("Enter elements for set 2:");
populateContainer(vec2);

// set algorithms require sorted ranges
sort(begin(vec1), end(vec1));
sort(begin(vec2), end(vec2));

println("Set 1: {:n}", vec1);
println("Set 2: {:n}", vec2);

if (includes(cbegin(vec1), cend(vec1), cbegin(vec2), cend(vec2))) {
    println("The second set is a subset of the first.");
}
if (includes(cbegin(vec2), cend(vec2), cbegin(vec1), cend(vec1))) {
    println("The first set is a subset of the second");
}

result.resize(size(vec1) + size(vec2));
auto newEnd { set_union(cbegin(vec1), cend(vec1), cbegin(vec2),
    cend(vec2), begin(result)) };
DumpRange("The union is: ", begin(result), newEnd);

newEnd = set_intersection(cbegin(vec1), cend(vec1), cbegin(vec2),
    cend(vec2), begin(result));
DumpRange("The intersection is: ", begin(result), newEnd);

newEnd = set_difference(cbegin(vec1), cend(vec1), cbegin(vec2),
    cend(vec2), begin(result));
DumpRange("The difference between set 1 and 2 is: ", begin(result), newEnd);

newEnd = set_symmetric_difference(cbegin(vec1), cend(vec1),
    cbegin(vec2), cend(vec2), begin(result));
DumpRange("The symmetric difference is: ", begin(result), newEnd);

Here is a sample run of the program:

Enter elements for set 1:
Enter a number (0 to stop): 5
Enter a number (0 to stop): 6
Enter a number (0 to stop): 7
Enter a number (0 to stop): 8
Enter a number (0 to stop): 0
Enter elements for set 2:
Enter a number (0 to stop): 8
Enter a number (0 to stop): 9
Enter a number (0 to stop): 10
Enter a number (0 to stop): 0
Set 1: 5, 6, 7, 8
Set 2: 8, 9, 10
The union is: 5, 6, 7, 8, 9, 10
The intersection is: 8
The difference between set 1 and set 2 is: 5, 6, 7
The symmetric difference is: 5, 6, 7, 9, 10

The merge() algorithm allows you to merge two sorted ranges together, while maintaining the sorted order. The result is a sorted range containing all the elements of both source ranges. It works in linear time. The following parameters are required:

• Start and end iterator of the first source range
• Start and end iterator of the second source range
• Start iterator of the destination range
• Optionally, a comparator callback

Without merge(), you could still achieve the same effect by concatenating the two ranges and applying sort() to the result, but that would be less efficient, O(N log N) instead of the linear complexity of merge().

Always ensure that you supply a big enough destination range to store the result of the merge!

The following example demonstrates merge():

vector<int> vectorOne, vectorTwo, vectorMerged;
println("Enter values for first vector:");
populateContainer(vectorOne);
println("Enter values for second vector:");
populateContainer(vectorTwo);

// Sort both containers
sort(begin(vectorOne), end(vectorOne));
sort(begin(vectorTwo), end(vectorTwo));

// Make sure the destination vector is large enough to hold the values
// from both source vectors.
vectorMerged.resize(size(vectorOne) + size(vectorTwo));

merge(cbegin(vectorOne), cend(vectorOne),
      cbegin(vectorTwo), cend(vectorTwo), begin(vectorMerged));

println("Merged vector: {:n}", vectorMerged);

Minimum/Maximum Algorithms

The min() and max() algorithms compare two or more elements of any type using operator< or a user-supplied binary predicate, returning a reference-to-const to the smallest or largest element, respectively. The minmax() algorithm returns a pair containing the minimum and maximum of two or more elements. These algorithms do not work with common ranges or ranges.

The min_element() and max_element() algorithms work with common ranges and return an iterator to the smallest or largest element in a range, respectively. The minmax_element() algorithm also works with a common range and returns a pair containing iterators to the smallest and largest element in a range.

The following program gives some examples:

int x { 4 }, y { 5 };
println("x is {} and y is {}", x, y);
println("Max is {}", max(x, y));
println("Min is {}", min(x, y));

// Using max() and min() on more than two values.
int x1 { 2 }, x2 { 9 }, x3 { 3 }, x4 { 12 };
println("Max of 4 elements is {}", max({ x1, x2, x3, x4 }));
println("Min of 4 elements is {}", min({ x1, x2, x3, x4 }));

// Using minmax().
auto p2 { minmax({ x1, x2, x3, x4 }) }; // p2 is of type pair<int, int>.
println("Minmax of 4 elements is <{},{}>", p2.first, p2.second);

// Using minmax() + structured bindings.
auto [min1, max1] { minmax({ x1, x2, x3, x4 }) };
println("Minmax of 4 elements is <{},{}>", min1, max1);

// Using minmax_element() + structured bindings.
vector values { 11, 33, 22 };
auto [min2, max2] { minmax_element(cbegin(values), cend(values)) };
println("minmax_element() result: <{},{}>", *min2, *max2);

Here is the program output:

x is 4 and y is 5
Max is 5
Min is 4
Max of 4 elements is 12
Min of 4 elements is 2
Minmax of 4 elements is <2,12>
Minmax of 4 elements is <2,12>
minmax_element() result: <11,33>

Note

Sometimes you might encounter non-standard macros to find the minimum and maximum. For example, the GNU C Library (glibc) has macros MIN() and MAX(), while the Windows.h header file defines min() and max() macros. Because these are macros, they have the potential to evaluate one of their arguments twice, whereas std::min() and std::max() evaluate each argument exactly once. Make sure you always use the C++ versions, std::min() and std::max().

std::clamp() is a little helper function, defined in <algorithm>, that you can use to make sure that a value (v) is between a given minimum (lo) and maximum (hi). It returns a reference to lo if v < lo, returns a reference to hi if v > hi, and otherwise returns a reference to v. Here is an example:

println("{}", clamp(-3, 1, 10));
println("{}", clamp(3, 1, 10));
println("{}", clamp(22, 1, 10));

The output is as follows:

1
3
10

Parallel Algorithms

C++ supports executing more than 60 Standard Library iterator-based algorithms in parallel to improve their performance. Examples include std::for_each(), all_of(), copy(), count_if(), find(), replace(), search(), sort(), transform(), and many more.

Algorithms that support parallel execution have an optional execution policy as their first parameter. The execution policy allows you to specify whether an algorithm is allowed to be vectorized and/or executed in parallel. When a compiler vectorizes code, it replaces several CPU instructions with a single vector CPU instruction. A vector instruction performs some operation on multiple pieces of data with a single hardware instruction. These are also known as single instruction multiple data (SIMD) instructions. There are four standard execution policy types, and corresponding global instances of those types, all defined in <execution> in the std::execution namespace:

EXECUTION POLICY TYPE	GLOBAL INSTANCE	DESCRIPTION
sequenced_policy	seq	The algorithm is not allowed to parallelize or vectorize its execution.
parallel_policy	par	The algorithm is allowed to parallelize but not vectorize its execution.
parallel_unsequenced_policy	par_unseq	The algorithm is allowed to parallelize and vectorize its execution. It’s also allowed to migrate its execution across threads.
unsequenced_policy	unseq	The algorithm is allowed to vectorize but not parallelize its execution.

A Standard Library implementation is free to add additional execution policies.

Let’s look at how you can specify an execution policy for an algorithm. Here is an example of sorting the contents of a vector using a parallel policy:

sort(execution::par, begin(values), end(values));

Callbacks passed to parallel algorithms are not allowed to throw any uncaught exceptions. Doing so will trigger a call to std::terminate() which terminates the application.

For algorithms executing with parallel_unsequenced_policy or unsequenced_policy, function calls to callbacks are allowed to get interleaved; that is, they are unsequenced. This helps the compiler to vectorize the code. However, this also means there are a lot of restrictions on what a function callback can do. For example, it cannot allocate/deallocate memory, acquire mutexes, use non-lock-free std::atomics (see Chapter 27, “Multithreaded Programming with C++”), and more. For the other standard policies, the function calls are sequenced, but in an indeterminate sequence. Such policies do not impose restrictions on what the function callbacks can do.

Parallel algorithms do not take any measures to prevent data races and deadlocks, so it is your responsibility to avoid them when executing an algorithm in parallel. Data race and deadlock prevention are discussed in detail in Chapter 27 in the context of multithreaded programming.

Parallel overloads of algorithms are not constexpr, even if the non-parallel overloads are.

The return type of some of the parallel overloads of algorithms can be slightly different compared to the non-parallel overloads. For example, the non-parallel overload of for_each() returns the supplied callback, while the parallel overload does not return anything. Consult your favorite Standard Library Reference for a complete overview of all algorithms, including their parameter and return types, for both the parallel and non-parallel overloads.

Note

When working with large datasets or when you have to perform a large amount of work on each individual element in a dataset, use the parallel overloads of algorithms to increase performance.

Keep in mind, though, that using a parallel overload of an algorithm does not guarantee that its execution will be faster compared to a non-parallel overload. For example, when processing a small number of elements, a parallel overload might actually be slower due to the overhead that parallelization brings with it. Another example is when your container does not support random access iterators. To decide whether to use a parallel or a sequential overload for a specific use case, you must profile both and pick the most performant one. Chapter 29, “Writing Efficient C++,” discusses profiling.

Numerical Processing Algorithms

You’ve already seen an example of one numerical processing algorithm: accumulate(). The following sections give examples of some more numerical algorithms.

iota

The iota() algorithm, defined in <numeric>, generates a sequence of values in a specified range starting with a specified value and applying operator++ to generate each successive value. The following example shows how to use this algorithm on a vector of integers, but it works on any element type that implements operator++:

vector<int> values(10);
iota(begin(values), end(values), 5);
println("{:n}", values);

The output is as follows:

5, 6, 7, 8, 9, 10, 11, 12, 13, 14

Reduce Algorithms

The Standard Library has four reduce algorithms: accumulate(), reduce(), inner_product(), and transform_reduce(), all defined in <numeric>. The accumulate() algorithm is discussed earlier in this chapter. All reduce algorithms repeatedly apply an operator to combine two elements of a given range or two given ranges, until only one value remains. These are also called accumulate, aggregate, compress, inject, or fold algorithms.

reduce

std::accumulate() is one of the few algorithms that does not support parallel execution. Instead, you need to use std::reduce() to calculate a generalized sum with the option to execute it in parallel.

For example, the following code calculates the same sum twice, once with accumulate() and once with reduce(). The latter runs a parallel and vectorized version and thus can be much faster on big input ranges. They both require a begin and end iterator of the range, and an initial value, 0 in this example.

vector values { 1, 3, 6, 4, 6, 9 };
int result1 { accumulate(cbegin(values), cend(values), 0) };
int result2 { reduce(execution::par_unseq, cbegin(values), cend(values), 0) };

In general, both accumulate() and reduce() calculate the following sum for a range of elements [x0, xn), with a given initial value Init, and a given binary operator Ѳ:

• Init Ѳ x0 Ѳ x1 Ѳ … Ѳ xn−1

By default, the binary operator for accumulate() is operator+, and for reduce() it is std::plus.

inner_product

inner_product() calculates the inner product of two sequences. For example, the inner product in the following example is calculated as (1*9)+(2*8)+(3*7)+(4*6), which is 70:

vector v1 { 1, 2, 3, 4 };
vector v2 { 9, 8, 7, 6 };
println("{}", inner_product(cbegin(v1), cend(v1), cbegin(v2), 0));

inner_product() can accept two additional parameters, which are the two binary operators used in the calculation, by default operator+ and operator*.

inner_product() is another algorithm that does not support parallel execution. If parallel execution is required, use transform_reduce(), discussed next.

transform_reduce

transform_reduce() supports parallel execution and can be executed on a single range of elements or on two ranges. In its first version, it calculates the following sum for a range of elements [x0, xn), with a given initial value Init, a given unary function f, and a given binary operator Ѳ, std::plus by default:

• Init Ѳ f(x0) Ѳ f(x1) Ѳ … Ѳ f(xn−1)

When executing on two ranges, it behaves the same as inner_product(), except by default it uses the binary operators std::plus and std::multiplies, respectively, instead of operator+ and operator*.

Scan Algorithms

Scan algorithms are also called prefix sum, cumulative sum, or partial sum algorithms. The result of such an algorithm applied to a range is another range containing sums of the elements of the source range.

There are five scan algorithms: exclusive_scan(), inclusive_scan()/partial_sum(), transform_exclusive_scan(), and transform_inclusive_scan(), all defined in <numeric>.

The following table shows which sums [y0, yn) are calculated by exclusive_scan() and by inclusive_scan()/partial_sum() for a range of elements [x0, xn), with a given initial value Init (0 for partial_sum()), and a given binary operator Ѳ:

EXCLUSIVE_SCAN()	INCLUSIVE_SCAN()/PARTIAL_SUM()
y0 = Init y1 = Init Ѳ x0 y2 = Init Ѳ x0 Ѳ x1 … yn-1 = Init Ѳ x0 Ѳ x1 Ѳ … Ѳ xn-2	y0 = Init Ѳ x0 y1 = Init Ѳ x0 Ѳ x1 … yn-1 = Init Ѳ x0 Ѳ x1 Ѳ … Ѳ xn-1

transform_exclusive_scan() and transform_inclusive_scan() both first apply a unary function to the elements before calculating the generalized sum, similar to how transform_reduce() applies a unary function to the elements before reducing.

Note that these scan algorithms, except partial_sum(), can accept an optional execution policy to parallelize their execution. The order of evaluation is non-deterministic, while it is guaranteed left to right for partial_sum() and accumulate(). That’s also the reason why partial_sum() and accumulate() cannot be parallelized.

Constrained Algorithms

Most of the algorithms have constrained variants in the std::ranges namespace. Consult your favorite Standard Library reference to find out exactly which constrained algorithms are available. These algorithms are also defined in <algorithm> and <numeric>, but unlike the equivalent unconstrained algorithms in the std namespace, the constrained variants use concepts (see Chapter 12) to constrain their template type parameters. This means you get better error messages from your compiler if you pass invalid arguments. For example, the sort() algorithm requires random-access iterators. Passing a pair of std::list iterators as arguments to std::sort() can result in a bunch of cryptic errors from your compiler. With the constrained ranges::sort() algorithm, the compiler tells you that the passed iterators are not random access.

Another benefit of these constrained algorithms is that they work on a sequence of elements given as either a begin and end iterator pair, or as a range. Additionally, they can support projections. Ranges and projections are discussed in Chapter 17.

Note

Constrained algorithms do not support parallel execution yet, so they do not accept a parallel execution policy as an argument.

Let’s look at a few of these constrained algorithms in action.

Constrained find

As with all constrained algorithms, the std::ranges::find() constrained algorithm can be called with a pair of iterators or with a range as argument. Calling it with an iterator pair works the same way as the unconstrained std::find():

vector values {1, 2, 3};
auto result { ranges::find(cbegin(values), cend(values), 2) };
if (result != cend(values)) { println("{}", *result); }

However, if you want to apply an algorithm on all elements of a container, as is often the case, it’s rather tedious to always have to specify a begin/end iterator pair to define your sequence. With ranges support, you can just specify a range with a single argument. The previous call to find() can be written more readable and less error prone as follows:

auto result { ranges::find(values, 2) };

Constrained generate

Here is another example, this time using the constrained std::ranges::generate() algorithm. The code first creates a lambda expression that simply returns a next number. Then it creates a vector of 10 integers and uses the generate() algorithm together with the nextNumber lambda expression to fill the vector with increasing integers. The contents of the vector are printed to the console, followed by four more invocations of the nextNumber lambda expression.

auto nextNumber { [counter = 0] () mutable { return ++counter; } };
vector<int> values(10);
ranges::generate(values, nextNumber);
println("Vector contains {:n}", values);
print("Four more next numbers: ");
for (unsigned i { 0 }; i < 4; ++i) { print("{}, ", nextNumber()); }

The output is as follows:

Vector contains 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Four more next numbers: 1, 2, 3, 4,

As the output demonstrates, generate() makes a copy of the lambda expression. This can be avoided using std::ref(), as explained earlier in this chapter, to pass a reference to the lambda expression instead of making a copy:

ranges::generate(values, ref(nextNumber));

The output now is:

Vector contains 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Four more next numbers: 11, 12, 13, 14,

Constrained for_each

The following example demonstrates using the std::ranges::for_each() algorithm on a filtered view created with std::ranges::views::filter (defined in <ranges>). Only the even values from the vector are kept in the view. This filtered view is subsequently passed to for_each(), which multiplies the values by 10. Outputting the contents of the vector confirms that only the even values in the vector have been multiplied.

vector values { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
println("Before: {:n}", values);
ranges::for_each(values | views::filter([](int value) { return value % 2 == 0; }),
    [](int& value) { value *= 10; });
println("After:  {:n}", values);

The output is as follows:

Before: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
After:  1, 20, 3, 40, 5, 60, 7, 80, 9, 100

Constrained-Only Algorithms

C++23 introduces new algorithms that are available only as constrained algorithms. They are all defined in the std::ranges namespace. These include the non-modifying sequence algorithms contains(), contains_subrange(), starts_with(), ends_with(), find_last(), find_last_if(), and find_last_if_not(), and the fold algorithms fold_left(), fold_left_first(), fold_right(), fold_right_last(), fold_left_with_iter(), and fold_left_first_with_iter().

Here is an example of some of the non-modifying sequence algorithms:

vector values { 11, 22, 33, 44, 55 };
vector v { 11, 22 };
println("{} contains 33 = {}", values, ranges::contains(values, 33));
println("{} contains {} = {}", values, v, ranges::contains_subrange(values, v));
println("{} starts with {} = {}", values, v, ranges::starts_with(values, v));

This produces the following output:

[11, 22, 33, 44, 55] contains 33 = true
[11, 22, 33, 44, 55] contains [11, 22] = true
[11, 22, 33, 44, 55] starts with [11, 22] = true

The following is an example of two of the folding algorithms. fold_left() and fold_right() accept an initial value as one of their arguments, while fold_left_first() uses the first element in a given range as the starting value, and fold_right_last() uses the last element in a given range as the starting value. The example demonstrates the difference between a left and a right fold. The fold_left_first() and fold_right_last() algorithms return an optional, so value_or() is used to handle an empty result.

vector values { 500.0, 10.0, 2.0 };
auto foldedLeft { ranges::fold_left_first(values, divides<>{}) };
auto foldedRight { ranges::fold_right_last(values, divides<>{}) };
println("foldedLeft = {}", foldedLeft.value_or(0.0));
println("foldedRight = {}", foldedRight.value_or(0.0));

The output is:

foldedLeft = 25
foldedRight = 100

The left fold operation calculates ((500.0 / 10.0) / 2.0), while the right fold operation calculates (500.0 / (10.0 / 2.0)).

See your favorite Standard Library reference for more details on all these constrained algorithms.

SUMMARY

This chapter provided coding examples for a selection of Standard Library algorithms. It also showed you that combining these algorithms with lambda expressions allows you to write elegant and easy-to-understand code. Together with the previous chapters, I hope you gained an appreciation for the usefulness and the power of the Standard Library containers and algorithms.

The following chapters continue the discussion of other C++ Standard Library functionality. Chapter 21 discusses regular expressions. Chapter 22 explains the date and time support. Chapter 23 shows how to generate random numbers. Chapter 24 covers a number of additional vocabulary types that are available for you to use. Finally, Chapter 25 gives a taste of some more advanced features, such as allocators and how to write your own Standard Library–compliant algorithms and containers.

EXERCISES

By solving the following exercises, you can practice the material discussed in this chapter. Solutions to all exercises are available with the code download on the book’s website at www.wiley.com/go/proc++6e. However, if you are stuck on an exercise, first reread parts of this chapter to try to find an answer yourself before looking at the solution from the website.

1. Exercise 20-1: Use your favorite Standard Library Reference to look up the parameters for the ranges::fill() algorithm. Ask the user for a number, and then use fill() to fill a vector of 10 integers with the given number. Write the contents of the vector to the standard output for verification. Provide a second solution using the std::fill() algorithm.
2. Exercise 20-2: Look back at the “Permutation Algorithms” section in Chapter 16, and then use a Standard Library Reference to figure out their parameters. Write a program that asks the user to enter a few numbers, and then use one of the permutation algorithms to print out all possible permutations of those numbers. Provide two solutions, one using only constrained algorithms and a second using legacy, unconstrained algorithms.
3. Exercise 20-3: Write a function called trim() that removes all whitespace at the beginning and end of a given string and returns the result. Use only constrained algorithms. Tip: to check if a character c is a whitespace character, you can use std::isspace(c), defined in <cctype>. It returns a non-zero value if c is a whitespace character, 0 otherwise. Test your implementation with several strings in your main() function.
4. Exercise 20-4: Use a constrained algorithm to create a vector containing the numbers 1 to 20. Then, using a single constrained algorithm, copy all even and odd numbers to evens and odds containers without doing any space reservation on those containers, and, still with this single algorithm call, make sure the even numbers are in ascending sequence, while the odd numbers are in descending sequence. Carefully choose the type for the evens and odds containers. Hint: maybe there is something in Chapter 17 that you could use.
5. Exercise 20-5: The solution for Exercise 20-3 uses only constrained algorithms. Can you do the same using only legacy, unconstrained algorithms?