Beginner's Guide
    First Steps
    Input & Output
    Custom Types – Part 1
    Standard Library
    Code Organization
    Custom Types – Part 2
    Generic Programming
    Memory Management
    Software Design Basics

    Standard Algorithms IntroAlgorithms IntroStd.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


    #include <algorithm>

    #include <numeric>

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

    #include <iterator>

    Iterator utilities (distance, …)

    • improved and easier to use versions of most standard algorithms
    • range and view adapters
    • more stringend handling of algorithm input requirements (based on Concepts)

    First Examples Examples

    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 element

    returns the size of an iterator range

    distance(@range_begin, @element_in_range) → index_of_element_in_range

    #include <vector>
    #include <iterator>  // std::distance
    std::vector<int> v {0,1,2,3,4,5,6,7,8};
    // size of subrange (as shown in image)
    auto n = distance(begin(v)+2, begin(v)+7);  // int n = 5
    // size of entire container
    auto m = distance(begin(v), end(v));  // int m = 9
    std::vector<int> w {4,5,1,9,8}; // get index of smallest element in w: auto argmin = distance( begin(w), min_element(begin(w),end(w)) ); // int argmin = 2

    Avoid using distance with iterators into non-random access containers like std::list, because the runtime will be proportional to the size of the input range!

    Input Ranges Input


    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 Ranges

    Iterator Categorization Categories

    • characteristics of the containers providing the iterators
    • input, output efficiency and correctness requirements of algorithms

      • swapping many arbitrary elements will be most efficient when one has random access to contiguous memory blocks
      • jumping across a range will only be efficient if one has constant-time random access to elements
    Categories Supported Operations

    read access to objects; advance to next position

    example: an iterator that reads values from a file

    * ++ == !=

    write access to objects; advance to next position

    example: an iterator that writes values to a file

    * ++ == !=

    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

    * ++ == !=

    traversal in both directions, but no random access

    example: std::list's iterators

    * ++ -- == !=

    random access, but not necessarily to a contiguous memory block

    example: std::deque's iterators

    * [] ++ -- += -= == != < <= > >=

    random access to contiguous memory

    example: std::vector's iterators

    * [] ++ -- += -= == != < <= > >=

    Functions As Parameters Function Parameters

    Many standard algorithms can be customized by passing a function or function object as parameter:

    The second version of min_element takes a function (object) 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.