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 <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 RangesInput

### 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 ObjectsRange Objs.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'
}``````
• 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 ParametersCustomization with CallablesCustomization

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 ExecutionParallelC++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` explicitly require not to parallelize
`std::execution::par` may parallelize
`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` may vectorize

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 CategoriesIterator 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 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 MessagesErrors

``````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 room for improvement (as of early 2021) 