15

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.

Improve this question
1
  • 2
    remove_if accepts a pair of iterators, and returns an iterator. Where do you think it removes the elements from? Commented Mar 1, 2012 at 11:35

2 Answers 2

Reset to default
32

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.

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

2 Comments

Thank you for answer. So, there have any elegant way to remove item from std::map without ugly code : void removeFromMap(FooMap & m, int id) { for (auto it = m.begin(), end = m.end(); it != end; ++it) { if (it->second._id == id) { m.erase(it); break; } } }
@Reddy: Nope, no other way I'm aware of. Btw, if your IDs are non-unique, you'll only erase the first element in the map. If they are, then that loop is fine.
3

You could use find and erase for the map. It's not as convenient as remove_if, but it might be the best you've got.

int removeId = 6; auto foundIter = m.find(removeId); // if removeId is not found you will get an error when you try to erase m.end() if(foundIter != m.end()) { m.erase(foundIter); }
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.