1

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

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

1）据说在出现次数上需要线性时间，但 2）是恒定时间。这是为什么？

4

3 回答 3

3

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

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

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

"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 倍的常数倍数 - 因此是线性的。

于 2014-09-26T08:09:04.183 回答
2

问题是 equal_range 返回“前向迭代器”（这在您提供的链接中提到），与随机访问迭代器相比，它只定义了增量操作。因此，要计算两者之间的差异，我们必须增加第一个，直到它等于第二个 - 这给出了线性计数时间。

例如，在 gcc 标准库中，count 就是以这种方式实现的：

count(const _Key& __k) const
{
  pair<const_iterator, const_iterator> __p = equal_range(__k);
  const size_type __n = std::distance(__p.first, __p.second);
  return __n;
}
于 2014-09-26T08:12:53.660 回答
1

1)计数

复杂性：大小成对数，匹配数成线性

例如：mymultiset.count(73)

对数大小：首先找到元素，与二分查找相同

匹配数量线性：由于找到元素，它将线性流动以知道匹配数量，因为我们知道集合是排序的

2）等范围

复杂性：大小为对数

" 函数返回一个pair，其成员pair::first 为范围的下限（与lower_bound 相同），pair::second 为上限（与upper_bound 相同）。"

检查最小复杂度以获得上限/下限你会发现它（大小为对数）你也可以检查该链接：http ://www.cplusplus.com/reference/set/multiset/equal_range/

于 2017-08-22T04:50:56.460 回答