Standard Template Library (STL) IV - Algorithms - 2020

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:

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

2. 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);
   

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

4. Numerical algorithms
   1. 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
      
      

   2. Adjacent difference
5. 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;
}

1. r=find(b,e,v)

   r points to the first occurrence of v in [b:e).

2. r=find_if(b,e,v)

   r points to the first occurrence of v in [b:e) so that v(x) is true.

3. r=count(b,e,v)

   r is the number of occurrence of v in [b:e).

4. r=count_if(b,e,v)

   r is the number of occurrence in [b:e) so that v(x) is true.

5. sort(b,e)

   Sort [b,e) using <.

6. sort(b,e,v)

   Sort [b,e) using v.

7. copy(b,e,b2)

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

8. unique_copy(b,e,b2)

   Copy [b,e) to [b2:b2+(e-b)); don't copy adjacent duplicates.

9. merge(b,e,b2,e2,r)

   Merge two sorted sequencec [b2,e2) and [b,e) into [r:r+(e-b)+(e2-b2)).

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

11. equal(b,e,b2)

    Do all elements of [b,e) and [b2:b2+(e-b)) compare equal?

12. x=accumulate(b,e,i)

    x is the sum of i and the elements of [b,e).

13. x=accumulate(b,e,i,op)

    Like the other accumulate, but with the sum calculate using op.

14. x=inner_product(b,e,b2,i)

    x is the inner product of [b,e) and [b2:b2+(e-b)).

15. x=inner_product(b,e,b2,i,op,op2)

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