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.

Matt · Accepted Answer · 2021-11-03 18:20:39Z

9

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.

edited Nov 3, 2021 at 18:20

Matt

20.8k1 gold badge61 silver badges76 bronze badges

answered Mar 7, 2017 at 2:25

Daniel Eisener

3331 silver badge4 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

shadow_map Over a year ago

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

Kerrek SB · Accepted Answer · 2017-03-07 02:17:00Z

7

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";
}

answered Mar 7, 2017 at 2:17

Kerrek SB

480k96 gold badges904 silver badges1.1k bronze badges

Comments

Vlad from Moscow · Accepted Answer · 2017-03-07 02:25:30Z

4

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

}

answered Mar 7, 2017 at 2:25

Vlad from Moscow

313k27 gold badges204 silver badges358 bronze badges

Collectives™ on Stack Overflow

Using std::find() With Reverse Iterators

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related