Adapting STL Algorithms on Sets
This article is NWH, standing for Not Written Here. NWH is inspired from the NIH (Not Invented Here) syndrome which consists in refraining from using existing code from outside the company and reinventing the wheel every time. Just like it is good practice to look out for solutions developed elsewhere, we’re going to look at a high quality article written elsewhere. Or said differently, an article that is NWH.
Algorithms on sets are very useful functions that the STL offers to compare and extract data from collections. We had an in-depth summer series exploring algorithms on sets (even beyond the STL), and here is an Autumn follow up to close off the topic for now.
For example, std::set_difference takes two collections and outputs the elements that are in the first one but not in the second one.
This is the kind of task that we need on a daily basis when programming, and that is a pain to re-write ourselves every time. Using the algorithms instead leads to more expressive code.
What’s more, naive implementations of algorithms on sets are inefficient. The naive approach would be to iterate on the elements of the first collection and look them up in the second collection. This leads to a complexity of m*n, where m and n are the sizes of the first and second collection respectively.
But the STL algorithms on sets have a complexity of m+n, and not m*n.
How do they do that? They don’t just take collections. They take “sets”, which means sorted collections. The fact that they are sorted allows them to perform a smarter algorithm and obtain a complexity of only m+n.
That’s all well, until you need to work on collections that are not sorted. That happens, not all collections are sorted in our day-to-day job, right?
What to do then?
This is what dr Ivan Čukić explores in the NWH I suggest for today: Knowing when not to use the STL algorithms – set operations.
Enjoy the reading!
You will also like
- STL Algorithms on Sets
- Know your algorithms: algos on sets
- How is std::set_difference Implemented?
- The World Map of C++ STL Algorithms
- Understanding the implementation of std::is_permutation
Share this post!
