41

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?

plasmacel
  • 8,183
  • 7
  • 53
  • 101
updogliu
  • 6,066
  • 7
  • 37
  • 50
  • 2
    Iteration of an entire container will always be `O(n)` _at least_ (I suppose really silly implementations could make it _worse_) – Chad Aug 02 '12 at 14:43

2 Answers2

69

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).

Mark Ransom
  • 299,747
  • 42
  • 398
  • 622
  • 4
    If map/set are implemented as a binary tree with parent pointers, iteration through all elements will visit each tree node at most 3 times. If the implementation is a b-tree with parent pointers, each node will be visited at most 2*n + 1 times, n the number of elements in the node. In both cases, this implies constant average time complexity for each iteration step. I'm not aware of any other compliant ways to implement map/set. – WaltK Apr 08 '17 at 14:21
  • 7
    Actually, for `std::set`, `std::multiset`, `std::map`, `std::multimap` if they are implemented as a Red-Black tree (which is the most common case), the worst case complexity of finding the next/prev in-order element is `O(log N)`. Of course, in practice, the average case is amortized constant. – plasmacel Aug 23 '18 at 23:50
19

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)

Chris Dargis
  • 5,891
  • 4
  • 39
  • 63
  • 7
    Why do you emphasize *amortized*? It is `O(N)` exactly for all known implementations. The prove is quite simple. The containers `set` and `map` are implemented using red-black tree. Just draw a line between two nodes every time you move from one to another. After you finish iterating you will see that all lines are doubled and you visited every node exactly twice. – Igor Mikushkin Oct 02 '18 at 16:01
  • 2
    @Elliott That's correct. Finding the next highest element in a binary tree takes O(log N) time. – Igor Mikushkin Sep 27 '20 at 18:39
  • 1
    @IgorMikushkin. Because of your two comments, and thinking on it further, I can see that it's roughly `2n` time, so `O(n)`. I've also realised that my description of how you find the element was wrong. You've helped me - I always assumed it was `O(n*log(n))`. Thanks! – Elliott Sep 28 '20 at 05:05