Standard Algorithms Introduction Algorithms Introduction Std.Algorithms

C++'s Standard Algorithms are

algorithmic building blocks
operating on (iterator) ranges of elements
implemented as free-standing functions
generic: implemented in a (mostly) container/element-agnostic way
many are customizable with function(object)s / lambdas
well-tested and efficient

First Example

returns an iterator to the smallest element and thereby both its position and value

#include <vector>
#include <algorithm>  // std::min_element
#include <iostream>

int main () {std::vector<int> v {7,9,3,5,3,2,4,1,8,0};
// smallest in subrange (as shown in image):
auto i = min_element(begin(v)+2, begin(v)+7);
auto min = *i;  // int min = 2
std::cout << min << '\n';// smallest in entire container:
auto j = min_element(begin(v), end(v));
std::cout << *j << '\n';  // prints '0'
v.erase(j);  // erases smallest element
}

Organization

`#include <algorithm>`

Non-Modifying Queries

finding elements / existence queries
minimum / maximum
comparing ranges of elements
binary search of sorted ranges

Modifying Operations

copying / moving elements
replacing / transforming elements
removing elements
union/intersection/etc. of sorted ranges

`#include <numeric>`

Operations on ranges of numbers (sums, reductions, …)

`#include <iterator>`

Iterator utilities (distance, next, …)

`#include <memory>`

operations on uninitialized memory

C++20

improved and easier to use versions of most standard algorithms
range and view adapters
more stringent handling of algorithm input requirements (based on Concepts)

Input Ranges

Iterators

Standard algorithms use iterators to traverse / access input elements.

allows algorithms to be implemented independent from container types
eliminates the need for having one algorithm implementation per container type
new (third party) containers can be used with existing standard algorithm implementations

Iterator .Ranges

= pair `p,q` of iterators

end-of-range iterator q points one behind the last element in the range

Range Objects As Inputs C++20

#include <iostream>#include <vector>
#include <algorithm>  // std::ranges::min_element

int main () {std::vector<int> v {3,5,3,2,4,1};
auto j = std::ranges::min_element(v);
std::cout << *j <<'\n';  // prints '0'
}

Algorithms in C++20's namespace `std::ranges`

also accept single range objects like containers or views as inputs (before C++20: only iterator pairs)
must be called with the full namespace (namespace-qualified in C++ parlance) because they can't be found by argument dependent lookup (= look up a function in the namespaces of its arguments).
A range is any object r for which std::ranges::begin(r) and std::ranges::end(r) return either valid iterators or end-of-range indicating sentinels.

Customization with Callable Parameters

Many standard algorithms can be customized by passing a callable entity like a function, lambda or custom function object as parameter:

The second version of min_element takes a callable entity as 3^rd argument for comparing pairs of elements unlike the first version which uses operator <.

Example: `min_element` with Custom Type

#include <vector>
#include <algorithm>
struct P { int q; char c; };
std::vector<P> v { {2,'c'}, {1,'b'}, {3,'a'} };

Compare using a function

// compares Ps by their 'q' member
bool less_q (P const& x, P const& y) {
  return x.q < y.q;
}
auto i = min_element(begin(v), end(v), less_q);
auto q1 = i->q;  // int  q1 = 1
auto c1 = i->c;  // char c1 = 'b'

Compare using a lambda

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

struct P { 
  int q; 
  char c; 
};

int main () {
std::vector<P> v { {2,'c'}, {1,'b'}, {3,'a'} };
// use lambda to compare Ps by 'c'
auto j = min_element(begin(v), end(v), 
  [](P const& x, P const& y){
      return x.c < y.c;
  });
auto q2 = j->q;  // int  q2 = 3
auto c2 = j->c;  // char c2 = 'a'
std::cout << q2 << ' ' << c2 << '\n';
}

Lambdas

can be thought of as anonymous functions
can be defined within functions (regular C++ functions can not be nested)
are function objects whose type is auto-generated by the compiler

We will learn more about function objects – and lambdas in particular – in later chapters. They are not only extremely useful, but also a lot more powerful than the above example suggests.

Parallel Execution C++17

Most standard algorithms can be executed in parallel.

This is configured by providing an execution policy object as first argument.

#include <execution>
…
sort(std::execution::par, begin(v), end(v));

