CODEWITHSUNDEEP
c++setoperator-overloading
nishantsingh
nishantsingh

Reputation: 4662

Operator overloading for making a set of elements of type pair<int, int>

How do I overload the '<' (less than) operator for pair of ints to insert the elements of this type into set. For example, consider the following program

#include <stdio.h>
#include <utility>
#include <set>
using namespace std;

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

int main(){
  pair<int, int> a = make_pair(1, 4);
  pair<int, int> b = make_pair(2, 3);
  set<pair<int ,int> > s;
  s.insert(b);
  s.insert(a);
  set<pair<int, int> >::iterator it = s.begin();
  for(; it!=s.end(); it++){
    printf("(%d %d)\n", it->first, it->second);
  }
  if(a < b) printf("a < b\n");
  else printf("b < a\n");
}

The output produced by the above code is:

(1 4)
(2 3)
b < a

I want the elements of the set to be ordered by the second element of the pair structure. How to do this?

Upvotes: 1

Views: 208

Answers (2)

TemplateRex
TemplateRex

Reputation: 70516

The problem is that std::set uses std::less internally for its comparisons and that delegates to the operator< of std::pair provided by the Standard Library. This will order your pairs lexicographically on first and then second.

However, you also pull in the entire namespace std and provide your own operator<. At the point where you do if(a<b), name lookup will find your own provided comparison and use that. This is why you got contradictory results.

You can write your own function object my_less and pass it to std::set. I'd recommend to use std::forward_as_tuple for it, but the implementation you provided is OK as well.

#include <stdio.h>
#include <utility>
#include <set>
#include <tuple>
using namespace std;

struct my_less 
{
    bool operator()(pair<int, int> const& a, pair<int, int> const& b) const
    {
        return std::forward_as_tuple(a.second, a.first) < std::forward_as_tuple(b.second, b.first);
    }
};

int main(){
  pair<int, int> a = make_pair(1, 4);
  pair<int, int> b = make_pair(2, 3);
  set<pair<int ,int>, my_less> s;
  s.insert(b);
  s.insert(a);
  set<pair<int, int> >::iterator it = s.begin();
  for(; it!=s.end(); it++){
    printf("(%d %d)\n", it->first, it->second);
  }
  if(my_less{}(a,b)) printf("a < b\n");
  else printf("b < a\n");
}

Live Example.

Upvotes: 3

Marco A.
Marco A.

Reputation: 43662

std::set maintains an order between its elements (each value is also its own key and thus it must be unique).

You cannot sort a std::set and subvert this ordering but you can define your own ordering criterion

struct sortBySecond {
  bool operator()(const pair<int, int>& e1, const pair<int, int>& e2) const {
    if (e1.second < e2.second)
      return true;
    else if (e1.second == e2.second) {
      if (e1.first < e2.first)
        return true;
      else
        return false;
    }
    else
      return false;
  }
};


int main() {
  pair<int, int> a = make_pair(1, 4);
  pair<int, int> b = make_pair(2, 3);
  set<pair<int, int>, sortBySecond> s;
  s.insert(b);
  s.insert(a);
  for (auto& el : s)
    std::cout << "(" << el.first << ";" << el.second << ")" << std::endl;
  return 0;
}

Live Example

Upvotes: 2

Related Questions