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 STL containers provide the patterns we can use to make custom containers, if needed.

Recall from Iterable ADT’s 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 great tools in the STL, we want to use them to solve problems. It turns out that many programming tasks fall into basic groups:

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

The abstractions in the STL are primarily concerned with performing actions on data stored in STL containers. Consider that counting elements in a list is not very different from counting elements in a vector.

17.1.1. STL Algorithms at a glance

The STL algorithms are part of the ISO C++ Standard. Currently, it contains more than 150 algorithms for searching, counting, and manipulating ranges. C++17 alone added 69 more algorithms to the library. While most of these (but not all) were new overloads to existing algorithms, it does demonstrate the dynamic nature of the STL and its growth.

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_partition

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

Notice that only a single category of algorithms is considered ‘numeric’. In C++11, only 5 algorithms specifically do numeric computations. C++17 adds 6 more.

17.1.2. STL algorithms and loops

Most STL algorithms are essentially wrappers around loops. They often take a range of elements and an operation that is performed on each element. Structurally, this makes them similar to loops.

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

One way to think about STL 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 STL 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 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    ++value;
7  }
8}

Note the order of operations on 5.

  • First first is dereferenced and value is assigned.

  • Then the iterator is incremented.

See this example running step-by-step

Why prefer algorithms to hand-written loops?

  • Efficiency, for one.

    Algorithms are often more efficient than the loops programmers produce. The developers of the STL have had overt 20 years to consider how to make these algorithms efficient. Many algorithms have code to handle specific edge cases your initial implementations might overlook.

  • Correctness

    Writing loops is more subject to errors than algorithm calls. 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 only need to get the start and end iterators correct.

    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.

    The STL implementations have been carefully reviewed and tested in many thousands of programs. It is safe to say that any STL algorithm has been tested more thoroughly than any comparable code you write yourself.

  • Maintainability

    Algorithm calls result in clearer code. The STL 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 lots of code you other wise would have needed to write and results in more straightforward than the corresponding explicit loops.

    Code you use from the STL 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

You have attempted of activities on this page