### unt311's blog

By unt311, history, 6 weeks ago,

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.

• +5

 » 6 weeks ago, # |   +2 $O(1)$
 » 6 weeks ago, # |   +23 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).