## Introduction

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

Also, see __Literals in C__.__Fibonacci Series in C++__

**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 β ;
```

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

**Also check out - **__Inorder Predecessor__

## Frequently Asked Questions

**What are mutating algorithms in C++?**

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

**What are non-mutating algorithms in C++?**

Non-mutating algorithms in C++ do not change the order of elements. They use iterators for a particular operation.

**What are containers in C++?**

An object used to store collections of specific types of other objects is known as a container in C++. These containers can store any data type, including user-defined data types. For example, you can use a vector to store a list of studentsβ names.

## Conclusion

In this article, we have discussed mutating and non-mutating algorithms in C++. We went over some of the algorithms in depth and provided examples.

You can visit more interesting articles on C++, such as

__Algorithms in C++ STL__.__STL in C++__.__More about STL Containers.____Dynamic Binding in C++____Bubble Sort C++____C++ Interview Questions__

To learn more about __Data Structures__, click __here.__