erasing from vector after remove_if, with reverse iterators: rbegin(), rend()

Question

Consider the following vector:

std::vector<int> arr = {20, 37, 11, 20, 15}

I need to remove the duplicate, that is encounter more than n times (in this example n=1) The resulting vector should look like:

{20, 37, 11, 15}

i.e. the succeeding elements should be deleted, but not the preceding ones.

I had an idea of using rbegin() and rend() iterators in std::remove_if function to start removing elements from the end, but then I am not sure how to approach the erasing of elements from the vector after remove_if is done. I belienve the "left over garbage" is accumulated in the beginning:

auto new_end = std::remove_if(arr.rbegin(), arr.rend(), [&n, &arr](const int a) {
    return std::count(arr.begin(), arr.end(), a) > n;
});
//how to erase garbage?

Answer 1

The functor passed to std::remove_if can have a memory.

Code using a functor

struct remove_duplicates {
  std::map<int, int> seen_values_;
  bool operator()(int x) {
    seen_values_[x]++;
    return seen_values_[x] > 1;
  }
};

int main() {
  std::vector<int> arr = {20, 37, 11, 20, 15};
  arr.erase(
    std::remove_if(arr.begin(), arr.end(), remove_duplicates()),
    arr.end());

  for (int x : arr)
    std::cout << x << " ";
  std::cout << std::endl;
}

Code using a lambda

int main() {
  std::vector<int> arr = {20, 37, 11, 20, 15};
  std::map<int, int> seen_values;
  arr.erase(
    std::remove_if(
      arr.begin(), arr.end(), [&seen_values](int x) {
        seen_values[x]++;
        return seen_values[x] > 1;
      }),
    arr.end());

  for (int x : arr)
    std::cout << x << " ";
  std::cout << std::endl;
}

Output is the same for both

20 37 11 15

A note about std::remove_if

The "left over garbage" actually is at the end. std::remove_if returns an iterator to the first position to start deleting from.