c++vectoriteratorfindreverse-iterator

Get index in vector from reverse iterator


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());

Solution

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