unt311's blog

time complexity of subtraction of iterators
By unt311, history, 5 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

Comments Comments (3)
| Write comment?
»
5 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

$$$O(1)$$$

→ Reply
»
5 years ago, hide # |
 
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
»
23 months ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

for the case of set and map it's $$$O(N)$$$ but there is a work around.

using the __gnu_pbds library

you can create an ordered_map or ordered_set and take advantage of .order_of_key() to find the difference in $$$log(n)$$$ .

→ Reply