Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Commonly Used Algorithms in C++
3.
Types of Algorithms in Algorithm Library
3.1.
Non-Manipulating Algorithms
3.2.
C++
3.3.
C++
3.4.
C++
3.5.
Manipulating Algorithms
3.6.
C++
3.7.
C++
4.
Example 1: Sort a Vector in Ascending Order
4.1.
C++
5.
Example 2: Copy Vector Elements
5.1.
C++
6.
Example 3: Move Vector Elements
6.1.
C++
7.
Example 4: Swap the Contents of Two Vectors
7.1.
C++
8.
Example 5: Merge Two Vectors
8.1.
C++
9.
Example 6: Replace Vector Element
9.1.
C++
10.
Example 7: Delete a Value From the Given Range
10.1.
C++
11.
Frequently Asked Questions
11.1.
How many types of methods are there in Sorting Algorithm?
11.2.
Why do we use the numeric library for accumulate method?
12.
Conclusion
Last Updated: May 20, 2024
Easy

Algorithms In C++ STL

Author Akash Nagpal
1 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

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.

Algorithms In C++ STL

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.

Commonly Used Algorithms in C++

AlgorithmDescription
Sorting Algorithms 
- Quick SortEfficient sorting algorithm based on partitioning the array into smaller segments and recursively sorting them.
- Merge SortDivides the array into smaller segments, sorts them individually, and merges them back together. Known for its stability and consistent performance.
- Heap SortBuilds a max-heap from the array, repeatedly extracts the maximum element, and rebuilds the heap until the array is sorted.
Searching Algorithms 
- Binary SearchEfficient search algorithm for sorted arrays, dividing the search interval in half each time until the target element is found or the interval is empty.
Graph Algorithms 
- Depth-First SearchTraverses a graph by exploring as far as possible along each branch before backtracking. Useful for topological sorting, cycle detection, and connected components.
- Breadth-First SearchExplores a graph level by level, visiting all neighbors of a node before moving to the next level. Ideal for finding shortest paths and minimum spanning trees.
Dynamic Programming 
- Fibonacci SequenceSolves the Fibonacci sequence efficiently using dynamic programming, storing previously computed values to avoid redundant calculations.
- Longest Common SubsequenceFinds the longest subsequence common to two sequences by breaking down the problem into smaller subproblems and memoizing the results.
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

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.
  • C++

C++

// 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.
  • C++

C++

// 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’. 
  • C++

C++

// 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.
  • C++

C++

// 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. 
  • C++

C++

// 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++

Example 1: Sort a Vector in Ascending Order

  • C++

C++

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
std::vector<int> vec = {5, 2, 9, 1, 7};

std::sort(vec.begin(), vec.end());

for (int num : vec) {
std::cout << num << " ";
}

return 0;
}

Output:

1 2 5 7 9

Explanation:

This example demonstrates sorting a vector vec in ascending order using the std::sort() algorithm from the <algorithm> library. The std::sort() function rearranges the elements in the range [begin, end) into ascending order.

Example 2: Copy Vector Elements

  • C++

C++

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination;

std::copy(source.begin(), source.end(), std::back_inserter(destination));

for (int num : destination) {
std::cout << num << " ";
}

return 0;
}

Output:

1 2 3 4 5

Explanation:

This example copies elements from the source vector to the destination vector using the std::copy() algorithm. The std::back_inserter() iterator inserts elements at the end of the destination vector.

Example 3: Move Vector Elements

  • C++

C++

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination;

std::move(source.begin(), source.end(), std::back_inserter(destination));

for (int num : destination) {
std::cout << num << " ";
}

return 0;
}

Output:

1 2 3 4 5

Explanation:

This example moves elements from the source vector to the destination vector using the std::move() algorithm. Moving elements allows efficient transfer of resources without unnecessary copying.

Example 4: Swap the Contents of Two Vectors

  • C++

C++

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
std::vector<int> vec1 = {1, 2, 3};
std::vector<int> vec2 = {4, 5, 6};

vec1.swap(vec2);

std::cout << "Vector 1 after swap: ";
for (int num : vec1) {
std::cout << num << " ";
}
std::cout << "\n";

std::cout << "Vector 2 after swap: ";
for (int num : vec2) {
std::cout << num << " ";
}

return 0;
}

Output:

Vector 1 after swap: 4 5 6 
Vector 2 after swap: 1 2 3

Explanation:

This example demonstrates swapping the contents of two vectors vec1 and vec2 using the swap() method. After the swap, the elements of vec1 become the elements of vec2, and vice versa.

Example 5: Merge Two Vectors

  • C++

C++

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
std::vector<int> vec1 = {1, 3, 5};
std::vector<int> vec2 = {2, 4, 6};

vec1.insert(vec1.end(), vec2.begin(), vec2.end());
std::sort(vec1.begin(), vec1.end());

for (int num : vec1) {
std::cout << num << " ";
}

return 0;
}

Output:

1 2 3 4 5 6

Explanation:

This example merges two sorted vectors vec1 and vec2 into vec1 using the insert() method to append the elements of vec2 to vec1. Then, the std::sort() algorithm is used to sort the merged vector.

Example 6: Replace Vector Element

  • C++

C++

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};

std::replace(vec.begin(), vec.end(), 3, 10);

for (int num : vec) {
std::cout << num << " ";
}

return 0;
}

Output:

1 2 10 4 5

Explanation:

This example replaces all occurrences of the value 3 in the vector vec with 10 using the std::replace() algorithm.

Example 7: Delete a Value From the Given Range

  • C++

C++

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};

vec.erase(vec.begin() + 1, vec.begin() + 3);

for (int num : vec) {
std::cout << num << " ";
}

return 0;
}

Output:

1 4 5

Explanation:

This example deletes elements from the vector vec in the range [1, 3) (excluding the element at index 3) using the erase() method.

Frequently Asked Questions

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 ) 

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.

Conclusion

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
Live masterclass