Beginner's Guide
    First Steps
    Input & Output
    Basic Custom Types
    Diagnostics
    Standard Library
    Code Organization
    Powerful Custom Types
    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

    Organization

    #include <algorithm>

    #include <numeric>

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


    #include <iterator>

    Iterator utilities (distance, …)


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

    #include <vector>
    #include <iterator>  // std::distance
    std::vector<int> v {1,2,3,4,5,6,7,8,9};
    
    // 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

    Avoid computing the size of iterator ranges for non-random access containers like std::list, because the time it takes is proportional to the size of the range!

    Input Ranges Input

    Iterators

    Standard algorithms use iterators to traverse / access input elements.

    • allows algorithms to be implemented independend 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

    based on both

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

    read access to objects; advance to next position

    example: an iterator that reads values from a file

    * ++ == !=
    Output

    write access to objects; advance to next position

    example: an iterator that writes values to a file

    * ++ == !=
    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

    * ++ == !=
    BiDirectional

    traversal in both directions, but no random access

    example: std::list's iterators

    * ++ -- == !=
    RandomAccess

    random access, but not necessarily to a contiguous memory block

    example: std::deque's iterators

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

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