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

Question

我一直在学习c ++.我遇到了这个问题.

我设置了包含一个自定义结构,其中包含两个long int的a&b.我有一个比较数字的自定义比较器结构,如果a或b不同,则返回true.

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

您的比较函数应返回某个元素是否小于另一个元素,而不是它们是否相等.(更正式地说,它必须在集合的元素上定义"严格的弱排序".)

使用类似的东西

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.

为了避免将来出现此类问题,请务必阅读文档.它们清楚地解释了你的比较函数应该做什么.

供参考:std::tie如上所用,构造对其参数的引用元组,然后可以按字典顺序进行比较<.这是一种简单,通用且快速的方法,可以为不太可比的东西的集合构建一些排序.

Answer 2

您的比较功能需要满足严格/弱的订购要求.

(我实际上更喜欢使用答案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;
}