unt311's blog

time complexity of subtraction of iterators
By unt311, history, 3 years ago, In English

I couldn't find relevant answers to this online.

If I do int pos = iterator1 - iterator2

would this be an O(n) or a O(1) operation.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

$$$O(1)$$$

→ Reply
»
3 years ago, # |
  Vote: I like it +23 Vote: I do not like it

To specify, I assume this is C++. For a RandomAccessIterator (for e.g. a vector) this is indeed $$$O(1)$$$. If it's a weaker form of iterator, e.g. a BidirectionalIterator from a set, then first of all it won't compile, you will need int pos=distance(it1, it2) and also it will be $$$O(it_2-it_1)=O(N)$$$.

If you are more innterested, you can have a look at the specifications of iterators here. I think the two iterator types I named are the most common ones in CP (just my feeling).

→ Reply