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

Introduction

In the world of C++ programming, the Standard Template Library (STL) is an indispensable tool that enhances productivity and efficiency. Whether you're a seasoned developer or just starting out, mastering STL algorithms can significantly boost your coding prowess. These algorithms provide powerful, reusable components that simplify complex operations and improve code clarity. However, with the extensive range of algorithms available, it can be overwhelming to know where to begin. In this post, we break down the vast landscape of STL algorithms into 10 essential groups, each with unique functionalities that every C++ programmer should be familiar with. By the end of this guide, you'll have a clearer understanding of how to leverage these groups to write more robust and efficient code. So, let's dive in and explore the must-know STL algorithm groups that will take your C++ skills to the next level!

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

  Copy
  std::rotate()

• Shuffle
  It uses a random generator and reorganizes the collection randomly.

  Copy
  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.

  Copy
  std::next_permutation()

• Prev_permutation
  Just like next_permutation, prev_permutation gives the previous order.

  Copy
  std::prev_permutation()

• Finally, reverse simply reverses the order of collection entirely.

  Copy
  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.

  Copy
  std::accumulate()

• Transformreduce
  Transformreduce 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 ).

  Copy
  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.

Conclusion

Mastering the 10 groups of STL algorithms is a game-changer for any C++ programmer. These powerful tools not only streamline your coding process but also enhance the readability and efficiency of your code. By familiarizing yourself with each group, you can tackle a wide range of programming challenges with confidence and ease. Whether you’re sorting data, performing complex calculations, or managing collections, the STL algorithms provide robust solutions that save time and effort. As you continue to develop your skills, keep exploring and experimenting with these algorithms to fully unlock their potential. With practice, you’ll find that these tools become an integral part of your programming toolkit, empowering you to write cleaner, faster, and more maintainable code. So, dive into the STL, embrace its versatility, and watch your C++ programming abilities soar to new heights!

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

---

Feel free to write your opinions, questions or any errors you may have come across while reading this blog in the comments section below.

You can use the contact form as well.