c++ - 为什么 multiset 保留重复元素的单独实例而不是它们的数量？

Question

我最近发现 multiset<T> STL 中的实现实际上在树中保留相同重复元素的不同拷贝。 我之前的期望是它在内部使用 map<T, int>并只保留重复元素的计数。

与仅保持计数相比，这种实现在什么情况下可以带来好处？ multiset 有任何用例吗？如果内部实现发生变化，代码会在哪里中断？或者有没有什么操作如果改变了会增加复杂度？

我想知道该选择背后的思考过程是什么？

Answer 1

默认 std::multiset使用 operator<决定两个元素是否等价(注意:等价不等价!)。现在考虑这种元素类型:

struct foo { 
    int x;
    int y;
    bool operator<(const foo& other) { return x < other.x; }
    bool operator==(const foo& other) { return (x==other.x) && (y==other.y);
};

当 !(a < b) && !(b < a) 时，两个元素被认为是等价的，这通常并不意味着 a == b .因此，仅存储计数是不够的。

此外，即使相等也不意味着身份( a==b 并不意味着 &a==&b )。由于容器拥有它的元素，容器中的两个元素不可能相同，它们总是两个不同的对象。另外，在上面foo我们可以添加一个成员 z这既不考虑operator<也不是 operator==但可以通过 getter 访问。

---

排序容器通常检查等价性而不是相等性的原因是它们无论如何都需要一种方法来比较元素(它们是排序的)。能够通过 < 比较两个元素足以检查等效性，同时需要 ==此外会使容器不那么通用而没有明显的好处。如果你愿意，你总是可以使用一个比较器，它使得等价性确实意味着相等(在上面的例子中:在 y 中也比较 operator<)。

---

正如评论中已经提到的，如果你想要你描述的行为，你可以使用 std::map<foo,size_t> (也使用 operator< 作为键的默认比较器)。而不是只存储 foo您可以存储一对 foo和伯爵。现在，因为两个 foo与x相同被认为是等价的，它们确实映射到相同的键:

 foo f,g;
 f.x = 42; f.y = 0;
 g.x = 42; g.y = 100;
 std::map<foo,size_t> counter;
 ++counter[f];
 ++counter[g];

因此，counter将包含 1 个元素:f 的拷贝该键的计数将为 2 .