Algorithms In STL

An Explicit Study Of Algorithms And Its Types In STL.

STL supports various algorithms that act on containers through iterators. As these algorithms act on iterators and not directly on containers, they can be used on any type of iterators.

STL algorithms are built-in and thus save a lot of time and are more reliable too. They also enhance code reusability. These algorithms are normally just one function call and we need not write exhaustive code to implement them.

=> Look For The Entire C++ Training Series Here.

Types Of STL Algorithms

STL supports the following types of algorithms

• Search algorithms
• Sorting Algorithms
• Numeric algorithms
• Non-transforming/Modifying algorithms
• Transforming/Modifying algorithms
• Minimum and Maximum operations

We will discuss each of these types in detail in the following paragraphs.

Search And Sort Algorithms

The prominent search algorithm in STL is a binary search. Binary search algorithm operates on a sorted array and searches for the element by dividing the array into half.

This is done by first comparing the element to be searched with the middle element of the array and then limiting the search to 1^st half or 2^nd half of the array depending on whether the element to be searched is lesser than or greater than the middle element.

Binary search is the most widely used search algorithms.

Its general syntax is:

binary_search(startaddr, endaddr, key)

Where,

startaddr: address of the first element of the array.
endaddr: address of the last element of the array.
key: the element to be searched.

STL provides us a “Sort” algorithm that is used to arrange the elements in a container in a particular order.

General Syntax of sort algorithm is:

sort(startAddr, endAddr);

Where,

startAddr: starting address of the array to be sorted.
endAddr: end address of the array to be sorted.

Internally STL uses the Quicksort algorithm to sort the array.

Let’s take an example to demonstrate binary search and sort algorithm:

#include <algorithm> 
#include <iostream> 

using namespace std; 

int main() 
{ 
    int testAry[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 }; 
    int arysize = sizeof(testAry) / sizeof(testAry[0]); 
    
    sort(testAry, testAry + arysize); 
     
    cout<<"\nSorted Array is \n";
    for(int i=0;i<arysize;i++)
          {
        cout<<testAry[i]<< " ";
          }
    
    if (binary_search(testAry, testAry + arysize, 2)) 
    cout << "\nKey = 2 found in the array"; 
    else
    cout << "\nKey = 2 not found in the array"; 
    
    if (binary_search(testAry, testAry + arysize, 10)) 
    cout << "\nKey = 10 found in the array"; 
    else
    cout << "\nKey = 10 not found in the array"; 
    
     return 0; 
}

Output:

Sorted Array is
0 1 2 3 4 5 6 7 8 9
Key = 2 found in the array
Key = 10 not found in the array

In the given code, we have provided an array in which we need to search a key element using the binary search. Since binary search requires a sorted array we first sort the array using the “sort” algorithm and then make a function call to “binary_search” by providing the required parameters.

First, we call the binary_search algorithm for key=2 and then for key=10. This way with just one function call we can conveniently do a binary search on an array or sort it.

Numeric Algorithms

<numeric> header in STL contains various functions that operate on Numeric values. These functions range from finding lcds, gcds to even calculating the sum of the elements in a container like arrays, vectors over a given range, etc.

We will discuss a few important functions here with examples.

(i) accumulate

The general syntax of the accumulate function is:

accumulate (first, last, sum);

This function returns the sum of all the elements within a range [first, last] in a variable sum. In the above syntax notation, first and last is the addresses of the first and last elements in a container and sum is the initial value of sum variable.

(ii) partial_sum

The general syntax of the partial_sum function is:

partial_sum(first, last, b)

Here

first: address of the starting element of the container.
Last: address of the last element of the container.
B: array in which the partial sum of the corresponding array elements will be stored.

Thus partial_sum function calculates the partial sum of the corresponding array or the vector elements and stores them in a different array.

If a represents the element in the range [first, last] and b represents the element in the resultant array then partial_sum will be:

b0 = a0
b1 = a0+a1
b2 = a0+a1+a2 …and so on.

Let’s see an example to demonstrate both these functions in a program:

#include<numeric>
#include<iostream>

using namespace std;

int main()
{
  
  int A[] = {21,25,64,32};
  int sum = 0;
  int b[4];
  cout<<"\nResult of accumulate function is: "<<accumulate(A,A+4,sum);
  
  partial_sum(A,A+4,b);
  cout<<"\npartial_sum of array A : ";
  for (int i=0; i<4; i++)
  cout << b[i] << ' ';
  cout << '\n';
  
 return 0;
}

Output:

Result of the accumulate function is: 142

partial_sum of array A: 21 46 110 142

As shown in the above program, first we calculate the sum of the elements using the accumulate function and then we call the function partial_sum to calculate the partial sum of the corresponding array elements.

Other algorithms supported by STL and <numeric> header:

• iota: Fills a range with successive increments of the starting value.
• reduce: Similar to accumulate, except out of order.
• inner_product: Computes the inner product of two ranges of elements.
• adjacent_difference: Computes the differences between adjacent elements in a range.
• inclusive_scan: Similar to partial_sum, includes the ith input element in the ith sum.
• exclusive_scan: Similar to partial_sum, excludes the ith input element from the ith sum.

