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

I can't use remove_if to find an element in map, right? It gave an compile time error. Am I missing something? — aJ.
– aJ., Commented Apr 29, 2009 at 6:10
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>. — MSalters
– MSalters, Commented Apr 29, 2009 at 7:00
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 ;-) — Atul Kumar
– Atul Kumar, Commented Mar 21, 2015 at 0:01
I see C++20 has std::erase_if for std::map ... if only I could transport my code into the future. — wcochran
– wcochran, Commented Jul 25, 2021 at 13:30

warchantua · Accepted Answer · 2020-01-02 19:50:08Z

143

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.

edited Jan 2, 2020 at 19:50

warchantua

1,2611 gold badge11 silver badges28 bronze badges

answered Apr 29, 2009 at 5:20

Steve Folly

8,70610 gold badges56 silver badges68 bronze badges

Sign up to request clarification or add additional context in comments.

17 Comments

taxilian Over a year ago

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.

Potatoswatter Over a year ago

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

Jamin Grey Over a year ago

@taxilian (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.

Sanchises Over a year ago

@taxilian 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.

Potatoswatter Over a year ago

@athos 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.

|

Danvil · Accepted Answer · 2018-12-13 04:44:11Z

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

@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.

MartinBG · Accepted Answer · 2021-11-04 14:59:07Z

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

Floern · Accepted Answer · 2017-04-07 15:43:01Z

10

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

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

edited Apr 7, 2017 at 15:43

Floern

34k24 gold badges106 silver badges122 bronze badges

answered Apr 7, 2017 at 15:41

user1633272

2,3437 gold badges30 silver badges64 bronze badges

1 Comment

L. F. Over a year ago

It's now in C++20

Mandrake Root · Accepted Answer · 2019-11-06 13:23:58Z

5

Here is some elegant solution.

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

answered Nov 6, 2019 at 13:23

Mandrake Root

591 silver badge2 bronze badges

1 Comment

Matthew M. Over a year ago

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.

1800 INFORMATION · Accepted Answer · 2009-04-29 05:22:03Z

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

This is no different to the original code. iter++ increments the iterator then returns an iterator pointing at the element before the increment.
But iter will not be invalidated since we then erase at the position of here
@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.
It works for array or vector, but will cause unexpected result in stl map.

Kate Gregory · Accepted Answer · 2013-01-16 18:41:50Z

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.

L. F. · Accepted Answer · 2019-07-08 11:45:50Z

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.

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

piotr · Accepted Answer · 2009-04-29 08:59:08Z

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.

Vincent · Accepted Answer · 2009-08-25 13:54:35Z

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.

Tadeusz Kopec for Ukraine · Accepted Answer · 2011-08-10 09:33:17Z

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.

Alexis Wilke · Accepted Answer · 2016-11-04 23:24:44Z

1

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

edited Nov 4, 2016 at 23:24

Alexis Wilke

21.2k11 gold badges111 silver badges183 bronze badges

answered May 19, 2009 at 9:28

user109134

4541 gold badge6 silver badges15 bronze badges

1 Comment

allyourcode Over a year ago

That's really unfortunate.

Community · Accepted Answer · 2017-05-23 12:32:19Z

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

voltento · Accepted Answer · 2018-11-27 08:13:51Z

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

Collectives™ on Stack Overflow

remove_if equivalent for std::map

14 Answers 14

17 Comments

erase_if for std::map (and other containers)

2 Comments

Comments

1 Comment

1 Comment

4 Comments

Comments

1 Comment

Comments

Comments

Comments

1 Comment

1 Comment

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

14 Answers 14

17 Comments

erase_if for std::map (and other containers)

2 Comments

Comments

1 Comment

1 Comment

4 Comments

Comments

1 Comment

Comments

Comments

Comments

1 Comment

1 Comment

Comments

Linked

Related