c++ - std::unordered_set迭代器遍历的复杂度

Question

我最近玩弄了一个 std::unordered_set .我怀疑我的 STL 版本会跟踪某些 FILO 数据结构(看起来像列表)中的非空桶。我想这样做是为了提供完整 std::unordered_set 的 O(n) 时间遍历(其中 n 表示unordered_set 中的元素具有 m 个桶且 m 比 n 大得多)。这改进了在 O(m) 时间内对所有桶的简单遍历。

我已经测试过，确实遍历大型且非常稀疏的 unordered_set(使用 begin - end)比 naive 快得多遍历所有桶。

问题:这个遍历运行时间有标准保证吗？或者这只是我的特定标准库的一个特性？

---

这是我的测试代码:

#include <iostream>
#include <vector>
#include <numeric>
#include <unordered_set>
using namespace std;

void test(vector<int> data, int alloc_size) {
   unordered_set<int> set(alloc_size);
   for (auto i: data) {
      set.insert(i);
   }

   for (size_t bidx = 0; bidx < set.bucket_count(); ++bidx) {
      cout << "[B" << bidx << ":";
      for (auto bit = set.begin(bidx); bit != set.end(bidx); ++bit) {
         cout << " " << *bit;
      }
      cout << "] ";
   }

   cout << "  {";
   for (auto const & d: set) {
      cout << d << " ";
   }
   cout << "}" << endl;
}

int main() {
   test({1, 2, 0}, 3);
   test({1, 2, 0, 7}, 3);
   test({18, 6, 11, 3, 13, 4}, 20);
   test({18, 6, 11, 3, 13, 4, 34}, 20);
}

打印:

[B0: 0] [B1: 1] [B2: 2] [B3:] [B4:]   {0 2 1 }
[B0: 0] [B1: 1] [B2: 7 2] [B3:] [B4:]   {0 7 2 1 }
[B0:] [B1:] [B2:] [B3: 3] [B4: 4] [B5:] [B6: 6] [B7:] [B8:] [B9:] [B10:] [B11: 11] [B12:] [B13: 13] [B14:] [B15:] [B16:] [B17:] [B18: 18] [B19:] [B20:] [B21:] [B22:]   {4 13 3 11 6 18 }
[B0:] [B1:] [B2:] [B3: 3] [B4: 4] [B5:] [B6: 6] [B7:] [B8:] [B9:] [B10:] [B11: 34 11] [B12:] [B13: 13] [B14:] [B15:] [B16:] [B17:] [B18: 18] [B19:] [B20:] [B21:] [B22:]   {4 13 3 34 11 6 18 }

看起来 begin - end 遍历报告桶以相反的顺序变为非空(参见第一行和第三行)。插入一个已经非空的桶不会改变这个顺序(参见第二和第四行)。

Answer 1

简而言之:是的，这是由标准保证的。

解释

所有的迭代器都需要有一个O(n)的遍历时间复杂度(其中n是遍历的项的数量)。这是因为迭代器上的每个操作都具有恒定的时间复杂度 (O(1))，包括将迭代器前进一个位置。

来自标准(第 24.2.1 §8 节):

All the categories of iterators require only those functions that are realizable for a given category in constant time (amortized). Therefore, requirement tables for the iterators do not have a complexity column.

因此，当遍历 std::unordered_set 的项目时，时间复杂度为 O(n)(n集合中的项目数量)。

不相信？

从字面上看上面的引述只能保证常量时间操作是可实现的。这不会阻止特定实现具有比可实现 更差的时间复杂度。这可能是因为用词不当，希望没有认真的实现真正做到这一点。

标准中唯一可以帮助解决这种歧义的其他地方是在第 24.4.4 §1 节中，标准中有关于 std::advance 的内容。和 std::distance :

These function templates use + and - for random access iterators (and are, therefore, constant time for them); for input, forward and bidirectional iterators they use ++ to provide linear time implementations.

因此，前向迭代器上的 ++ 操作(用于 std::unordered_set )隐含为常数时间操作。

总而言之，虽然第一个引用的措辞含糊不清，但第二个引用证实了意图。