What's the Time Complexity of Iterating Through a Std::Set/Std::Map

What's the time complexity of iterating through a std::set/std::map?

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

iterator++ complexity for stl map

The amortized complexity when incrementing the iterator over the whole container is O(1) per increment, which is all that's required by the standard. You're right that a single increment is only O(log n), since the depth of the tree has that complexity class.

It seems likely to me that other RB-tree implementations of map will be similar. As you've said, the worst-case complexity for operator++ could be improved, but the cost isn't trivial.

It quite possible that the total time to iterate the whole container would be improved by the linked list, but it's not certain since bigger node structures tend to result in more cache misses.

What is the time complexity of std::map

Lookups are proportional to log(N). In a typical case (implementation as a red-black tree) the number of comparisons can be up to twice Log₂N.

Insertions are normally proportional to Log₂N as well--but there's a special provision made for when you're inserting a number of items that are already in order¹. In this case, you can specify a "hint" for where an insertion is going to take place. When that hint is correct, each insertion is (amortized) O(1) instead of O(Log N), so inserting a range of items in sorted order is linear instead of N log(N). The hint you specify is an iterator to the position just after the item to be inserted.

For example, if you have a number of items in a file in sorted order, and you want to insert them into the map, you can specify your_map.end() as the "hint", and building the map will have O(N) complexity instead of O(N Log N) complexity.

---

_{1. Technically, this applies anytime you insert items, not just when you're inserting them in order--but by far the most common case where you have a reasonable "hint" available is when you're inserting items in order.}

Computational time complexity of std::map::merge

I would expect that std::map::merge takes advantage of the fact that
the elements of both std::maps are already sorted, so there is no need
to search the place of insertion for every single element [...]

You are missing the fact that the map to be merged may be of a different type, ie it might use a different sorting:

template <class C2>
void merge(std::map<Key, T, C2, Allocator>& source); 
                            ^--- this is not necessarily the same as for the map you 
                                 are merging into

So actually the map to be merged has to be considered not sorted to get the worst case complexity.

Time complexity of find() in std::map?

Log(n) It is based on a red black tree.

Edit: n is of course the number of members in the map.

What's the complexity of map/set :: insert if one has provided a correct iterator hint?

The standard doesn't say how the containers are to be implemented, so
you can't count on an RB or a AVL tree. In practice... the complexity
constraints are such that I don't know of any other implementations
which would fit the bill. But it's in the complexity constraints that
you will find the answer: “logarithmic in general, but amortized
constant if t is inserted right before p.” So if the hint is
correct, the implementation must be such that the insertion is O(1).

---

Related Topics