std::set存在重复条目

Question

std::set存在重复条目

14

我有一组由3个整数构成的元组，我不想有任何重复。也就是说，我不希望有两个条目具有相同的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<函数是否存在内部问题？

- Sindhura Bandi

你能发布一些重复的值吗？ - StenSoft

1

恭喜你为这个问题提出了正确的初始问题——通常一个破碎的严格弱序会导致这种情况。如果你在奇怪的方式下使用集合，那么你可能还有其他未定义行为。 - Lightness Races in Orbit

我试图简化我的问题。我测试的集合实际上将元组的第一个元素类型定义为 'boost::asio::ip::address_v4'。鉴于此，我在集合中看到了两次 (172.20.20.10, 4077, 17) 的条目。 - Sindhura Bandi

3个回答

9

您的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;

- jhnnslschnr

谢谢澄清。我看到我的比较函数存在一些排序问题。但它是否可以接受重复项？ - Sindhura Bandi

1

@jhnnslschnr：除非排序符合前提条件，否则它是UB。你关于!comp(a,b) && !comp(b,a)的断言是错误的，因为在破碎的排序中，可能会出现comp(a,b) == comp(b,a)，这显然是荒谬的。请参见我的答案。 - Lightness Races in Orbit

@LightnessRacesinOrbit 好的，UB是一个公平的观点，任何事情都有可能发生。 - jhnnslschnr

UB并不是一个神奇的独角兽 - 您看到的每个结果症状都有一个实际的原因，只是为了解释它，您必须深入了解内部算法，并拼凑使用的每个内存片段，每次越界数组访问时的内存值，每个单个内部操作的精确顺序，...而且它非常复杂，从来不值得做。因此，我们将其抽象化并说“任何事情都可能发生”。 :) - Lightness Races in Orbit

@jhnnslschnr cpp reference 是 cppreference.com，你正在链接到 cplusplus.com。 - Cubbi

显示剩余2条评论

2

您可以使用标准类std::tuple作为键。

然而，操作符可以定义如下：

bool operator <( const Key &rhs ) const
{
    return
    ( a < rhs.a ) ||
    ( !( rhs.a < a ) && ( b < rhs.b ) ) ||
    ( !( rhs.a < a ) && !( rhs.b < b ) && ( c < rhs.c ) );
};

这个运算符可以工作，只需要为对象类型a、b和c定义operator <。当然，对于算术类型，它已经被定义好了。

实际上，它与下面的代码是相同的：

#include <tuple>

//...

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

- Vlad from Moscow

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Lightness Races in Orbit · Accepted Answer

差不多就快对了！但你太早级联了。

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中有重复的key呢？

set内部算法依赖于排序是一个严格弱序——当你打破这个前提条件时，你就会破坏管理内部树的算法，而这棵树是使用这个排序作为其“圣经”构建和排列的。

基本上一切都会变得混乱。你可能会因此遇到崩溃。在你的情况下，症状比较温和（至少目前如此），导致数据树变形/混乱，看起来出现了重复数据。

如果你从一开始就打破了前提条件并引起UB，那么尝试推断导致特定结果的特定事件链是愚蠢的。