STL Algorithms in C++
The C++ Standard Template Library (STL) algorithms are a strong and adaptable collection of tools that make it easier to do different data manipulation work. The C++ <algorithm> header contains the STL algorithms. These algorithms can be used on various data kinds and containers, including arrays, vectors, lists, and more, because they are implemented as function templates. The main objective of the STL algorithms is to offer effective, general, and reusable solutions to frequent programming issues.
STL algorithms follow the functional programming paradigm, which gives up direct data manipulation instead of returning results in new data structures or iterators. This unchangeability guarantees safer and more consistent behavior while preventing negative impacts.
You must include the <algorithm> header in your C++ program to use the STL algorithms. Then, you may directly run these algorithms on containers or ranges by giving the proper iterators and function objects. This clear approach makes The code easier to understand and more expressive.
Because of their widespread use and extensive application, STL algorithms are crucial to modern C++ programming. They use effective and thoroughly tested solutions for common operations, which not only increase code quality but also code readability. STL algorithms in C++ offer a standardized and powerful toolset for various data manipulation applications. They are useful tools for C++ developers, enabling them to create clearer, more manageable, and more performant code because of their generic nature, functional programming style, and efficiency. The STL algorithms provide a variety of methods for searching, sorting, and modifying data in a container, enhancing the efficiency and fun of C++ programming.
Types of STL Algorithms
The STL algorithms in C++ are divided into many groups according to their operation. Various algorithms in each category are focused on particular tasks. The primary STL algorithm subtypes in C++ are listed below.
- Search algorithms
- Sorting Algorithms
- Numeric algorithms
- Non-transforming/Modifying algorithms
- Transforming/Modifying algorithms
- Minimum and Maximum operations
1. Search Algorithms
A Search Algorithm is an algorithm or technique used to find a specific value in the collection of the given or the required data. The data can be of any type, such as structure, array, list, vector, etc. Numerous applications depend on search algorithms because they enable us to find particular items repeatedly without searching the full collection.
The Standard Template Library (STL) in C++ offers easily accessible search algorithms. These algorithms, part of the algorithm> header, provide effective ways to seek items in different data structures. The main benefit of employing STL search algorithms is their generality, enabling them to operate on various container types, including arrays, vectors, lists, and more.
Std::find, the most used search algorithm in C++, looks for a certain value inside a range specified by two iterators. If the value cannot be found, the end iterator gets returned instead of an iterator pointing to the initial instance of the value inside the range.
Example:
#include<iostream>
#include<algorithm>
#include<vector>
int main() {
// Create a vector of integers
std::vector <int> numbers={10, 20, 30, 40, 50};
//Define the target value to be searched
int targetValue=30;
// Using std::find to search for the target value in the vector
// The 'it' variable will hold the iterator pointing to the found value
auto it=std::find(numbers.begin(), numbers.end(), targetValue);
// Check if the value is found by comparing the iterator with the end iterator
if (it != numbers.end()) {
// The value is found, and 'it' points to the first occurrence
// Calculate the index of the found value using std::distance
int index=std::distance(numbers.begin(), it);
// Display the result
std::cout<<"Value "<< targetValue<<" found at index "<<index<<std::endl;
}
else {
// The value is not found
std::cout<<"Value "<<targetValue<<"not found in the vector."<<std::endl;
}
return 0;
}
Output:
![STL Algorithms in C++](https://static.tutorialandexample.com/cpp/stl-algorithms-in-cpp1.png)
Explanation:
This C++ program searches a named vector of integers called numbers for a certain target value (30) using the std :: find method. If the value is found, std :: distance is used to report the index of the first occurrence.
It prints a message saying that the value was not found if it wasn't in the vector. The code explains how to use the STL algorithm in C++ to carry out a straightforward search operation.
2. Sort Algorithm
A sorting algorithm is an algorithm or technique which is used to sort or arrange the data in an order which is either ascending or descending based on the user input. The sort algorithm is a part or belongs to the Standard Template Library (STL).
It is a crucial technique for manipulating data since it easily rearranges objects according to their values. The std::sort function, a component of the algorithm header, uses the QuickSort algorithm. It may be customized using lambdas or comparison functions for different sorting criteria and can sort several containers, including vectors, arrays, and lists. The sort algorithm enables efficient data retrieval and processing in C++ applications when data is sorted in ascending or descending order.
Example:
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
int arr[]={1, 5, 8, 9, 6, 7, 3, 4, 2, 0};
int size=sizeof(arr)/sizeof(arr[0]);
// Sorting the array in ascending order
sort(arr, arr+size);
cout << "\nSorted Array is: \n";
for(int i=0; i<size;i++)
{
cout<<arr[i]<<" ";
}
// Searching for key=2 in the sorted array using binary_search
if (binary_search(arr, arr + size, 2))
cout << "\nKey=2 found in the array";
else
cout <<"\nKey = 2 not found in the array";
// Searching for key=10 in the sorted array using binary_search
if (binary_search(arr, arr + size, 10))
cout <<"\nKey = 10 found in the array";
else
cout <<"\nKey = 10 not found in the array";
return 0;
}
Output:
![STL Algorithms in C++](https://static.tutorialandexample.com/cpp/stl-algorithms-in-cpp2.png)
Explanation:
The above example program creates a ten-number integer array with the name arr. We determine the array's size and store it in the variable size using the sizeof operator. The array members are then rearranged using the std::sort function, ascending from the smallest to the biggest. We use a loop to print each element and display the sorted array.
The std::binary_search function is then used to do two binary searches. The sorted array is initially searched to see if the value 2 exists. If it is, we display "Key=2 found in the array," whereas, in the absence of it, we print "Key=2 not found in the array." The second search also looks for the value 10 in the sorted array. If it is, we publish "Key=10 found in the array," whereas, in the absence of it, we print "Key=10 not found in the array." The program concludes by returning 0.
3. Numeric Algorithm
C++'s numerical algorithms offer an effective toolkit for different mathematical operations on numeric data collections. The Standard Template Library (STL) is complete with these algorithms, which allow programmers to quickly and effectively handle numerical values in arrays, vectors, and other containers. Numerical algorithms simplify working with numerical data by computing sums, products, and differences and even determining the greatest common factor and least common multiple.
These methods improve code readability and maintainability while encouraging effective and optimized computations by encapsulating complicated calculations into straightforward function calls. This adds to the general flexibility and efficiency of C++ programming by making numeric algorithms an invaluable tool for jobs ranging from simple arithmetic operations to more complex mathematical computations. The important functions of Numeric algorithms are:
i. Accumulate:
The C++ Standard Library includes the accumulate function as a fundamental mathematical procedure in the <numeric> header. It determines the total values in a sequence, such as an array or a container, that fall inside a given range. The function requires two iterators to indicate the range and a potential beginning accumulation value.
The accumulate function operates as follows:
Accumulate (first, last, sum);
The accumulate function from the C++ Standard Library's numeric> header is used when the syntax accumulate(first, last, sum) is used. The total values inside a range determined by the iterators first and last are calculated, and this sum is then added to the supplied sum value.
- First: This iterator points to the first element in the range you wish to consider while adding.
- Last: This iterator points to the element in the range you wish to consider for the total immediately after the last element.
- Sum: This amount will be added when the computed sum is applied. It serves as the accumulation's starting point value.
ii. Partial sum:
The partial sum of a sequence of items is calculated using the std::partial_sum method in C++, and the results are then stored in another sequence. It uses an input range, a binary operation on nearby items, and an output range to record the partial sum.
Syntax:
partial_sum(first, last, b)
First, last: The set of items you wish to compute the partial sum. First is the range's start, and last is one beyond the range's finish.
The start of the range where the partial sums will be kept at the destination.
To hold the results in an output range, the partial_sum function computes the partial sums of the input data range. The components of the input range are added together, and the partial sums are saved in the output range.
Example:
#include<numeric>
#include<iostream>
using namespace std;
int main()
{
// Define an array of integers
int numbers[] = {21, 25, 64, 32};
// Initialize a sum variable
int totalSum = 0;
// Create an array to store partial sums
int partialSums[4];
// Using the accumulate function to calculate the sum of elements
cout<<"\nResult of accumulate function is: " << accumulate(numbers, numbers + 4, totalSum);
// Using partial_sum function to calculate partial sums
partial_sum(numbers, numbers + 4, partialSums);
// Displaying the partial sums
cout<<"\nPartial sums of array numbers: ";
for(int i = 0;i <4;i++)
cout<<partialSums[i] << ' ';
cout<<'\n';
return 0;
}
Output:
![STL Algorithms in C++](https://static.tutorialandexample.com/cpp/stl-algorithms-in-cpp3.png)
Explanation:
This code sample shows how to use the accumulate and partial_sum methods from the <numeric> header of the C++ Standard Library.
The first step is constructing an array called numbers with a collection of integer values.
This array is then subjected to the accumulate function, with the total sum variable initialized to 0. This function computes the sum of the set of items whose range is determined by numbers, updating the total sum. The final output, which displays the array's element totals, is printed.
The partial_sum function will then be used. When computing the cumulative sum of an array's elements, the same array is used, and the partial sums array is used to store each intermediate sum. The code then uses a loop to display these partial sums, showing how the amount changes as parts are gradually added.
The ability of the <numeric> header functions to quickly execute mathematical operations on sequences of numbers is demonstrated by this code. The partial_sum function sheds light on the cumulative nature of successive additions, whereas the accumulating function helps swiftly find the sum of items. This program shows how these functions may speed up and simplify various numerical operations in C++ programs.
Additional Algorithms that STL and Numeric Header Support
The numeric header in the C++ Standard Library offers several other helpful algorithms that work on sequences of numerical values in addition to accumulating and partial_sum. These algorithms are made to carry out a variety of mathematical operations and computations efficiently. Other important algorithms that the numeric header supports are those listed below:
- inner_product: This method determines the inner product of two sequences by multiplying and adding the matching components. It is helpful for operations like computing weighted sums or dot products.
- Iota: Starting from a predetermined beginning value, the iota function fills a range with successively rising values. To create sequences of succeeding numbers, this is frequently employed.
- adjacent_difference: This algorithm estimates the differences between items next to each other in a series and saves the results in another range. It is frequently employed for tasks like estimating derivatives and computing first differences.
- Power: Use the power function to calculate the outcome of increasing each element in a sequence to a certain power. The calculated results are then stored in an output range.
- GCD: The gcd function determines the greatest common divisor of two integers.
- LCM: This determines the least common multiple between two numbers.
- Modulus: Using a given divisor, the modulus function calculates the modulus of each element in a sequence and stores the results in an output range.
- transform_inclusive_scan and transform_exclusive_scan: This computes inclusive or exclusive prefix sums and stores the results in an output range.
- transform_reduce: With the help of this algorithm, which combines transformation and reduction operations, each element is subjected to a specific function before the results are added together.
4. Non-transforming Algorithms
Non-transforming algorithms are a class of functions in the C++ Standard Template Library that operate on ranges of items in a container without changing the actual elements. These algorithms must modify the original pieces to perform several actions, including searching, counting, checking conditions, and identifying extrema. The following are some important STL non-transforming algorithms:
- count
- equal
- mismatch
- Search
- search_n
Let us go through the count and equal algorithms
i. Count:
To count the occurrences of a certain value inside a range, use the std::count algorithm. It requires the range's starting and finishing iterators and the value to be counted. The value's frequency of occurrence within the range is returned.
Example code:
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
int nums[]={7, 3, 8, 9, 4, 3, 12, 7, 7, 7, 3, 8, 9, 7, 46};
// Define the target value to be counted
int targetValue=7;
// Count the occurrences of the target value in the array
int countOfTarget = count(nums, nums + 15, targetValue);
// Display the result
cout <<"The number of times '" << targetValue << "' appears in the array = "<< countOfTarget;
return 0;
}
Output:
![STL Algorithms in C++](https://static.tutorialandexample.com/cpp/stl-algorithms-in-cpp4.png)
Explanation:
This C++ program explains how to utilize the count function from the algorithm library. It starts by creating an array called nums that contains an array of integer values. The program aims to determine how frequently a particular target value, in this example, the number 7, occurs in the array.
The program uses the count function, which requires three arguments: the goal value to be counted and the start and end of the search range, correspondingly. In this instance, the array's entire range is covered by the iterators nums and nums + 15. The count of occurrences of the desired value 7, within this range, is then determined by the program.
The number of times the target value appears in the array is shown by the program using the cout command once the count has been computed. This code snippet shows a straightforward example of effectively counting the occurrences of a certain value in an array using the count algorithm.
ii. Equal:
The degree of equality of the items in two ranges is compared using the std::equal method. Two ranges' beginning and ending iterators are used for the comparison. A third argument, either a comparison function or an equality predicate, can be used to customize the comparison further.
Example code:
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
// Defining two arrays of integers
int arr1[] ={10, 20, 30, 40, 50};
int arr2[] ={10, 20, 35, 40, 55};
// Check if the elements in the two ranges are equal using the equal function
if ( equal(arr1, arr1 + 5, arr2) == 1)
cout<<"Elements in the two ranges are equal";
else
cout<<"Elements in the two ranges are not equal";
return 0;
}
Output:
![STL Algorithms in C++](https://static.tutorialandexample.com/cpp/stl-algorithms-in-cpp5.png)
Explanation:
This C++ code compares corresponding entries in two integer arrays, arr1 and arr2, using the equal method from the STL's "algorithm" module. The code recognizes if the elements are equal by giving the ranges to compare and utilizing the returned boolean value. If they are, it says, "Elements in the two ranges are equal," and if they aren't, it says, "Elements in the two ranges are not equal." This illustrates how the equal method streamlines and makes a comparison of elements in various ranges in C++ programs simpler and faster.
5. Modifying Algorithms
Modifying algorithms in C++ is an important part of the Standard Template Library, which provides several functions that enable users to change a range of items in various ways. Such methods may be employed to change values, reorder elements, and execute other changes on sequences. Modifying techniques are required to handle data in arrays, vectors, and lists without using explicit loops.
In C++, some of the most important modifying algorithms are:
- The most well-known and often applied modifying algorithms are "swap" and "reverse," which swap two values and reverse the items in the container.
- The "swap" and "reverse" modifying algorithms are the most well-known and commonly used in C++. The "swap" method effectively switches two values' locations within a container by allowing the exchange of two values.
Example:
#include<iostream>
#include<utility>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
// Defining the two vectors of integers
vector< int> numbers1={1, 1, 2, 3, 5};
vector< int> numbers2={2, 4, 6, 8, 10};
// swapping the numbers using the swap algorithm
swap (numbers1, numbers2);
// Display the elements of the first vector after swapping
cout << "Vector 1 after swapping: ";
for (auto it = numbers1.begin (); it< numbers1.end (); ++it) {
cout << *it << " ";
}
cout << endl;
// Display the elements of the second vector after swapping
cout << "Vector 2 after swapping: ";
for(auto it = numbers2.begin (); it < numbers2.end ();++it) {
cout << *it << " ";
}
cout << endl;
// Reverse the elements in the first vector using the 'reverse' algorithm
reverse(numbers1.begin(), numbers1.end());
// Display the reversed elements of the first vector
cout << "Reversed Vector 1: ";
for (auto it = numbers1.begin (); it< numbers1.end (); ++it) {
cout << *it << " ";
}
cout << endl;
// Reverse the elements in the second vector using the 'reverse' algorithm
reverse(numbers2.begin(), numbers2.end());
// Display the reversed elements of the second vector
cout << "Reversed Vector 2: ";
for(auto it = numbers2.begin ();it < numbers2.end ();++it) {
cout << *it << " ";
}
cout << endl;
return 0;
}
Output:
![STL Algorithms in C++](https://static.tutorialandexample.com/cpp/stl-algorithms-in-cpp6.png)
Explanation:
The 'swap' and 'reverse' algorithms are used to change two vectors of numbers in this C++ code, functioning as examples. The first step is to define and initialize two vectors with names such as "numbers1" and "numbers2". The two vectors' contents undergo a swap, resulting in the elements of the two vectors switching positions.
Following the data exchange, the program shows the components of both vectors. The order of the items within each vector is then turned around using the 'reverse' method, and the vector's contents are shown in the new order. The code demonstrates how these altering algorithms may effectively swap and reverse the elements of containers to obtain desired results.
6. Minimum And Maximum Operations
The minimum and maximum operations are crucial parts of the algorithm library in the C++ Standard Template Library, allowing programmers to quickly recognize the lowest and greatest elements within a particular range of values. Without the need for human iteration, these methods offer a quick and reliable approach to carrying out comparisons and retrieving external values.
The 'max_element' technique locates the largest element within the same range, whereas the 'min_element' strategy locates the smallest element inside a particular range. Both techniques return iterators pointing to the determined extrenal items and accept iterators as parameters representing the range's start and end.
Minimum Function:
The min_element algorithm or minimum function is used to find the lowest or the smallest value or element in the given range or the group of numbers. The minimum function takes two integers as input. One is the starting value, and the other is the ending value of the range.
Example:
#include<iostream>
#include<algorithm>
#include<vector>
int main() {
// Define the vector with integers
std::vector<int> values = {5, 2, 8, 3, 1, 6};
// Find the minimum element in the vector
auto minVal=std::min_element(values.begin(),values.end());
// Display the minimum element
std::cout<<"Minimum Element:"<<*minVal<<std::endl;
return 0;
}
Output:
![STL Algorithms in C++](https://static.tutorialandexample.com/cpp/stl-algorithms-in-cpp7.png)
Explanation:
We have a vector named values in this code containing a number collection. The smallest element in the vector is located using the std::min_element algorithm. The starting iterator (values.begin()) and the ending iterator (values.end()) of the range in which we wish to discover the minimal element are the two arguments that the min_element method accepts. It gives back an iterator pointing to the range's lowest element.
The result of std::min_element is saved in the minVal variable, and the real minimum value is obtained using the dereference operator (*minVal). Finally, we use std:: to show the minimal element.cout
The min_element technique from the C++ Standard Template Library effectively locates and shows this code's minimal element in a vector.
Advantages of STL Algorithm in C++
The STL algorithms in C++ greatly improve developers' productivity, efficiency, and code quality. The following are some major benefits of implementing STL algorithms:
- Reusability and Standardisation: STL algorithms provide a collection of frequently employed and standardized algorithms for a range of data structures, including arrays, lists, and vectors. As a result, there is no need to create something from the beginning, and code reuse is encouraged across many projects.
- Code Readability: STL algorithms capitalize on self-explanatory and straightforward function names (such as sort, find, and accumulate), which make the code easier to read and interpret. This encourages improved developer communication and decreases the learning curve for newly created team members.
- Efficiency: STL algorithms are developed by highly qualified experts and are performance-optimized. They are often built with effective time and space complexity, ensuring that activities are carried out as efficiently as possible.
- Generic programming: STL algorithms can execute on various data types since they are created using templates. As a result, algorithms may be utilized with user-defined classes and structures, and generic programming is supported.
- Ease of Use: STL algorithms enable a high-level interface while abstracting the complexities of underlying data structures. This simplifies complicated procedures, lowering the risk of coding flaws and mistakes.
- Safety and Correctness: The C++ community extensively evaluates and vets STL algorithms. This makes them more trustworthy, accurate, and empty of frequent programming errors, which results in more dependable software.
- Consistency: STL algorithms' behavior, parameter order, and naming standard are all uniform. This consistency among algorithms facilitates a consistent coding style and makes switching between them easier.
- Ease of Maintenance: Although STL algorithms are well-known and frequently utilized, code maintenance and upgrading are made easier. When new developers join a project, they may get up to speed on the current codebase and use it immediately.
Disadvantages of STL Algorithm in C++
- Performance Overhead: Compared to manually optimized algorithms specially tuned to a particular use case, STL methods might impose a modest performance overhead since they are general and built to deal with a wide variety of data types. Handcrafted algorithms could be more effective in performance-critical applications.
- Limited Customization: STL algorithms offer a standardized interface, which may restrict how much you alter the algorithm's behavior to meet your requirements. Even though they address various use cases, there may be circumstances in which a customized implementation provides more control.
- Lack of Domain-Specific Optimisation: STL algorithms may not include domain-specific optimizations because they are intended to be general and flexible. Hand-tailored algorithms may perform better in certain circumstances.
- Limited Control Over Memory Management: STL techniques abstract memory management aspects, which can help usability. However, you could prefer a more manual method when precise memory management is essential.
- Runtime Overhead: Due to dynamic memory allocation and deallocation, some STL algorithms, particularly those using data structures like vectors or lists, may cause runtime overhead.
- Potential for Overuse: Because STL algorithms are simple to use, they may be overused in some circumstances when a more specialized or optimized solution would be preferable. An excessive dependence on STL could hamper the growth of algorithmic and problem-solving abilities.