## C++ STL has a bunch of algorithms in itself. Sorting, numeric, removal, modifying and non-modifying algorithms are some examples.

In the article let’s talk about the famous mutating and non-mutating algorithms in C++.

**Mutating Algorithms**: These algorithms are modifying algorithms that are designed to work on the container elements and perform operations like shuffle, rotation, changing the order and more.

**Non-mutating Algorithms**: These algorithms do not change the order of elements. They use iterators for a particular operation.

## Some of the mutating and non-mutating algorithms

**NON-MUTATING**:

- max_element()
- min_element()
- accumulate()
- count()
- find()
- binary_search()
- lower_bound()
- upper_bound()
- rotate()
- fill()
- is_permutation()
- rand()

**MUTATING**:

- sort()
- reverse()
- next_permutation()
- prev_permutation()
- make_heap()
- merge()

Let us understand these algorithms in detail:

**max_element and min_element()**: These functions are used to find the minimum and maximum element from an array and vector. The functions return an iterator to the current element else return the end of the container.

**Example:**

vector v={ 10, 2, 3, 6, 90 };

auto it1 = max_element( v.begin(), v.end() );

auto it2 = min_element( v.begin(), v.end() );

cout << *(it1); // Prints 90 as max element

cout << *(it2); // Prints 2 as min element

int arr[] = { 1, 20, 3, 40, 70 };

cout << *( max_element( arr, arr+5) ); // Outputs 70

cout << *( min_element( arr, arr+5) ); // Outputs 1

**accumulate() and count()**: The accumulate() function sums up all the elements in the array or vector.

Example:

vector v ={ 10, 20, 30};

int result =0; // To store the accumulated sum

cout << accumulate( v.begin(), v.end(), res ); // Outputs 60

The **count()** function give the count of a number in an array, a character in a string.

**Example**

vector v = { 30, 20, 5, 10, 6, 10, 10 };

cout << count( v.begin(), v.end(), 10 ); // Outputs 3 as ’10’ is occuring 3 times

cout << count( v.begin(), v.end(), 3 ); // Outputs 0 as ‘3’ is occuring 0 times

string s = “codingninjas”

cout << count( s.begin(), s.end(), ‘n’ ); // Outputs 3 as ‘n’ is occuring 3 times

cout << count( s.begin(), s.end(), ‘e’ ); // Outputs 0 as ‘e’ is occuring 0 times

