19

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());
TemplateRex
  • 69,038
  • 19
  • 164
  • 304
Neil Kirk
  • 21,327
  • 9
  • 53
  • 91
  • See also http://stackoverflow.com/questions/2037867/can-i-convert-a-reverse-iterator-to-a-forward-iterator – pzed Jul 28 '14 at 15:00

3 Answers3

17

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.

TemplateRex
  • 69,038
  • 19
  • 164
  • 304
  • My idx is unsigned. When value isn't found, distance returns -1 and overflows to big number. But I can compare this to >= size to see if it wasn't found. Is this safe? – Neil Kirk Jul 28 '14 at 15:06
  • @NeilKirk, Yeah, you'll have to deal with that separately. Using `std::prev` on `.rend().base()` is undefined behaviour AFAIK. – chris Jul 28 '14 at 15:11
  • http://stackoverflow.com/questions/24998519/how-to-convert-reverse-iterator-into-forward-iterator-when-it-is-rend – Neil Kirk Jul 28 '14 at 15:19
5

You could use:

container.size() - 1 - (iterator - container.rbegin())

or

container.size() - 1 - std::distance(container.rbegin(), iterator)

More info about reverse iterators. How To Use Reverse Iterators Without Getting Confused. To convert reverse iterators into forward iterators and much more.

NetVipeC
  • 4,402
  • 1
  • 17
  • 19
  • This works, but if value isn't found it gives an overflowing value. That's fine for me to test it was found, but it is safe? – Neil Kirk Jul 28 '14 at 15:04
  • The problem is when container.size() == 0, when the value is not found would give you the index that would have .end(), i think it's pretty similar to iterators end(), the index would be == .size(). – NetVipeC Jul 28 '14 at 15:05
4

I would change TemplateRex's answer to use only reverse iterators, thus avoiding any headache with reverse-forward conversions.

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(rit, v.rend()) - 1;
        std::cout << idx;
    } else
        std::cout << "not found!";
}

The -1 is still needed because the first element of the vector (index 0) is actually at v.rend() - 1.

Fire Yoshi
  • 91
  • 5