What is the most effective way to get the index of

Question

I'm iterating over a vector and need the index the iterator is currently pointing at. AFAIK this can be done in two ways:

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

What are the pros and cons of these methods?

Answer 1

As UncleBens and Naveen have shown, there are good reasons for both. Which one is "better" depends on what behavior you want: Do you want to guarantee constant-time behavior, or do you want it to fall back to linear time when necessary?

it - vec.begin() takes constant time, but the operator - is only defined on random access iterators, so the code won't compile at all with list iterators, for example.

std::distance(vec.begin(), it) works for all iterator types, but will only be a constant-time operation if used on random access iterators.

Neither one is "better". Use the one that does what you need.

Answer 2

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;.

Answer 3

I would prefer std::distance(vec.begin(), it) as it will allow me to change the container without any code changes. For example, if you decide to use std::list instead of std::vector which doesn't provide a random access iterator your code will still compile. Since std::distance picks up the optimal method depending on iterator traits you'll not have any performance degradation either.

Answer 4

According to http://www.cplusplus.com/reference/std/iterator/distance/, since vec.begin() is a random access iterator, the distance method uses the - operator.

So the answer is, from a performance point of view, it is the same, but maybe using distance() is easier to understand if anybody would have to read and understand your code.

Answer 5

I like this one: it - vec.begin(), because to me it clearly says "distance from beginning". With iterators we're used to thinking in terms of arithmetic, so the - sign is the clearest indicator here.

Answer 6

If you are already restricted/hardcoded your algorithm to using a std::vector::iterator and std::vector::iterator only, it doesn't really matter which method you will end up using. Your algorithm is already concretized beyond the point where choosing one of the other can make any difference. They both do exactly the same thing. It is just a matter of personal preference. I would personally use explicit subtraction.

If, on the other hand, you want to retain a higher degree of generality in your algorithm, namely, to allow the possibility that some day in the future it might be applied to some other iterator type, then the best method depends on your intent. It depends on how restrictive you want to be with regard to the iterator type that can be used here.

• If you use the explicit subtraction, your algorithm will be restricted to a rather narrow class of iterators: random-access iterators. (This is what you get now from std::vector)

• If you use distance, your algorithm will support a much wider class of iterators: input iterators.

Of course, calculating distance for non-random-access iterators is in general case an inefficient operation (while, again, for random-access ones it is as efficient as subtraction). It is up to you to decide whether your algorithm makes sense for non-random-access iterators, efficiency-wise. It the resultant loss in efficiency is devastating to the point of making your algorithm completely useless, then you should better stick to subtraction, thus prohibiting the inefficient uses and forcing the user to seek alternative solutions for other iterator types. If the efficiency with non-random-access iterators is still in usable range, then you should use distance and document the fact that the algorithm works better with random-access iterators.