Lesson 13: Algorithms

Lesson 0013 — A Tour of C++, Chapter 13 (§13.1–§13.7)

A data structure, such as a list or a vector, is not very useful on its own. To use one, we need operations for basic access — adding and removing elements — and, beyond that, we rarely just store objects in a container: we sort them, print them, extract subsets, remove elements, search for objects, and so on. Consequently, the standard library provides the most common algorithms for containers in addition to the most common container types. The thread running through this chapter: an algorithm is a function template operating on (half-open) sequences of elements, sequences are identified by pairs of iterators — not by containers — and iterators are the seam that separates data storage from computation.

13.1 Introduction

The simplest example: sort a vector<Entry> and place a copy of each unique element on a list:

void f(vector<Entry>& vec, list<Entry>& lst) {
    sort(vec.begin(), vec.end());          // use < for order
    unique_copy(vec.begin(), vec.end(), lst.begin());   // don't copy adjacent equal elements
}

bool operator<(const Entry& x, const Entry& y) {   // less than
    return x.name < y.name;                 // order Entries by their names
}

A standard algorithm is expressed in terms of (half-open) sequences: a sequence is represented by a pair of iterators specifying the first element and the one-beyond-the-last element. For writing (output), we need only to specify the first element to be written; if more than one element is written, the elements following that initial element will be overwritten. Thus, to avoid errors, lst must have at least as many elements as there are unique values in vec. The standard library doesn't offer an abstraction to support range-checked writing into a container — but we can define one:

template<typename C> class Checked_iter {
public:
    using value_type = typename C::value_type;
    using difference_type = int;
    Checked_iter() { throw Missing_container{}; }   // concept forward_iterator requires a default constructor
    Checked_iter(C& cc) : pc{&cc} {}
    Checked_iter(C& cc, typename C::iterator pp) : pc{&cc}, p{pp} {}
    Checked_iter& operator++() { check_end(); ++p; return *this; }
    Checked_iter operator++(int) { check_end(); auto t{*this}; ++p; return t; }
    value_type& operator*() const { check_end(); return *p; }
    bool operator==(const Checked_iter& a) const { return p==a.p; }
    bool operator!=(const Checked_iter& a) const { return p!=a.p; }
private:
    void check_end() const { if (p == pc->end()) throw Overflow{}; }
    C* pc {};    // default initialize to nullptr
    typename C::iterator p {};
};

vector<int> v1 {1, 2, 3};          // three elements
vector<int> v2(2);                 // two elements
copy(v1, v2.begin());              // will overflow
copy(v1, Checked_iter{v2});        // will throw

If we had wanted to place the unique elements in a new list, we could use back_inserter():

list<Entry> f(vector<Entry>& vec) {
    list<Entry> res;
    sort(vec.begin(), vec.end());
    unique_copy(vec.begin(), vec.end(), back_inserter(res));   // append to res
    return res;
}

The call back_inserter(res) constructs an iterator for res that adds elements at the end of the container, extending the container to make room. This saves us from first having to allocate a fixed amount of space and then filling it — the standard containers plus back_inserter()s eliminate the need to use error-prone, explicit C-style memory management using realloc(). The standard-library list has a move constructor (§6.2.2) that makes returning res by value efficient (even for lists of thousands of elements).

When the pair-of-iterators style feels tedious, use the range versions: sort(vec) is equivalent to sort(vec.begin(),vec.end()) (§13.5). Similarly, a range-for loop is roughly equivalent to a C-style loop using iterators directly — and in addition to being simpler and less error-prone, the range-for version is often also more efficient.

13.2 Use of Iterators

For a container, a few iterators referring to useful elements can be obtained; begin() and end() are the best examples. In addition, many algorithms return iterators. For example, find looks for a value in a sequence and returns an iterator to the element found:

bool has_c(const string& s, char c) {          // does s contain the character c?
    auto p = find(s.begin(), s.end(), c);
    if (p != s.end()) return true;
    else return false;
}
// Like many standard-library search algorithms, find returns end() to indicate "not found".
bool has_c(const string& s, char c) { return find(s, c) != s.end(); }   // range version

