Find key in std::set with custom comparator

Question

I've a class named Example with two integer elements a and b creating a set with that class and customized comparator. The comparator is used the second variable b as a higher priority with descending order. If the value is identical then first variable will be prioritize with higher value. Here is my code:

[C++ 14 ISO]

#include <iostream>
#include <set>

using namespace std;

class Example
{
    public:
        int a;
        int b;
        Example(int x, int y) { a=x; b=y; }
};

class Comparator
{
    public:
        using is_transparent = true_type;

        bool operator()(const int &left, const Example& right) const
        {
            if(left > right.b) return true;
            if(left == right.b) return left > right.a ? true: false;

            return false;
        }

        bool operator()(const Example& left, const int& right) const
        {
            if(left.b > right) return true;
            if(left.b == right) return left.a > right ? true: false;

            return false;
        }

        bool operator()(const Example& left, const Example& right) const
        {
            if(left.b > right.b) return true;
            if(left.b == right.b) return left.a > right.a ? true: false;

            return false;
        }
};

int main()
{
    set<Example, Comparator> sa;
    sa.emplace(Example(4,3));
    sa.emplace(Example(1,2));
    sa.emplace(Example(5,3));
    sa.emplace(Example(2,7));
    sa.emplace(Example(3,1));

    for(auto it=sa.begin(); it!=sa.end(); it++)
        cout<< it->a <<" "<< it->b<<endl;

    cout<<"Find: "<<endl;
    auto it=sa.find(3);
    if(it!=sa.end())
        cout << it->a<<" " << it->b << endl;
    return 0;
}

Output:

2 7
5 3
4 3
1 2
3 1
Find:

It dose not find the value 3 with the above comparator. Anybody tell me, how can I find the first value with variable a in the class Example using set data while customized comparator is used?

When I use below comparator is working well while sorted in ascending and descending order compared with only first variable a.

class Comparator
{
    public:
        using is_transparent = true_type;

        bool operator()(const int & left, const Example& right) const
        {
            return left < right.a;
        }

        bool operator()(const Example & left, const int& right) const
        {
            return left.a < right;
        }

        bool operator()(const Example& left, const Example& right) const
        {
            return left.a < right.a;
        }
};

Output:

1 2
2 7
3 1
4 3
5 3
Find:
3 1

Answer 1

Make two changes. First, in heterogeneous comparison, compare the int value only with b component:

    bool operator()(const Example& left, int right) const
    {
        return left.b > right;
    }

(You won't need the mirror comparison in light of the second change we are about to make).

Second, use lower_bound in place of find:

auto it=sa.lower_bound(3);
if(it!=sa.end() && it->b == 3) { /* Found */ }

Note that we now have to additionally confirm that the element found has the correct b component; e.g. sa.lower_bound(4) would also find {5, 3} element. On the positive side, lower_bound is guaranteed to give us the first element in the sorted order, one with the largest a.

Demo

Answer 2

This implementation cannot work. The 2 comparator functions with the int on the left or right side, have a wrong comparison.

You can only compare to one value. It does not make sense, to compare to 2 values. There is only one.

And the "find"-algorithm will do a comparison from both ends to find out, if a value is equal.

For inserting a new Example into the set, only bool operator()(const Example& left, const Example& right) const will be used.

For finding a value with std::find, first bool operator()(const Example& left, const int& right) const will be invoked and then bool operator()(const int& left, const Example& right) const will be called for the same pair.

if(left.b == right) return left.a > right ? true: false; in the first case will then always lead to a wrong result. And, for the second case the same. Here if(left > right.b) return true; will already lead to the wrong result.

---

Simply modify your code like this:

#include <iostream>
#include <set>

using namespace std;

class Example
{
public:
    int a;
    int b;
    Example(int x, int y) { a = x; b = y; }
};

class Comparator
{
public:
    using is_transparent = true_type;

    bool operator()(const int& left, const Example& right) const
    {
        if (left > right.b) return true;
        return false;
    }

    bool operator()(const Example& left, const int& right) const
    {
        if (left.b > right) return true;
        return false;
    }

    bool operator()(const Example& left, const Example& right) const
    {
        if (left.b > right.b) return true;
        if (left.b == right.b) return left.a > right.a ? true : false;
        return false;
    }
};

int main()
{
    set<Example, Comparator> sa;
    sa.emplace(Example(4, 3));
    sa.emplace(Example(1, 2));
    sa.emplace(Example(5, 3));
    sa.emplace(Example(2, 7));
    sa.emplace(Example(3, 1));

    for (auto it = sa.begin(); it != sa.end(); it++)
        cout << it->a << " " << it->b << endl;

    cout << "Find: " << endl;
    auto it = sa.find(3);
    if (it != sa.end())
        cout << it->a << " " << it->b << endl;
    return 0;
}