重载运算符<for std :: set使我困惑

Question

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

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

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

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。