Why overloading operator< for std::tuple doesn't seem to work in priority

Here is the MWE:

#include <iostream>
#include <tuple>
#include <queue>
using namespace std;

bool operator<(tuple<int, int, int> lhs, tuple<int, int, int> rhs)
{
    return get<1>(lhs) < get<1>(rhs);
}

int main()
{
    priority_queue<tuple<int, int, int>> q;
    q.push(make_tuple(2, 5, 3));
    q.push(make_tuple(2, 3, 3));
    cout << get<1>(q.top());
    return 0;
}

The weird part is that whether I type < or > in the sentence return get<1>(lhs) < get<1>(rhs);, the output is always 5. Why does this happen?

CodePudding user response：

Your overload of operator< is not selected because it's in a different namespace than both std::priority_queue and std::tuple. It is never considered as an overload candidate.

The search for a suitable overload happens in the namespace where the operator is called from, which is the namespace priority_queue lives in, i.e. std. Argument-dependent lookup causes an additional search in the namespaces of the arguments, but because tuple is also in the std namespace, that doesn't help either. There is no reason for the compiler to ever consider the global namespace at all.

Instead, the standard library's definition of std::operator< for tuples is used. You can see that if you put your own implementation in a namespace std block:

// !!!!!!!!!!!!!!!!!!!!!!!!
// BAD SOLUTION, DO NOT USE
// !!!!!!!!!!!!!!!!!!!!!!!!

namespace std {
bool operator<(tuple<int, int, int> lhs, tuple<int, int, int> rhs)
{
    return get<1>(lhs) > get<1>(rhs); // Changed to > so we can see the difference.
}
}

Now the output is 3. Your operator is now considered and takes precedence over the default one, because non-template functions come before template functions.

But it is forbidden by the standard to put your own code into namespace std (with some small exceptions), so what to do? The solution is to pass a comparator functor explicitly:

#include <iostream>
#include <tuple>
#include <queue>
using namespace std;

struct element_1_greater {
    bool operator()(tuple<int, int, int> lhs, tuple<int, int, int> rhs)
    {
        return get<1>(lhs) > get<1>(rhs);
    }
};

int main()
{
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, element_1_greater> q;
    q.push(make_tuple(2,5,3));
    q.push(make_tuple(2,3,3));
    cout << get<1>(q.top()) << '\n';
    return 0;
}

Notice that we need to pass the second argument to priority_queue as well; you can shorten this with a typedef or using declaration of course.

CodePudding user response：

std::tuple has overloaded operator< (3) in the namespace std until C 20 and operator<=> (7) also in the namespace std since C 20. They are closer matches than one that you define in the global namespace as first seen in std prior the global namespace.

The fix:

#include <iostream>
#include <tuple>
#include <queue>
using namespace std;

bool operator<(tuple<int, int, int> lhs, tuple<int, int, int> rhs)
{
    return get<1>(lhs) > get<1>(rhs);
}

int main()
{
    using T = tuple<int, int, int>;
    priority_queue<T, vector<T>, bool(*)(T, T)> q(::operator<);
    q.push(make_tuple(2,5,3));
    q.push(make_tuple(2,3,3));
    cout << get<1>(q.top());
    return 0;
}
// Outputs: 3