Mutating & Non-Mutating algorithms in C++

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

• Prims and Kruskal Algorithm

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.