Remove_If Equivalent For Std::Map

remove_if equivalent for std::map

Almost.

for(; iter != endIter; ) {
     if (Some Condition) {
          iter = aMap.erase(iter);
     } else {
          ++iter;
     }
}

What you had originally would increment the iterator twice if you did erase an element from it; you could potentially skip over elements that needed to be erased.

This is a common algorithm I've seen used and documented in many places.

[EDIT] You are correct that iterators are invalidated after an erase, but only iterators referencing the element that is erased, other iterators are still valid. Hence using iter++ in the erase() call.

using remove_if for a map container

remove_if works by scanning the elements and once an element is to be removed, it remembers the "gap" that will leave (keeping an iterator pointing thereto) while advancing another iterator to find the next element to retain... it then starts copying or moving elements from the latter position to the former until it reaches end().

That doesn't work for map, because you can't overwrite the pair<key,value> elements wholesale: the key values aren't allowed to be modified or the sorted-order invariant the implementation needs could be invalidated.

So, you'll need to abandon remove_if. You could use a normal loop, being careful to save the iterator-to-next-element rather than attempting to advance from a just-erased iterator. Lots of other questions about how to erase elements from a map while iterating, e.g. here....

map, lambda, remove_if

The problem is that std::map<K,V>::value_type is std::pair<const K, V>, aka .first is const and not assignable. Lambdas have nothing to do with the problem here.

std::remove_if "removes" items by moving the elements of the container around, so that everything that does not fit the predicate is at the front, before the returned iterator. Everything after that iterator is unspecified. It does that with simple assignment, and since you can't assign to a const variable, you get that error.^†

The name remove can be a bit misleading and in this case, you really want erase_if, but alas, that doesn't exist. You'll have to make do with iterating over all items and erasing them by hand with map.erase(iterator):

for(auto it = map.begin(), ite = map.end(); it != ite;)
{
  if(it->second._id == remove_id)
    it = map.erase(it);
  else
    ++it;
}

This is safe because you can erase individual nodes in the tree without the other iterators getting invalidated. Note that I did not increment the iterator in the for loop header itself, since that would skip an element in the case where you erase a node.

---

† By now, you should have noticed that this would wreak havoc in the std::map's ordering, which is the reason why the key is const - so you can't influence the ordering in any way after an item has been inserted.

Erase specific elements in std::map

Write it like this for map, since remove_if won't work for map iterators (it merely puts offending elements at the end, and map iterators don't allow for this):

template <typename Map, typename F>
void map_erase_if(Map& m, F pred)
{
    typename Map::iterator i = m.begin();
    while ((i = std::find_if(i, m.end(), pred)) != m.end())
        m.erase(i++);
}

or if you like one-liners:

template <typename Map, typename F>
void map_erase_if(Map& m, F pred)
{
    for (typename Map::iterator i = m.begin();
         (i = std::find_if(i, m.end(), pred)) != m.end();
         m.erase(i++));
}

Remove elements from map with keys not containing in another vector

My first instinct is to erase chunks of non-real objects in bulk:

// Assuming real_objets is sorted (otherwise sort it)

auto first = some_container.begin();

for(int i : real_objects) {
  // end of the chunk to erase is the place where i could be
  // inserted without breaking the order
  auto last = some_container.lower_bound(i);

  some_container.erase(first, last);

  // if i is a key in the container, skip that element
  if(last != some_container.end() && last->first == i) {
    ++last;
  }

  first = last;
}

// and in the end, kill stuff that comes after real_objects.back()
some_container.erase(first, some_container.end());

This has runtime complexity O(n * log(m)), where n is real_objects.size() and m is some_container.size(), meaning it performs best if some_container is much larger than real_objects. Otherwise, since it is possible to iterate through a std::map in linear time, you could walk through both in lock-step and remove discrepancies in order:

// again, sort real_objects.
if(!some_container.empty()) { // else there's nothing to do
  auto ir  = real_objects.begin();
  auto ire = std::lower_bound(real_objects.begin(),
                              real_objects.end  (),
                              some_container.rbegin()->first);
  auto is  = some_container.begin();

  for(;;) {
    // find the next place where the real_objects and the keys of some_container don't match
    auto p = std::mismatch(ir, ire, is, [](int i, std::pair<int, int> const &p) { return i == p.first; });

    if(p.first  == real_objects  .end() ||
       p.second == some_container.end())
    {
      // upon reaching the end, remove all that comes after the
      // end of real_objects (if anything)
      some_container.erase(p.second, some_container.end());
      break;
    } else if(*p.first < p.second->first) {
      // if there's something in real_objects that's not in
      // some_container, skip it
      ++p.first;
    } else {
      // otherwise there's something in some_container that's
      // not in real_objects, so delete it.
      p.second = some_container.erase(p.second);
    }

    ir = p.first;
    is = p.second;
  }
}

This has runtime complexity O(max(n, m)), so it should perform well if some_container and real_objects almost match.

remove elements from `map` that are not in `set`

I'd start with this simple approach:

for (auto it = myMap.begin(); it != myMap.end(); )
{
    if (mySet.find(it->first) == mySet.end()) { myMap.erase(it++); }
    else                                      { ++it;              }
}

If you want something more efficient, you could iterate both containers in lockstep and do key-wise comparisons to take advantage of the compatible element order. On the other hand, the present algorithm works even on unordered containers, and given that your keys are strings, unordered containers may have a better performance anyway.

Finding and erasing a value from a std::vector holding std::map elements

You can also go a little bit functional: Playground

#include <algorithm>
#include <functional>

// removes maps from x1, that are equal to none of x2 maps 
auto remove_start = std::remove_if(x1.begin(), x1.end(), [&](const auto& x1_map){ 
  return std::none_of(x2.begin(), x2.end(), 
    std::bind(std::equal_to(), x1_map, std::placeholders::_1)); 
});
x1.erase(remove_start, x1.end());

EDIT: To check keys only, change std::equal_to to a custom lambda

auto keys_equal = [](auto& m1, auto& m2){ 
  return m1.size() == m2.size() 
    && std::equal(m1.begin(), m1.end(), m2.begin(), 
      [](auto& kv1, auto& kv2){ return kv1.first == kv2.first; });
};

// removes maps from x1, that are equal to none of x2 maps 
auto remove_start = 
  std::remove_if(x1.begin(), x1.end(), [&](const auto& x1_map){ 
    return std::none_of(x2.begin(), x2.end(), 
      std::bind(keys_equal, x1_map, std::placeholders::_1)); 
  });
x1.erase(remove_start, x1.end());

Erase/Remove contents from the map (or any other STL container) while iterating it

bool IsOdd( int i )
{
    return (i&1)!=0;
}

int a[] = {1,2,3,4,5};
vector<int> v( a, a + 5 );
v.erase( remove_if( v.begin(), v.end(), bind1st( equal_to<int>(), 4 ) ), v.end() );
// v contains {1,2,3,5}
v.erase( remove_if( v.begin(), v.end(), IsOdd ), v.end() );
// v contains {2}

---

Related Topics