In this article you will learn about stl algorithm library in c++.
Are you a competitive programmer or very passionate programmer then you must know about STL algorithm library. It contains very rich set of algorithms. If you practice this well you can nail any programming interview. All inbuilt algorithms implemented in this library were implemented in the best complexity way. So using those is better than writing own code. It also saves time and code readability.
C++ STL Algorithm Library
There are many of those algorithms. We will see some of them which mostly used.
To work with these we first need to include algorithm library. That is #include<algorithm>
In all previous articles we learned about containers, now we can apply these algorithms on those containers.
Since main intention of algorithm is to retrieve information or to know some of properties, these will not do any modifications on container sizes or container storage. They just use iterators to apply on containers.
min (a, b): This gives minimum value of a and b. Here conditions are both a and b must be same data type. In case if a and b are equal it gives same value.
max (a,b) : This gives maximum value of a and b. Both a and b should be same data type.
sort (first_iterator , last_iterator): Sorts the elements of a container between given vectors.
Above sort sorting function used to sort containers only. Because they only have iterators. But for normal arrays. We have to use sort (array_begin, array_end):
Example program to show above algorithms:
//Standard library algorithms
#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;
int main(){
cout << "min(10,3) gives " << min(10,3) << "\n";
cout << "min(5,5) gives " << min(5,5) << "\n";
cout << "min ('A', 'B') gives" << min ('A' , 'B') << "\n";
cout << endl << "max(10,3) gives " << max(10,3) << "\n";
cout << "max(5,5) gives " << max(5,5) << "\n";
cout << "max ('A', 'B') gives" << max ('A' , 'B') << "\n";
vector <int> v;
vector <int> :: iterator it;
for(int i=0; i<5;i++) v.push_back(10-i);
cout << endl << "Elements of vector before sort " << endl;
for(it= v.begin(); it!=v.end();it++) cout << *it << " ";
cout << endl;
cout << "Performing sort(v.begin(), v.end()) " << endl;
sort(v.begin(), v.end());
cout << "After above function vector elements are " << endl;
for(it= v.begin(); it!=v.end(); it++) cout << *it << " " ;
cout << endl;
int ar[5];
for(int i=0; i<5 ;i++) ar[i]= 15-i;
cout << endl << "Array elements are " << endl;
for(int i=0; i<5; i++) cout << ar[i] << " " ;
cout << endl;
cout << "Performing sort(ar+0, ar+5) " << endl;
sort(ar+0, ar+5);
cout << "After above operation array elements are " << endl;
for(int i=0;i<5; i++) cout << ar[i] << " ";
cout << endl;
return 0;
}
Output
min(10,3) gives 3
min(5,5) gives 5
min (‘A’, ‘B’) givesA
max(10,3) gives 10
max(5,5) gives 5
max (‘A’, ‘B’) givesB
Elements of vector before sort
10 9 8 7 6
Performing sort(v.begin(), v.end())
After above function vector elements are
6 7 8 9 10
Array elements are
15 14 13 12 11
Performing sort(ar+0, ar+5)
After above operation array elements are
11 12 13 14 15
find(): This will find given element present in container or not. Input parameters for this are range and element. Range contains two values, beginning of the range and ending of the range.
find() on arrays will be find(ar_base_address, ar_end, element);
Similarly find() on other stl containers will be find(iterator_to_1st, iterator_to_last, element);
One more thing we need to know about this find() is, if given element is present it points that element position, else it points to end of the container. This we can use for checking purpose.
count (): This is same way of find() algorithm. But this returns number of times given element present in the given range of elements.
Same like find(), for arrays we need to give base address as range and for other STL containers like vector, dequeue, list, etc. give iterator positions as range.
equal(): This is used to compare range of sequences. We will give some range as parameter to compare other range. It gives true if all elements equal in the range else returns false.
For example if give a vector and an array ranges, equal gives true if and only if ith element of vector and array are same. Where i is between given range.
Example program to show above algorithms:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
int ar[5];
for(int i=0;i<5; i++) ar[i]= i*i;
cout << "Array contains 0, 1, 4, 9, 16" << endl;
cout << "Performing find(ar+0, ar+5, 44) " << endl;
int *position= find(ar+0, ar+5, 44);
if(position == ar+5){
cout << "Element not found in the array " << endl;
}
else{
cout << "Element found in the array " << endl;
}
vector <int> vec;
vector <int> :: iterator it;
for(int i=0; i<5; i++) vec.push_back(i*i);
cout << endl << "Vector contains elements 0, 1, 4, 9, 16" << endl;
cout << "Performing find (vec.begin(), vec.end(), 4) " << endl;
it = find (vec.begin(), vec.end(), 4);
if(it == vec.end()){
cout << "Element not found in the vector " << endl;
}
else{
cout << "Element found in the vector " << endl;
}
ar[0]= vec[0]= 2;
ar[1]= vec[1]= 3;
ar[2]= vec[2]= 2;
ar[3]= vec[3]= 2;
ar[4]= vec[4]= 5;
cout << endl << "Array and vector contains elements 2, 3, 2, 2, 3" << endl;
cout << "Performing count (ar+0, ar+5, 2) on array " << endl;
int cnt= count(ar+0, ar+5, 2);
cout << "2 present " << cnt << " times in the array" << endl;
cout << "Performing count (vec.begin(), vec.end(), 3) on vector " << endl;
cnt= count(vec.begin(), vec.end(), 3);
cout << "3 present " << cnt << " times in the vector " << endl;
cout << endl << "elements of array are " << endl;
for(int i=0; i<5; i++) cout << ar[i] << " " ;
cout << endl;
cout << "elements in the vector are " << endl;
for(it=vec.begin(); it!=vec.end(); it++) cout << *it << " ";
cout << endl;
cout << "Now performing equal(vec.begin(), vec.end(), ar) " << endl;
bool chk = equal(vec.begin(), vec.end(), ar);
if(chk)
cout << "Both sequences are equal "<< endl;
else
cout << "Givens sequences are not equal " << endl;
return 0;
}
Output
Array contains 0, 1, 4, 9, 16
Performing find(ar+0, ar+5, 44)
Element not found in the array
Vector contains elements 0, 1, 4, 9, 16
Performing find (vec.begin(), vec.end(), 4)
Element found in the vector
Array and vector contains elements 2, 3, 2, 2, 3
Performing count (ar+0, ar+5, 2) on array
2 present 3 times in the array
Performing count (vec.begin(), vec.end(), 3) on vector
3 present 1 times in the vector
elements of array are
2 3 2 2 5
elements in the vector are
2 3 2 2 5
Now performing equal(vec.begin(), vec.end(), ar)
Both sequences are equal
reverse(start_, end_): This algorithm reverse the elements in given range.
accumulate(start_, end_, initial_sum ): Accumulate is used to sum the all elements in the give range. It adds elements to initial sum which also we specify as a parameter to this accumulate function.
To use this accumulate function we should include numeric library. i.e #include <numeric>
distance( start_, position): This function used to find the how much distance from the given iterator position to given position. Position might be anything specified by user. For example position may be minimum element, of maximum element of the vector/container.
Example program to show above functions:
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric> // This is for accumulate function
using namespace std;
int main(){
vector <int> vec;
vector <int> :: iterator it;
for(int i=0; i<5; i++) vec.push_back(i+5);
cout << "Vector contains elements " ;
for(it=vec.begin(); it!= vec.end(); it++) cout << *it << " ";
cout << endl;
cout << "Performing reverse(vec.begin(), vec.end()) " << endl;
reverse(vec.begin(), vec.end());
cout << "Now vector elements are " ;
for(it=vec.begin(); it!= vec.end(); it++) cout << *it << " ";
cout << endl;
cout << endl << "Performing accumulate (vec.begin(), vec.end(), 0) " << endl;
int total= accumulate(vec.begin(), vec.end(), 0);
cout << "Total of vector elements using accumulate function is " << total << endl;
cout << endl << "Finding distance from starting of vector to maximum element of the vector " << endl;
cout << "For that performing distance(vec.begin(), max(vec.begin(), vec.end()) " << endl;
int dist= distance (vec.begin(), max(vec.begin(), vec.end() ));
cout << "The distance to maximum element from starting of the iterator is " << dist << endl;
return 0;
}
Output
Vector contains elements 5 6 7 8 9
Performing reverse(vec.begin(), vec.end())
Now vector elements are 9 8 7 6 5
Performing accumulate (vec.begin(), vec.end(), 0)
Total of vector elements using accumulate function is 35
Finding distance from starting of vector to maximum element of the vector
For that performing distance(vec.begin(), max(vec.begin(), vec.end())
The distance to maximum element from starting of the iterator is 5
next_permuatation(start_ , end_ ): As I said starting of this article, STL is a friend to competitive programmer, generating permutations is one of the main task in some questions. By using this we can generate next permutation of given sequence between the elements given specified range.
prev_permutation (start_, end_ ): This gives previous permutation of the sequence.
Example program to show above functions:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
vector <int> vec;
vector <int> :: iterator it;
for(int i=1; i<=5; i++) vec.push_back(i);
cout << "Elements in the vector are " ;
for(it = vec.begin(); it!= vec.end(); it++) cout << *it << " ";
cout << endl;
cout << "next_permutation (vec.begin(), vec.end()) gives " << endl;
next_permutation(vec.begin(), vec.end());
for(it = vec.begin(); it!= vec.end(); it++) cout << *it << " ";
cout << endl;
cout << "prev_permutation (vec.begin(), vec.end()) gives " << endl;
prev_permutation(vec.begin(), vec.end());
for(it = vec.begin(); it!= vec.end(); it++) cout << *it << " ";
cout << endl;
return 0;
}
Output
Elements in the vector are 1 2 3 4 5
next_permutation (vec.begin(), vec.end()) gives
1 2 3 5 4
prev_permutation (vec.begin(), vec.end()) gives
1 2 3 4 5
lower_bound(start_, end_ , ele ): Returns an iterator pointing to the first element in the range which has element not less than ele.
upper_bound(start_, end_ ,ele ): Returns an iterator pointing to the first element in the given range which has element greater than ele.
These two functions used in performing binary search operation:
Example program to show above functions:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
int ar[5]= {10, 20, 30, 40, 50};
vector <int> vec (ar, ar+5) ;
vector <int> :: iterator it;
sort(vec.begin(), vec.end()); // Sorting must need for lower_bound, upper_bound and binary search
cout << "Elements in the vector are " ;
for(it = vec.begin(); it!= vec.end(); it++) cout << *it << " ";
cout << endl;
it = lower_bound(vec.begin(), vec.end(), 25);
cout << "Lower bound for 25 is at position " << it- vec.begin() << endl;
it = upper_bound(vec.begin(), vec.end(), 35);
cout << "upper bound for 35 is at position " << it- vec.begin() << endl;
return 0;
}
Output
Elements in the vector are 10 20 30 40 50
Lower bound for 25 is at position 2
upper bound for 35 is at position 3
Comment below if you have any queries related to above C++ stl algorithm library.
The post C++ STL Algorithm Library appeared first on The Crazy Programmer.
from The Crazy Programmer https://www.thecrazyprogrammer.com/2017/12/stl-algorithm.html
Comments
Post a Comment