17.1. Background

Recall from Container classes that a container is a generic collection. Containers allow us to store data using well-known data structures. The standard library containers provide reusable interfaces and behavior that we can use directly or study when designing custom containers.

Recall from Iterable Types that an iterator is a type that performs operations that feel like a pointer. Although an iterator allows syntax very similar to a pointer, it is not a pointer. Each container is responsible for its own iterators. When a container is created, it has the ability to create an iterator that knows how to visit elements of the type stored in the container.

Now that we have these two tools in the standard library, we want to use them to solve problems. It turns out that many programming tasks fall into basic groups:

  • find

  • copy

  • sum

  • count

  • sort

These are all actions that we perform on sequences. The goal of standard library algorithms is to define these actions in a generic way. They satisfy this goal using small, reusable functions that avoid writing repetitive code and define a consistent, portable interface.

The abstractions in the standard library are primarily concerned with performing actions on data accessed through iterator ranges. Consider that counting elements in a list is not very different from counting elements in a vector.

17.1.1. Standard library algorithms at a glance

The standard library algorithms are part of the ISO C++ Standard. The library provides algorithms for searching, counting, comparing, rearranging, sorting, and manipulating ranges. The set of available algorithms grows as new C++ standards add capabilities and new overloads.

The algorithms are organized into broad categories:

Algorithm operations

Example algorithms

Non-modifying sequence operations

for_each, count_if, find_if, search

Modifying sequence operations

copy_if, move, swap, transform

Partitioning operations

is_partitioned, partition_copy, stable_partition

Sorting operations

is_sorted, sort, stable_sort

Binary search operations

lower_bound, binary_search, equal_range

Set operations

merge, includes, set_difference, set_union

Heap operations

is_heap, make_heap, sort_heap

Min/max operations

max, min, max_element, clamp

Comparison operations

equal, lexicographical_compare

Permutation operations

is_permutation, next_permutation

Numeric operations

iota, accumulate, inner_product, reduce

Uninitialized memory operations

uninitialized_copy, uninitialized_fill, destroy

Numeric algorithms are grouped together because they combine or generate values, but several other standard algorithms also perform arithmetic as part of their work. The categories above are a guide for finding related operations, not an exhaustive classification of every algorithm.

17.1.2. Standard library algorithms and loops

Many standard library algorithms are reusable patterns for traversing a range. They often take a range of elements and an operation that is performed on each element, although some algorithms do more than a simple loop or have optimized implementations. Structurally, this makes them similar to loops.

Most tasks you've written so far could be rewritten using algorithms.

One way to think about standard library algorithms is to consider them named loops. That is, a loop that is important and general enough to justify getting named and encapsulated in its own function.

iota is a standard library algorithm that fills a range [first, last) with sequentially increasing values. This is the sort of algorithm that occurs often enough that it was decided to include it in the standard library (but not until C++11).

The example below shows a possible implementation.

Example: iota

The parameter value defines the start value. This value is assigned to first, and both first and value are incremented.

1template<typename ForwardIterator, typename T>
2void iota(ForwardIterator first, 
3          ForwardIterator last, T value) {
4  while(first != last) {
5    *first = value;
6    ++first;
7    ++value;
8  }
9}

Run It

 1#include <iomanip>
 2#include <iostream>
 3#include <vector>
 4
 5template<typename ForwardIterator, typename T>
 6void iota(ForwardIterator first,
 7          ForwardIterator last, T value) {
 8  while(first != last) {
 9    *first = value;
10    ++first;
11    ++value;
12  }
13}
14
15void print(const std::vector<int>& v) {
16  for (auto x: v) {
17    std::cout << std::setw(3) << x;
18  }
19  std::cout << '\n';
20}
21
22int main () {
23  std::vector<int> nums(13);
24  std::cout << "Before iota:";
25  print(nums);
26
27  iota(nums.begin(), nums.end(), -6);
28  std::cout << "After iota: ";
29  print(nums);
30}

Why prefer algorithms to hand-written loops?

  • Reuse and clarity

    An algorithm gives a common name to a well-defined operation. It can make the intent of the code easier to recognize and avoids repeating the same loop structure in multiple places. Standard implementations are also carefully designed and may take advantage of library- or platform-specific optimizations, but an algorithm call is not automatically faster than an equivalent hand-written loop.

  • Correctness

    Writing loops exposes more bookkeeping details than an algorithm call. As a programmer you have to worry about initializing the loop, incrementing the loop, terminating the loop as well as the loop body.

    When calling an algorithm, you still need to provide a valid range, the required iterator category, suitable predicates, and any required output range. The algorithm handles the traversal and its documented edge cases, but it cannot make an invalid range or invalid predicate safe.

    Often you don't even need to care about the body - the algorithm takes care of all the details for you. Sometimes a lambda or function pointer is expected.

    Standard library implementations receive extensive review and testing. Using them avoids maintaining another copy of a common operation, provided the caller follows the algorithm's documented contract.

  • Maintainability

    Algorithm calls result in clearer code. The standard library is designed around a simple, consistent set of interfaces. The more you use these interfaces, the more consistently your own code will be structured.

    When combined together, algorithms can eliminate code that would otherwise need to be written and can make the result more straightforward than a collection of explicit loops.

    Code you use from the standard libray is code you don't need to maintain. The less code you have to maintain, the cheaper and easier it is to maintain.

More to Explore