wannbegood's blog

Strange Behaviour with std::set comparators
By wannbegood, history, 4 years ago, In English 
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define int long long

const int N = 1e5 + 20;

int m[N];

struct comp {
    bool operator() (const pair <int , int> &lhs, const pair <int , int> &rhs) const {
        return lhs.first > rhs.first;
    }
};


int32_t main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

    set <pair <int , int> , comp> s;
    s.insert({1 , 1});
    s.insert({1 , 2});
    s.insert({1 , 3});
    s.insert({1 , 4});

    for(auto x : s)
        cout << "(" << x.first << "," << x.second << ")  ";
    cout << endl;
    return 0;
}

I expected the above code to print : (1,4) (1,3) (1,2) (1,1) But it only prints :

(1,1)

However, that works fine without the comparator. Why is this strange thing happening?

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by wannbegood (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
← Rev. 5   Vote: I like it +9 Vote: I do not like it

All elements in a set must be unique when compared using the comparator.

The comparator considers two elements a and b equal if a < b == false and b < a == false

In your case all elements are considered equal by the set since only the first element of each pair is compared a simple fix would be

struct comp { bool operator() (const pair <int , int> &lhs, const pair <int , int> &rhs) const { 
return lhs.first == rhs.first? lhs.second > rhs.second: lhs.first > rhs.first; } };
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thanks, that helped.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      Pandemic Can you please suggest errors/fixes for this problem as well : Comparators in C++

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i don't know how to maintain the relative order and move zeros to the end using sort.

        you can use use to move zeros to the end and sort the rest of the elements in non-decreasing order using this

        bool comp(const int &a, const int &b)
{
    if (a == 0)
        return false;
    if (b == 0)
        return true;
    return a < b;
}
        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I found that my comparator doesn't follow the transitivity rule that every comparator should follow, that is, if(comp(a , b) == true and comp(b, c) == true), then comp(a , c) should also be true.

          → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    std::pair already defines all comparison operators in such a way that both elements are checked. So you can just write lhs > rhs. Even shorter would be to get rid of comp altogether and use std::greater<> instead.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

That's the risk of using a comparator with set. Basically what a comparator does is that, it treats the elements you're inserting, as the quantity that is being compared to insert it. In this case, you're comparing only the first value to insert in the set which are all the same, and as set doesn't contain repititions, it is discarding all the "1" values other than the first one.

For example:

Main code
Comparator 1
Comparator 2
Comparator 3
→ Reply