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>
Non-Modifying Queries
- finding elements / existence queries
- minimum / maximum
- comparing ranges of elements
- binary search of sorted ranges
Modifying Operations
- copying / moving elements
- replacing / transforming elements
- removing elements
- union/intersection/etc. of sorted ranges
#include <numeric>
Operations on ranges of numbers (sums, reductions, …)
#include <iterator>
Iterator utilities (distance, …)
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
)
#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 = 2Avoid 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!
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
= pair [p,q) of iterators
end-of-range iterator q
points one behind the last element
in the range
based on
- 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: |
* ++ == != |
| BiDirectional | traversal in both directions, but no random access example: |
* ++ -- == != |
| RandomAccess | random access, but not necessarily to a contiguous memory block example: |
* [] ++ -- += -= == != < <= > >= |
| Contiguous | random access to contiguous memory example: |
* [] ++ -- += -= == != < <= > >= |
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 <.
Example: min_element with custom type
Example: Custom Type
#include <vector>
#include <algorithm>
struct P { int q; char c; };
std::vector<P> v { {2,'c'}, {1,'b'}, {3,'a'} };Compare using a function
// 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'Compare using a lambda
// 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'Lambdas
- 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.