A more interesting exercise: find the location of all occurrences of a character in a string, returned as a vector<string::iterator>. Returning a vector is efficient because vector provides move semantics (§6.2.1):

vector<string::iterator> find_all(string& s, char c) {   // find all occurrences of c in s
    vector<string::iterator> res;
    for (auto p = s.begin(); p != s.end(); ++p)
        if (*p == c) res.push_back(p);
    return res;
}

void test() {
    string m {"Mary had a little lamb"};
    for (auto p : find_all(m, 'a'))
        if (*p != 'a') cerr << "a bug!\n";
}

Iterators and standard algorithms work equivalently on every standard container for which their use makes sense, so we can generalize:

template<typename C, typename V>   // find all occurrences of v in c
vector<typename C::iterator> find_all(C& c, V v) {
    vector<typename C::iterator> res;
    for (auto p = c.begin(); p != c.end(); ++p)
        if (*p == v) res.push_back(p);
    return res;
}

The typename is needed to inform the compiler that C::iterator is supposed to be a type and not a value of some type, say, the integer 7. Alternatively, we could have returned a vector of ordinary pointers to the elements, using a range-for and the standard-library range_value_t (§16.4.4) to name the element type — with a simplified template<typename T> using range_value_type_t = T::value_type;. The same find_all() then works for a string, a list<int>, and a vector<string>, and we can even modify found elements through the returned iterators (*p = "vert";).

Iterators are used to separate algorithms and containers. An algorithm operates on its data through iterators and knows nothing about the container in which the elements are stored. Conversely, a container knows nothing about the algorithms operating on its elements; all it does is supply iterators upon request (e.g., begin() and end()). This model of separation between data storage and algorithm delivers very general and flexible software.

13.3 Iterator Types

What are iterators really? Any particular iterator is an object of some type, and there are many different iterator types — an iterator needs to hold the information necessary for doing its job for a particular container type. These types can be as different as the containers and the specialized needs they serve:

• A vector's iterator could be an ordinary pointer, because a pointer is quite a reasonable way of referring to an element of a vector.
• Alternatively, a vector iterator could be implemented as a pointer to the vector plus an index — using such an iterator allows range checking.
• A list iterator must be something more complicated than a simple pointer to an element, because an element of a list in general does not know where the next element is. Thus, a list iterator might be a pointer to a link.

What is common for all iterators is their semantics and the naming of their operations: applying ++ to any iterator yields an iterator that refers to the next element; applying * yields the element to which the iterator refers. In fact, any object that obeys a few simple rules like these is an iterator. Iterator is a general idea, a concept (§8.2); different kinds of iterators are made available as standard-library concepts, such as forward_iterator and random_access_iterator (§14.5). Furthermore, users rarely need to know the type of a specific iterator; each container "knows" its iterator types and makes them available under the conventional names iterator and const_iterator. In some cases an iterator is not a member type, so the standard library offers iterator_t<X> that works wherever X's iterator is defined.

13.3.1 Stream Iterators

Containers are not the only place where we find sequences of elements. An input stream produces a sequence of values, and we write a sequence of values to an output stream — so the notion of iterators can be usefully applied to input and output.

ostream_iterator<string> oo {cout};   // write strings to cout
*oo = "Hello, ";        // meaning cout << "Hello, "
++oo;
*oo = "world!\n";       // meaning cout << "world!\n"

The effect of assigning to *oo is to write the assigned value to cout; the ++oo mimics writing into an array through a pointer. That way, we can use algorithms on streams: copy(v, oo) writes all of v to cout.

Similarly, an istream_iterator treats an input stream as a read-only container — we must specify the stream and the type of values expected (istream_iterator<string> ii {cin};). Input iterators are used in pairs, so we must provide an istream_iterator to indicate the end of input — this is the default istream_iterator<string> eos {};. Typically they are not used directly but provided as arguments to algorithms. The classic file-word-sort program:

