Using std::find() With Reverse Iterators

Question

I'm having some trouble understanding how to use reverse iterators with the std::find() function. I believe that if I could see an example that completed the following task, I would be able to understand it perfectly.

So, suppose I have a std::vector I want to search through; however, I do not want to search the typical way. I want to find the first occurrence of a value starting at a certain index and heading towards the start of the vector. To illustrate:

    3 | 4 | 7| 4| 2| 6| 3|
    ^             ^
    |<------------| 
             start_point

Search: find first occurrence, given the above search layout, of 4

Expected Result: index 3

I'm rather sure that one would have to work with reverse iterators in this situation, but I can't figure out how to do it.

Solution 1

If you're using a std::vector, or any other container that provides Random Access Iterators, you can advance an iterator just using arithmetic, like you would with a pointer. Your example vector has 7 elements, and you want to start at index 4, so you could get a normal iterator to that element just with:

auto i = v.begin() + 4;

For a reverse iterator, you're starting from the back of the vector, not the front, so to get the right offset you have to subtract the desired index+1 from the size, like so:

auto i = v.rbegin() + (v.size() - 5);

This'll be, in your example, 2, so the reverse iterator will start pointing to the last element, then move two spaces toward the beginning, reaching your desired start point.

Then, you can use std::find in the normal way:

auto found = std::find(v.rbegin() + (v.size() - 5), v.rend(), 4);
if(found == v.rend()) {
    std::cout << "No element found." << std::endl;
} else {
    std::cout << "Index " << (v.rend() - found) << std::endl;
}

Remember that, when testing the result of std::find to see if it found anything, you need to use rend(), not end(). When you compare reverse iterators to normal iterators, you're comparing the actual positions, not the offsets from the start, so v.rend() != v.end().

If you don't have Random Access Iterators (for example, in a std::list) you can't use pointer-style arithmetic, so you can instead use std::advance to advance iterators to a specific position and std::distance to get the distance between two iterators.

Solution 2

First you set the start position:

auto it = v.rbegin() + 2;  // two from the end

Then search:

auto kt = std::find(it, v.rend(), 4);

If kt == v.rend(), no element is found; otherwise we can compute the index from the front with a simple distance computation:

if (kt == v.rend()) {
  std::cerr << "Element 4 not found.\n";
  std::abort();
} else {
  auto n = std::distance(kt, v.rend()) - 1;
  std::cout << "Element 4 found at position v[" << n << "].\n";
}

Solution 3

Try something like the following

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

int main()
{
    std::vector<int> v = { 3, 4, 7, 4, 2, 6, 3 };
    std::vector<int>::size_type pos = 4;

    auto it = std::find(std::next(v.rbegin(), v.size() - pos), v.rend(), 4);

    if (it != v.rend())
    {
        std::cout << std::distance(v.begin(), it.base() - 1) << std::endl;
    }

}

Comments

[shadow_map]

(v.rend() - found) returns an index that is one too large, e.g. in this case 4 instead of the expected index 3.