Are incrementing/decrementing iterators of standard library container iterators deterministic?

Question

Are there upper bounds on the time it can take to increment/decrement an iterator of a standard library collection (e.g. std::map)? (Assuming the container itself is not changed.)

Answer 1

No, there is no upper bound on the time it can take to increment/decrement an iterator. The standard is silent on how long any program takes to run. As far as I know, all of the popular compilers are also silent on the subject.

Having said that, however, the typical implementations do nothing that would take significant time. There are no memory allocations or file-IO (other than VM page-ins, I suppose.)

Answer 2

The increment operation for a std::map iterator is guaranteed to have amortized constant cost. That is, full traversal of n elements is O(n). This is in fact true for all iterators (see 24.2.1/8):

All the categories of iterators require only those functions that are realizable for a given category in constant time (amortized).