remove_if equivalent for std::map

user_64960 0
Viewed 73003

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;
}
map stl c++
14 Answers

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.

Steve_Folly_486590

Here is some elegant solution.

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

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

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

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.

user_727840

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

user_1091340

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

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