## Introduction

The Standard Template Library(STL) is a C++ library of container classes, algorithms, and iterators that contains many of computer science's fundamental algorithms and data structures. Since this STL is a generic library, its components are strongly parameterized: practically every component is a template.

STL provides a variety of algorithms that are implemented on any container. As a result, we no longer need to develop complicated algorithms and can instead rely on the built-in methods supplied by the STL algorithm library.

The use of these algorithms from STL saves time, effort, code and are very reliable. Hence, a single algorithm function is applied to every container type.

For example, To implement Binary Search in ** C++**, we will have to write the following function:

```
bool binary_search( int l , int r , int key ,int a[])
{
if(l > r)
return -1;
else
{
int mid=(l+r)/2;
if(a[mid] == key)
{
return true;
}
else if(a[mid] > key)
{
return binary_search(l, mid-1, key, a);
}
else if(a[mid] < key)
{
return binary_search(mid+1, r, key, a);
}
}
}
```

In STL, however, we can use the algorithm library's binary search() function to execute the binary search. The library already has a definition for it:

`return binary_search(a, a+a.size())`

Also see, __Literals in C____.__

## Types of Algorithms in Algorithm Library

### Non-Manipulating Algorithms

Some of the STL built-in algorithms are as follows:

**sort**– To sort a given vector.**reverse**– To reverse a vector.***max_element**– To find the maximum element from a vector.***min_element**– To find the minimum element from a vector.-
**accumulate**– Does the summation of vector elements.

```
// Program to demonstrate working of STL Algorithms
//(sort,reverse,max_element, min_element, accumulate)
#include <algorithm>
#include <iostream>
#include <vector>
#include <numeric> //For accumulate algo operation
using namespace std;
int main()
{
// Initializing a vector with int
int arr[] = {40,60,15,73,12,5};
int n = sizeof(arr)/sizeof(arr[0]);
vector<int> vect(arr, arr+n);
cout << "Vector is: ";
for (int i=0; i<n; i++)
cout << vect[i] << " ";
// Sorting the elements in Ascending order
sort(vect.begin(), vect.end());
cout << "\nVector after sorting is: ";
for (int i=0; i<n; i++)
cout << vect[i] << " ";
// Reversing the Vector elements’ order
reverse(vect.begin(), vect.end());
cout << "\nVector after reversing is: ";
for (int i=0; i<6; i++)
cout << vect[i] << " ";
//Finding the max and min element from the vector
cout << "\nMaximum element of vector is: ";
cout << *max_element(vect.begin(), vect.end());
cout << "\nMinimum element of vector is: ";
cout << *min_element(vect.begin(), vect.end());
// Starting the summation from 0
cout << "\nThe summation of vector elements is: ";
cout << accumulate(vect.begin(), vect.end(), 0);
return 0;
}
```

Output

```
Vector is: 40 60 15 73 12 5
Vector after sorting is: 5 12 15 40 60 73
Vector after reversing is: 73 60 40 15 12 5
Maximum element of vector is: 73
Minimum element of vector is: 5
The summation of vector elements is: 205.
```

Try and compile with __online c++ compiler__.

**count**– It counts the occurrences of an element ‘ele’ from the vector.-
**find**– it returns an iterator to the first occurrence of an element ‘ele’ in vector and points to the last address of vector if the element is not present in the vector.

```
// Program to demonstrate working of STL Algorithms //(find,count)
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main()
{
// Initializing vector
int arr[] = {40, 60, 78, 93 ,12, 60, 9};
int n = sizeof(arr)/sizeof(arr[0]);
vector<int> vect(arr, arr+n);
cout << "Occurrences of 60 in vector : ";
// To Count the occurrences of 60
cout << count(vect.begin(), vect.end(), 60);
// To find and return the result from the vector
find(vect.begin(), vect.end(),93) != vect.end()?
cout << "\nElement found":
cout << "\nElement not found";
return 0;
}
```

Output

```
Occurrences of 60 in vector : 2
Element found
```

Must Read __Algorithm Types__

