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;
}

Muslin

What do you mean that remove_if does not work? – Propane

I can't use remove_if to find an element in map, right? It gave an compile time error. Am I missing something? – Muslin

Nope - it doesn't work as remove_if works by reordering a sequence, moving elements that fail the condition towards the end. Hence it does work on a T[n], but not a map<T,U>. – Kaitlynkaitlynn

With C+11, you can use for(auto iter=aMap.begin(); iter!=aMap.end(); ){ ....} to reduce clutter. Rest is as others said. This question saved me some hair splitting just now ;-) – Naturalize

I see C++20 has std::erase_if for std::map ... if only I could transport my code into the future. – Bhutan

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.

Exchequer

Yes, I've seen this algorithm on the newsgroups and have used it in production code. We kitted it up in a utility function in our toolbox. – Mccowan

I'm confused; why would you use for(; ... ;) instead of while(...)? Also, while this probably works, doesn't .erase return an iterator of the next one? So it seems like the if (Some Condition) blog should be iter = aMap.erase(iter) to be the most compatible. Perhaps I'm missing something? I lack the experience some of you have. – Katharynkathe

@Taxilian: The return type of .erase() depends on the kind of container you're calling it on. The map::erase(iterator) method returns void. – Coppage

Note, in C++11 all associative containers, including map, return the next iterator from erase(iter). It's much cleaner to do iter = erase( iter ). – Saintebeuve

@Katharynkathe (years late) while() or for() would work, but semantically, people often use for() for iterating over a known range, and while() for an unknown number of loops. Since the range is known in this case (from the beginning, to endIter), for() wouldn't be an unusual choice, and would probably be more common. But again, both would be acceptable. – Rola

@Katharynkathe More importantly: with 'for', you can have your iterator definition INSIDE the scope of the loop, so it doesn't mess with the rest of your program. – Adagio

@sanchises I do understand that about for, of course; my confusion was that in this case the definition isn't inside the scope of the loop. I think this has been adequately explained, however. – Katharynkathe

@Saintebeuve It is not also cleaner but faster and more memory efficient, since the post increment operator makes a copy which can be expensive in case of custom iterators. This is also the reason why you should always use for(auto it = items.begin(); it != items.end(); ++it) instead of for(auto it = items.begin(); it != items.end(); it++) – Hellespont

@Saintebeuve are you saying use for(; iter != endIter; ) { if (Some Condition) { iter = aMap.erase(iter); } else { ++iter; } } instead of for(; iter != endIter; ) { if (Some Condition) { aMap.erase(iter++); } else { ++iter; } } ? – Glamorize

@Glamorize [Edit: Yes, that's the advice of my previous comment.] This Q&A from 2009 is outdated. Please refer to something newer. – Saintebeuve

@Saintebeuve i don't get it.. do you mean in C++ 11 it's recommended to write for(; iter != endIter; ) { if (Some Condition) { iter = aMap.erase(iter); } else { ++iter; } } ? – Glamorize

@Glamorize If I were writing it now, I suppose I'd do while ( iter != endIter ) { auto oldIter = iter ++; if (Some Condition) { aMap.erase( oldIter ); } }. – Saintebeuve

@Saintebeuve i'm lost. what's the benefit of doing so? and what's the reason this is more preferrable? – Glamorize

@Glamorize The question is phrased in the passive voice, "it's recommended." There's no universal recommendation. I think my last comment is the most straightforward way. It does involve two copies of the iterator variable, which loses a little efficiency as someone pointed out here. It's your call what's appropriate for you. – Saintebeuve

This solution is kind of confusing since stl doesn't support function erase returning next iterator. – Robinette

Out-of-date for modern C++ (e.g. 20) – Interrogative

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
});

Squashy

@CodeAngry Thanks--it always seemed weird to me that this didn't already exist in std. I understand why it isn't a member of std::map, but I think something like it should be in the standard library. – Squashy

Will be added in C++20 for std::map and others. – Endicott

Answer 3

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

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

Folkestone

It's now in C++20 – Analgesia

Answer 4

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;
});

Societal

Answer 5

Here is some elegant solution.

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

Golf

This relies on it++ fully evaluating before map.erase(...) is called (which, of course, it does) and it relies on map.erase(...) not invalidating any iterators other than what is erased. All of this is true. I just think it's worth spelling out in case someone unknowingly carries this pattern over to another container. – Fisch

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)
}

Nekton

This is no different to the original code. iter++ increments the iterator then returns an iterator pointing at the element before the increment. – Exchequer

But iter will not be invalidated since we then erase at the position of here – Nekton

@1800INFORMATION: entering a function call is a sequence point, the increment side effect is evaluated before erase is called. So they are indeed equivalent. Still, I'd strongly prefer your version over the original. – Ranit

It works for array or vector, but will cause unexpected result in stl map. – Robinette

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.

Saenz

Answer 8

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.

Pelerine

Answer 9

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().

Stakhanovism

That's really unfortunate. – Iddo

Answer 10

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.

Fidge

Answer 11

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.

Unvalued

Answer 12

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.

Helwig

"Identifiers starting with an underscore followed by an upper case letter are reserved for all usage by the implementation." – Winou

Answer 13

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);

Muslin

That seems inefficient. – Iddo

Answer 14

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;
    }
 }

Unhair