Understanding Standard Library Algorithms and Iterators

Chapter 21 -Algorithms In theory, practice is simple. Trygve Reenskaug

Overview Standard-library algorithms Function objects Lambdas Numerical algorithms Copying Sorting and searching Stroustrup/Programming/2024/Chapter21 2

Basic model of a sequence/range A pair of iterators defines a half-open sequence [begin:end) The beginning (points to the first element if any) The end (points to the one-beyond-the-last element) Also {begin:number of elements} and {begin:termination criteria} begin: end: An iterator is a type that supports the iterator operations of ++ Point to the next element * Get the element value == Does this iterator point to the same element as that iterator? Some iterators support more operations (e.g., --, +, and [ ]) Stroustrup/Programming/2024/Chapter21 3

Selected standard algorithms p=find( p=find(b,e,v p= p=find_if find_if( (b,e,p x=count( x=count(b,e,v x= x=count_if count_if( (b,e,p sort( sort(b,e b,e) ) sort( sort(b,e,p b,e,p) ) x= x=is_sorted is_sorted( (b,e b2=copy(b,e,b2) b2=copy(b,e,b2) b2=move(b,e,b2) b2=move(b,e,b2) b2= b2=uninitialized_copy uninitialized_copy(b,e,b2) b2= b2=unique_copy unique_copy(b,e,b2) b,e,v) ) b,e,p) ) b,e,v) ) b,e,p) ) p p points to the first occurrence of v v in [b b:e e) p p points to the first element x in [b b:e e) so that p(x) x x is the number of occurrences of v v in [b b:e e). x x is the number of elements in [b b:e e) so that p(x) Sort [b b:e e) using < < Sort [b b:e e) using p p If [b b:e e) is sorted x is true Copy [b b:e e) to [b2 b2:b2+(e b2+(e- -b) b)) Move [b b:e e) to [ [\ \{b2 {b2\ \}: }:\ \{b2+(e {b2+(e- -b) b)\ \}) }) Copy [b b:e e) to an uninitialized [b2:b2+(e Copy [b b:e e) to [ [\ \{b2 {b2\ \}: }:\ \{b2+(e {b2+(e- -b) b)\ \}) }); don't copy adjacent duplicates. p(x) is true p(x) is true b,e) ) (b,e,b2) [b2:b2+(e- -b)) b)) (b,e,b2) For move() move(), copy() sequence, , there had better be enough elements after b2 copy(), unitialized_copy unitialized_copy(), (), and other algorithms that writes to a b2 to hold [b b:e e) Stroustrup/Programming/2024/Chapter21 4

Selected standard algorithms e2=merge(b,e,b2,e2,r) e2=merge(b,e,b2,e2,r) [ [p,q p,q]= ]=equal_range equal_range( (b,e,v equal(b,e,b2) equal(b,e,b2) x=accumulate( x=accumulate(b,e,i r=max( r=max(x,y x,y) ) p= p=max_element max_element( (b,e iota( iota(b,e,i b,e,i) ) Merge two sorted sequences [ [\ \{b [p p:q q) is the subsequence of the sorted range [b b:e e) with the value v v, basically, a binary search for v v Do all elements of [ [\ \{b {b\ \}: }:\ \{e {e\ \}) }) and [b2:b2+(e The sequences must be sorted. x x is the sum of i i and the elements of [ [\ \{b r r is a reference to the larger of x x and y y p p points to the largest element in [b b:e e) [b b:e e) becomes the sequence i i, i+1 i+1, i+2 {b\ \}: }:\ \{e {e\ \}) }) and [b2 b2:e2 e2) into [r r:r r+(e +(e- -b)+(e2 b)+(e2- -b2) b2)) b,e,v) ) [b2:b2+(e- -b)) b)) compare equal? b,e,i) ) b,e) ) {b\ \}: }:\ \{e {e\ \}). }). i+2, ... Usually, a standard algorithm is faster than our handcrafted code Knowing relevant standard library algorithms saves us a lot of work For each pair-of-iterators algorithm, algo( algo(b,e b,e) ) , there is a ranges version ranges::algo(r) ranges::algo(r) Stroustrup/Programming/2024/Chapter21 5

The simplest algorithm: find() Traversing a sequence doing something to each element template< template<input_iterator input_iterator In, In find(In first, In last, const T& In find(In first, In last, const T& val { { while (first!=last && *first!= while (first!=last && *first!=val ++first; ++first; return first; return first; } } In, equality_comparable equality_comparable<In:: val) ) <In::value_type value_type> T> // find the first element in [first,last) that equals val > T> // val) ) Yes, we can use an argument as a variable if (auto p = find(begin(v), end(v),x); p!= if (auto p = find(begin(v), end(v),x); p!=v.end // // ... we found x in v; we can use *p ... } } else { else { // // ... no x in v; don't dereference p ... } } // // ... v.end()) { ()) { Condition in if-statement Stroustrup/Programming/2024/Chapter21 6

The simplest algorithm: find() We could almost equivalently have written auto p = find(begin(v), end(v),x); auto p = find(begin(v), end(v),x); if (p!= if (p!=v.end v.end()) { ()) { // // ... we found x in v; we can use *p ... } } else { else { // // ... no x in v; don't dereference p ... } } // // ... But now p is in scope after the if-statement Do we want that? Sometimes we do, and sometimes the scope ends right after the if if-statement Stroustrup/Programming/2024/Chapter21 7

The simplest algorithm: find() Traversing a range doing something to each element template<ranges::range R, template<ranges::range R, equality_comparable R::iterator find(R R::iterator find(R r r, const T& , const T& val { { return find( return find(r.begin r.begin, , r.end r.end(), } } equality_comparable<R:: val) ) <R::value_type value_type> T> // find the first element in r that equals val > T> // (), val val); ); if (auto p = find( if (auto p = find(v,x // // ... we found x in v; we can use *p ... } } else { else { // // ... no x in v; don't dereference p ... } } // // ... v,x); p!= ); p!=v.end v.end()) { ()) { Stroustrup/Programming/2024/Chapter21 8

The simplest algorithm: ranges::find() Traversing a range doing something to each element if (auto p = ranges::find( if (auto p = ranges::find(v,x // // ... we found x in v; we can use *p ... } } else { else { // // ... no x in v; don't dereference p ... } } // // ... v,x); p!= ); p!=v.end v.end()) { ()) { Stroustrup/Programming/2024/Chapter21 9

find_if find_if() () Often, we don t look for a value but for something that meets a criteria template< template<input_iterator input_iterator In, predicate<In:: In In find_if find_if(In first, In last, Pred pred) (In first, In last, Pred pred) { { while (first!=last && !pred(*first)) while (first!=last && !pred(*first)) ++first; ++first; return first; return first; } } In, predicate<In::value_type value_type> Pred> > Pred> A predicate: true if x<42 if (auto p = if (auto p = find_if } } else { else { } } // // ... find_if(begin(v), end(v), (begin(v), end(v), Greater_than // // ... we found something greater than 42 in v; we can use *p ... Greater_than{42}); p!= {42}); p!=v.end v.end()) { ()) { // // ... no value greater than 42 in v; don't dereference p ... Stroustrup/Programming/2024/Chapter21 10

Predicates true if a criteria is met and false A predicate I something that returns true A function template<typename T> template<typename T> bool greater(const T& x, const T& y) {return x>y; } bool greater(const T& x, const T& y) {return x>y; } Obvious, but clumbsy where we want to compare many elements against the same value A function object template<typename T> template<typename T> struct struct Greater_than Greater_than { { T T val val; ; Greater_than Greater_than(const T& x) : (const T& x) : val val(x) {} (x) {} bool operator()(const T& x) { return x> bool operator()(const T& x) { return x>val }; }; A lambda expression template<typename T> template<typename T> [](const T& x} {return x>42;} [](const T& x} {return x>42;} Generates a function object (like Greater_than Greater_than) false otherwise val; } ; } Stroustrup/Programming/2024/Chapter21 11

Lambda expressions A lambda is an expression, so we can use it as a function argument if (auto p = if (auto p = find_if find_if(begin(v), end(v),[](int x) {return x>42;}), p!= (begin(v), end(v),[](int x) {return x>42;}), p!=v.end // // ... we found something greater than 42 in v; we can use *p ... } } else { else { // // ... no value greater than 42 in v; don't dereference p ... } } Or if (auto p = ranges:: if (auto p = ranges::find_if find_if(v, [](int x) {return x>42;}), p!= (v, [](int x) {return x>42;}), p!=v.end // // ... we found something greater than 42 in v; we can use *p ... } } else { else { // // ... no value greater than 42 in v; don't dereference p ... } } Stroustrup/Programming/2024/Chapter21 v.end()) { ()) { v.end()) { ()) { 12

Function objects A function object is an object that can be called like a function A generalization of a function class F { class F { S S s s; ; public: public: F(const S& ss) :s(ss) { /* establish initial state*/ } F(const S& ss) :s(ss) { /* establish initial state*/ } T operator() (const S& ss) const T operator() (const S& ss) const { { // // do something with ss to s // // return a value of type T (T is often void, bool, or S) } } const S& state() const { return s; } const S& state() const { return s; } void reset(const S& ss) { s = ss; } void reset(const S& ss) { s = ss; } }; }; // // abstract example of a function object // // state // // reveal state // // reset state Stroustrup/Programming/2024/Chapter21 13

Lambdas A lambda generates a function object can be used wherever an expression is allowed can carry values (since they are objects) yielding more compact code Can access its enclosing scope can be used to avoid defining a function in on place and then using it elsewhere (yielding more compact code) Should not be used where a named function yields clearer and less repetitive code Keep lambdas short and simple An abstract lambda: [c]( [c](arg arg){ code } ){ code } becomes a function object F Values to be captured. Becomes F s member variables, Initialized by F s constructor Arguments for F s operator()() Code to be executed. Becomes the body of F s operator()() Stroustrup/Programming/2024/Chapter21 14

Lambda usage examples struct Record { struct Record { }; }; vector<Record> vector<Record> vr vr; ; string name; string name; char char addr addr[24]; // ... // ... // // standard string for ease of use // // old style to match database layout [24]; ranges::sort( ranges::sort(vr vr, [](const Record& a, const Record& b) { return a.name < b.name; }); , [](const Record& a, const Record& b) { return a.name < b.name; }); ranges::sort( ranges::sort(vr vr, [](const Record& a, const Record& b) { return , [](const Record& a, const Record& b) { return strncmp strncmp( (a.addr a.addr, , b.addr b.addr, 24) < 0; }); , 24) < 0; }); Stroustrup/Programming/2024/Chapter21 15

Lambda usage examples Lambdas are very flexible vector<int> vi; vector<int> vi; list<string> ls; list<string> ls; string s = Hello! string s = Hello! int answer = 42; int answer = 42; // // auto p1 = ranges:: auto p1 = ranges::find_if if (p1!= if (p1!=v.end v.end()) { ()) { // // ... we found a int value > 31 ... } } auto p2 = ranges:: auto p2 = ranges::find_if if (p2!= if (p2!=ls.end ls.end()) { ()) { // // ... we found a C-style string > s ... } } auto p3 = ranges:: auto p3 = ranges::find_if if (p3!= if (p3!=v.end v.end()) { ()) { // // ... we found a double > answer ... } } find_if(vi, [](int a) { return a>31; }); (vi, [](int a) { return a>31; }); find_if(ls, [&](const char* a) { return a>s; }); (ls, [&](const char* a) { return a>s; }); find_if(vi, [=answer](double a) { return a>answer; }); (vi, [=answer](double a) { return a>answer; }); Stroustrup/Programming/2024/Chapter21 16

Lambdas Lambda captures : [] []: If there is nothing between [ [ and ] ], the lambda is just like an ordinary function: it can access its arguments, its own local variables, and names in the global (namespace) scope [&] [&]: If we use [&] [&], the lambda can also use names from the scope in which it is defined, its enclosing scope. References to local objects are stored in the lambda object. Now the lambda acts like a local function [=] [=]: You can even ask to access copies of variables in the enclosing scope. Copies of the objects in the enclosing scope are stored in the lambda object Stroustrup/Programming/2024/Chapter21 17

Numerical algorithms x=accumulate( x=accumulate(b,e,i x= x=inner_product inner_product(b,e,b2,i) r= r=partial_sum partial_sum( (b,e,r r= r=adjacent_difference adjacent_difference(b,e,b2,r) iota( iota(b,e,v b,e,v) ) x=midpoint( x=midpoint(a,b a,b) ) x= x=gcd gcd( (a,b a,b) ) x=lcm( x=lcm(a,b a,b) ) b,e,i) ) Add a sequence of values; e.g., for { {a,b,c,d The type of the result x x is the type of the initial value i i. Multiply pairs of values from two sequences and sum the results; e.g., for { {a,b,c,d a,b,c,d} } and { {e,f,g,h e,f,g,h} } produce i+a The type of the result x x is the type of the initial value i i. Produce the sequence of sums of the first \{n\} elements of [b b:e e); e.g., for {a,b,c,d a,b,c,d} } produce {a, a, a+b a+b, , a+b+c (b,e,b2,r) Produce the sequence of differences between elements of [b b:e e); e.g., for { {a,b,c,d a,b,c,d} } produce { {a,b Fill the range [b b:e e)with the values v v, v+1 v+1, v+2 The values are computers using prefix ++ Compute the midpoint between a a and b b; roughly ( (a+b x x is the greatest common divisor of a a and b b x x is the least common multiple of a a and b b a,b,c,d} } produce i+a+b+c+d i+a+b+c+d. (b,e,b2,i) i+a* *e+b e+b* *f+c f+c* *g+d g+d*h *h. b,e,r) ) a+b+c, , a+b+c+d a+b+c+d} }. a,b- -a,c a,c- -b,d b,d- -c}. c}. v+2, ...; ++. a+b)/2 )/2 without overflow Stroustrup/Programming/2024/Chapter21 18

Simple accumulate() accumulate() template< template<input_iterator input_iterator In, Number T> T accumulate(In first, In last, T T accumulate(In first, In last, T init { { while (first!=last) { while (first!=last) { init init = = init ++first; ++first; } } return return init init; ; } } In, Number T> init) ) init + *first; + *first; int a[] = { 1, 2, 3, 4, 5 }; int a[] = { 1, 2, 3, 4, 5 }; cout cout << accumulate(a, << accumulate(a, a+sizeof a+sizeof(a)/ (a)/sizeof sizeof(*a), 0); // (*a), 0); // yes, that s how to get the size of a built-in array Stroustrup/Programming/2024/Chapter21 19

Ranges numerical algorithms For lack of time, the ranges versions of the numerical algorithms didn't make it into C++20, but they are not hard to define. For example: template< template<input_range input_range R, T accumulate(R T accumulate(R r r, Out { { return accumulate(begin(r),end(r), return accumulate(begin(r),end(r),oo,init } } R, output_iterator output_iterator Out, typename T> , Out oo oo, T , T init init) ) Out, typename T> oo,init); ); Stroustrup/Programming/2024/Chapter21 20

accumulate() accumulate() The type of the result (the sum) is the type of the variable that accumulate() uses to hold the accumulator. This gives a degree of flexibility that can be important. accumulate() void g(vector<int>& v) void g(vector<int>& v) { { int s1 = accumulate(v, 0); int s1 = accumulate(v, 0); long long sl sl = accumulate(v, long{0}); = accumulate(v, long{0}); double s2 = accumulate(v, 0.0); double s2 = accumulate(v, 0.0); } } // // sum into an int // // sum the ints into a long // // sum the ints into a double Stroustrup/Programming/2024/Chapter21 21

Generalized accumulate() accumulate() template< template<input_iterator input_iterator In, typename T, invocable< In, typename T, invocable<T,In [[ [[nodiscard nodiscard]] ]] // // warn if the return value isn't used by a caller T accumulate(In first, In last, T T accumulate(In first, In last, T init init, , BinOp { { while (first!=last) { while (first!=last) { init init = op( = op(init init, *first); , *first); ++first; ++first; } } return return init init; ; } } T,In:: ::value_type value_type> > BinOp BinOp> > BinOp op) op) vector<double> a = { 1.1, 2.2, 3.3, 4.4 }; vector<double> a = { 1.1, 2.2, 3.3, 4.4 }; cout cout << accumulate( << accumulate(a.begin a.begin(), (),a.end a.end(), 1.0, multiplies<double>()); (), 1.0, multiplies<double>()); Stroustrup/Programming/2024/Chapter21 22

accumulate() accumulate() struct Record { struct Record { }; }; double double unit_price unit_price; ; int units; int units; // ... // ... // // number of units sold double price(double v, const Record& r) double price(double v, const Record& r) { { return v + return v + r.unit_price r.unit_price * * r.units } } r.units; ; // // extract values, calculate price, and accumulate void f(const vector<Record>& void f(const vector<Record>& vr vr) ) { { double total = accumulate( double total = accumulate(vr.begin // ... // ... } } vr.begin(), (), vr.end vr.end(), 0.0, price); (), 0.0, price); Stroustrup/Programming/2024/Chapter21 23

Copy operations b2=copy(b,e,b2) b2=copy(b,e,b2) b2= b2=unique_copy unique_copy(b,e,b2) b2= b2=copy_if copy_if(b,e,b2,p) (b,e,b2,p) Copy [b b:e e) ) to [b2 Copy [b b:e e) ) to [b2 Copy [b b:e e) ) that meets the predicate p to [b2 b2:b2+(e b2+(e- -b) b)) b2:b2+(e b2+(e- -b) b)); suppress adjacent copies (b,e,b2) b2:b2+(e b2+(e- -b) b)) template< template<input_iterator input_iterator In, Out copy(In first, In last, Out res) Out copy(In first, In last, Out res) { { while (first!=last) { while (first!=last) { } } return res; return res; } } In, output_iterator output_iterator Out> // // The simplest copy Out> *res = *first; *res = *first; ++res; ++res; ++first; ++first; // // copy element Make sure that there is enough space For the result in the target Stroustrup/Programming/2024/Chapter21 24

copy_if copy_if() () template< template<input_iterator input_iterator In, Out Out copy_if copy_if(In first, In last, Out res, Pred p) (In first, In last, Out res, Pred p) // { { while (first!=last) { while (first!=last) { if (p(*first)) { if (p(*first)) { *res = *first; *res = *first; ++res; ++res; } } ++first; ++first; } } return res; return res; } } In, output_operator output_operator Out, predicate<In:: Out, predicate<In::value_type // copy elements that fulfill the predicate p into res value_type> Pred> > Pred> void f(const vector<int>& v) void f(const vector<int>& v) // { vector<int> v2( vector<int> v2(v.size ranges:: ranges::copy_if // ... // ... } } // copy all elements with a value larger than 6 into v2 v.size()); (v, v2.begin(), [](int x){ return x>6;}); ()); copy_if(v, v2.begin(), [](int x){ return x>6;}); Stroustrup/Programming/2024/Chapter21 25

Sorting: sort() sort() template< template<random_access_iterator random_access_iterator Ran> void sort(Ran first, Ran last); void sort(Ran first, Ran last); Ran> template< template<random_access_iterator random_access_iterator Ran, void sort(Ran first, Ran last, void sort(Ran first, Ran last, Cmp Ran, less_than_comparable less_than_comparable<Ran:: Cmp cmp cmp); ); <Ran::value_type value_type> > Cmp Cmp> > Stroustrup/Programming/2024/Chapter21 26

Searching: binary_search binary_search() () template< template<random_access_range random_access_range Ran, typename T> bool bool binary_search binary_search(Ran r, const T& template< template<random_access_range random_access_range Ran, typename T, predicate<Ran:: predicate<Ran::value_type,Ran bool bool binary_search binary_search(Ran r, const T& Ran, typename T> (Ran r, const T& val Ran, typename T, value_type,Ran:: ::value_type (Ran r, const T& val // // compare using < val); ); value_type> > Cmp val, , Cmp Cmp cmp Cmp> > cmp); ); // // compare using cmp void f(vector<string>& vs) void f(vector<string>& vs) { { if (ranges:: if (ranges::binary_search // // we have a starfruit (but we don t know where it is) } } // // ... } } // // vs is sorted binary_search( (vs,"starfruit vs,"starfruit")) { ")) { Stroustrup/Programming/2024/Chapter21 27

Searching: equal_range equal_range() () It is often useful to know where a matching term is: template< template<forward_iterator forward_iterator Iter equal_range equal_range( ( Iter Iter first, first, Iter Iter, typename T > , typename T > Iter last, const T& value ); last, const T& value ); // // compare using < template< template<forward_iterator forward_iterator Iter predicate<Ran:: predicate<Ran::value_type,Ran equal_range equal_range( ( Iter Iter first, Iter, typename T, , typename T, value_type,Ran:: ::value_type first, Iter Iter last, const T& value ); last, const T& value ); value_type> > Cmp Cmp> > // // compare using cmp template<typename T> template<typename T> void print same(const vector<T>& v, const T& x) void print same(const vector<T>& v, const T& x) { { for (const auto& x : ranges:: for (const auto& x : ranges::equal_range cout cout << x << ' << x << '\ \n'; } } equal_range( (v,x v,x)) )) // // equal_range() returns a sub-range n'; Stroustrup/Programming/2024/Chapter21 28

And there is more! Have a look at the Software ideals and history from PPP2: https://www.stroustrup.com/PPP3_slides/22-ideals.pptx Also, you can find the more specialized broadening the view chapters on the Web: Chapter 1: Computers, People, and Programming Chapter 11: Customizing Input and Output Chapter 22: Ideal and History Chapter 23: Text Manipulation Chapter 24: Numerics Chapter 25: Embedded Systems Programming Chapter 26: Testing Chapter 27: The C Programming Language And lecture slides for those: https://www.stroustrup.com/PPP2slides.html Stroustrup/Programming/2024/Chapter21 29