5

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.

therainmaker
  • 4,253
  • 1
  • 22
  • 41

2 Answers2

11

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.

Kerrek SB
  • 464,522
  • 92
  • 875
  • 1,084
  • Then why does the overloaded operator work in the latter part of the code when I call `a < b`? Also, are `less` and `operator<` the same thing? – therainmaker Sep 16 '15 at 09:08
  • 3
    @therainmaker: Updated. `std::less` is a named predicate in the standard library that (usually) uses `<`, but may be specialized for user types. Ordering containers use it as the default comparator, but algorithms usually have separate overloads for the predicate version (though as @T.C. pointed out, the non-predicate form may delegate to the predicate form by using [`std::less` as of C++14](http://stackoverflow.com/questions/20317413/what-are-transparent-comparators)). – Kerrek SB Sep 16 '15 at 09:22
1

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;
});
Shreevardhan
  • 12,233
  • 3
  • 36
  • 50
  • 2
    I don't think this is an improvement, particularly if he wants to reuse that predicate. But maybe that's just me. – TartanLlama Sep 16 '15 at 09:09
  • 10
    "It seems you use a C++11 compiler"....and then you go on and use a C++14 feature. – T.C. Sep 16 '15 at 09:10