通过std :: set / std :: map迭代的时间复杂度是多少? [英] What's the time complexity of iterating through a std::set/std::map?
问题描述
通过 std :: set
/ std :: map
迭代的时间复杂度是多少?我相信它是集合/地图的大小是线性的,但不是那么确定。是否在语言标准中指定?
What's the time complexity of iterating through a std::set
/std::map
? 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迭代的时间复杂度是多少?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!