Beginner's Guide

# Standard Algorithms IntroductionAlgorithms IntroductionStd.Algorithms

• 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
}``````

##### `#include <numeric>`

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

##### `#include <ranges>`

composable range views, range utilitites

##### `#include <iterator>`

Iterator utilities (distance, next, …)

##### `#include <memory>`

operations on uninitialized memory

##### C++20
• improved and easier to use versions of most standard algorithms
• 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

### Range Objects As InputsC++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'
}``````
• 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 3rd argument for comparing pairs of elements unlike the first version which uses operator `<`.

``````#include <vector>
#include <algorithm>
struct P { int q; char c; };
std::vector<P> v { {2,'c'}, {1,'b'}, {3,'a'} };``````
``````// 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'``````
``````#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';
}``````
• 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 ExecutionC++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));``````
`std::execution::seq` parallelization and vectorization are not allowed
`std::execution::unseq` C++20 may vectorize, but parallelization is not allowed
`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

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`

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

## Iterator / Range Categories

• based on common algorithm requirements (input, output, efficiency, correctness, …)
• determined by the input range object or the host container providing the iterator
SentinelC++20 Input iterator-like position specifier; usually only used for denoting the end of a range supports`== !=` read access to objects; advanceable to next position example: iterator that reads values from a file supports`* ++ == !=` write access to objects; advanceable to next position example: iterator that writes values to a file supports`* ++ == !=` 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`* ++ == !=` multi-pass guarantee, traversal in both directions (but no random access) example: `std::list`'s iterators supports`* ++ -- == !=` random access, but not necessarily to a contiguous memory block example: `std::deque`'s iterators supports`* [] ++ -- += -= - + == != < <= > >= ` random access to contiguous memory example: `std::vector`'s iterators supports`* [] ++ -- += -= - + == != < <= > >= `

If you need detailed information about algorithm 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

``````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'.

• 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 some room for improvement

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