**find() and binary_search()**: The **find()** function finds an element in an array or a vector. If the element found it returns an iterator to that element(index at which the element is present else returns the iterator to the last of the vector or array.

**Example:**

vector v = { 5, 10, 7, 20 };

auto it = find ( v.begin(), v.end(), 10);

if( it == v.end() )

cout << ” Not Found ” ;

else

cout << ” Found ” << ( it – v.begin() ) ; // gives 1 as the output as 10 is present at 1st position in the vector

The binary_search() functions work similarly as the binary search algorithm. It gives TRUE if the search key is found else FALSE.

vector v = { 10, 20, 30, 40, 50 };

int x = 20;

if( binary_search ( v.begin(), v.end(), x ) == true ) // if x is found

cout << ” Found ” ;

else

cout << ” Not Found ” ;

**lower_bound and upper_bound**: The **lower_bound()** returns an iterator having an address of element greater than or equal to a given value in a sorted range. If you pass element greatest then it will return an iterator to the last element.

**Example:**

vector v = { 10, 20, 20, 30, 40 };

auto it = lower_bound( v.begin(), v.end(), 20 );

cout << (it – v.begin()); // outputs 1 as the index

cout << (*it); // Outputs the element 20

The **upper_bound()** returns an iterator to the first greater in the sorted array.

**Example: **vector v = { 10, 20, 20, 20, 30, 40};

auto it = upper_bound( v.begin(), v.end(), 20 );

cout << (it – v.begin()); // outputs 4 as the index

cout << (*it); // Outputs the element 30

**rotate() and Fill()**: The **rotate()** functions rotates a vector or array around a point.

**Example:**

vector v = { 10, 20, 20, 20, 30, 40};

auto it = upper_bound( v.begin(), v.end(), 20 );

cout << (it – v.begin()); // outputs 4 as the index

cout << (*it); // Outputs the element 30

The **fill() **function fills a vector or an array in two manners.

- All elements equal to the number to be filled
- Fill an element at a particular position.

**Example:**

vector v = { 10, 20, 30, 40};

fill( v.begin(), v.end(), 5); // If you print the vector it will be 5 5 5 5

fill(v.begin()+1, v.end()-2, 5); // Vector will be 10 5 30 40

**is_permutation() and rand(): **The **rand()** function takes no arguments and returns an integer that is a pseudo-random number between 0 and RAND_MAX. On the transformer, RAND_MAX is 2147483647. Consequently, we can take rand() % 10 to give us numbers from 0-9. If we want numbers from 1-10 we can now just scale up by adding one. The final result is : cout << (rand() % 10) + 1 << endl; To get different values, we use *srand(time(NULL))* once during the program.

The **is_permutation()** checks the two containers have the same set of items order may be different. It also handles multiple occurrences. When you use this function for the map and unordered map it checks for keys only.

**Example:**

vector v1 = { 10, 20, 30, 5};

vector v2 = { 20, 10, 5, 30};

if( is_permutation ( v1.begin(), v1.end(), v2.begin() )

cout << ” Yes ” ; // Outputs yes if same

else

cout << ” No ” ;

s**ort() and reverse():** The **sort()** algorithm sorts a container either in non-increasing or non-decreasing order.

**Example**

int arr[]={10, 2, 3, 100};

sort(arr, arr+4); // Outputs the array in ascending order

sort(arr, arr+4, greater ); // Outputs the array in descending order

The reverse() functions reverse a container.**Example:**

vector v = { 10, 20, 30 };

reverse( v.begin(), v.end() ); // Outputs 30 20 10

string str = “coding ninjas”;

reverse( str.begin(), str.end()); // Outputs sajnin gnidoc

**next_permutation() and prev_permutation(): **The **next_permutation()** is used to rearrange the elements in the range [first, last) into the next lexicographically greater permutation. A permutation is each one of the N! possible arrangements the elements can take (where N is the number of elements in the range). Different permutations can be ordered according to how they compare lexicographically to each other.

**Syntax:** bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

**Parameters: first, last:** Bidirectional iterators to the initial and final positions of the sequence. The range used is [first, last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.

**True:** if the function could rearrange the object as a lexicographically greater permutation. Otherwise, the function returns false to indicate that the arrangements not greater than the previous, but the lowest possible (sorted in ascending order).

**Application: **next_permutation is to find next lexicographically greater value for a given array of values.

**Examples:**

Input : next permutation of 1 2 3 is

Output : 1 3 2

Input : next permutation of 4 6 8 is

Output : 4 8 6

The **prev_permutation()** used to rearrange the elements in the range [first, last) into the previous lexicographically-ordered permutation. A permutation is each one of the N! possible arrangements the elements can take (where N is the number of elements in the range). Different permutations can be ordered according to how they compare lexicographically to each other.

**Syntax:** bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last );

**Parameters:** first, last: Bidirectional iterators to the initial and final positions of the sequence. The range used is [first, last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.

**True:** if the function could rearrange the object as a lexicographically smaller permutation. Otherwise, the function returns false to indicate that the arrangement is not less than the previous, but the largest possible (sorted in descending order).

**Application: **prev_permutation is to find previous lexicographically smaller value for a given array of values.

**Examples:**

Input : prev permutation of 3 2 1 is

Output : 3 1 2

Input : prev permutation of 8 6 4 is

Output :8 4 6

**make_heap() and merge(): **The make_heap() makes a max heap of a container by default. It can be further modified to min_heap.

**Example:**

vector v = { 15, 6, 7, 12, 30};

make_heap(v.begin(), v.end()); // Makes max heap

cout << v.front(); // Outputs 30 make_heap(v.begin(), v.end(), greater() ); // Makes min heap

cout << v.front(); // Outputs 6

The merge() function merges two containers into the third container.

The function will not work for an unsorted container.**Example:**

vector v1 = { 10, 20, 40 };

vector v2 ={ 5, 15, 30 };

vector v3(6);

merge( v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin() );

// v3 becomes 5 10 15 20 30 40

To learn more about Data Structures, click here.

**By Mansi Agarwal**

## Leave a Reply