## Standard Template Library (STL) IV
- Algorithms - 2018

The standard algorithms are found in **<algorithms>**.
There are about 60 standard algorithms are defined in <algorithms>.

STL Algorithms Library can be characterized as following:

- Sorting algorithms

**Quicksort**algorithm over elements**a**to**b**:template <typename RandomAccessIterator> void sort(RandomAccessIterator a, RandomAccessIterator b)

**Stable sort**algorithm over elements**a**to**b**:template <typename RandomAccessIterator> void sort(RandomAccessIterator a, RandomAccessIterator b)

Note: "

**Stable sorting**algorithms maintain the relative order of records with equal keys (i.e. values). That is, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list."

- wiki on stable sort - Non-mutating sequence algorithms

It does not modify contents of the containers they work on

Typical operation is searching container for particular element and returning its position.Finds position of

**t**in range**a**to**b**:template <typeame InputIterator, typename T> InputIterator find(InputIterator a, InputIterator b, const T& t);

Finds position of first element that makes predicate true in range of

**a**to**b**, otherwise position**b**returned:template <typeame InputIterator, typename Predicate> InputIterator find(InputIterator a, InputIterator b, Predicate p);

- Mutating sequence algorithms
STL's copy() function copies elements from a range to a location identified by an iterator:

template<typename InputIterator, typename OutputIterator> OutputIterator copy(InputIterator first, // beginning of source InputIterator last, // end of source OutputIterator result) // beginning of destination { while (first != last) { *result = *first; ++first; ++result; } return result; );

A sample code is available at STL iterators - copy_algorithm.

- Numerical algorithms
- Sums and Inner products
#include <iostream> #include <algorithm> using namespace std; int main() { double u[3] = {1.1, 2.2, 3.3}; double v[3] = {11.1, 22.2, 33.3}; /* sum */ double sum = accumulate(u, u+3, 0.0); /* inner product */ double ip = inner_product(u, u+3, v, 0.0); cout << "sum = " << sum << endl << "inner product = " << ip << endl; return 0; }

Output:

$ g++ -std=c++11 -o num num.cpp $ ./num sum = 6.6 inner product = 170.94

- Adjacent difference

- Sums and Inner products
- Generally use iterators to access containers instantiated on a given type

An input sequence is defined by a pair of iterators; an output sequence is defined by an iterator to its first element.
In general, an algorithm is parameterized by one or more operations that can be defined as functions or as function objects.
By returning the end of an input sequence, the algorithms indicate failure. For instance, **find(begin, end, x)** returns
**end** if it can not find **x**.

**find** is one of the non-modifying sequence operations. It finds the first occurrence of a value in a range:

#include <iostream> #include <vector> using namespace std; template<class T, class U> T find(T first, T last, const U&val;) { while(first != last && *first != val) ++first; return first; } int main() { vector<int> v; for(int i = 0; i < 10; i++) v.push_back(i); int x1 = 5, x2 = 100; vector<int>::iterator it; it = find(v.begin(),v.end(),x1); if(it != v.end()) { cout << "found " << x1 << endl; } else { cout << "could not find " << x1 << endl; } it = find(v.begin(),v.end(),x2); if(it != v.end()) { cout << "found " << x2 << endl; } else { cout << "could not find " << x2 << endl; } return 0; }

Output is:

found 5 could not find 100

**find()** operates on a sequence defined by pair of iterators. We're trying to find **val**
in the range **[fist:last)**. The **find()** returns iterator as the result. The iterator points either
to the first element of the sequence with the value **val** or to **last**.
Returning an iterator to the **one-beyond-the-last**
element of a sequence indicates **not found**.

The sequence consists of all the elements of a container, in this case, **vector**:

vector<int>::iterator it; it = find(v.begin(),v.end(),x1);

The iterator operations used are those of a **vector<int>::iterator**, in other words, **++** simply
moves a pointer to the next location in memory and ***** dereferences the pointer.

while(first != last && *first != val) ++first;

The iterator comparison, **first != last** is a pointer comparison, and the value comparison ***first != val** simply compares two integers.

We check the returned iterator against the end of our sequence to see if we found the value:

if(it != v.end()) {

We could have written the implicit loop of the **find()** more explicitly:

template<class T, class U> T find(T first, T last, const U&val;) { for(T iter = first; iter != last; ++iter) if(*iter == val) return iter; return last; }

Note that we needed addition variable **iter**. So, the original **find()** may be more
efficient and more compact.

The **find()** algorithm we wrote is generic. In other words, it can be used for different data types.

Here is an example using **list** instead of **vector** with the same **find()**:

#include <iostream> #include <list> #include <string> using namespace std; template<class T, class U> T find(T first, T last, const U&val;) { while(first != last && *first != val) ++first; return first; } int main() { list<string> myList(3); // creates a list with 3 elements myList.push_back ("A"); myList.push_front("B"); myList.push_back("C"); string x1 = "B", x2 = "F"; list<string>::iterator it; it = find(myList.begin(),myList.end(),x1); if(it != myList.end()) { cout << "found " << x1 << endl; } else { cout << "could not find " << x1 << endl; } it = find(myList.begin(),myList.end(),x2); if(it != myList.end()) { cout << "found " << x2 << endl; } else { cout << "could not find " << x2 << endl; } return 0; }

Output is:

found B could not find F

Here, the iteration for **find()** is that of a **list<string>::iterator**.
The operators have the required meaning, so that the underlying logic remains the same as for the
**vector<int>** of the previous example. However, the implementation is different. In other words,
**++** of the **++first** simply follows a pointer in the **link (or next)** part of the
element to where the next element of the **list** is stored.

From the examples above, we can easily find that the **find()** is extremely flexible as long as
we obey the simple rules for iterators.

Typically, we don't look for a specific value, rather we are more often look for a value that meets a certain criteria.
The **find()** would be more useful if we could set our own find criteria. The standard algorithm that searches
based on a criterion of user's choice is **find_if()**:

template<class T, class P> T find_if(T first, T last, P predicate) { while(first != last && !predicate(*first) ++first; return first; }

When we compare the **find_if()** with **find()**, it uses **!predicate(*first)** as
a stop condition rather than ***first != val**. So, it stops searching once the **predicate()** succeeds
rather than when an element has the same value with **val**.

A predicate is a function that returns
**true** or **false**. Our **find_if()** needs a predicate that takes one argument so that it can
say **predicate(*first)**.

Here are the examples of predicates:

bool GreaterThan5(double d) { return 5.0 < d; } bool FirstEven(int n) { return !(n % 2);}

And the complete code of using the **predicates** and **find_if()** is:

#include <iostream> #include <vector> #include <list> using namespace std; template<class T, class P> T find_if(T first, T last, P predicate) { while(first != last && !predicate(*first)) ++first; return first; } bool GreaterThan5(double d) { return 5.0 < d; } bool FirstEven(int n) { return !(n % 2);} void f1(vector<double>&v;) { vector<double>::iterator it = find_if(v.begin(), v.end(), GreaterThan5); if(it != v.end()) cout << "found " << *it << endl; else cout << "could not find " << endl; } void f2(list<int>&l;) { list<int>::iterator it = find_if(l.begin(), l.end(), FirstEven); if(it != l.end()) cout << "found " << *it << endl; else cout << "could not find " << endl; } int main() { vector<double> v; for(int i = 1; i <= 10; i++) v.push_back(i*1.0); list<int> myList; for(int i = 1; i <= 10; i++) myList.push_back(i); f1(v); f2(myList); return 0; }

Output from the run is:

found 6 found 2

The **find_if()** calls **GreaterThan5()** or **FirstEven()** for each element until
it finds the right element.

In the previous example, we used a predicate:

bool GreaterThan5(double d) { return 5.0 < d; }

That is ugly because if we want to find an element greater than 10, we have to make another one.
So, we need to find a better way! Let's investigate what the property of **GreaterThan()** predicate.
First, we can call it as a predicate like **predicate(*first)**. Second, we can store a value,
such as **10** or **x** so that it can be used when called.

That's the reason why we need a function object. In other words, we need an object that can behave like a function while it can store data. Here is the object we need:

class GreaterThan { int data; public: GreaterThan(int n):data(n) {} bool operator()(int n) const { return n > data; } };

When we say **GreaterThan(5)**, we make an object of class **GreaterThan** holding
**5** as its member **data**:

find_if(v.begin(), v.end(), GreaterThan(5));

We pass that object to **find_if()** as its parameter called **predicate**. For
each element of **v**, **find_if()** makes a call

predicate(*first)

This will invoke **GreaterThan::operator()** which is our function object using the argument ***first**.
The result is a comparison of the element's value, ***first**, with **5**.

What do we see here? The function call can be seen as an operator, the **() operator**, just like any operator.
Therefore, **()** in **predicate(*first)** is given a meaning by
**GreaterThan::operator()**, just as subscripting in **v[i]** is given a meaning by
**vector::operator[]**.

Here is the complete code:

#include <iostream> #include <vector> #include <list> using namespace std; template<class T, class P> T find_if(T first, T last, P predicate) { while(first != last && !predicate(*first)) ++first; return first; } class GreaterThan { int data; public: GreaterThan(int n):data(n) {} bool operator()(int n) const { return n > data; } }; void f(vector<int>&v;) { vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterThan(5)); if(it != v.end()) cout << "found " << *it << endl; else cout << "could not find " << endl; } int main() { vector<int> v; for(int i = 1; i <= 10; i++) v.push_back(i); f(v); return 0; }

Now, we established a way of allowing a function to carry around data that it needs. Obviously, the function objects provide us with a very powerful and convenient mechanism.

**accumulate()** is one of the simplest and most useful numerical algorithm:

a = accumulate(b,e,val)

It adds a sequence of values, and the type of the result **a** is the type of the
initial value **val**.

It is found in **<numeric>**.

#include <iostream> template <typename T, typename U> U accumulate(T first, T last, U acc) { while (first != last) { acc = acc + *first; ++first; } return acc; } int main() { int a[] = {1,2,3,4,5,6,7,8,9,10}; std::cout << accumulate(a, a + sizeof(a)/sizeof(int), 0) << std::endl; // 55 return 0; }

Here is another **accumulator()** which has four arguments, with the last one,
we can specify the operation to be used:

/* acc.cpp */ #include <iostream> #include <vector> #include <functional> template <typename T, typename U, typename Op> U accumulate(T first, T last, U acc, Op op) { while (first != last) { acc = op(acc, *first); ++first; } return acc; } int main() { double arr[] = {1.0, 2.1, 3.2, 4.3, 5.4}; std::vector<double> v(arr, arr+5); std::cout << accumulate(v.begin(),v.end(), 1.0, std::multiplies<double>()) << std::endl; std::cout << accumulate(v.begin(),v.end(), 1.0, std::divides<double>()) << std::endl; std::cout << accumulate(v.begin(),v.end(), 1.0, std::minus<int>()) << std::endl; return 0; }

Output is:

$ g++ -o acc acc.cpp $ ./acc 156.038 0.00640868 -14

Note that unlike other operations, the **minus()** operation was done against integers.

template <class InputIterator, class OutputIterator, class UnaryOperator> OutputIterator transform ( InputIterator first, InputIterator last, OutputIterator output, UnaryOperator op );

The **op** will be applied to all the elements in the input range **([first,last))** and stores each returned value in the range beginning at **output**.

Here is the sample which converts a string to uppercase.

#include <iostream> #include <string> #include <algorithm> std::string toUpperCase(std::string str) { std::string out; std::transform(str.begin(), str.end(), std::back_inserter(out), ::toupper); return out; } int main() { std::string str = "Stravinsky"; std::cout << "In: " << str << std::endl; std::cout << "Out: " << toUpperCase(str) << std::endl; return 0; }

**r=find(b,e,v)****r**points to the first occurrence of**v**in [**b**:**e**).**r=find_if(b,e,v)****r**points to the first occurrence of**v**in**[b:e)**so that**v(x)**is**true**.**r=count(b,e,v)****r**is the number of occurrence of**v**in**[b:e)**.**r=count_if(b,e,v)****r**is the number of occurrence in**[b:e)**so that**v(x)**is**true**.**sort(b,e)**Sort

**[b,e)**using**<**.**sort(b,e,v)**Sort

**[b,e)**using**v**.**copy(b,e,b2)**Copy

**[b,e)**to**[b2:b2+(e-b))**; there had better be enough elements after**b2**.**unique_copy(b,e,b2)**Copy

**[b,e)**to**[b2:b2+(e-b))**; don't copy adjacent duplicates.**merge(b,e,b2,e2,r)**Merge two sorted sequencec

**[b2,e2)**and**[b,e)**into**[r:r+(e-b)+(e2-b2))**.**r=equal_range(b,e,v)****r**is te subsequence of the sorted range**[b,e)**with the value**v**, basically, a binary search for**v**.**equal(b,e,b2)**Do all elements of

**[b,e)**and**[b2:b2+(e-b))**compare equal?**x=accumulate(b,e,i)****x**is the sum of**i**and the elements of**[b,e)**.**x=accumulate(b,e,i,op)**Like the other

**accumulate**, but with the sum calculate using**op**.**x=inner_product(b,e,b2,i)****x**is the inner product of**[b,e)**and**[b2:b2+(e-b))**.**x=inner_product(b,e,b2,i,op,op2)**Like the othe

**inner_product**, but with**op**and**op2**instead of**+**and*****.

Ph.D. / Golden Gate Ave, San Francisco / Seoul National Univ / Carnegie Mellon / UC Berkeley / DevOps / Deep Learning / Visualization