Why does overloading operator< for std::tuple not seem to work in priority_queue?

Question

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?

Answer 1

Your overload of operator< is not selected because it's in a different namespace than both std::priority_queue and std::tuple. It's not in the candidate set, so it is never even 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.

Answer 2

std::tuple is in the namespace std, the compiler looks for an overloaded operator< (3) in the namespace std until C++20 and operator<=> (7) also in the namespace std since C++20. The one of the global namespace is not considered while searching due to the argument dependent name lookup rules.

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