Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Types of Algorithms in Algorithm Library
2.1.
Non-Manipulating Algorithms
2.2.
Manipulating Algorithms
3.
FAQs
4.
Key Takeaways:
Last Updated: Mar 27, 2024
Easy

Algorithms In C++ STL

Author Akash Nagpal
1 upvote
gp-icon
Basics of C++
Free guided path
9 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

The Standard Template Library(STL) is a C++ library of container classes, algorithms, and iterators that contains many of computer science's fundamental algorithms and data structures. Since this STL is a generic library, its components are strongly parameterized: practically every component is a template.

STL provides a variety of algorithms that are implemented on any container. As a result, we no longer need to develop complicated algorithms and can instead rely on the built-in methods supplied by the STL algorithm library.

The use of these algorithms from STL saves time, effort, code and are very reliable. Hence, a single algorithm function is applied to every container type.


For example, To implement Binary Search in C++, we will have to write the following function:

bool binary_search( int l , int r , int key ,int a[])
{
    if(l > r)
        return -1;
    else
    {
        int mid=(l+r)/2;
       
        if(a[mid] == key) 
        {
            return true;
        }
        else if(a[mid] > key) 
        {
            return binary_search(l, mid-1, key, a);
        }
        else if(a[mid] < key) 
        {
            return binary_search(mid+1, r, key, a);
        }
    }
}

 

In STL, however, we can use the algorithm library's binary search() function to execute the binary search. The library already has a definition for it:

return binary_search(a, a+a.size())


Also see, Literals in C.

Types of Algorithms in Algorithm Library

Non-Manipulating Algorithms

Some of the STL built-in algorithms are as follows: 

  • sort – To sort a given vector.
  • reverse – To reverse a vector.
  • *max_element – To find the maximum element from a vector.
  • *min_element – To find the minimum element from a vector.
  • accumulate – Does the summation of vector elements.
     
// Program to demonstrate working of STL Algorithms
//(sort,reverse,max_element, min_element, accumulate)
#include <algorithm>
#include <iostream>
#include <vector>
#include <numeric> //For accumulate algo operation
using namespace std;
 
int main()
{
    // Initializing a vector with int
    int arr[] = {40,60,15,73,12,5};
    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 elements in Ascending order
    sort(vect.begin(), vect.end());
 
    cout << "\nVector after sorting is: ";
    for (int i=0; i<n; i++)
       cout << vect[i] << " ";
 
    // Reversing the Vector elements’ order
    reverse(vect.begin(), vect.end());
 
    cout << "\nVector after reversing is: ";
    for (int i=0; i<6; i++)
        cout << vect[i] << " ";
    
    //Finding the max and min element from the vector
    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;
}

Output

Vector is: 40 60 15 73 12 5 
Vector after sorting is: 5 12 15 40 60 73 
Vector after reversing is: 73 60 40 15 12 5 
Maximum element of vector is: 73
Minimum element of vector is: 5
The summation of vector elements is: 205.

Try and compile with online c++ compiler.

  • count – It counts the occurrences of an element ‘ele’ from the vector.
  • find – it returns an iterator to the first occurrence of an element ‘ele’ in vector and points to the last address of vector if the element is not present in the vector.
     
// Program to demonstrate working of STL Algorithms //(find,count)
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    // Initializing vector
    int arr[] = {40, 60, 78, 93 ,12, 60, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    vector<int> vect(arr, arr+n);
 
    cout << "Occurrences of 60 in vector : ";
 
    // To Count the occurrences of 60 
    cout << count(vect.begin(), vect.end(), 60);
 
    // To find and return the result from the vector
    find(vect.begin(), vect.end(),93) != vect.end()?
                         cout << "\nElement found":
                     cout << "\nElement not found";
 
    return 0;
}

Output

Occurrences of 60 in vector : 2
Element found

Must Read Algorithm Types

  • Binary_search – This function tests whether an element ‘ele’ exists in sorted vector order or not.
  • Lower_bound – returns an iterator pointing to the first element in the range [first, last], which has a value not less than ‘ele’.
  • upper_bound – it returns an iterator pointing to the first element in the range [first, last], which has a value greater than ‘ele’. 
     
