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

Question

我最近发现 multiset<T> STL 中的实现实际上保留了树中相同重复元素的不同副本。我之前的期望是它在内部使用 map<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 访问。

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

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

 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。

Answer 2

少数情况下这可能是一个问题：

你的比较器不区分不相等的对象。

假设我有一堆请求需要按优先级顺序填写。我可能会写一个比较器来比较请求的优先级。如果结果只是一个计算每个优先级有多少请求的结构，而无法访问实际请求，我会不高兴。

您的多重集需要拥有对象

如果多重集包含实际对象，而不是数字或指针，如果您插入一个与现有对象比较相等的新对象，会发生什么情况？我们应该销毁已经存在的对象吗？我们要添加的那个？将某些东西插入到集合中可能会立即破坏的预期结果，或者它可能会在未来某个时候因插入某些东西而破坏？

（公平地说，容器在重新分配时实际上会发生这种情况，但不会发生在可以移动的对象上。当然，有些对象可以移动但不能复制，例如对象拥有一个缓冲区。）

您希望您的多重集高效

比较器告诉我们一个对象是否小于另一个对象。为了确定两个对象是否相等，我们必须进行第二次比较，检查是否 a < b，然后检查 b < a。现有的实现避免了必须进行第二次检查。在许多情况下可能不会产生很大的性能差异，但如果您的数据涉及相同少数等价物的大量重复项类，这实际上会使您的代码速度降低 2 倍。

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

Why multiset keeps separate instances of repeated elements instead of their count?

c++

time-complexity

multiset

unordered-multiset