Search Algorithms

Finding the Last Occurrence of an Element in a Container

How do I search for the last occurrence of an element using std::ranges::find() or std::find()?

Abstract art representing computer programming

To find the last occurrence of an element in a container using std::ranges::find() or std::find(), you can use the std::ranges::find_end() algorithm.

This algorithm searches for the last occurrence of a subsequence in a range, which can be adapted to find a single element.

Using std::ranges::find_end()

Here's how you can use std::ranges::find_end() to find the last occurrence of an element:

#include <algorithm>
#include <iostream>
#include <ranges>
#include <vector>

int main() {
  std::vector<int> numbers{1, 2, 3, 4, 2, 5, 2};

  int target = 2;
  auto result = std::ranges::find_end(
    numbers, std::views::single(target));

  if (result.begin() != numbers.end()) {
    std::cout << "Last occurrence of "
      << target << " found at position "
      << std::distance(
        numbers.begin(), result.begin());
  } else {
    std::cout << target << " not found";
  }
}
Last occurrence of 2 found at position 6

Explanation

  • std::ranges::find_end() is used to find the last occurrence of a subsequence in a range.
  • In this case, the subsequence is a single element, represented by a pointer to the target and one past the target.

Alternative: Using Reverse Iterators

Another way to find the last occurrence is to use reverse iterators with std::find():

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

int main() {
  std::vector<int> numbers{1, 2, 3, 4, 2, 5, 2};

  int target = 2;
  auto rresult = std::find(
    numbers.rbegin(), numbers.rend(), target);

  if (rresult != numbers.rend()) {
    auto position = std::distance(
      numbers.begin(), rresult.base()) - 1;
    std::cout << "Last occurrence of "
      << target << " found at position "
      << position;
  } else {
    std::cout << target << " not found";
  }
}
Last occurrence of 2 found at position 6

Explanation

  • std::find() is used with reverse iterators (rbegin() and rend()) to search the container from the end to the beginning.
  • The position is calculated by converting the reverse iterator back to a normal iterator and adjusting the index.

Using either std::ranges::find_end() or reverse iterators with std::find(), you can efficiently find the last occurrence of an element in a container.

Answers to questions are automatically generated and may not have been reviewed.

A computer programmer
Part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, unlimited access

This course includes:

  • 124 Lessons
  • 550+ Code Samples
  • 96% Positive Reviews
  • Regularly Updated
  • Help and FAQ
Free, Unlimited Access

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved