Performance cost of comparing two C++ iterators

Question

In general, what is the performance cost of an equality comparison between two STL container iterators? I'm only talking about defined operations; that is, comparing two iterators referring to the same object.

My specific use-case is that I have a std::map that could potentially have very large elements, lots of elements, or both. If an equality comparison between two iterators over such a map have hidden penalties that I'm not aware of, it could impact the performance of my code.

Answer 1

Generally, the performance of comparing two iterators depends on the implementation of the STL.

However, concerning the time complexity, the C++ standard imposes the restriction that comparison of input iterators (and thus forward iterators, bidirectional iterators and random access iterators) takes amortized constant time. Particularly, this means for an std::map<std::string, int>, that its iterators cannot be compared by comparing the keys for equality, because that would be linear with respect to the length of the key.