增加/减少标准库集合（例如 std::map）的迭代器所需的时间是否有上限？（假设容器本身没有改变。）
问问题
555 次
2 回答
3
std::map保证迭代器的增量操作具有摊销的常数成本。也就是说，n个元素的完全遍历是O( n )。这实际上适用于所有迭代器（参见 24.2.1/8）：
迭代器的所有类别只需要在恒定时间内（摊销）对给定类别可实现的那些函数。
于 2012-11-14T16:22:40.147 回答
1
不，增加/减少迭代器所需的时间没有上限。该标准没有说明任何程序需要多长时间才能运行。据我所知，所有流行的编译器也都对这个问题保持沉默。
然而，话虽如此，典型的实现并没有做任何需要大量时间的事情。没有内存分配或文件 IO（我想除了 VM 页面输入。）
于 2012-11-14T16:18:14.040 回答