remove_if equivalent for std::map

Question

I was trying to erase a range of elements from map based on particular condition. How do I do it using STL algorithms?

Initially I thought of using remove_if but it is not possible as remove_if does not work for associative container.

Is there any "remove_if" equivalent algorithm which works for map ?

As a simple option, I thought of looping through the map and erase. But is looping through the map and erasing a safe option?(as iterators get invalid after erase)

I used following example:

bool predicate(const std::pair<int,std::string>& x)
{
    return x.first > 2;
}

int main(void) 
{

    std::map<int, std::string> aMap;

    aMap[2] = "two";
    aMap[3] = "three";
    aMap[4] = "four";
    aMap[5] = "five";
    aMap[6] = "six";

//      does not work, an error
//  std::remove_if(aMap.begin(), aMap.end(), predicate);

    std::map<int, std::string>::iterator iter = aMap.begin();
    std::map<int, std::string>::iterator endIter = aMap.end();

    for(; iter != endIter; ++iter)
    {
            if(Some Condition)
            {
                            // is it safe ?
                aMap.erase(iter++);
            }
    }

    return 0;
}

Answer 1

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.

Answer 2

erase_if for std::map (and other containers)

I use the following template for this very thing.

namespace stuff {
  template< typename ContainerT, typename PredicateT >
  void erase_if( ContainerT& items, const PredicateT& predicate ) {
    for( auto it = items.begin(); it != items.end(); ) {
      if( predicate(*it) ) it = items.erase(it);
      else ++it;
    }
  }
}

This won't return anything, but it will remove the items from the std::map.

Usage example:

// 'container' could be a std::map
// 'item_type' is what you might store in your container
using stuff::erase_if;
erase_if(container, []( item_type& item ) {
  return /* insert appropriate test */;
});

Second example (allows you to pass in a test value):

// 'test_value' is value that you might inject into your predicate.
// 'property' is just used to provide a stand-in test
using stuff::erase_if;
int test_value = 4;  // or use whatever appropriate type and value
erase_if(container, [&test_value]( item_type& item ) {
  return item.property < test_value;  // or whatever appropriate test
});

Answer 3

Now, std::experimental::erase_if is available in header <experimental/map>.

See: http://en.cppreference.com/w/cpp/experimental/map/erase_if

Answer 4

Here is some elegant solution.

for (auto it = map.begin(); it != map.end();)
{   
    (SomeCondition) ? map.erase(it++) : (++it);
}

Answer 5

For those on C++20 there are built-in std::erase_if functions for map and unordered_map:

std::unordered_map<int, char> data {{1, 'a'},{2, 'b'},{3, 'c'},{4, 'd'},
                                    {5, 'e'},{4, 'f'},{5, 'g'},{5, 'g'}};
 
const auto count = std::erase_if(data, [](const auto& item) {
    auto const& [key, value] = item;
    return (key & 1) == 1;
});

Answer 6

I got this documentation from the excellent SGI STL reference:

Map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements. Erasing an element from a map also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.

So, the iterator you have which is pointing at the element to be erased will of course be invalidated. Do something like this:

if (some condition)
{
  iterator here=iter++;
  aMap.erase(here)
}

Answer 7

The original code has only one issue:

for(; iter != endIter; ++iter)
{
    if(Some Condition)
    {
        // is it safe ?
        aMap.erase(iter++);
    }
}

Here the iter is incremented once in the for loop and another time in erase, which will probably end up in some infinite loop.

Answer 8

First

Map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements. Erasing an element from a map also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.

Second, the following code is good

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

When calling a function, the parameters are evaluated before the call to that function.

So when iter++ is evaluated before the call to erase, the ++ operator of the iterator will return the current item and will point to the next item after the call.

Answer 9

Based on Iron Savior's answer For those that would like to provide a range more along the lines of std functional taking iterators.

template< typename ContainerT, class FwdIt, class Pr >
void erase_if(ContainerT& items, FwdIt it, FwdIt Last, Pr Pred) {
    for (; it != Last; ) {
        if (Pred(*it)) it = items.erase(it);
        else ++it;
    }
}

Curious if there is some way to lose the ContainerT items and get that from the iterator.

Answer 10

If you want to erase all elements with key greater than 2, then the best way is

map.erase(map.upper_bound(2), map.end());

Works only for ranges though, not for any predicate.

Answer 11

From the bottom notes of:

http://www.sgi.com/tech/stl/PairAssociativeContainer.html

a Pair Associative Container cannot provide mutable iterators (as defined in the Trivial Iterator requirements), because the value type of a mutable iterator must be Assignable, and pair is not Assignable. However, a Pair Associative Container can provide iterators that are not completely constant: iterators such that the expression (*i).second = d is valid.

Answer 12

IMHO there is no remove_if() equivalent.
You can't reorder a map.
So remove_if() can not put your pairs of interest at the end on which you can call erase().

Answer 13

I use like this

 std::map<int, std::string> users;    
 for(auto it = users.begin(); it <= users.end()) {
    if(<condition>){
      it = users.erase(it);
    } else {
    ++it;
    }
 }

Answer 14

Steve Folly's answer I feel the more efficient.

Here is another easy-but-less efficient solution:

The solution uses remove_copy_if to copy the values we want into a new container, then swaps the contents of the original container with those of the new one:

std::map<int, std::string> aMap;

...
//Temporary map to hold the unremoved elements
std::map<int, std::string> aTempMap;

//copy unremoved values from aMap to aTempMap
std::remove_copy_if(aMap.begin(), aMap.end(), 
                    inserter(aTempMap, aTempMap.end()),
                    predicate);

//Swap the contents of aMap and aTempMap
aMap.swap(aTempMap);