1

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

与仅保留计数相比，此实施可以带来什么好处的场景是什么？multiset如果内部实现发生变化，是否存在代码中断的用例？或者是否有任何操作如果更改会增加复杂性？

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

4

2 回答 2

5

默认情况下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 访问的成员。

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

于 2021-07-14T06:51:27.440 回答
3

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

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

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

您的多重集需要拥有这些对象

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

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

您希望您的多重设置高效

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

于 2021-07-14T06:52:13.153 回答