dummy text

The 10 groups of STL algorithms you need to know in 2020

Standard Template Library (STL) is the most commonly used library in C++ but also very daunting for the beginners. So let me try to clarify the common algo's in the STL.

Posted by Simar Mann Singh on 23 Nov, 2019

Algorithm

An Algorithm is essentially a finite set of instructions, which when executed produces a desired result. The calculation it perform could require some input data, or it could also require access to some resources depending on the application it serves. Algorithms are not new, as many people would perceive them to be. They date back to atleast ancient Babylonion era (around 2500 BC.) if not prior. As per wikipedia,

"Arithmetic algorithms, such as a division algorithm, was used by ancient Babylonian mathematicians c. 2500 BC and Egyptian mathematicians c. 1550 BC. Greek mathematicians later used algorithms in the Sieve of Eratosthenes for finding prime numbers"

As of today, there are a ton of algorithms out there. Speaking specifically of programming language C++, if you have gone through the STL library, there are at least 105 major algorithms in STL itself. The thing with Algorithms is that you need to practice a lot to feel confidant. However, for the beginners, the most difficult conundrum is to determine where to start and which algorithms to master first. The plethora of algorithms out there for every niche tends to baffle the beginners. But there’s a good news for those already intimidated beginners. You surely need to learn a lot of algorithms, but you don’t need to know all of them to start working. We can classify all the algorithms into some bunch of sections. What you can do instead, is learn a few algorithms from each section and thus you’ll not be marooned on the island when someone asks you about algorithms.

Below is a list of ten algorithm classes in which all the algorithms from the STL library can be classified into and under each class, there are a handful of algorithms that you can befriend with for the time being. Also mentioned are the situations under which you will find those algorithms useful.

So, to start with, lets go through the list of ten algorithms classes (and one bonus class) that we will discuss here and then we will elaborate each one.

  1. Heap
  2. Sort
  3. Partition
  4. Permutations
  5. Query a Value
  6. Query a Property
  7. Search a Value or a Range
  8. Sets
  9. Movers
  10. Modifiers

Heap

Heap, in real life which can be represented as a tree where every node is smaller than its child or the node below it. Figure 1(a) shows how a heap might look like in real life. However, a heap in C++ is slightly different. Unlike in real life, heap in C++ can be represented like a tree where parent node is always larger than its children, as shown in figure 1(b).

To represent Heap in Memory, we can use an Array. To initialize an array, we simply add elements row-wise. Heap initialization is shown in figure 2. As seen in the figure, for a heap which appears like a tree, elements are stored in array in a row-wise manner.

At the moment, this array is merely a collection of integers (in given example). To make it a heap, we can call the STL algo make_heap.

std::make_heap(begin(number), end(number));

To add a new element to the heap and bubble its way to its appropriate position, we use push_back(element) and then push_heap as shown below.

number.push_back(8.81); std::push_heap(begin(number), end(number));

To pop something from a heap, we can only remove elements from one end which can only be largest element. To do so, we swap its position with the last element of the heap (which is probably the smallest element of the heap) & then pop it out. We use pop_heap and then pop_back as shown below.

std::pop_heap(begin(number), end(number)); number.pop_back()

NOTE

If pop_back is not called, then calling pop_heap() will cause all the largest elements fall in order at the end of the heap. This will cause heap to be sorted and this is the actual mechansm of sort_heap.

Sort

Sorting a collection is basically rearranging the elements of a collection in a certain order depending on the criteria. There are lots of sorting algorithms. In STL, simplest sorting algorithm is Sort. This sorts the collection in ascending order.

std::sort()

When we need to sort only a subset of a collection, we can use partial_sort. This algorithm takes in, the beginning of the collection and the point up to where collection needs to be sorted.

std::partial_sort()

When we need to know an element that would have been there, had the collection been sorted, we can do so by using nth_element algorithm.

std::nth_element()

When there are two sorted sub-collections that are adjacent to each other, however the entire collection as a whole is not sorted, we can use inplace_merge.

std::inplace_merge()

Partitioning

It is basically organizing a collection based on a predicate. One example could be a situation where a collection has mixed values of zeroes and ones but we need to partition the collection into two parts based on whether the element is a zero or a one as shown below.

we can use partition to put all the zeroes in the beginning and all the ones at the end. The point which creates the divide between the two regions is called “Partition Point”.

std::partition()

The algorithm which retrieves the partitioning point is called partition_point.

std::partition_point()

Permutations

These are the algorithms which change the order of the elements of a collection without changing their values.

  • Rotate
    It is one algorithm where elements in the middle and end goes to the beginning and that is decided by where the middle points to as shown in the figure below

    std::rotate()
  • Shuffle
    It uses a random generator and reorganizes the collection randomly.

    std::shuffle()
  • Next_permutation
    Elements can be compared to each other depending on their order which is similar to order of alphabets that appears in a Dictionary. By calling this algorithm, it will rearrange the elements of the collection in such a way that the new collection order is just the next order of permutation in respect of order of elements.

    The figure shown below clarifies what the order means in this context.

    std::next_permutation()
  • Prev_permutation
    Just like next_permutation, prev_permutation gives the previous order.

    std::prev_permutation()
  • Finally, reverse simply reverses the order of collection entirely.

    std::reverse()

Query a Value

Querying forms a fundamental class in algorithms as many times, we only need to know what value or property certain variable or objects have. This class has numeric algorithms which return a specific value (or No value as No values is also technically a value)

  • Count
    This algorithm counts the occurrence of an input value in a collection of elements and returns the occurrence as integer value. As shown in the figure, count(a) returns 3 as there are three times ‘a’ has occurred in the collection.
  • Accumulate / (Transform) reduce
    Accumulate find the sum of all the elements of a collection and returns it. Reduce works just like accumulate except for the fact that it doesn’t take initial value (which certainly saves some overhead) and this algorithm can be parallelized which means, it can be programmed to utilize multiple cores of a microprocessor simultaneously (Obviously, if the microprocessor has multiple cores in the first place. No points for guessing that. :p).

    Following figure shows how accumulate works.

    std::accumulate()
  • Transformreduce
    Transform
    reduce works same as reduce but it works on functions and templates. Its like the cousin twin brother who also happen to go and live abroad with his rich parent (poor reduce couldn’t afford all that ).

    std::transform_reduce()
  • Partial_sum
    Partial_sum is used to calculate sum of adjacent elements upto a given position in a collection of elements.

    For instance, the element at position three will constitute of the sum of first two elements elements and the third element (which basically means sum of first three elements) as shown below.

I hope with this blog post, I could help someone in understanding the common algorithms from Standard template library that are often used in C++.