CODEWITHSUNDEEP
c++iteratordeterministic
Micha Wiedenmann
Micha Wiedenmann

Reputation: 20863

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

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

Upvotes: 1

Views: 568

Answers (2)

Kerrek SB
Kerrek SB

Reputation: 477454

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

Upvotes: 3

Robᵩ
Robᵩ

Reputation: 168776

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

Upvotes: 1

Related Questions