Execution Policy	Effect
`std::execution::seq`	explicitly require not to parallelize
`std::execution::par`	may parallelize, but vectorization is not allowed
`std::execution::par_unseq`	may parallelize, vectorize, or migrate computation across threads; allows to invoke input element access functions in an unordered fashion, and unsequenced with respect to each other within each thread
`std::execution::unseq` C++20	may vectorize

Compiler Support (min. required versions)

GNU g++ 9

Requires TBB Library (Intel Thread Building Blocks)

Install on Debian/Ubuntu/WSL: sudo apt install libtbb-dev

The executable needs to be linked against TBB: g++ -std=c++17 ... -o exename -ltbb

Microsoft MSVC 19.14 (VS 2017 15.7)

Microsoft C++ Team Blog: Using C++17 Parallel Algorithms for Better Performance

NVIDIA NVC++

can use NVIDIA GPUs to accelerate C++ standard algorithms:

NVIDIA developer blog: Accelerating Standard C++ with GPUs Using stdpar

Iterator / Range Categories

Category = set of supported iterator / range object operations & guarantees

based on common algorithm requirements (input, output, efficiency, correctness, …)
determined by the input range object or the host container providing the iterator

Sentinel C++20	iterator-like position specifier; usually only used for denoting the end of a range	supports `== !=`
Input	read access to objects; advanceable to next position example: iterator that reads values from a file	supports `* ++ == !=`
Output	write access to objects; advanceable to next position example: iterator that writes values to a file	supports `* ++ == !=`
Forward	read/write access; forward traversal, no random access multi-pass guarantee: iterators to the same range can be used to access the same objects multiple times example: `std::forward_list`'s iterators	supports `* ++ == !=`
BiDirectional	multi-pass guarantee, traversal in both directions (but no random access) example: `std::list`'s iterators	supports `* ++ -- == !=`
RandomAccess	random access, but not necessarily to a contiguous memory block example: `std::deque`'s iterators	supports `* [] ++ -- += -= - + == != < <= > >=`
Contiguous C++17	random access to contiguous memory example: `std::vector`'s iterators	supports `* [] ++ -- += -= - + == != < <= > >=`

If you need detailed information about an algorithms requirements, runtime complexity, etc. refer to cppreference.com

The descriptions there are not very beginner-friendly but very detailed, usually up-to date and checked by a lot of C++ experts.

Error Messages

of generic algorithms can be quite confusing:

std::list x {4,2,8,1};
std::sort(begin(x), end(x));

This does not compile as sort requires random access iterators, but list provides only bi-directional iterators. The resulting error messages of GCC 10 look like this:

/opt/gcc-10.2.0/include/c++/10.2.0/bits/stl_algo.h: In instantiation of 'constexpr void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::_List_iterator<int>; _Compare = __gnu_cxx::__ops::_Iter_less_iter]':/opt/gcc-10.2.0/include/c++/10.2.0/bits/stl_algo.h:4859:18:   required from 'constexpr void std::sort(_RAIter, _RAIter) [with _RAIter = std::_List_iterator<int>]'<source>:25:31:   required from here/opt/gcc-10.2.0/include/c++/10.2.0/bits/stl_algo.h:1975:22: error: no match for 'operator-' (operand types are 'std::_List_iterator<int>' and 'std::_List_iterator<int>')1975 |     std::__lg(__last - __first) * 2,     |               ~~~~~~~^~~~~~~~~… many, many more lines…

By default, requirements of generic functions regarding their input types are only checked in an ad-hoc manner inside the function implementation and not at the call site.

This means that compilation fails when an unsupported operation, here iterator1 - iterator2, is used in the implementation.

Always look for the first message that contains the word 'error'.

C++20 Algorithms in Namespace `std::ranges`

requirements are checked at the call site using Concepts (more on that later)
requirements are overall more consistently specified
allow compiler error messages to be more helpful, but there is still room for improvement (as of early 2021)

Algorithm Parameter Iconography

The following graphical conventions are used for visualizations of standard algorithms, functions, container member functions, etc. throughough this website.

Set/Map

Beginner's Guide / Std.Library 1

Traversal

Related …

A Tour of C++: Containers and Algorithms

Last updated: 2022-03-09

First Steps

Input & Output

Custom Types – Part 1

Diagnostics

Standard Library – Part 1

Function Objects

Standard Library – Part 2

Code Organization

Custom Types – Part 2

Generic Programming

Memory Management

Software Design Basics