How to erase from a multimap while reverse iterating

luca 0
Viewed 31

How can I erase elements from a std::multimap while reverse iterating over it?

Erasing elements while forward iterating is straightforward, but the reverse iteration seems to require a little more thinking: the return value of multimap::erase is a forward iterator and cannot be directly assigned to the reverse iterator used in the loop.

c++
1 Answers

This works with other containers as well, not only multimap:

std::multimap<T1, T2> mmap = {...};

for (auto it = mmap.rbegin(); it != mmap.rend();) {
  if ( ...condition...) {
    it = decltype(it)(mmap.erase(std::next(it).base()));
  } else {
    it++;
  }
}

Example code:

#include <iostream>
#include <map>
#include <set>

void print(std::multimap<char, int> mmap) {
  std::cout << "mmap contains:\n";
  std::set<char> chars;
  for (auto kv : mmap)
    chars.insert(kv.first);

  for (char ch : chars) {
    auto ret = mmap.equal_range(ch);
    std::cout << ch << " =>";
    for (std::multimap<char, int>::iterator it = ret.first; it != ret.second;
         ++it)
      std::cout << ' ' << it->second;
    std::cout << '\n';
  }
}

int main() {
  std::multimap<char, int> mmap = {
      {'a', 10}, {'a', 20}, {'b', 30}, {'b', 40}, {'b', 50},
      {'c', 60}, {'c', 70}, {'d', 80}, {'d', 90},
  };
  print(mmap);

  for (auto it = mmap.rbegin(); it != mmap.rend();) {
    if (it->second == 70 || it->first == 'b') {
      it = decltype(it)(mmap.erase(std::next(it).base()));
      // more verbose alternative
      // it = std::reverse_iterator<decltype(mmap.begin())>(mmap.erase(std::next(it).base()));
    } else {
      it++;
    }
  }

  print(mmap);

  for (auto it = mmap.rbegin(); it != mmap.rend();) {
    it = decltype(it)(mmap.erase(std::next(it).base()));
    // more verbose alternative
    // it = std::reverse_iterator<decltype(mmap.begin())>(mmap.erase(std::next(it).base()));
  }

  print(mmap);

  return 0;
}

Example output:

mmap contains:
a => 10 20
b => 30 40 50
c => 60 70
d => 80 90
mmap contains:
a => 10 20
c => 60
d => 80 90
mmap contains:
luca0
Related