std::set already contains the member even though it's different

Admin 1
Viewed 60

I wrote the following simple code:

std::set<Edge> edges;
Edge edge1("a","b");
Edge edge2("a","c");
edges.insert(edge1);
if (edges.find(edge2) != edges.end()) //edge2 already exists
    std::cout << "OH NO!";

Which has a bug since OH NO! gets printed even though edge1 and edge2 are different from each other.

Here's how I have implemented operator == and operator < for Edge:

bool operator==(const Edge &e1, const Edge &e2) {
    return (e1.source == e2.source) && (e1.destination == e2.destination);
}

bool operator<(const Edge &e1, const Edge &e2) {
    return e1.source < e2.source;
}

What is causing this bug?

set c++
1 Answers

According to your operator<, Edge("a","b") and Edge("a","c") are equal. You need to tell the computer how you want to sort items when the first element is the same. The easiest way is to do a lexicographical sort. std::tie is great for this.

You'll need to #include <tuple> for this.

bool operator<(const Edge &e1, const Edge &e2) {
    return std::tie(e1.source, e1.destination) < std::tie(e2.source, e2.destination);
}

Edit: Nah don't define the other operators in terms of operator< if it's simple enough.

Or do. It's up to you. I'm undecided which style I prefer.

bool operator==(const Edge &e1, const Edge &e2) {
    return e1.source == e2.source && e1.destination == e2.destination;
}

is perfectly readable and maintainable. Maybe if it were more complicated I'd define it in terms of operator<.

Old suggestion follows:

It's also recommended to define all your other comparison functions in terms of operator<:

bool operator==(const Edge &e1, const Edge &e2) {
    return !(e1 < e2) && !(e2 < e1);
}

Not necessarily the most efficient (depending on your compiler), but unless you absolutely need it to be as fast as possible this keeps your code super maintainable.

user_20271960
Related