map, lambda, remove_if

Question

So, i've problem with std::map, lambda and stl algorithm(remove_if). Actually, same code with std::list or std::vector works well.

My test example :

#include <map>
#include <iostream>
#include <algorithm>

struct Foo
{
    Foo() : _id(0) {}
    Foo(int id) : _id(id)
    {

    }

    int _id;    
};
typedef std::map<int, Foo> FooMap;


int main()
{
    FooMap m;
    for (int i = 0; i < 10; ++i)
        m[i + 100] = Foo(i);

    int removeId = 6;
    // <<< Error here >>>
    std::remove_if(m.begin(), m.end(), [=](const FooMap::value_type & item) { return item.second._id == removeId ;} ); 

    for (auto & item : m )
        std::cout << item.first << " = " << item.second._id << "\n";    

    return 0;
}

Error message :

In file included from /usr/include/c++/4.6/utility:71:0,
                 from /usr/include/c++/4.6/algorithm:61,
                 from main.cxx:1:
/usr/include/c++/4.6/bits/stl_pair.h: In member function ‘std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(std::pair<_T1, _T2>&&) [with _T1 = const int, _T2 = Foo, std::pair<_T1, _T2> = std::pair<const int, Foo>]’:
/usr/include/c++/4.6/bits/stl_algo.h:1149:13:   instantiated from ‘_FIter std::remove_if(_FIter, _FIter, _Predicate) [with _FIter = std::_Rb_tree_iterator<std::pair<const int, Foo> >, _Predicate = main()::<lambda(const value_type&)>]’
main.cxx:33:114:   instantiated from here
/usr/include/c++/4.6/bits/stl_pair.h:156:2: error: assignment of read-only member ‘std::pair<const int, Foo>::first’

I don't understand what's wrong here. So, i gladly to read some advices/directions about it. My goal - use new lambda-style with std::map and algorithms, such as remove_if.

g++ 4.6, -std=c++0x.

Answer 1

The problem is that std::map<K,V>::value_type is std::pair<const K, V>, aka .first is const and not assignable. Lambdas have nothing to do with the problem here.

std::remove_if "removes" items by moving the elements of the container around, so that everything that does not fit the predicate is at the front, before the returned iterator. Everything after that iterator is unspecified. It does that with simple assignment, and since you can't assign to a const variable, you get that error.^†

The name remove can be a bit misleading and in this case, you really want erase_if, but alas, that doesn't exist. You'll have to make do with iterating over all items and erasing them by hand with map.erase(iterator):

for(auto it = map.begin(), ite = map.end(); it != ite;)
{
  if(it->second._id == remove_id)
    it = map.erase(it);
  else
    ++it;
}

This is safe because you can erase individual nodes in the tree without the other iterators getting invalidated. Note that I did not increment the iterator in the for loop header itself, since that would skip an element in the case where you erase a node.

---

† By now, you should have noticed that this would wreak havoc in the std::map's ordering, which is the reason why the key is const - so you can't influence the ordering in any way after an item has been inserted.