what is the complexity of iterating an unordered_map

Question

What is the complexity of iterating through an unordered_map implemented using hashing with chaining? Specifically does this involve traversing all the buckets, in which case complexity is O(Buckets + NElements) vs. ideal, e.g. O(NElements)

Answer 1

What is the complexity of iterating through an unordered_map?

O(N) where N is the number of elements stored. The most relevant part of the Standard:

All the categories of iterators require only those functions that are realizable for a given category in constant time (amortized). Therefore, requirement tables for the iterators do not have a complexity column.

You can see more about that - and discussion - in e.g. this answer

..implemented using hashing with chaining?

All unordered maps use hashing with chaining - see here.

Specifically does this involve traversing all the buckets, in which case complexity is O(Buckets + NElements) vs. ideal, e.g. O(NElements)

It does what you're calling "ideal". In the case of GCC, buckets hold iterators into a singly linked list, and it's that usually-shorter list is traversed when iterating over the container. Usually because even without changing the default max_load_factor() of 1.0 it's possible for the number of buckets to exactly equal the number of elements - any more elements than that will then trigger a resize. But, big-O efficiency of iteration becomes more important when almost all the elements have been deleted, as the number of buckets won't be automatically resized downwards (i.e. reduced).