Non-Modifying Algorithms

Non-modifying or non-transforming algorithms are the ones that do not change the contents of the container they are operating in. STL supports many non-modifying algorithms.

We have listed some of them below:

• count: Returns the number of values in the given range.
• equal: Compares the elements in two ranges and returns a Boolean value.
• mismatch: Returns a pair of iterator when two iterators are compared and a mismatch occurs.
• search: Searches for a given sequence in a given range.
• search_n: Searches in a given range for a sequence of the count value.

Let’s elaborate more on “count” and “equal” functions!!

count(first, last, value) returns the number of times the ‘value’ appears in the range [first, last].

#include <iostream>   
#include <algorithm>
using namespace std;
int main ()
{
       int values[] = {5,1,6,9,10,1,12,5,5,5,1,8,9,7,46};
    int count_5 = count(values, values+15, 5);
    cout<<"The number of times '5' appears in array= "<<count_5;
    return 0;
}

Output:

The number of times ‘5’ appears in an array= 4

As you see in this code, we define an array value and then call the count function by providing the range of value and value of 5. The function returns the number of times (count) value 5 appears in the range.

Let’s take an example to demonstrate the ‘equal’ function.

equal(first1, last1, first2) compares the elements in the range [first1, last1] to the first element pointed by first2 and returns true if all the elements are equal otherwise false.

#include <iostream> 
#include <algorithm>
using namespace std;
int main()
{   
    int inputs1[] = { 1,2,3,4,5,6,7,8};
    int inputs2[] = { -1,2,1,2,3,4,6,7,8,9};    
    if (equal( inputs1 , inputs1+8 , inputs2 )==1)
        cout<<"Elements in Two ranges are equal";
    else
        cout<<"Elements in two ranges are not equal";
 }

Output:

Elements in two ranges are not equal.

In the code above, we define two integer arrays and compare their corresponding elements using the ‘equal’ function. As the elements of the array are not the same, equal returns false.

Modifying Algorithms

Modifying algorithms modify or transform the contents of the containers when they are executed.

Most popular and widely used modifying algorithms include “swap” and “reverse” that swaps two values and reverses the elements in the container respectively.

Let’s see the examples for these functions:

#include <iostream>     
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;
int main ()
{
    vector<int> vec1 = {1,1,2,3,5};
    vector<int> vec2 = {2,4,6,8,10};
    swap(vec1,vec2);
    cout<<"Vector 1 : ";
    for (auto it = vec1.begin(); it < vec1.end(); ++it) 
    	 cout << *it << " "; 
    cout<<endl;
    cout<<"Vector 2 : ";
    for (auto it = vec2.begin(); it < vec2.end(); ++it)
    	cout << *it << " "; 
    cout<<endl;
    reverse(vec1.begin(),vec1.end());
    cout<<"Reversed Vector 1 :";
    for (auto it = vec1.begin(); it < vec1.end(); ++it) 
    	cout << *it << " "; 
        cout<<endl;
    reverse(vec2.begin(),vec2.end());
    cout<<"Reversed Vector 2 :";
    for (auto it = vec2.begin(); it < vec2.end(); ++it) 
    	cout << *it << " "; 
    cout<<endl;
    return 0;
}

Output:

Vector 1 : 2 4 6 8 10

Vector 2 : 1 1 2 3 5

Reversed Vector 1 :10 8 6 4 2

Reversed Vector 2 :5 3 2 1 1

As seen, we have two vectors defined in the program. First using the swap function we swap the contents of vector1 and vector2. Next, we reverse the contents of each vector using the reverse function.

The program outputs Vector 1 and Vector 2 after swapping their contents and also after reversing the contents.

Minimum And Maximum Operations

This category consists of min and max functions that find out the minimum and maximum values respectively from the given two values.

The general syntax of these functions is:

max(objecta, objectb);
min(objecta, objectb);

We can also provide a third parameter to provide ‘compare_function’ or the criteria that would be used to find min/max value. If this is not provided, then the max function uses the ‘>’ operator for comparison whereas min function uses ‘<’ operator for comparison.

Let’s demonstrate these functions using a program.

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int x=4, y=5;
    cout<<"Max of 4 and 5 : ";
    cout << max(x,y);
    cout<<endl;
    cout<<"Min of 4 and 5 : ";
    cout << min(x,y);   
    
    string s = "smaller string";
    string t = "longer string---";
    cout<<endl;
    
    cout<<"\nMax string : ";
    string s1 = max(s, t);
    cout<< s1 <<endl;  
    cout<<endl;
    
    cout<<"Min String : ";
    string s2 = min(s, t);
    cout<< s2 <<endl;  
}

Output:

Max of 4 and 5: 5

Min of 4 and 5: 4

Max String: smaller string

Min String: longer string

The above program is self-explanatory as we use min and max functions on the numbers first and then on strings. As we did not provide optional ‘compare_function’, the min/max functions acted on ‘<’ and ‘>’ operators respectively.

Conclusion

With this, we have come to the end of this tutorial on major algorithms used in STL.

In our subsequent tutorials, we will discuss iterators in detail along with the common functions used in STL irrespective of containers.

=> Read Through The Easy C++ Training Series.