int main() {
    string from, to;
    cin >> from >> to;                          // get source and target file names
    ifstream is {from};                          // input stream for file "from"
    istream_iterator<string> ii {is};            // input iterator for stream
    istream_iterator<string> eos {};             // input sentinel
    ofstream os {to};                            // output stream for file "to"
    ostream_iterator<string> oo {os, "\n"};      // output iterator plus a separator
    vector<string> b {ii, eos};                  // b is a vector initialized from input
    sort(b);                                     // sort the buffer
    unique_copy(b, oo);                          // copy the buffer to output, discard replicated values
    return !is.eof() || !os;                     // return error state (§1.2.1, §11.4)
}

I used the range versions of sort() and unique_copy(); I could have used iterators directly, e.g. sort(b.begin(),b.end()), as is common in older code. Remember that to use both a traditional iterator version of a standard-library algorithm and its ranges counterpart, we need to either explicitly qualify the call of the range version or use a using-declaration (§9.3.2):

copy(v, oo);            // potentially ambiguous
ranges::copy(v, oo);    // OK
using ranges::copy;     // copy(v, oo) OK from here on
copy(v, oo);            // OK

An ifstream is an istream attached to a file (§11.7.2); an ofstream is an ostream attached to a file; the ostream_iterator's second argument is used to delimit output values. The program is longer than it needs to be — a more elegant solution doesn't store duplicates at all, by keeping the strings in a set, which doesn't keep duplicates and keeps its elements in order (§12.5). Then two lines using a vector collapse into one using a set, and unique_copy() is replaced by the simpler copy():

int main() {
    string from, to;
    cin >> from >> to;
    ifstream is {from};
    ofstream os {to};
    set<string> b {istream_iterator<string>{is}, istream_iterator<string>{}};   // read input
    copy(b, ostream_iterator<string>{os, "\n"});                               // copy to output
    return !is.eof() || !os;
}

13.4 Use of Predicates

In the examples so far, the algorithms have simply "built in" the action to be done for each element of a sequence. However, we often want to make that action a parameter to the algorithm. For example, find provides a convenient way of looking for a specific value; a more general variant, find_if, looks for an element that fulfills a specified requirement — a predicate. For instance, we might want to search a map for the first value larger than 42. A map allows us to access its elements as a sequence of (key,value) pairs, so we search a map<string,int>'s sequence for a pair<const string,int> where the int is greater than 42. Greater_than is a function object (§7.3.2) holding the value (42) to be compared against a map entry:

struct Greater_than {
    int val;
    Greater_than(int v) : val{v} {}
    bool operator()(const pair<string,int>& r) const { return r.second > val; }
};
auto p = find_if(m, Greater_than{42});   // m is a map<string,int>

// Alternatively and equivalently, a lambda expression (§7.3.2):
auto p = find_if(m, [](const auto& r) { return r.second > 42; });

A predicate should not modify the elements to which it is applied.

13.5 Algorithm Overview

A general definition of an algorithm: "a finite set of rules which gives a sequence of operations for solving a specific set of problems [and] has five important features: Finiteness, Definiteness, Input, Output, Effectiveness" [Knuth, 1968, §1.1]. In the context of the C++ standard library, an algorithm is a function template operating on sequences of elements. The standard library provides many dozens of algorithms, defined in namespace std and presented in the <algorithm> and <numeric> headers. These all take sequences as inputs; a half-open sequence from b to e is referred to as [b:e). A few examples:

For each algorithm taking a [b:e) range, the <ranges> library offers a version that takes a range. These algorithms — and many more (e.g., §17.3) — can be applied to elements of containers, strings, and built-in arrays. Two structural facts to remember:

• Some algorithms, such as replace() and sort(), modify element values, but no algorithm adds or subtracts elements of a container. The reason: a sequence does not identify the container that holds the elements of the sequence. To add or delete elements, you need something that knows about the container — e.g., a back_inserter (§13.1) — or directly refers to the container itself (e.g., push_back() or erase(), §12.2).
• Lambdas are very common as operations passed as arguments, e.g. for_each(v, [](int& x){ x = x*x; }); to square every element, or for_each(v.begin(), v.begin()+3, [](int& x){ x = sqrt(x); }); to transform just the first three.