// lower_bound()and upper_bound().
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    // Initializing the vector
    int arr[] = {5, 10, 15, 30, 30, 33, 42, 45};
    int n = sizeof(arr)/sizeof(arr[0]);
    vector<int> vect(arr, arr+n);
 
    // Sorting array for lower_bound()
    // and upper_bound() to work.
    sort(vect.begin(), vect.end());
 
    // Returns the first occurrence of 30
    auto q = lower_bound(vect.begin(), vect.end(), 30);
 
    // Returns the last occurrence of 30
    auto p = upper_bound(vect.begin(), vect.end(), 30);
 
    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;
}

Output

The lower bound is at position: 3
The upper bound is at position: 5


Must Read Lower Bound in C++

Manipulating Algorithms

  • arr.erase(position to be deleted) – It removes a selected element from a vector and resizes and shifts the vector elements
  • arr.erase(unique(arr.begin(),arr.end()),arr.end()) – This deletes duplicate occurrences on a single line in a sorted vector.
     
// Code to demonstrate erase()
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    // Initializing 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 << "Vector is :";
    for (int i=0; i<6; i++)
        cout << vect[i]<<" ";
 
    // Delete second element of vector
    vect.erase(vect.begin()+1);
 
    cout << "\nVector after erasing the element: ";
    for (int i=0; i<vect.size(); i++)
        cout << vect[i] << " ";
 
    // sorting to enable use of unique()
    sort(vect.begin(), vect.end());
 
    cout << "\nVector before removing duplicate "
             " occurrences: ";
    for (int i=0; i<vect.size(); i++)
        cout << vect[i] << " ";
 
    // Deletes the duplicate occurrences
    vect.erase(unique(vect.begin(),vect.end()),vect.end());
 
    cout << "\nVector after deleting duplicates: ";
    for (int i=0; i< vect.size(); i++)
        cout << vect[i] << " ";
 
    return 0;
}

Output

Vector is :5 10 15 20 20 23 
Vector after erasing the element: 5 15 20 20 23 
Vector before removing duplicate  occurrences: 5 15 20 20 23 
Vector after deleting duplicates: 5 15 20 23 42 45

 

  • next_permutation(first_iterator, last_iterator) – It changes a vector to its next permutation.
  • prev_permutation(first_iterator, last_iterator) – It changes a vector to its previous permutation. 
// Code to demonstrate next_permutation() and prev_permutation()
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    // Initializing 
    int arr[] = {15, 40, 65, 8, 8, 21, 31, 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] << " ";
 
    // changes the 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;
}

Output

Given Vector is:
15 40 65 8 8 21 31 45 
Vector after performing next permutation:
15 40 65 8 8 21 45 31 
Vector after performing prev permutation:
15 40 65 8 8 21 31 45

Check out this problem - First And Last Occurrences Of X

Must Read Dynamic Binding in C++

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

FAQs

  1. How many types of methods are there in Sorting Algorithm?
    There are about three types of Sorting methods available in the Sorting Algorithm. These methods are :
    Sort : Syntax sort(start_iterator, end_iterator ) 
    Is_sorted : Syntax is_sorted(start_iterator, end_iterator)
    Partial_sort : Syntax partial_sort(start, middle, end ) 
     
  2. Why do we use the numeric library for accumulate method?
    The numeric library is used to compute the cumulative inner product of a particular range. It is used to compute partial sums of range as well as to store increasing sequences.

Key Takeaways:

In this article, we have extensively discussed the Algorithms in C++ STL. Check out the Sequence Containers for the following topics.

Also read - Kadane's Algorithm, Include iostream

We hope that this blog has helped you enhance your knowledge regarding various Algorithms of STL Libraries and if you would like to learn more, check out our articles on Coding Ninjas and visit our Library for more. Do upvote our blog to help other ninjas grow. Happy Coding!
 

Previous article
Iterators & Auto Keyword
Next article
Graph Implementation using STL
Guided path
Free
gridgp-icon
Basics of C++
9 chapters
104+ Problems
gp-badge
Earn badges and level up
Live masterclass