CODEWITHSUNDEEP
c++stldictionary
aJ.
aJ.

Reputation: 35450

remove_if equivalent for std::map

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

Upvotes: 150

Views: 87072

Answers (14)

MartinBG
MartinBG

Reputation: 1648

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

Upvotes: 12

Steve Folly
Steve Folly

Reputation: 8607

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.

Upvotes: 141

Mandrake Root
Mandrake Root

Reputation: 59

Here is some elegant solution.

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

Upvotes: 5

Greg Domjan
Greg Domjan

Reputation: 14095

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.

Upvotes: 2

Iron Savior
Iron Savior

Reputation: 4368

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

Upvotes: 90

voltento
voltento

Reputation: 877

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

Upvotes: 0

user1633272
user1633272

Reputation: 2309

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

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

Upvotes: 10

user109134
user109134

Reputation: 454

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

Upvotes: 1

partha biswas
partha biswas

Reputation: 242

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.

Upvotes: 2

Tadeusz Kopec for Ukraine
Tadeusz Kopec for Ukraine

Reputation: 12403

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.

Upvotes: 1

Vincent
Vincent

Reputation: 2722

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.

Upvotes: 1

aJ.
aJ.

Reputation: 35450

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

Upvotes: 0

piotr
piotr

Reputation: 5787

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.

Upvotes: 1

1800 INFORMATION
1800 INFORMATION

Reputation: 135265

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

Upvotes: 3

Related Questions