迭代std :: set/std :: map的时间复杂度是多少？

迭代通过std::set/std::map的时间复杂度是多少？我相信它在集合/地图的大小上是线性的，但不太确定。它在语言标准中有规定吗？迭代std :: set/std :: map的时间复杂度是多少？

来源

2012-08-02 updogliu

整个容器的迭代将始终是'O（n）'_at least_（我认为真正愚蠢的实现可能会使它变得更糟糕） – Chad 2012-08-02 14:43:39

当你说“遍历”时，你究竟是什么意思？你在使用标准迭代器编写一个while/for循环吗？你在使用其中一种标准算法吗？ – 2012-08-02 14:51:14

在draft C++11 standard N3337的答案可以在§找到24.2.1段8：

所有迭代器的类别只需要那些变现为一个功能按固定时间给定类别（摊销）。

由于上一个迭代每个操作必须是恒定的时间，通过n元件迭代必须O(n)。

来源

2012-08-02 14:55:45

如果使用父指针将映射/集合实现为二叉树，则遍历所有元素将至多访问每个树节点3次。如果实现是一个带有父指针的b树，则每个节点最多访问2 * n + 1次，n是节点中元素的数量。在这两种情况下，这意味着每个迭代步骤的恒定平均时间复杂度。我不知道有任何其他符合实现地图/设置的方法。 – WaltK 2017-04-08 14:21:38

我相信它在集合/地图的大小上是线性的，但是肯定不是那么的。

这是正确的。通过整个集合或地图迭代是O(N)

来源

2012-08-02 14:41:37

迭代std :: set/std :: map的时间复杂度是多少？

回答

相关问题