std::set 的重载运算符<让我感到困惑

overloading operator < for std::set confused me

提问人:DinoStray 提问时间:3/31/2019 最后编辑:Lightness Races in OrbitDinoStray 更新时间:4/2/2019 访问量:85

问:

我知道我必须重载 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未找到

C++ 算法 排序 std

评论

0赞 Sam Varshavchik 3/31/2019
是的,是错误的。那么你到底在问什么。你的问题中缺少一些基本的东西。这将是一个实际的、具体的问题。UniqueIDWithBug
0赞 DinoStray 3/31/2019
我混淆了为什么 UniqueIDWithBug 是错误的,我认为 UniqueIDWithBug 的运算符<就足够了
2赞 TrebledJ 3/31/2019
跟踪和比较 和 .做,都回来了.那么如何定义排序呢?UniqueIDWithBug a{1, 10}UniqueIDWithBug b{2,5}a < bb < atrue
0赞 TrebledJ 3/31/2019
考虑使用unordered_set
4赞 Retired Ninja 3/31/2019
std::tie使正确地执行此操作变得更加容易。 是你所需要的一切。想象一下,扩展您的正确版本以手动处理 4 个变量。return std::tie(unique_id_a_, unique_id_b_) < std::tie(t.unique_id_a_, t.unique_id_b_);operator<

答:

5赞 Lightness Races in Orbit 3/31/2019 #1

您定义为用于(和其他)的 less-than 运算必须是有效的严格弱排序std::set

您的 UniqueIDWithBug 排序不是。

例如,请考虑:

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

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

因此,您的程序具有未定义的行为。该机制的内部假定有有效的排序,但您的则不是。在本例中,可观察的结果是“未找到元素”。它可能是“做披萨”。std::set

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

或者,完全放弃排序,定义一个哈希函数,然后切换到 。unordered_set