How is std::set_difference Implemented?
In last week video, we saw the algorithms on sets that the STL provides. We saw how you can use them to manipulate sorted collections in your code, in an expressive manner.
Sean Parent said in one of his talks that we should be as familiar with STL algorithms as possible, and take this to the point where we understand how the STL algorithms are implemented.
So this is what we’re going to do in this week’s video: we dive deep inside the implementation of std::set_difference.
This sort of analysis is particularly useful for algorithms on sets. Indeed they have some specific properties, such as requiring that their inputs are sorted for example. Also, if you want to override their comparison operator, your custom operator must have the semantics of operator< for the algorithm to do what you expect, and not operator==. And they have a complexity in O(n).
It’s all well to just learn those properties by heart. But a better way to integrate them is to see really how they fit into the implementation of the algorithm.
We analyze std::set_difference to get the idea behind the implementation of algorithms on sets. Indeed, the other ones use similar implementation patterns.
Ready to dive in?
You’ll find the corresponding code here.
As usual, your feedback is more than welcome. If you like the concept of digging into the implementation of STL algorithms, we could take other ones and analyze them.
And if you have an algorithm you’re curious about, be there on how to use it or how it is implemented, don’t hesitate to let me know. The more we study them, the more we’ll be able to use them well and write expressive code to manipulate collections in C++.
Related articles:
- The importance of knowing the STL <algorithm>s
- Know your algorithms: algos on sets
- The STL algorithms on sets (video)
Share this post!
