CODEWITHSUNDEEP
c++sorting
therainmaker
therainmaker

Reputation: 4343

overloaded operator< on pair not being used in sort

I have overloaded the less than operation for pair<int,int>, so that I can sort a vector in a particular manner. I want it to be in ascending order according to the first key of a pair, and if the first keys are equal, then I'd want it in descending order according to the second key.

The issue is that the sort function doesn't seem to be using the overloaded < operator, but if < is called on 2 pairs, the output returned is what I expect. I have attached a snippet of code below which I'm using for testing:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
bool operator<(pair<int, int> &a, pair<int, int> &b)
{
    if (a.first < b.first) return true;
    else if ((a.first == b.first) && (a.second > b.second)) return true;
    return false;
}

int main() {
    vector<pair<int, int>> test {make_pair(1,10), make_pair(3,4), make_pair(3,8),  make_pair(6, 23), make_pair(1,6)};
    sort(test.begin(), test.end());
    for (int i = 0; i < test.size(); i++)
      cout << test[i].first << " - " << test[i].second << "  ";
    cout << endl;
    auto a = make_pair(3,4);
    auto b = make_pair(3,8);
    cout << (a < b) << endl;
    return 0;
}

The input vector is {(1,10), (3,4), (3,8), (6,23), (1,6)}.

I expect the output to be {(1,10), (1,6), (3,8), (3,4), (6,23)}.

Obtained output is {(1,6), (1,10), (3,4), (3,8), (6, 23)}.

As you can see, the obtained output is the one you'd get by using the standard < operator without overloading. So I thought that this might be an issue, and checked (3,4) < (3,8). In this case, the answer was returned as false, in accordance to my overloaded operator. So where am I going wrong? Why isn't sort being affected by the overloaded operator? There are various questions on SO about similar issues, but couldn't find any that helped.

Upvotes: 5

Views: 288

Answers (2)

Shreevardhan
Shreevardhan

Reputation: 12641

It seems you use a C++11 compiler, correct and make it easier using lambda functions. Something like

sort(test.begin(), test.end(), [](const pair<int, int> & a, const pair<int, int> & b) {
    if (a.first < b.first) return true;
    else if ((a.first == b.first) && (a.second > b.second)) return true;
    return false;
});

Upvotes: 1

Kerrek SB
Kerrek SB

Reputation: 477070

There's already an operator< defined for pairs in the std namespace, and that's the one that's found by the version of std::sort that you are using. Your overload is never found. Use a named predicate instead:

struct MyPairComparator
{
    bool operator()(const std::pair<int, int> & a,
                    const std::pair<int, int> & b) const
    {
        // ...
    }
};

sort(test.begin(), test.end(), MyPairComparator());    // ADL, maybe
//                             ^^^^^^^^^^^^^^^^^^

Also, the predicate should be callable with constant values, so either take the arguments by value or by const reference.

Note that sort lives in the std namespace. By contrast, when you use the < expression in main, your own overload in the global namespace is indeed found.

Upvotes: 11

Related Questions