STL Algorithms in C++

The Standard Template Library in C++ is a large native library in C++ that provides in-built data structures and algorithms. It is a collection of containers, iterations and algorithms. STL is templated and thus supports multiple variants of data types like vectors, lists, deque, arrays, heaps and sets. This article talks about the general algorithms for searching, sorting and queries applicable to these containers.

Introduction

This list of algorithms is not exhaustive yet contains the most common and# useful C++ native algorithms in the STL library. Any of these algorithms can be written again though the efficiency of the same would atmost be comparable to the same available in the STL libraries.

NOTE:
vector.begin(), vector.end() can also be replaced by std::begin(vector) and std::end(vector) respectively as std::begin(vector) was only introduced in C++ 11 to allow easy coding for generic templated structures that support C-style arrays (that do not have methods like .begin()) as well as STL containers.

HEAPS

Heaps are special tree-based data structures following one particular heap condition: node values down the tree are sctricty ascending(min heap) or strictly descending (max heap), i.e. parent-child relationship is monotonic. A heap is not completely sorted but partially ordered binary tree and thus knowing the priority for the element, a heap can serve for efficient data manipulation and accessibility.

The Standard Template Library in C++ allows for a heap data structure and which has a priority queue as the base container. The algorithms provide the functions necessary to use the features of a heap.

Algorithms for Heaps

⇒ Create a heap from vector of numbers
std::make_heap(vector.begin(), vector.end())

⇒ Add contents to a heap (it handles the pushing of numbers and arranges them in the heap based on the comparison)
std::push_heap(vector.begin(), vector.end())

⇒ Pop out the highest number
std::pop_heap(vector.begin(), vector.end())

⇒ Reverse the order of the heap (Applicable to other containers as well )
std::reverse(vector.begin(), vector.end())

⇒ Sort the elements of the heap in ascending order and the range is no longer a heap
std::sort_heap(vector.begin(), vector.end())

SORTING

Sorting the information stored in containers based on conditions is one of the most common things to do while dealing with any data. As simple as ranking students on the scores obtained means first arranging the scores in descending order.

The Standard Template Library in C++ provides in-built implementations for different kinds of sorting operations. The templated nature of the library allows for the same algorithm to be applicable to all kinds of containers offered by C++.

Algorithms for Sorting

⇒ Sorting of numbers in ascending order. If function is provided then it is used for sorting comparison. If fucntion returns true, then first element ordered before second.
std::sort(vector.begin(), vector.end(), function)

⇒ Sorting of numbers in ascending order. If function is provided then it is used for sorting comparison. If fucntion returns true, then first element ordered before second.
Different from sort because it preserves the order of elements that have the same values, thus called stable.
std::stable_sort(vector.begin(), vector.end(), function)

⇒ Sorting of numbers in the range [first, last) only for specified middle values. If function provided then it is used for sorting comparison. If fucntion returns **true**, then first element ordered before second.
std::partial_sort(vector.begin(), middle, vector.end())

⇒ Rearrange the list such that the nth element has the value that should have existed there if the list was sorted. The nth element has all preceding elements lesser than it and succeeding elements larger than it.
std::nth_element(vector.begin(), nth_element, vector.end())

PERMUTATIONS

Elements of a container are required to be shuffled in different orders as per need.

The Standard Template Library in C++ provides in-built implementations for different kinds of permutation/re-arranging operations. The templated nature of the library allows for the same algorithm to be applicable to all kinds of containers offered by C++.

Algorithms for Permutations

⇒ Reverse the order of elements in the container
std::reverse(vector.begin(), vector.end())

⇒ Create a new copy of the container to a new_vector with reversed order of elements
std::reverse_copy(vector.begin(), vector.end(), new_vector.begin())

⇒ Rotate the container about the middle element such that the middle element becomes the first element of the new rotated vector. Possible applications are found in insertion sort or order reshuffling
std::rotate(vector.begin(), vector.middle(), vector.end())

⇒ Reshuffle the elements of the container based on using the std::rand as the random seed generator function
std::random_shuffle(vector.begin(), vector.end())

⇒ Reshuffle the elements of the container based on a seed obtained via URBG (Uniform Random Bit Generator). More efficient that the std::random_shuffle
std::shuffle(vector.begin(), vector.end(), random_number_generator)

⇒ Rearrange the elements of the container into a permutation higher up in the lexicographical order.
std::next_premutation(vector.begin(), vector.end())

⇒ Rearrange the elements of the container into a permutation lower down in the lexicographical order.
std::prev_premutation(vector.begin(), vector.end())

QUERYING RANGES

Several queries about the features of containers are made, either for one single container or multiple ones.

The Standard Template Library in C++ provides in-built implementations for several such querying operations. The templated nature of the library allows for the same algorithm to be applicable to all kinds of containers offered by C++.

Algorithms for Querying Containers

⇒ Counts the number of occurences of the value in the container
std::count(vector.begin(), vector.end(), value)

⇒ Compute the sum of the contents of the container and store it to the value init. If binary method function is provided, then the method is used for accumulation.
std::accumulate(vector.begin(), vector.end(), init)
std::accumulate(vector.begin(), vector.end(), init, function)

⇒ Compute the partial sum of the contents of the container iteratively and store the it to container with result interator as the beginning. If binary method function is provided, then the method is used for the partial operation.
std::partial_sum(vector.begin(), vector.end(), result)
std::partial_sum(vector.begin(), vector.end(), result, function)

⇒ Checks for all the elements of the container returning true for the given unary operator.

If all elements return true, the function returns true else returns false. It returns false for an empty range.
std::all_of(vector.begin(), vector.end(), unary_function)

⇒ Checks for all the elements of the container returning true for the given unary operator.

If at least one of the elements return true, the function returns true else returns false. It returns false for an empty range.
std::any_of(vector.begin(), vector.end(), unary_function)

⇒ Checks for all the elements of the container returning true for the given unary operator.

If none of the elements return true, the function returns true else returns false. It returns true for an empty range.
std::none_of(vector.begin(), vector.end(), unary_function)