std::set 有重复的条目 [英] std::set has duplicate entry

问题描述

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

I have a set of tuples of 3 integers and I don't want any duplicates. That is, I don't want 2 entries with the same 3 values.

这是我的代码.

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< 函数是否存在本质上的错误?

But I see duplicates in myset sometimes. I can't catch exactly what sequence causes the duplicate entry to be added. It doesn't always happen. My question is this, is there something intrinsically wrong with my operator< function?

推荐答案

几乎正确！但是你的级联太早了.

It's nearly right! But you are cascading too soon.

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

否则，例如以下内容会给出错误的结果:

Otherwise the following, for example, gives the wrong result:

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++ 的标准库已经知道如何处理它，所以您不必这样做.

C++'s standard library already knows what to do with that, so you don't have to.

现在，您的错误如何导致 set 中的重复键?

Now, how can your bug lead to duplicate keys in a set?

Set 的内部算法依赖于严格弱排序 —当你打破这个先决条件时，你就破坏了管理内部树的算法，内部树是使用这个顺序作为它的圣经来构建和排列的.

Set's internal algorithm relies on the ordering being a strict weak ordering — when you break that precondition, you break the algorithms managing the internal tree, which is constructed and arranged using this ordering as its bible.

基本上，所有的地狱都崩溃了.你可能会因此崩溃.在您的情况下，症状稍微温和一些(至少目前是这样)，变形/损坏的数据树导致出现重复数据.

All hell breaks loose, basically. You could get a crash from this. In your case the symptoms were somewhat more benign (at least for now), with a deformed/mangled data tree resulting in the appearance of duplicated data.

如果您一开始就打破先决条件并导致 UB，那么试图对导致特定结果的特定事件链进行推理是愚蠢的.

It's folly to try to reason about the specific chain of events that led to a specific outcome, if you started off by breaking the preconditions and causing UB.

• https://stackoverflow.com/a/979768/560648
• 通过元组"和领带"实现比较运算符，好主意吗?

这篇关于std::set 有重复的条目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！