3

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.

TemplateRex
  • 69,038
  • 19
  • 164
  • 304
George Hilliard
  • 15,402
  • 9
  • 58
  • 96

3 Answers3

5

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.

Oswald
  • 31,254
  • 3
  • 43
  • 68
  • 1
    That's not really saying anything. The **only** way to compare two iterators is by testing whether both point to the same element. That says nothing about how expensive (or how cheap) it is to perform this comparison – jalf Oct 14 '13 at 07:21
  • @jalf Yet it says that in practice some O(n) comparison or comparison of the pointee is extremely unlikely (which I think were the scenarios the OP was after). – Christian Rau Oct 14 '13 at 09:12
  • @ChristianRau No, *this* answer says nothing about any of that. It just says that the cost of comparing two C++ iterators is the cost of testing whether they are equal (which is obvious and not helpful), and it **could** be as simple as comparing two pointers. – jalf Oct 14 '13 at 09:59
  • @jalf Yet if it *"could"*, why *shouldn't* it, you cannot expect a more precise answer anyway, as the first sentence says (yet I see in another answer you can at least expect O(1) from the standard). – Christian Rau Oct 14 '13 at 10:54
  • @ChristianRau: Yes, I *can* expect a more precise answer. I could, for example, expect what *you* said, that it must be a constant-time operation. Or I could expect an answer which specifies that the *value* of the object is not considered, so the element type (or the size of each element) is irrelevant. I could expect some actual *information*, rather than a verbose "huh, who knows" – jalf Oct 14 '13 at 11:38
  • I hope it's more precise now. – Oswald Oct 14 '13 at 12:07
  • @jalf Hmm, true indeed. – Christian Rau Oct 14 '13 at 12:50
  • @Oswald Though your last sentence doesn't make so much sense. The length of the key doesn't matter anyway in complexity considerations. The comparison of the keys (or values for that matter) is the part where it is a *"probably not"*, the constant complexity and thus the dependence on the map size is the *"cannot"* part. – Christian Rau Oct 14 '13 at 12:52
  • I really like the quote and clear explanation in @TemplateRex's answer. I think this answer has become right after editing though! – George Hilliard Oct 14 '13 at 15:22
  • @ChristianRau Iterators do not need to iterate over a container with a finite number of elements. This means, the constant time complexity requirement cannot be resticted to refer solely to the number elements in that container. Rather, the constant time complexity requirement is meant with respect to all iterators of the same type. – Oswald Oct 15 '13 at 08:00
4

Most of STL containers operator==() is just raw pointer comparison. Which is meaningless unless it's for boundaries checking. More over, if you are comparing iterators from different containers - it's undefined behaviour.

If you override this operator or use external comparison function, perfomance depends on how large are object you are comparing.

Probably I got your question wrong, it's not 100% clear what do you mean by "iterator comparison" and what's your use case.

Wintermute
  • 1,501
  • 17
  • 22
4

The draft Standard states that iterator operations are amortized constant time

24.2.1 In general [iterator.requirements.general]

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

If you look at the signatures of iterator operations, there are no parameters or return types that correspond to the underlying elements T themselves, only T* and T& are required. Even operator== does not have to directly compare two arbitrarily large elements T themselves.

However, this does not give a hard real-time upper-bound for iterator operations. In particular, iterators can do very costly bounds checking, but these Debug mode security guards can usually be left out in Release builds.

Community
  • 1
  • 1
TemplateRex
  • 69,038
  • 19
  • 164
  • 304