Algorithm Library | C++ Magicians STL Algorithm
For all those who aspire to excel in competitive programming, only having a knowledge about containers of STL is of less use till one is not aware what all STL has to offer.
STL has an ocean of algorithms, for all < algorithm > library functions : Refer here.
Some of the most used algorithms on vectors and most useful oneβs in Competitive Programming are mentioned as follows :
Non-Manipulating Algorithms
- sort(first_iterator, last_iterator) β To sort the given vector.
- sort(first_iterator, last_iterator, greater<int>()) β To sort the given container/vector in descending order
- reverse(first_iterator, last_iterator) β To reverse a vector. ( if ascending -> descending OR if descending -> ascending)
- *max_element (first_iterator, last_iterator) β To find the maximum element of a vector.
- *min_element (first_iterator, last_iterator) β To find the minimum element of a vector.
- accumulate(first_iterator, last_iterator, initial value of sum) β Does the summation of vector elements
CPP
// A C++ program to demonstrate working of sort(), // reverse() #include <algorithm> #include <iostream> #include <vector> #include <numeric> //For accumulate operation using namespace std; int main() { // Initializing vector with array values int arr[] = {10, 20, 5, 23 ,42 , 15}; 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 Vector in Ascending order sort(vect.begin(), vect.end()); cout << "\nVector after sorting is: " ; for ( int i=0; i<n; i++) cout << vect[i] << " " ; // Sorting the Vector in Descending order sort(vect.begin(),vect.end(), greater< int >()); cout << "\nVector after sorting in Descending order is: " ; for ( int i=0; i<n; i++) cout << vect[i] << " " ; // Reversing the Vector (descending to ascending , ascending to descending) reverse(vect.begin(), vect.end()); cout << "\nVector after reversing is: " ; for ( int i=0; i<n; i++) cout << vect[i] << " " ; 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; } |
Vector is: 10 20 5 23 42 15 Vector after sorting is: 5 10 15 20 23 42 Vector after sorting in Descending order is: 42 23 20 15 10 5 Vector after reversing is: 5 10 15 20 23 42 Maximum element of vector is: 42 Minimum element of vector is: 5 The summation of vector elements is: 115
6.count(first_iterator, last_iterator,x) β To count the occurrences of x in vector.
7. find(first_iterator, last_iterator, x) β Returns an iterator to the first occurrence of x in vector and points to last address of vector ((name_of_vector).end()) if element is not present in vector.
CPP
// C++ program to demonstrate working of count() // and find() #include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { // Initializing vector with array values int arr[] = {10, 20, 5, 23 ,42, 20, 15}; int n = sizeof (arr)/ sizeof (arr[0]); vector< int > vect(arr, arr+n); cout << "Occurrences of 20 in vector : " ; // Counts the occurrences of 20 from 1st to // last element cout << count(vect.begin(), vect.end(), 20); // find() returns iterator to last address if // element not present find(vect.begin(), vect.end(),5) != vect.end()? cout << "\nElement found" : cout << "\nElement not found" ; return 0; } |
Occurrences of 20 in vector : 2 Element found
8. binary_search(first_iterator, last_iterator, x) β Tests whether x exists in sorted vector or not.
9. lower_bound(first_iterator, last_iterator, x) β returns an iterator pointing to the first element in the range [first,last) which has a value not less than βxβ.
10. upper_bound(first_iterator, last_iterator, x) β returns an iterator pointing to the first element in the range [first,last) which has a value greater than βxβ.
C++
// C++ program to demonstrate working of lower_bound() // and upper_bound(). #include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { // Initializing vector with array values int arr[] = {5, 10, 15, 20, 20, 23, 42, 45}; int n = sizeof (arr)/ sizeof (arr[0]); vector< int > vect(arr, arr+n); // Sort the array to make sure that lower_bound() // and upper_bound() work. sort(vect.begin(), vect.end()); // Returns the first occurrence of 20 auto q = lower_bound(vect.begin(), vect.end(), 20); // Returns the last occurrence of 20 auto p = upper_bound(vect.begin(), vect.end(), 20); 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; } |
The lower bound is at position: 3 The upper bound is at position: 5
Some Manipulating Algorithms
- arr.erase(position to be deleted) β This erases selected element in vector and shifts and resizes the vector elements accordingly.
- arr.erase(unique(arr.begin(),arr.end()),arr.end()) β This erases the duplicate occurrences in sorted vector in a single line.
C++
// C++ program to demonstrate working // of erase #include <algorithm> #include <bits/stdc++.h> #include <iostream> #include <vector> using namespace std; int main() { // Initializing vector with array 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 << "Given Vector is:\n" ; for ( int i = 0; i < n; i++) cout << vect[i] << " " ; vect.erase(find(vect.begin(),vect.end(),10)); cout << "\nVector after erasing element:\n" ; for ( int i = 0; i < vect.size(); i++) cout << vect[i] << " " ; vect.erase(unique(vect.begin(), vect.end()), vect.end()); cout << "\nVector after removing duplicates:\n" ; for ( int i = 0; i < vect.size(); i++) cout << vect[i] << " " ; return 0; } |
Given Vector is: 5 10 15 20 20 23 42 45 Vector after erasing element: 5 15 20 20 23 42 45 Vector after removing duplicates: 5 15 20 23 42 45
3. next_permutation(first_iterator, last_iterator) β This modified the vector to its next permutation.
4. prev_permutation(first_iterator, last_iterator) β This modified the vector to its previous permutation.
CPP
// C++ program to demonstrate working // of next_permutation() // and prev_permutation() #include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { // Initializing vector with array 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 << "Given Vector is:\n" ; for ( int i=0; i<n; i++) cout << vect[i] << " " ; // modifies 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; } |
Given Vector is: 5 10 15 20 20 23 42 45 Vector after performing next permutation: 5 10 15 20 20 23 45 42 Vector after performing prev permutation: 5 10 15 20 20 23 42 45
5. distance(first_iterator,desired_position) β It returns the distance of desired position from the first iterator.This function is very useful while finding the index.
CPP
// C++ program to demonstrate working of distance() #include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { // Initializing vector with array values int arr[] = {5, 10, 15, 20, 20, 23, 42, 45}; int n = sizeof (arr)/ sizeof (arr[0]); vector< int > vect(arr, arr+n); // Return distance of first to maximum element cout << "Distance between first to max element: " ; cout << distance(vect.begin(), max_element(vect.begin(), vect.end())); return 0; } |
Distance between first to max element: 7
More β STL Articles