Get index in vector from reverse iterator

Neil Kirk picture Neil Kirk · Jul 28, 2014 · Viewed 9.3k times · Source

I know how to get the index from a vector iterator, by subtracting the begin iterator from it. For example:

vector<int>::iterator it = find(vec.begin(), vec.end(), x);
size_t position = it - vec.begin();

However, now I want to find the index of the last x in the vector. How can I get the real index from the reverse iterators? I've found the following that seems to work (edit: it doesn't) but maybe there is a better (more idiomatic or whatever..) way.

vector<int>::reverse_iterator it = find(vec.rbegin(), vec.rend(), x);
size_t position = vec.size() - (it - vec.rbegin());

Answer

TemplateRex picture TemplateRex · Jul 28, 2014

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.