Блог пользователя unt311

Автор unt311, история, 3 года назад, По-английски

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
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

$$$O(1)$$$

»
3 года назад, # |
  Проголосовать: нравится +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).