Beginner's Guide
    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

    Standard Algorithms Introduction Algorithms Introduction Std.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

    standard library algorithm 'min_element1' visual 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 << '\n';  // prints '0'
    v.erase(j);  // erases smallest element
    
    #include <algorithm>

    #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
    • 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

    Range Objects As Inputs C++20

    standard library algorithm 'ranges-min_element2' visual example
    #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 <<'\n';  // prints '1'
    
    • 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:

    standard library algorithm 'min_element' visual example

    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'
    // 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'
    
    • 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));
    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:

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

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

    legend of symbols and colors used in algorithm visualizations