C++ Algorithm - Naukri Code360

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())

You can also try this code with Online C++ Compiler

Run Code

Also see, Literals in C.

Commonly Used Algorithms in C++

Algorithm	Description
Sorting Algorithms
- Quick Sort	Efficient sorting algorithm based on partitioning the array into smaller segments and recursively sorting them.
- Merge Sort	Divides the array into smaller segments, sorts them individually, and merges them back together. Known for its stability and consistent performance.
- Heap Sort	Builds a max-heap from the array, repeatedly extracts the maximum element, and rebuilds the heap until the array is sorted.
Searching Algorithms
- Binary Search	Efficient 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 Search	Traverses a graph by exploring as far as possible along each branch before backtracking. Useful for topological sorting, cycle detection, and connected components.
- Breadth-First Search	Explores 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 Sequence	Solves the Fibonacci sequence efficiently using dynamic programming, storing previously computed values to avoid redundant calculations.
- Longest Common Subsequence	Finds the longest subsequence common to two sequences by breaking down the problem into smaller subproblems and memoizing the results.

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

// 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;
}

You can also try this code with Online C++ Compiler

Run Code

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

// 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;
}

You can also try this code with Online C++ Compiler

Run Code

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

// 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;
}

You can also try this code with Online C++ Compiler

Run Code

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

// 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;
}

You can also try this code with Online C++ Compiler

Run Code

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

// 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;
}

You can also try this code with Online C++ Compiler

Run Code

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

Prims and Kruskal Algorithm

Example 1: Sort a Vector in Ascending Order

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;
}

You can also try this code with Online C++ Compiler

Run Code

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

#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;
}

You can also try this code with Online C++ Compiler

Run Code

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

#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;
}

You can also try this code with Online C++ Compiler

Run Code

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

#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;
}

You can also try this code with Online C++ Compiler

Run Code

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

#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;
}

You can also try this code with Online C++ Compiler

Run Code

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

#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;
}

You can also try this code with Online C++ Compiler

Run Code

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

#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;
}

You can also try this code with Online C++ Compiler

Run Code

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!

Algorithms In C++ STL

Introduction

Commonly Used Algorithms in C++

Types of Algorithms in Algorithm Library

Non-Manipulating Algorithms

C++

C++

C++

Manipulating Algorithms

C++

C++

Example 1: Sort a Vector in Ascending Order

C++

Example 2: Copy Vector Elements

C++

Example 3: Move Vector Elements

C++

Example 4: Swap the Contents of Two Vectors

C++

Example 5: Merge Two Vectors

C++

Example 6: Replace Vector Element

C++

Example 7: Delete a Value From the Given Range

C++

Frequently Asked Questions

How many types of methods are there in Sorting Algorithm?

Why do we use the numeric library for accumulate method?

Conclusion