The standard-library algorithms tend to be more carefully designed, specified, and implemented than the average hand-crafted loop. Know them and use them in preference to code written in the bare language.

13.6 Parallel Algorithms

When the same task is to be done to many data items, we can execute it in parallel on each data item, provided the computations on different data items are independent:

• parallel execution: tasks are done on multiple threads (often running on several processor cores);
• vectorized execution: tasks are done on a single thread using vectorization, also known as SIMD ("Single Instruction, Multiple Data").

The standard library offers support for both, and we can be specific about wanting sequential execution. In <execution>, in namespace execution, we find: seq (sequential execution), par (parallel execution, if feasible), unseq (unsequenced/vectorized execution, if feasible), and par_unseq (parallel and/or unsequenced vectorized execution, if feasible). Consider std::sort():

sort(v.begin(), v.end());              // sequential
sort(seq, v.begin(), v.end());         // sequential (same as the default)
sort(par, v.begin(), v.end());         // parallel
sort(par_unseq, v.begin(), v.end());   // parallel and/or vectorized

Whether it is worthwhile to parallelize and/or vectorize depends on the algorithm, the number of elements in the sequence, the hardware, and the utilization of that hardware by programs running on it. Consequently, the execution policy indicators are just hints: a compiler and/or run-time scheduler will decide how much concurrency to use. This is all nontrivial, and the rule against making statements about efficiency without measurement is very important here. Unfortunately, the range versions of the parallel algorithms are not yet in the standard — but if we need them, they are easy to define:

void sort(auto pol, random_access_range auto& r) { sort(pol, r.begin(), r.end()); }

Most standard-library algorithms, including all in the §13.5 table except equal_range, can be requested to be parallelized and vectorized using par and par_unseq as for sort(). Why not equal_range()? Because so far nobody has come up with a worthwhile parallel algorithm for that. Many parallel algorithms are used primarily for numeric data (see §17.3.1). When requesting parallel execution, be sure to avoid data races (§18.2) and deadlock (§18.3).

13.7 Advice

Here is a summary of the guidance from this chapter. All 11 items, with the section where each is introduced. The C++ Core Guidelines link each item to its recommended practice.

Retrieval Quiz

Notes

Primary source: Stroustrup, B. (2022). A Tour of C++, 3rd ed., Chapter 13: "Algorithms." Addison-Wesley.
Reference: Chapter 1–12 Quick Reference & Glossary — keep it beside you while you study.
Recommended supplement: cppreference on algorithms library, iterators library, and execution policies.

Questions? Ask your agent — your teacher — about anything unclear: why end() is the "not found" convention, when a plain pointer can be a vector iterator, or whether a loop you just wrote could be a standard algorithm. Follow-ups are expected, not optional.

Chapters

1. Lesson 1: The Basics (Ch. 1)
2. Lesson 2: User-Defined Types (Ch. 2)
3. Lesson 3: Separate Compilation (Ch. 3)
4. Lesson 4: Error Handling (Ch. 4)
5. Lesson 5: Classes (Ch. 5)
6. Lesson 6: Essential Operations (Ch. 6)
7. Lesson 7: Templates (Ch. 7)
8. Lesson 8: Concepts and Generic Programming (Ch. 8)
9. Lesson 9: Library Overview (Ch. 9)
10. Lesson 10: Strings and Regular Expressions (Ch. 10)
11. Lesson 11: Input and Output (Ch. 11)
12. Lesson 12: Containers (Ch. 12)
13. Lesson 13: Algorithms (Ch. 13 — this lesson)
14. Lesson 14: Ranges (Ch. 14)
15. Lesson 15: Pointers and Containers (Ch. 15)
16. Lesson 16: Utilities (Ch. 16)
17. Lesson 17: Numerics (Ch. 17)
18. Lesson 18: Concurrency (Ch. 18)
19. Lesson 19: History and Compatibility (Ch. 19)