c++ - std::set 的重载运算符 < 让我很困惑

Question

我知道我必须为 std::set 重载运算符 <。

我用两个类重载运算符 <:“UniqueID”和“UniqueIDWithBug”。唯一的区别是“UniqueID”在比较时添加了代码this->unique_id_a_ == t.unique_id_a_。

然后我将相同的元素放入两个集合中。最后我在集合中找到了一个元素。一组可以找到它，另一组不能。这个问题困扰了我很久。

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;
}

输出:_set_with_bug 找不到

Answer 1

您定义用于 std::set 的小于操作(和其他)必须是有效的严格弱排序。

您的 UniqueIDWithBug 排序不是。

例如，考虑:

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

现在观察 a < b和 b < a是真的。这只是一个快速演示，表明您没有严格的弱排序；事实上，这根本不是一个命令!

所以你的程序有未定义的行为。 std::set 的内部构造机制假设一个有效的顺序，但你的不是。在这种情况下，可观察到的结果是“找不到元素”。它可能是“做披萨”。

构建良好的严格弱排序可能很困难，但您已经完成了艰苦的工作，因为 UniqueID 的排序是正确的。

或者，完全放弃排序，定义一个散列函数，然后切换到 unordered_set .