std :: set有重复的条目

Question

我有一组3个整数的元组,我不想要任何重复.也就是说,我不希望2个条目具有相同的3个值.

这是我的代码.

struct Key{
    unsigned a;
    unsigned b;
    unsigned c;
  public:
    Key(unsigned _a, unsigned _b, unsigned _c) :
        a(_a),
        b(_b),
        c(_c) {}
    bool operator<(const Key& rhs) const
    {
        if (a < rhs.a) {
            return true;
        }
        if (b < rhs.b) {
            return true;
        }
        if (c < rhs.c) {
            return true;
        }
        return false;
    };
};
std::set<Key> myset;

但我myset有时会看到重复.我无法准确捕捉到什么序列导致添加重复条目.它并不总是发生.我的问题是,我的operator<功能有什么本质上的错误吗？

Answer 1

这几乎是正确的!但是你太快了.

bool operator<(const Key& rhs) const
{
    if (a < rhs.a)
        return true;
    if (a > rhs.a)
        return false;

    if (b < rhs.b)
        return true;
    if (b > rhs.b)
        return false;

    return (c < rhs.c);
};

否则,例如,以下结果会给出错误的结果:

Key lhs{3,1,0};
Key rhs{2,2,0};

assert(lhs < rhs); // passes, wrongly, because !(3 < 2) but then (1 < 2).
                   // you need an immediate `return false` when !(3 < 2)

做这样的事情比较安全:

bool operator<(const Key& rhs) const
{
    return std::tie(a, b, c) < std::tie(rhs.a, rhs.b, rhs.c);
}

C++的标准库已经知道如何处理它,所以你不必这样做.

现在,你的bug如何导致重复密钥set？

Set的内部算法依赖于排序是严格的弱排序 - 当你打破这个前提条件时,你打破了管理内部树的算法,内部树是使用这种排序作为其圣经构造和排列的.

基本上,所有的地狱都破裂了.你可能会因此而崩溃.在您的情况下,症状稍微更温和(至少现在),变形/损坏的数据树导致重复数据的出现.

如果您通过打破先决条件并导致UB开始,尝试推断导致特定结果的特定事件链是愚蠢的.

• /sf/answers/68583791/
• 通过'tuple'和'tie'实现比较运算符,这是一个好主意？

Answer 2

你operator<()是不相符的,因为key1<key2和key2<key1可以都true(例如:key1={1,3,0},key2={3,1,0}).您应该为成员变量赋予优先权:

    if (a < rhs.a) {
        return true;
    } else if (a == rhs.a) {
        if (b < rhs.b) {
            return true;
        } else if (b == rhs.b) {
            if (c < rhs.c) {
                return true;
            }
        }
    }
    return false;