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

问题描述

遍历 std::set/std::multiset/std::map/ 的时间复杂度是多少std::multimap?我相信它在集合/地图的大小上是线性的，但不太确定.语言标准里有规定吗?

What's the time complexity of iterating through a std::set/std::multiset/std::map/std::multimap? I believe that it is linear in the size of the set/map, but not so sure. Is it specified in the language standard?

推荐答案

在 草案 C++11 标准 N3337 答案可以在 § 24.2.1 第 8 段中找到:

In the draft C++11 standard N3337 the answer can be found in § 24.2.1 paragraph 8:

所有类别的迭代器只需要那些可在固定时间内实现给定类别(摊销).

All the categories of iterators require only those functions that are realizable for a given category in constant time (amortized).

由于对迭代器的每次操作都必须是常数时间，因此遍历n 个元素必须是O(n).

Since each operation on an iterator must be constant time, iterating through n elements must be O(n).

这篇关于迭代 std::set/std::map 的时间复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持跟版网！