Erasing Elements from a Map: A Mini-Pattern
It's a reality of programming in C++ that all containers are not created equal, and do not receive equal protection under the algorithms. Or something.
Today at work, for example, I needed to scan a std::map,
and erase elements from it for which some predicate was true. The
typical way to remove an element from a map is to use the map's erase
method. There is an erase method that takes a range (a start and end
iterator), but no way to perform the erase based on the result of a
predicate. That is, there's no map::erase_if.
For sequence containers, there exists an algorithm,
std::remove_if(start, end, pred), but it operates by
reordering the elements of the range it's operating on, by assigning an
element from one position to another with operator=.
Because the first element of the pair that comprises a map::value_type,
the key, is const, it can't be assigned to.
typedef std::map<T,U> Map;
typedef Map::value_type Value;
extern bool predicate(const Value &v);
Map m;
// Wrong: compile error.
std::remove_if(m.begin(), m.end(), std::ptr_fun(predicate));
The next obvious thing to try is an explicit loop, with an explicit branch based on the predicate. The naïve implementation, though, will have problems.
for(Map::iterator i = m.begin(); i != m.end(); i++) {
if(predicate(*i))
m.erase(i); // ONOZ!
}
ONOZ!
because after the call to m.erase(i),
i is no longer valid: it refers to memory that has been
released. I suspect the increment clause of the for-statement puts us in
nasal
demon territory, but I'm not sure what the standard says.
To be honest, I knew the above constructs were wrong, but I didn't know if there was an idiom to get the behavior I wanted. After some research and some experimenting, the following is the construct I decided to use.
for(Map::iterator i = m.begin(); i != m.end(); /* increment in body */ ) {
Map::iterator current = i++;
if(predicate(*current))
m.erase(current);
}
Comments: 2