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
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
// smallest in entire container:
auto j = min_element(begin(v), end(v));
std::cout << *j; // prints '0'
v.erase(j); // erases smallest elementOrganization
#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 stringend handling of algorithm input requirements
(based on
Concepts
)
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
= pair p,q of iterators
end-of-range iterator q
points one behind the last element
in the range
#include <vector>
#include <algorithm> // std::ranges::min_element
std::vector<int> v {3,5,3,2,4,1};
auto j = std::ranges::min_element(v);
std::cout << *j; // 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
rfor whichstd::ranges::begin(r)andstd::ranges::end(r)return either valid iterators or end-of-range indicating sentinels.
Customization with Callable Parameters Customization with Callables Customization
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 <.
Example: min_element with custom type
Example: 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
// 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'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.
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 |
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 |
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
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; advancable to next position example: iterator that reads values from a file |
supports* ++ == != |
| Output | write access to objects; advancable 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: |
supports* ++ == != |
| BiDirectional | multi-pass guarantee, traversal in both directions (but no random access) example: |
supports* ++ -- == != |
| RandomAccess | random access, but not necessarily to a contiguous memory block example: |
supports* [] ++ -- += -= - + == != < <= > >= |
| Contiguous C++17 |
random access to contiguous memory example: |
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.
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 Parameter Iconography
Comments