C++ 中的 std::set 和 std::multiset

Question

在C++中，默认情况下，std::set和std::multiset都使用std::less<T>作为它们的比较器。有没有人可以解释一下为什么std::multiset允许重复元素，而std::set不允许呢？

- A Roy

Answer 1

两者都从现有内容的等效upper_bound开始，以找到新项的正确插入点。

然后，std::set检查是否找到了一个键等于新键的现有项，如果是，则返回并发出失败信号。 std::multiset只在该点插入新项（如果它没有在上一步返回，则std::set也会这样做）。

- Jerry Coffin

---

我认为std::set检查的是等效性而不是相等性，对吧？尤其是可以使用仅定义 operator<（严格弱排序）但未定义 operator== 的类型。 - vsoftco

这是否意味着upper_bound的返回值可以有效地用作insert的提示？ - Lingxi

@Lingxi 可能可以，但这并不会减少插入所需的比较总数，因为您需要支付“upper_bound”的代价。 - vsoftco

Answer 2

跟进Jerry的回答，注意std::set和std::multiset假定元素可通过operator<进行比较，满足严格弱序。特别地，元素不必在operator==下可比较。std::set仅允许非等价元素，而std::multiset除此之外还允许等价元素。这与相等/非相等稍有不同。当且仅当!(A < B) && !(B < A)时，两个元素A和B是等价的，而std::set::insert会检查这个条件，如果为真，则不插入该元素。

示例{{link2：在Ideone上实时运行}}

#include <iostream>
#include <set>

struct Foo
{
    int _x, _y, _z;
    Foo(int x, int y, int z): _x(x), _y(y), _z(z) {}
    bool operator<(const Foo& rhs) const // weak majorization
    {
        return (_x < rhs._x) && (_x + _y < rhs._x + rhs._y) &&
               (_x + _y + _z < rhs._x + rhs._y + rhs._z) ; 
    }
};

int main()
{
    std::set<Foo> setFoo;
    // try to insert 2 equivalent elements
    setFoo.insert(Foo{1, 2, 3}); 
    if(setFoo.insert(Foo{1, 2, 0}).second == false) // failed to insert
        std::cout << "Equivalent element already in the set!" << std::endl;
}

- vsoftco