C++ – Benefits of std::distance Over Subtracting Iterators

c++iteratorstdstdvector

I'm iterating over a vector and need the index the iterator is currently pointing at. What are the pros and cons of the following methods?

it - vec.begin()
std::distance(vec.begin(), it)

Best Answer

I would prefer it - vec.begin() precisely for the opposite reason given by Naveen: so it wouldn't compile if you change the vector into a list. If you do this during every iteration, you could easily end up turning an O(n) algorithm into an O(n^2) algorithm.

Another option, if you don't jump around in the container during iteration, would be to keep the index as a second loop counter.

Note: it is a common name for a container iterator,std::container_type::iterator it;.

Related Solutions

C++ – Get Iterator from Index in STL Vectors

Try this:

vector<Type>::iterator nth = v.begin() + index;

C++ – Get Index in Vector from Reverse Iterator

I would use:

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    auto v = std::vector<int> { 1, 2, 3 };
    auto rit = std::find(v.rbegin(), v.rend(), 3);
    if (rit != v.rend()) {
        auto idx = std::distance(begin(v), rit.base()) - 1;
        std::cout << idx;
    } else
        std::cout << "not found!";
}

Live Example.

The reason for the -1 in the distance computation is because of the conversion between reverse and regular iterators in the .base() member:

24.5.1 Reverse iterators [reverse.iterators]

1 Class template reverse_iterator is an iterator adaptor that iterates from the end of the sequence defined by its underlying iterator to the beginning of that sequence. The fundamental relation between a reverse iterator and its corresponding iterator i is established by the identity: &*(reverse_iterator(i)) == &*(i - 1).

Note: you could also use the above code without the check for v.rend(), and use the convention that idx == -1 is equivalent to an element that is not found. However, that loses the ability to do v[idx], so eventually you would need a check against that as well.

Best Answer

Related Solutions

C++ – Get Iterator from Index in STL Vectors

C++ – Get Index in Vector from Reverse Iterator

Related Question