Beginner's Guide

# 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 <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
• more stringend handling of algorithm input requirements (based on Concepts)

## First ExamplesExamples 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``````
``````#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 RangesInput

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

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

example: an iterator that reads values from a file

`* ++ == !=`
Output

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

example: `std::vector`'s iterators

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

## Functions As ParametersFunction 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.