CODEWITHSUNDEEP
c++c++11set
Gizmo
Gizmo

Reputation: 2210

std::set contains duplicate element after using std::set.erase

Ehm, I'm in the need of desiging a player timer which will be executed each 30 minuts for each player.

instead of looping all players I made a std::set<std::pair<playerid,last_time_executed>> (both are ints std::set<std::pair<int,int>>) and:

But I don't know how to erase an element by playerid only, so I did a few test with random values which my brain chose, and the results:

#include <iostream>
#include <set>

typedef std::pair<int, int> Pair;
struct Cmp{bool operator ()(const Pair &a, const Pair &b){return a.second < b.second;}};
std::set<Pair, Cmp> myset;

int main() {

    myset.insert(Pair(0, 5));
    myset.insert(Pair(1, 0));
    myset.insert(Pair(1, 1));
    myset.erase(Pair(0, 698));

    std::cout << myset.size() << std::endl;
    for (auto i : myset)
        std::cout << "(" << i.first << "," << i.second << ")" << std::endl;
    return 0;
}

This actually prints.... (note the duplicated id '1')

3 (1,0) (1,1) (0,5)

While this:

int main() {

    myset.insert(Pair(0, 5));
    myset.insert(Pair(1, 0));
    myset.insert(Pair(1, 1));

    std::cout << myset.size() << std::endl;
    for (auto i : myset)
        std::cout << "(" << i.first << "," << i.second << ")" << std::endl;
    return 0;
}

prints this (no duplicate id?):

2 (1,1) (0,5)

andeven more stangely(!) now, this:

int main() {

    myset.insert(Pair(0, 5));
    myset.insert(Pair(1, 0));
    myset.insert(Pair(1, 1));
    myset.erase(Pair(0, 0));
    std::cout << myset.size() << std::endl;
    for (auto i : myset)
        std::cout << "(" << i.first << "," << i.second << ")" << std::endl;
    return 0;
}

prints this (no duplicate id?):

2 (1,1) (0,5)

Which is really surprising as I would expect the same output as in the first test.

Why is this happening?

Upvotes: 1

Views: 1163

Answers (2)

Chris Drew
Chris Drew

Reputation: 15334

A std::set uses the comparator to "determine both the order the elements follow in the container and whether two element keys are equivalent".

As your comparator only compares the last_time_executed it considers two Pair equivalent if they have the same last_time_executed. Consequently when you do myset.erase(Pair(0, 0)); it erases Pair(1, 0).

When I run your second example I get the duplicate player id as I would expect.

Upvotes: 1

sehe
sehe

Reputation: 392911

Your comparison predicate compares only the second field of the pair.

The "collision" in the first field is irrelevant.

Change it to get the behaviour you describe:

struct Cmp {
    bool operator()(const Pair &a, const Pair &b) { return a.first < b.first; }
};

Live On Coliru

Also, as others have noticed, this is more like std::map<idtype, valuetype>:

Live On Coliru

#include <iostream>
#include <map>

std::map<int, int> myset;

int main() {

    mymap.emplace(0, 5);
    mymap.emplace(1, 0);
    mymap.emplace(1, 1);
    mymap.erase(0);

    std::cout << myset.size() << std::endl;
    for (auto i : myset)
        std::cout << "(" << i.first << "," << i.second << ")" << std::endl;
    return 0;
}

Note, to actually update the value for an (existing) key:

    mymap[0] = 5;
    mymap[1] = 0;
    mymap[1] = 1;

Upvotes: 1

Related Questions