# STL in CPP ( Part VI )

## Algorithms

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:

   ```cpp
   template <typename RandomAccessIterator>
   void sort(RandomAccessIterator a, RandomAccessIterator b)
   ```

   Stable sort algorithm over elements a to b:

   ```cpp
   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](http://en.wikipedia.org/wiki/Category:Stable_sorts)
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:

   ```cpp
   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:

   ```cpp
   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:

   ```cpp
   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](http://www.bogotobogo.com/cplusplus/stl3_iterators.php#copy_algorithm).
4. **Numerical algorithms**
   1. Sums and Inner products

      ```cpp
      #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:

      ```shortcode
      $ 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()

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

```cpp
#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**:

```cpp
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.

```cpp
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:

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

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

```cpp
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()**:

```cpp
#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.

## find\_if()

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()**:

```cpp
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:

```cpp
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:

```cpp
#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.

## Functors

In the previous example, we used a predicate:

```cpp
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:

```cpp
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**:

```cpp
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

```cpp
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:

```cpp
#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()

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

```cpp
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>**.

```cpp
#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:

```cpp
/* 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:

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

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

## transform()

```cpp
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.

```cpp
#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;
}
```

## List of algorithms

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 **\***.

<br>