c++ - 计算多集

Question

我使用 C++ STL 已有一段时间，但从未真正开始使用多重集(或多重映射)。我有一个基于计算具有相同键的元素数量的问题。例如。这是一个 unordered_multiset {0, 2, 5, 1, 1, 2, 7, 5}

如果我说，count(5)，它应该返回 2。有两种方法可以使用 unordered_multiset 的 C++11 标准来实现。1) count2) equal_range然后减去生成的迭代器。

1) 据说在出现次数上花费线性时间，但 2) 是常数时间。这是为什么？

Answer 1

首先，您自己提供的链接中记录了 equal_range 的复杂性:

Average case: constant.
Worst case: linear in container size.

其次，“减去结果迭代器”的逻辑操作必须使用复杂度为O(bucket_size(bucket(key)))的线性迭代来实现，步进通过哈希冲突值的列表或 vector 检查匹配项，所以...

"2) equal_range and then subtracting the resulting iterator"..."is constant time"

...不是一个有充分根据的断言。

至于“1) 计数”，它的复杂性同样被记录在案——在这种情况下:

Average case: linear in the number of elements counted.
Worst case: linear in container size.

这又可能不同于您的“发生次数的线性时间”。 平均值 的原因是，通常 max_load_factor 的默认值为 1.0 和良好的散列函数，只会发生随机散射的碰撞 - 大约 10 -20% 标记，因此大多数时间唯一散列到特定存储桶的键将是您正在计算的那些 - 平均值是 1.1 倍左右的常数倍或 1.2 倍 - 因此是线性的。