C++ std::set and std::multiset Changing the default sort of a set
Example
set and multiset have default compare methods, but in some cases you may need to overload them.
Let's imagine we are storing string values in a set, but we know those strings contain only numeric values. By default the sort will be a lexicographical string comparison, so the order won't match the numerical sort. If you want to apply a sort equivalent to what you would have with int values, you need a functor to overload the compare method:
#include <iostream>
#include <set>
#include <stdlib.h>
struct custom_compare final
{
bool operator() (const std::string& left, const std::string& right) const
{
int nLeft = atoi(left.c_str());
int nRight = atoi(right.c_str());
return nLeft < nRight;
}
};
int main ()
{
std::set<std::string> sut({"1", "2", "5", "23", "6", "290"});
std::cout << "### Default sort on std::set<std::string> :" << std::endl;
for (auto &&data: sut)
std::cout << data << std::endl;
std::set<std::string, custom_compare> sut_custom({"1", "2", "5", "23", "6", "290"},
custom_compare{}); //< Compare object optional as its default constructible.
std::cout << std::endl << "### Custom sort on set :" << std::endl;
for (auto &&data : sut_custom)
std::cout << data << std::endl;
auto compare_via_lambda = [](auto &&lhs, auto &&rhs){ return lhs > rhs; };
using set_via_lambda = std::set<std::string, decltype(compare_via_lambda)>;
set_via_lambda sut_reverse_via_lambda({"1", "2", "5", "23", "6", "290"},
compare_via_lambda);
std::cout << std::endl << "### Lambda sort on set :" << std::endl;
for (auto &&data : sut_reverse_via_lambda)
std::cout << data << std::endl;
return 0;
}
Output will be:
### Default sort on std::set<std::string> :
1
2
23
290
5
6
### Custom sort on set :
1
2
5
6
23
290
### Lambda sort on set :
6
5
290
23
2
1
In the example above, one can find 3 different ways of adding compare operations to the std::set, each of them is useful in its own context.
Default sort
This will use the compare operator of the key (first template argument).
Often, the key will already provide a good default for the std::less<T> function. Unless this function is specialized, it uses the operator< of the object.
This is especially useful when other code also tries to use some ordering, as this allows consistency over the whole code base.
Writing the code this way, will reduce the effort to update your code when the key changes is API, like: a class containing 2 members which changes to a class containing 3 members. By updating the operator< in the class, all occurrences will get updated.
As you might expect, using the default sort is a reasonable default.
Custom sort
Adding a custom sort via an object with a compare operator is often used when the default comparison doesn't comply. In the example above this is because the strings are referring to integers. In other cases, it's often used when you want to compare (smart) pointers based upon the object they refer to or because you need different constraints for comparing (example: comparing std::pair by the value of first).
When creating a compare operator, this should be a stable sorting. If the result of the compare operator changes after insert, you will have undefined behavior. As a good practice, your compare operator should only use the constant data (const members, const functions ...).
As in the example above, you will often encounter classes without members as compare operators. This results in default constructors and copy constructors. The default constructor allows you to omit the instance at construction time and the copy constructor is required as the set takes a copy of the compare operator.
Lambda sort
Lambdas are a shorter way to write function objects. This allows writing the compare operator on less lines, making the overall code more readable.
The disadvantage of the use of lambdas is that each lambda gets a specific type at compile time, so decltype(lambda) will be different for each compilation of the same compilation unit (cpp file) as over multiple compilation units (when included via header file). For this reason, its recommended to use function objects as compare operator when used within header files.
This construction is often encountered when a std::set is used within the local scope of a function instead, while the function object is preferred when used as function arguments or class members.
Other sort options
As the compare operator of std::set is a template argument, all callable objects can be used as compare operator and the examples above are only specific cases. The only restrictions these callable objects have are:
- They must be copy constructable
- They must be callable with 2 arguments of the type of the key. (implicit conversions are allowed, though not recommended as it can hurt performance)
