STL containers are too often used incorrectly and inefficiently. One area often falling in inefficient use is erasing certain elements from your STL containers. It is also first programmer instinct to write a handwritten loop to iterate over all elements and erase something. Now though that works, it is often suboptimal and more code than you really need. So then one might ask what is the best way to remove elements from various STL containers? Let's find that out in this quick guide. We will take various use cases and then divide them on container type basis. This guide is inspired by Scott Meyers’s famous advice (If you never heard that name then consider yourself a novice in C++!).
Use case – I – Remove specific element from the container
For sequence containers, to remove specific element, you should use the famous “Erase-Remove” technique. This technique is so popular now that this idiom got its wiki page now! This technique will work for vector, deque and string. E.g.,
SequenceContainer<int> c;
…
// Remove element 130
c.erase( remove( c.begin(), c.end(), 130 ), c.end() );
So what is happening here? The ‘remove’ is STL algorithm, which does not really remove the element but it reshuffles elements of the container such that removed element is moved to the end and new end is updated for the container. The ‘remove’ will also return the iterator to the removed element with its new position, and that along with old end will do the trick with ‘erase’ to really get rid of storage for it. Nice and clean right? It is not only less code, but also it is self-explanatory code when somebody is reading it. Such things do impact the maintenance of your code in the long run.
Okay, so you ask now what about the list and associative containers? For ‘std::list,’ you simply use ‘remove’ member function, and it does the same thing, but more efficiently.
std::list<int> myList;
…
myList.remove( 130 );
For associative containers, like a map, multimap, set and multiset, you would use just member function ‘erase.’ The ‘erase’ function will do the job very efficiently.
std::map<int> myMap;
…
myMap.erase( 130 );
Using these respective functions, or function combinations will make your code short, crisp, efficient and self-documenting.
Use case – II – Remove element matching specific constraint
Okay, so removing specific element is fine as we saw earlier, but what if we want to remove a range of elements matching certain condition? The “erase-remove-if” comes to rescue. Just change ‘remove’ with ‘remove-if’ in the erase-remove idiom, and we are still good. This below will work for vector, string, and deque.
bool badElement(int); // Predicate for the match
SequenceContainer<int> c;
…
// Remove elements which are returned as true by badElement
c.erase( remove_if( c.begin(), c.end(), badElement ), c.end() );
For std::list, we also have an equivalent ‘remove_if’ member function.
std::list<int> myList;
…
myList.remove_if( badElement );
For associative containers (like a map, set, multimap and multiset), there are two ways to do this. The first way is using ‘remove_copy_if’ code, which is less efficient but it is easier to understand and maintain
std::map<int> myMap;
…
std::map<int> goodvaluesMap; // Temporary map to hold “good entries”
remove_copy_if( myMap.begin(),
myMap.end(),
inserter( goodvaluesMap.begin(), goodvaluesMap.end() ),
badElement
);
myMap.swap( goodvaluesMap );
As you probably already noticed, it is not efficient due to the temporary copy of entries with a transient map, but it is code which is easy to read and understand. To make it the efficient version, unfortunately, we have to iterate through all elements of an associative container and then remove individually.
for( std::map<int>::iterator i = myMap.begin(); i != myMap.end(); )
{
// Notice the i++ use
if( badElement( *i ) ) myMap.erase( i++ );
else ++i;
}
Now there is nothing special about this loop except for the iterator increments part. The ‘erase’ member method for associative containers invalidates input iterator to it, so we have to make sure it is copied and incremented right before that invalidation. Above, post-increment form of use for ‘i’ just does that. We pass the value of ‘i’ to erase and then increment it. Erase only gets called after ‘i’ is incremented. If you don’t do this then behavior of using ‘i’ after erase returns is undefined (at best, it will crash your code).
Use case – III – Remove element and do additional processing
Okay, so far so good. But what is now you want to do some additional processing on the elements which are getting removed from the container, how do we do that? For the simplicity of the example, let's just assume that we want to log the element being erased from the container.
The erase-remove can’t help now as there’s no way to modify any of those functions to do additional functionality. Your gut feel may suggest writing logging functionality in the predicate (like ‘badElement’ from the previous example), but that’s a poor choice as predicates are supposed to be “pure functions.” This form of pure is not anything related to pure virtual functions. Pure predicates basically yield a result which is only influenced or changed by input to it, and it does not maintain any internal state. So for logging example case, unless we pass additional context to the predicate (like logger object, for our example), it is not possible to achieve the result and passing any such additional context will make it non-pure and so non-compliant with what C++ and STL standards demand. That is the reason we will not even consider that as an alternative.
For sequence containers, our hand-written loop for conditional removal from associative containers will do the trick. Of course, we have to do little change on how we handle iterators. Here’s an example (SequenceContainer below can be either of: list, vector, deque, string):
std::SequenceContainer<int> myContainer;
…
std::ostream logFile;
…
for( std::SequenceContainer<int>::iterator i = myContainer.begin(); i != myContainer.end(); )
{
if( badElement( *i ) )
{
logFile << “Erasing element ” << *i << std::endl;
// Notice return value copy
i = myContainer.erase( i );
}
else ++i;
}
Again, there is nothing special in the loop, except for the part where we copy the return value of ‘erase.’ All sequence containers invalidate iterator passed as input to ‘erase’ and any references to subsequent elements in the container. But they also return for the call to ‘erase’ with a valid iterator to the next element (to the one erased) with its new position. That’s exactly the reason we copy it above.
For associative containers, loop we wrote for conditional remove still remains valid when we want to do additional processing. So it would become something like below for our example:
std::ostream logFile;
…
for( std::map<int>::iterator i = myMap.begin(); i != myMap.end(); )
{
if( badElement( *i ) )
{
logFile << “Erasing element ” << *i << std::endl;
// Notice the i++ use as before
myMap.erase( i++ );
}
else ++i;
}
Summary
We saw three use cases for removal – specific element remove, the range of elements removal and removal with additional processing. In each case, we employ a different technique depending on the container type.
For specific element removal: we use “erase-remove” technique for sequence containers, use member ‘remove’ for std::list, and member erase for associative containers.
For a range of elements removal matching certain predicate: we use “erase-remove-if” technique for sequence containers, use member ‘remove_if’ for std::list, and hand-written loop (with post-increment form for iterator) for associative containers.
For removal with additional processing: we use a handwritten loop for all container types. The only difference between sequence container and associative ones is that we store iterator to the next element from the return value of member ‘erase’ for sequence containers, while we use post-increment form of iterator input for the member ‘erase’ in case of associative containers
Just keep this short summary in mind, and you will be all good whenever you need removal from any STL container type.
Comments