Understanding Algorithms in C++

The standard library provides dozens of algorithms, defined in namespace std and presented in the <algorithm> header.

Programming

Where the Standard Algorithms Live

The C++ standard library provides dozens of ready-made algorithms. Each one performs a specific job on a sequence of elements, such as finding a value, counting matches, or sorting. You do not have to write these loops yourself, because the library already supplies them.

Definition

A standard library algorithm is a function template provided by the C++ standard library that operates on a sequence described by bounds. The algorithms are defined in namespace std and presented in the <algorithm> header, so a program that uses them includes that header and refers to them with the std:: prefix, as in std::find.

The namespace and the header work together. The header tells the compiler where the declarations come from, and the namespace keeps the names separate from other code. The individual algorithm name, such as find or count, is what you choose for the job you need done.

Watching Two Algorithms Work

Before any rules are defined, it helps to see an algorithm do something. The program below calls find and count on a small vector. Read it first and predict the four numbers it prints. The rest of this article explains the rule that produces them.

cpp

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {4, 7, 1, 7, 9, 7};
    auto b = v.begin();
    auto e = v.end();

    auto pos = std::find(b, e, 7);
    std::cout << (pos - b) << "\n";

    std::cout << std::count(b, e, 7) << "\n";

    std::cout << std::count(v.begin(), v.begin() + 3, 7) << "\n";

    std::cout << (std::find(v.begin(), v.begin() + 1, 7) == v.begin() + 1) << "\n";
}

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {4, 7, 1, 7, 9, 7};
    auto b = v.begin();
    auto e = v.end();

    auto pos = std::find(b, e, 7);
    std::cout << (pos - b) << "\n";

    std::cout << std::count(b, e, 7) << "\n";

    std::cout << std::count(v.begin(), v.begin() + 3, 7) << "\n";

    std::cout << (std::find(v.begin(), v.begin() + 1, 7) == v.begin() + 1) << "\n";
}

Notes on the code

The header <algorithm> supplies find and count, and the calls use the std:: prefix
b and e are the two bounds that describe the whole vector
find returns an iterator to the first match, so pos - b gives its index
count returns how many elements in the range equal 7
The third call uses a smaller range that stops before index 3
The fourth call searches a range with no 7 in it and compares the result to the end bound

What do you think happens?

What four values does the program print, one per line?

Reveal answer

Answer:

1, 3, 1, 1

The first 7 is at index 1, so find reports position 1. The whole vector holds three 7s, so count returns 3. The range [0 : 3) covers 4, 7, and 1, which holds one 7. The last line compares the result of a search over [0 : 1), which contains only 4, to the end bound, so the comparison is true and prints 1.

Half-Open Sequences and Their Bounds

All standard library algorithms take sequences as inputs, and a sequence is described by bounds. The usual pair of bounds is called b for the beginning and e for the end. The sequence written $[b : e)$ is half-open: it includes its beginning and excludes its end.

The element at b is part of the sequence. Moving forward one position at a time, every position is included until e is reached, and e itself is not part of the sequence. Because e is excluded, the two bounds are not symmetric: b belongs to the range and e does not.

Given the vector {4, 7, 1, 7, 9, 7}, the bound b points at position 0, and the bound e points one position past the last element. The range [b : e) covers every element from position 0 through position 5.

Rule

The count of elements is $e - b$. For the vector above, b sits at position 0 and e sits at position 6, so $e - b = 6$, which matches the six values stored. The formula also explains why an empty range happens when b and e are equal: then $e - b = 0$ and there are no elements to examine.

Tracing find Through a Range

Because the algorithm receives the bounds, the same find call can be reused on any region that can be described by a start and an end. The algorithm does not look past e. It examines the elements in order from b, and it stops at the first element that matches or when it reaches e.

When find searches the whole vector for 7, it examines positions in order from b. It stops at position 1, the first match, and returns that position.

Worked example

Tracing find and count over two different ranges

Given v = {4, 7, 1, 7, 9, 7}, what does count return over the whole range, and what does it return over [0 : 3)?

1
Identify the whole range
The whole range is [v.begin() : v.end()), which is [0 : 6). It has six elements, the values 4, 7, 1, 7, 9, and 7.
2
Count over the whole range
Scanning all six elements, the value 7 appears at positions 1, 3, and 5, so count returns 3.
3
Identify the smaller range
The range [v.begin() : v.begin() + 3) is [0 : 3). Its bound e is at position 3, so position 3 is excluded.
4
Count over the smaller range
The elements examined are at positions 0, 1, and 2, with values 4, 7, and 1. Only position 1 holds a 7, so count returns 1.
5
Notice what changed
The value at position 3 is also a 7, but it is excluded by e. The result depends on the bounds, not on the vector alone.

