CODEWITHSUNDEEP
c++algorithmsortingsetstd
DinoStray
DinoStray

Reputation: 774

overloading operator < for std::set confused me

I know that I have to overload operator < for std::set.

I overload operator < with two classes: "UniqueID" and "UniqueIDWithBug". The only difference is "UniqueID" added code this->unique_id_a_ == t.unique_id_a_ while comparing.

Then I put same elements into the two sets. Finally I find one element inside the sets. One set can find it, another can not. This problem confused me for a long time.

struct UniqueID {
    uint64_t unique_id_a_{0};
    uint64_t unique_id_b_{0};

    bool operator<(const UniqueID &t) const {
        if (this->unique_id_a_ < t.unique_id_a_) {
            return true;
        }
        if (this->unique_id_a_ == t.unique_id_a_ &&
            this->unique_id_b_ < t.unique_id_b_) {
            return true;
        }
        return false;
    }
};

struct UniqueIDWithBug {
    uint64_t unique_id_a_{0};
    uint64_t unique_id_b_{0};

    bool operator<(const UniqueIDWithBug &t) const {
        if (this->unique_id_a_ < t.unique_id_a_) {
            return true;
        }
        return (this->unique_id_b_ < t.unique_id_b_);
    }
};

// init data
std::set<UniqueID> _set = {
        {17303934402126834534u, 2922971136},
        {8520106912500150839u,  3118989312},
        {9527597377742531532u,  2171470080},
        {10912468396223017462u, 3972792320},
};
std::set<UniqueIDWithBug> _set_with_bug = {
        {17303934402126834534u, 2922971136},
        {8520106912500150839u,  3118989312},
        {9527597377742531532u,  2171470080},
        {10912468396223017462u, 3972792320}};

UniqueID _unique_id = {10912468396223017462u, 3972792320};
UniqueIDWithBug _unique_id_with_bug = {10912468396223017462u, 3972792320};

if (_set.find(_unique_id) == _set.end()) {
    std::cout << "_set not find" << std::endl;
}

if (_set_with_bug.find(_unique_id_with_bug) == _set_with_bug.end()) {
    std::cout << "_set_with_bug not find" << std::endl;
}

The outputs: _set_with_bug not find

Upvotes: 1

Views: 91

Answers (1)

Lightness Races in Orbit
Lightness Races in Orbit

Reputation: 385174

The less-than operation you define for use with std::set (and others) must be a valid strict weak ordering.

Your UniqueIDWithBug ordering is not.

For example, consider:

UniqueIDWithBug a{1, 10};
UniqueIDWithBug b{2, 5};

Now observe that both a < b and b < a are true. This is just a quick demonstration that you do not have a strict weak ordering; indeed, this is not an ordering at all!

So your program has undefined behaviour. The internals of the std::set mechanism assume a valid ordering, but yours is not. In this case the observable result was "element not found". It could have been "make a pizza".

Constructing a good strict weak ordering can be difficult, but you've already done the hard work, because UniqueID's ordering is correct.

Alternatively, abandon the ordering entirely, define a hash function, and switch to unordered_set.

Upvotes: 5

Related Questions