using remove_if for a map container

Question

I was trying to use remove_if template for a map container but I am getting compiler error for the template argument. I am unable to understand why.

int main()
{
  map<const int, int> intmap;

  intmap[1] = 1;
  intmap[2] = 2;
  intmap[3] = 3;
  intmap[4] = 4;

  auto isOdd = [&](pair<const int, int> it)->bool 
     { return static_cast<bool>(it.second % 2); };

  isOdd(*(intmap.begin()));

 remove_if(intmap.begin(), intmap.end(), isOdd); 
}

This remove_if is throwing compiler errors. Any suggestion to fix it?

Error message is

C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\INCLUDE\utility(260) : error C2166: l-value specifies const object
        C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\INCLUDE\utility(259) : while compiling class template member function 
        'std::pair<_Ty1,_Ty2> &std::pair<_Ty1,_Ty2>::operator =(std::pair<_Ty1,_Ty2> &&)'
        with
        [
            _Ty1=const int,
            _Ty2=int
        ]
        maperaseif.cpp(29) : see reference to class template instantiation 'std::pair<_Ty1,_Ty2>' being compiled
        with
        [
            _Ty1=const int,
            _Ty2=int
        ]

related: http://stackoverflow.com/questions/800955/remove-if-equivalent-for-stdmap — dragosht, Mar 12 '15 at 07:37
`remove_if` ends up reordering the elements in the range. `map` enforces a particular order. Hence the 2 are not compatible. The details is just messing about with types and `const`. — BoBTFish, Mar 12 '15 at 07:38

score 5 · Accepted Answer · edited May 23 '17 at 11:33

remove_if works by scanning the elements and once an element is to be removed, it remembers the "gap" that will leave (keeping an iterator pointing thereto) while advancing another iterator to find the next element to retain... it then starts copying or moving elements from the latter position to the former until it reaches end().

That doesn't work for map, because you can't overwrite the pair<key,value> elements wholesale: the key values aren't allowed to be modified or the sorted-order invariant the implementation needs could be invalidated.

So, you'll need to abandon remove_if. You could use a normal loop, being careful to save the iterator-to-next-element rather than attempting to advance from a just-erased iterator. Lots of other questions about how to erase elements from a map while iterating, e.g. here....

score 2 · Answer 2 · answered Mar 12 '15 at 07:39

2

This little erase_if templated function should do what you want. (I didn't write it, just picked it up from somewhere - so credit to whoever did!)

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

In your example, you would use it like this:

erase_if(intmap, isOdd);

answered Mar 12 '15 at 07:39

Jonathan Potter

36,172
4
64
79

I tried even that namespace generic { template 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 ; } }; } generic::erase_if, [&](pair it){} > (intmap, isOdd); But this too fails to compile complaining about PredicateT should be a type. – Awanish Golwara Mar 12 '15 at 08:01
@AwanishGolwara `generic::erase_if, [&](pair it){} > (intmap, isOdd); ` is ***wrong*** . For free functions you don't need to specify type. Just FYI, if you need to know the type of your lambda, you need `decltype(isOdd)`. So, if you want to specify type, it should be `erase_if, decltype(isOdd)>(intmap, isOdd);` – Jagannath Mar 12 '15 at 08:31

score 1 · Answer 3 · edited Dec 08 '17 at 12:08

1

You cannot use remove_if on map, since its value type is actually std::pair<const Key, Value>, but it you look at requirements of remove_if, you can see, that dereferenced iterator type should be MoveAssignable.

Just write loop, or use boost for example.

edited Dec 08 '17 at 12:08

Toby Speight

27,591
48
66
103

answered Mar 12 '15 at 07:34

ForEveR

55,233
2
119
133

I don't see the connection between the 2 halves of that statement. Note that his lamdba takes a `std::pair`. – BoBTFish Mar 12 '15 at 07:35
@BoBTFish look at requirements of std::remove_if. – ForEveR Mar 12 '15 at 07:36
I didn't mean to imply your original answer was wrong, just that it didn't really explain itself. – BoBTFish Mar 12 '15 at 07:36

using remove_if for a map container

3 Answers3