Result

The whole range gives 3, and the range [0 : 3) gives 1. The only difference is where e sits.

The same reasoning applies to find. When the value is absent, or when the range is empty so that b equals e, find has no element to return. In that case it returns e itself, which is why the fourth line of the earlier program compared the result to v.begin() + 1. The result is a position that the caller can test against e.

Mistakes With Sequence Bounds

Most errors with these algorithms come from misreading the bounds rather than from misremembering an algorithm name. The items below are the mistakes learners make most often with half-open sequences.

Common mistake
Assuming the end bound is included in the range
What it looks like
Calling std::count(v.begin(), v.begin() + 3, 7) and expecting the element at position 3 to be counted.
Why it fails
The sequence [b : e) excludes e. The element at position 3 is not examined, so it does not contribute to the result.
Do this instead
Remember that e is one past the last element. For a range covering positions 0 through 2, use v.begin() + 3 as the end.
Common mistake
Passing the position of the last element as the end bound
What it looks like
Calling std::count(v.begin(), v.begin() + 5, 7) on a six-element vector and expecting all three 7s.
Why it fails
The range stops at position 4, so the final 7 at position 5 is left out.
Do this instead
Use v.end() as the end bound to cover the whole vector.
Common mistake
Treating a missing value as an error that throws
What it looks like
Expecting find to throw an exception when the value is not in the range.
Why it fails
find signals absence by returning e, and an empty range is handled the same way.
Do this instead
Compare the returned iterator with e to test whether a match was found.

Searching, Counting, Modifying, Copying, Sorting, and Merging

The source presents a set of representative algorithms, and each one takes a sequence and does one specific job with it. Grouping them by what they do to the sequence helps you choose the right one. Algorithms such as find and count examine the sequence and report a result. Algorithms such as replace change values, copy writes to a destination, and sort reorders elements.

Each representative algorithm reads or changes the sequence in a different way. Search and count read the sequence and return a result, replace and sort change the sequence, and copy and merge produce output elsewhere.

Algorithm	Works on	What it gives back or does	Notes from the source
find	One sequence [b : e)	A position in the range, or e when the value is absent	Takes a value to match
count	One sequence [b : e)	The number of matching elements	Counts within the range only
replace	One sequence [b : e)	Changes matching values in the sequence	Modifies the existing elements
copy	A source sequence and a destination	Writes the elements to a new place	Output goes to a destination rather than the source
sort	One sequence [b : e)	Reorders the elements of the sequence	Changes the order of the elements
merge	Two sequences, [b : e) and [b2 : e2)	Combines the two input sequences	Algorithms with a second sequence take [b2 : e2) as well

Representative standard library algorithms grouped by the kind of work they perform on a sequence

The variants whose names end in _if take a function f that decides which elements qualify. A search such as find_if therefore uses the same bounds as find, but the test for a match is supplied by the caller. The bounds rule stays the same in every case: b is included and e is not.

Practice Tracing a Range

MEDIUM

Given v = {5, 2, 8, 2, 6}, what does std::count(v.begin() + 1, v.begin() + 4, 2) return? Trace which positions are examined before answering.

Hints

Write down the positions b and e. b is v.begin() + 1, which is position 1, and e is v.begin() + 4, which is position 4.
The range [1 : 4) includes positions 1, 2, and 3. Check the values at those positions.
Position 4 is excluded by e, so the value 6 there is never examined.

Your attempt (not saved)

Summary of Standard Algorithms and Bounds

1
The standard library algorithms are defined in namespace std and presented in the <algorithm> header, and you call them with the std:: prefix.
2
A half-open sequence [b : e) includes b and excludes e, so it contains $e - b$ elements.
3
Because the algorithm receives the bounds, the same call works on any region described by a start and an end, and its result depends on those bounds.
4
find, count, replace, copy, sort, and merge each perform a specific operation, and their return values differ in kind: a position, a number, or changed and produced sequences.

At a glance

The standard library algorithms are defined in namespace std and presented in the <algorithm> header.
A half-open sequence [b : e) includes its beginning b and excludes its end e, so it contains $e - b$ elements.
find, count, replace, copy, sort, and merge each perform a specific operation on a sequence, and their return values differ in kind.
The result of find and count depends on the bounds, so changing e changes which elements are examined.

Related concepts

More concepts starting with U