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

    Input Ranges Input

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

    Range Objects Range Objs. 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 '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 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:

    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 Parallel 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 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:

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

    Iterator / Range Categories Iterator 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; 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: 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 Errors

    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)
    legend of symbols and colors used in algorithm visualizations