std::unordered_set 迭代器遍历的复杂性

我最近玩了一个std::unordered_set http://en.cppreference.com/w/cpp/container/unordered_set。我怀疑我的 STL 版本会跟踪某些 FILO 数据结构（看起来像列表）中的非空存储桶。我想这样做是为了提供O(n)完整的时间穿越std::unordered_set (where n表示 a 中的元素数量unordered_set with m水桶和m远大于n）。这改进了对所有存储桶的简单遍历O(m) time.

我已经测试过，确实可以遍历大量且非常稀疏的数据unordered_sets (with begin - end）比简单地遍历所有桶要快得多。

Question：这个遍历运行时间有标准保证吗？或者这只是我特定标准库的一个功能？

这是我可以使用的测试代码：

#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遍历以桶变为非空的相反顺序报告桶（参见第一行和第三行）。插入已经非空的桶中不会改变这个顺序（参见第二行和第四行）。

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

解释

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

根据标准（第 24.2.1 §8 节）：

所有类别的迭代器仅需要那些可在恒定时间（摊销）内为给定类别实现的函数。因此，迭代器的需求表没有复杂性列。

因此，当迭代 a 的项目时std::unordered_set，时间复杂度为O(n) (with n集合中的项目数量）。

不相信？

从字面上看上面的引用只能保证恒定时间操作可实现的。这并不能阻止特定实现的时间复杂度比实际实现更差可实现的。这可能是由于用词不当造成的，希望没有认真的实现真正做到这一点。

标准中唯一可以帮助解决这种歧义的地方是第 24.4.4 §1 节，其中标准对此进行了说明std::advance http://en.cppreference.com/w/cpp/iterator/advance and std::distance http://en.cppreference.com/w/cpp/iterator/distance :

这些函数模板使用+ and -对于随机访问迭代器（因此，它们的时间是恒定的）；对于输入、前向和双向迭代器，他们使用++提供线性时间 实施。

So, the ++对前向迭代器的操作（如用于std::unordered_set http://en.cppreference.com/w/cpp/container/unordered_set) 隐含为常数时间操作。

总之，虽然第一句话的措辞含糊不清，但第二句话证实了意图。