std::set has duplicate entry

Question

I have a set of tuples of 3 integers and I don't want any duplicates. That is, I don't want 2 entries with the same 3 values.

And here is my code.

struct Key{
    unsigned a;
    unsigned b;
    unsigned c;
  public:
    Key(unsigned _a, unsigned _b, unsigned _c) :
        a(_a),
        b(_b),
        c(_c) {}
    bool operator<(const Key& rhs) const
    {
        if (a < rhs.a) {
            return true;
        }
        if (b < rhs.b) {
            return true;
        }
        if (c < rhs.c) {
            return true;
        }
        return false;
    };
};
std::set<Key> myset;

But I see duplicates in myset sometimes. I can't catch exactly what sequence causes the duplicate entry to be added. It doesn't always happen. My question is this, is there something intrinsically wrong with my operator< function?

Answer 1

It's nearly right! But you are cascading too soon.

bool operator<(const Key& rhs) const
{
    if (a < rhs.a)
        return true;
    if (a > rhs.a)
        return false;

    if (b < rhs.b)
        return true;
    if (b > rhs.b)
        return false;

    return (c < rhs.c);
};

Otherwise the following, for example, gives the wrong result:

Key lhs{3,1,0};
Key rhs{2,2,0};

assert(lhs < rhs); // passes, wrongly, because !(3 < 2) but then (1 < 2).
                   // you need an immediate `return false` when !(3 < 2)

It is safer to do something like this:

bool operator<(const Key& rhs) const
{
    return std::tie(a, b, c) < std::tie(rhs.a, rhs.b, rhs.c);
}

C++'s standard library already knows what to do with that, so you don't have to.

---

Now, how can your bug lead to duplicate keys in a set?

Set's internal algorithm relies on the ordering being a strict weak ordering — when you break that precondition, you break the algorithms managing the internal tree, which is constructed and arranged using this ordering as its bible.

All hell breaks loose, basically. You could get a crash from this. In your case the symptoms were somewhat more benign (at least for now), with a deformed/mangled data tree resulting in the appearance of duplicated data.

It's folly to try to reason about the specific chain of events that led to a specific outcome, if you started off by breaking the preconditions and causing UB.

---

• https://stackoverflow.com/a/979768/560648
• Implementing comparison operators via 'tuple' and 'tie', a good idea?

Answer 2

Your operator<() is not consistent, as key1<key2 and key2<key1 could both be true (example: key1={1,3,0}, key2={3,1,0}). You should give the member variables a precedence in comparison:

    if (a < rhs.a) {
        return true;
    } else if (a == rhs.a) {
        if (b < rhs.b) {
            return true;
        } else if (b == rhs.b) {
            if (c < rhs.c) {
                return true;
            }
        }
    }
    return false;