Блог пользователя wannbegood

Strange Behaviour with std::set comparators
Автор wannbegood, история, 6 лет назад, По-английски 
#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?

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
6 лет назад, скрыть # |
← Rev. 5  
Проголосовать: нравится +9 Проголосовать: не нравится

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; } };
→ Ответить
»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +7 Проголосовать: не нравится

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
→ Ответить