Inserting pair in std::set is inconsistent (doesn't recognize .second)

Question

This code performs differently if I add a condition:

First case:

#include<bits/stdc++.h>
using namespace std;

struct comp
{
    bool operator()(pair<int,pair<int,int> > a, pair<int,pair<int,int> > b)
    {
        return a.first>b.first;
    }
};

int main()
{
    set<pair<int,pair<int,int>>,comp> s;
    auto d = s.insert({4,{6,10}});
    cout<<(d.first)->first<<" "<<(d.first)->second.first<<" "<<(d.first)->second.second<<endl;
    d = s.insert({4,{0,4}});
    cout<<(d.first)->first<<" "<<(d.first)->second.first<<" "<<(d.first)->second.second<<endl;
}

Output:

4 6 10
4 6 10

Second case: (with condition on .second)

#include<bits/stdc++.h>
using namespace std;

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

int main()
{
    set<pair<int,pair<int,int>>,comp> s;
    auto d = s.insert({4,{6,10}});
    cout<<(d.first)->first<<" "<<(d.first)->second.first<<" "<<(d.first)->second.second<<endl;
    d = s.insert({4,{0,4}});
    cout<<(d.first)->first<<" "<<(d.first)->second.first<<" "<<(d.first)->second.second<<endl;
}

Output:

4 6 10
4 0 4

Why does the set not add a different pair in the first case? I thought the extra condition only decides the order, and doesn't differentiate between elements.

Please do tell: Who told you to include that header? We must make sure to warn people off against taking advice from that source. — Kerrek SB, Apr 23 '16 at 11:07
@KerrekSB You mean ? Whats wrong with it other than being non-standard (its useful for coding contests AFAIK)? — goelakash, Apr 23 '16 at 11:17
@KerrekSB people use it in competitive programming for most of the time on platform like codeforces, codechef, topcoder etc. It is much quicker to code your solution than writing all the header files individually. Although it is not a good practice to include such header. — Rishit Sanmukhani, Apr 23 '16 at 11:19
@Rishit: You mean there's a real-time constraint on how long you can take to type out the source code? Hm. I suppose you could have a ready-made file at hand locally to copy-paste from... [Edit.] Oh, I found [this question](https://stackoverflow.com/questions/25311011), apparently the host has that header precompiled, so it may be more efficient to compile the program. — Kerrek SB, Apr 23 '16 at 11:26
@KerrekSB Yeah, copy-paste does work which is why most of people keep a template file with all necessary headers included. Yes, time taken to type source code does account for score. Faster you code, faster you will be able to submit fetching more points.... [Edit.] Good link! — Rishit Sanmukhani, Apr 23 '16 at 11:30
@KerrekSB all-in-one headers help for setups using precompiled headers — M.M, Apr 23 '16 at 11:50

rems4e · Accepted Answer · 2016-04-23T11:42:49.853

3

Your first comparator only takes the first item of the pair in consideration. When you try to insert the second pair, it is considered equal to the already inserted pair, and thus not inserted.

Instead, you get back the object that was already inserted in the set, which is the expected behavior.

Remember, a set, by definition, only has one instance of a particular object, and your comparator helps it to state how 2 objects compare to each other.

edited Apr 23 '16 at 11:42

answered Apr 23 '16 at 10:53

rems4e

3,112
1
17
24

Note: without using a custom comparator, the `std::set` is able to distinguish between (a,(b,c)) and (a,(d,e)). – goelakash Apr 24 '16 at 17:01

Inserting pair in std::set is inconsistent (doesn't recognize .second)

1 Answers1