<set> 自定义结构包含重复项

Question

我一直在学习c++。我被这个问题困住了。

我有 set，其中包含一个包含两个 long int 的 a 和 b 的自定义结构。我有一个自定义比较器结构，用于比较数字和 returns 如果 a 或 b 不同则为真。

typedef long int li;

struct number {
    number(li a1,li b1): a(a1), b(b1) {}
    li a, b;
};

struct compare {
    bool operator() (const number &lhs, const number& rhs) const{
        return lhs.a != rhs.a || lhs.b != rhs.b;
    }
};

int main() {
    set<number, compare> nums;
    nums.insert(number(1, 2));
    nums.insert(number(1, 1));
    nums.insert(number(2, 1));
    nums.insert(number(1, 2));
    for (auto &i : nums) {
        cout << i.a << " " << i.b << endl;
    }
    return 0;
}

这里的输出是

1 2

2 1

1 1

1 2

它有两个条目 1 2。如有任何澄清，我们将不胜感激。

Answer 1

您的比较函数应该 return 是否某个元素小于另一个元素，而不是它们是否相等。（更正式地说，它必须在集合的元素上定义 "Strict weak ordering"。）

使用类似

的东西

struct compare {
    bool operator() (const number &lhs, const number& rhs) const{
        return std::tie(lhs.a, lhs.b) < std::tie(rhs.a, rhs.b);
    }
};

如果您不关心排序，您可能想为您的类型定义一个合适的散列函数并使用 std::unordered_set。

为避免将来出现此类问题，请务必阅读 the docs. They clearly explain what your comparison function 应该做的事情。

供参考：上面使用的 std::tie 构造了对其参数的引用的元组，然后可以按字典顺序将其与 < 进行比较。这是一种简单、通用且快速的方法，可以为无法比较的东西的集合建立排序。

Answer 2

您的比较函数需要满足 strict/weak 排序要求。

（其实我更喜欢用std::tie的答案，但这对新手来说可能更能说明问题）

bool compare(const number& lhs, const number& rhs)
{
   if(lhs.a < rhs.a)
      return true;
   else if(lhs.a > rhs.a)
      return false;
   else
      return lhs.b < rhs.b;
}

<set> 自定义结构包含重复项

<set> with custom struct contains duplicates

c++

struct

set

comparator

stdset