重载operator <for std :: set confused me

Question

我知道我必须重载operator <for std :: set。

我使用两个类重载operator <：“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。