**Binary_search**– This function tests whether an element ‘ele’ exists in sorted vector order or not.**Lower_bound**– returns an iterator pointing to the first element in the range [first, last], which has a value not less than ‘ele’.-
**upper_bound**– it returns an iterator pointing to the first element in the range [first, last], which has a value greater than ‘ele’.

```
// lower_bound()and upper_bound().
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main()
{
// Initializing the vector
int arr[] = {5, 10, 15, 30, 30, 33, 42, 45};
int n = sizeof(arr)/sizeof(arr[0]);
vector<int> vect(arr, arr+n);
// Sorting array for lower_bound()
// and upper_bound() to work.
sort(vect.begin(), vect.end());
// Returns the first occurrence of 30
auto q = lower_bound(vect.begin(), vect.end(), 30);
// Returns the last occurrence of 30
auto p = upper_bound(vect.begin(), vect.end(), 30);
cout << "The lower bound is at position: ";
cout << q-vect.begin() << endl;
cout << "The upper bound is at position: ";
cout << p-vect.begin() << endl;
return 0;
}
```

Output

```
The lower bound is at position: 3
The upper bound is at position: 5
```

Must Read __Lower Bound in C++__

### Manipulating Algorithms

**arr.erase**(position to be deleted) – It removes a selected element from a vector and resizes and shifts the vector elements-
**arr.erase**(unique(arr.begin(),arr.end()),arr.end()) – This deletes duplicate occurrences on a single line in a sorted vector.

```
// Code to demonstrate erase()
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main()
{
// Initializing values
int arr[] = {5, 10, 15, 20, 20, 23, 42, 45};
int n = sizeof(arr)/sizeof(arr[0]);
vector<int> vect(arr, arr+n);
cout << "Vector is :";
for (int i=0; i<6; i++)
cout << vect[i]<<" ";
// Delete second element of vector
vect.erase(vect.begin()+1);
cout << "\nVector after erasing the element: ";
for (int i=0; i<vect.size(); i++)
cout << vect[i] << " ";
// sorting to enable use of unique()
sort(vect.begin(), vect.end());
cout << "\nVector before removing duplicate "
" occurrences: ";
for (int i=0; i<vect.size(); i++)
cout << vect[i] << " ";
// Deletes the duplicate occurrences
vect.erase(unique(vect.begin(),vect.end()),vect.end());
cout << "\nVector after deleting duplicates: ";
for (int i=0; i< vect.size(); i++)
cout << vect[i] << " ";
return 0;
}
```

Output

```
Vector is :5 10 15 20 20 23
Vector after erasing the element: 5 15 20 20 23
Vector before removing duplicate occurrences: 5 15 20 20 23
Vector after deleting duplicates: 5 15 20 23 42 45
```

**next_permutation**(first_iterator, last_iterator) – It changes a vector to its next permutation.**prev_permutation**(first_iterator, last_iterator) – It changes a vector to its previous permutation.

```
// Code to demonstrate next_permutation() and prev_permutation()
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main()
{
// Initializing
int arr[] = {15, 40, 65, 8, 8, 21, 31, 45};
int n = sizeof(arr)/sizeof(arr[0]);
vector<int> vect(arr, arr+n);
cout << "Given Vector is:\n";
for (int i=0; i<n; i++)
cout << vect[i] << " ";
// changes the vector to its next permutation order
next_permutation(vect.begin(), vect.end());
cout << "\nVector after performing
next permutation:\n";
for (int i=0; i<n; i++)
cout << vect[i] << " ";
prev_permutation(vect.begin(), vect.end());
cout << "\nVector after performing prev
permutation:\n";
for (int i=0; i<n; i++)
cout << vect[i] << " ";
return 0;
}
```

Output

```
Given Vector is:
15 40 65 8 8 21 31 45
Vector after performing next permutation:
15 40 65 8 8 21 45 31
Vector after performing prev permutation:
15 40 65 8 8 21 31 45
```

**Check out this problem - **__First And Last Occurrences Of X__

Must Read__ ____Dynamic Binding in C++__