Skip to main content

C++ STL Algorithm Library

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
Labels:

Comments

Post a Comment

Popular posts from this blog

dotnet sdk list and dotnet sdk latest

Can someone make .NET Core better with a simple global command? Fanie Reynders did and he did it in a simple and elegant way. I'm envious, in fact, because I spec'ed this exact thing out in a meeting a few months ago but I could have just done it like he did and I would have used fewer keystrokes! Last year when .NET Core was just getting started, there was a "DNVM" helper command that you could use to simplify dealing with multiple versions of the .NET SDK on one machine. Later, rather than 'switching global SDK versions,' switching was simplified to be handled on a folder by folder basis. That meant that if you had a project in a folder with no global.json that pinned the SDK version, your project would use the latest installed version. If you liked, you could create a global.json file and pin your project's folder to a specific version. Great, but I would constantly have to google to remember the format for the global.json file, and I'd constan...
Post a Comment
Read more

15 Web Design Trends to Watch in 2018

The modern world is full of extraordinary things that influence our imagination and mood. Our soul needs a perfect atmosphere and impressive spots. To apply such things in practice, we have submitted the list of the web trends that deserve your attention. Robert frost design analysis will meet all your wishes and expectations. Image Source Web Design Trends to Watch in 2018 1. More Organic Shapes Until this year, web design, as well as mobile design, were based on the right-angled and sharp-edged shapes. However, it seems that this year will bring some significant changes in the field of web design. The recent trends will offer the absolute rounded corners. In addition, the web design of 2018 will make the real things look like the cartoonish ones. 2.   Bold Minimalism Although some of you may think that this web design trend will not attract the Internet users. Indeed, the notion of minimalism is often associated with boredom and dullness. However, in this case, bold ...
Post a Comment
Read more

R vs Python for Machine Learning

There are so many things to learn before to choose which language is good for Machine Learning. We will discuss each and everything about R as well as Python and the situation or problem in which situation we have to use which language. Let’s start Python and R are the two most Commonly used Programming Languages for Machine Learning and because of the popularity of both the languages Novice or you can say fresher are getting confused, whether they should choose R or Python language to commence their career in the Machine learning domain. Don’t worry guys through this article we will discuss R vs Python for Machine Learning. So, without exaggerating this article let’s get started. We will start it from the very Basics things or definitions. R vs Python for Machine Learning Introduction R is a programming language made by statisticians and data miners for statistical analysis and graphics supported by R foundation for statistical computing. R also provides high-quality graphics and...
1 comment
Read more