In this tutorial, we will discuss how to use set in C++ with custom comparator.

Make set to store elements in decreasing order in C++

In C++, the set container stores only unique elements. By default, it stores elements in sorted order, which is ascending. However, there are scenarios when we might want the set to store elements in decreasing order. In such cases, we can use comparators. If you are using a set with custom objects, you can either overload the less-than operator in your class or provide a custom comparator. This custom comparator can be a lambda function or a separate comparator class. The set container will use this comparator to compare elements while storing them in sorted order.

Let’s start with some examples.

Suppose we have a set of integers:

std::set<int> setObj = {3, 5, 5, 3, 6, 7, 6, 3, 2, 5, 9, 8};

If we store these integers in a set, but only unique values, and numbers will be stored in ascending order. We can confirm this by iterating through and printing the set. All integers in the set will be displayed in ascending order. Like this,

2 3 5 6 7 8 9 

Now, if we want our set to store elements in decreasing order, we can pass a comparator as the second template parameter when declaring the set object. Here, we’ll use the std::greater function from the STL:

std::set<int, std::greater<int> > setObj = {3, 5, 5, 3, 6, 7, 6, 3, 2, 5, 9, 8};

Now, if we insert integers into this set (or initialize it with a list of integers), they will be stored in decreasing order.

To confirm this, let’s see an example:

for (int val : setObj)
{
    std::cout << val << " ";
}
// Output: 9 8 7 6 5 3 2 

This output shows that the integers in setObj are stored in decreasing order.

Let’s see the complete example,

#include <iostream>
#include <set>

int main()
{
    // Create a set of integers and initialize
    std::set<int, std::greater<int> > setObj = {3, 5, 5, 3, 6, 7, 6, 3, 2, 5, 9, 8};

    // Print the set.
    for (int val : setObj)
    {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

Output:

9 8 7 6 5 3 2 

Using Lambda Function as Comparator with Set in C++

Now, instead of using a generic function, you can either use lambda functions or create custom comparator classes. Let’s see an example. Suppose we have a set of strings. By default, the set uses the less-than operator to sort the elements inside the set. Therefore, in a set of strings, all the elements will be stored in alphabetical order by default, in ascending order. However, if we want to store the elements in the set in order of size (i.e., the smallest string first and the longest string last), we need to provide a custom comparator while creating the set object. We can achieve this in two ways. The first method is by using a lambda function.

Here’s an example where we will use a lambda function that accepts two strings as arguments and compares those strings based on their size. We will then pass this lambda function while creating the set object.

#include <iostream>
#include <set>
#include <string>

int main()
{
    // Using lambda function for custom sorting based on string length
    auto func = [](const std::string &a, const std::string &b) -> bool {
                        return a.length() < b.length();     
                };  

    std::set<std::string, decltype(func)> setObj(func);

    setObj.insert({"London", "Oslo", "Tokyo", "Berlin", "London", "Sydney", "Tokyo", "Delhi", "San Francisco", "Delhi"});

    std::cout << "set content: " << std::endl;

    for (const auto &city : setObj)
    {
        std::cout << "\"" << city << "\" ";
    }
    std::cout << std::endl;

    return 0;
}

Output:

set content: 
"Oslo" "Tokyo" "London" "San Francisco" 

This set of strings will store the elements in ascending order based on their size.

Using a Comparator class with Set in C++

Now, instead of using a lambda function, we can also use a custom comparator. For this purpose, we will create a comparator class and overload the () operator. We can provide this class as a template parameter when creating a set of strings. Consequently, the set will store the strings based on their length. Let’s see a complete example:

#include <iostream>
#include <set>
#include <string>

// Comparator class
class LengthComparator
{
public:
    bool operator()(const std::string &a, const std::string &b) const
    {
        return a.length() < b.length();
    }
};

int main()
{

    std::set<std::string, LengthComparator> setObj;

    setObj.insert({"London", "Oslo", "Tokyo", "Berlin", "London", "Sydney", "Tokyo", "Delhi", "San Francisco", "Delhi"});

    std::cout << "set content: " << std::endl;

    for (const auto &city : setObj)
    {
        std::cout << "\"" << city << "\" ";
    }
    std::cout << std::endl;

    return 0;
}

Output:

set content: 
"Oslo" "Tokyo" "London" "San Francisco" 

With this setup, strings in the set are sorted in ascending order based on their size, i.e., the number of characters in the string.

Important Point about Comparators

This is how we can use a comparator to control the sorting order that the set uses. An important point to note here is how the set determines equality. For equality, the set uses the provided comparator function or the less-than operator, if no comparator is provided. For instance, when comparing elements A and B, the set will invoke the custom comparator (or the less-than operator). It first checks if A is less than B. If this is false, it checks if B is greater than A. If both conditions are false, it deduces that A is equal to B. We need to keep this behaviour in mind when creating a comparator function.

Ritika Ohri

Hi, I am Ritika Ohri, founder of this blog. I craft comprehensive programming tutorials and also manage a YouTube channel. You can also connect with me on Linkedin.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.