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

Question

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

与仅保持计数相比，此实现在哪些情况下有益？multiset如果内部实现发生变化，是否有任何用例会导致代码中断？或者是否有任何操作如果更改会增加复杂性？

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

Answer 1

默认情况下std::multiset用于operator<决定两个元素是否相等（注意：equiavent 不相等！）。现在考虑这个元素类型：

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 访问的成员。

排序容器通常检查等价性而不是相等性的原因是它们需要一种方法来比较元素（它们已排序）。能够比较两个元素 via<就足以检查等价性，而==额外的要求会使容器不那么通用而没有明显的增益。如果您愿意，您始终可以使用这样的比较器，即等价确实意味着相等（在上面的示例中：也比较yin operator<）。

正如评论中已经提到的，如果你想拥有你描述的行为，你可以使用 a std::map<foo,size_t>（也operator<用作键的默认比较器）。foo您可以存储一对foo和计数，而不是仅存储s 。现在，因为两个foo相同的 sx被认为是等价的，它们确实映射到相同的键：

 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。