What's the time complexity of iterating through a std::set/std::map?
23,787
Solution 1
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).
Since each operation on an iterator must be constant time, iterating through n
elements must be O(n)
.
Solution 2
I believe that it is linear in the size of the set/map, but not so sure.
That is correct. Iterating through an entire set or map is O(N)
Author by
updogliu
Updated on September 21, 2020Comments
-
updogliu over 3 years
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?