How do I erase elements from STL containers?

Question

How do I erase elements from STL containers, having a specified value, or satisfying some condition?

Is there a single common or uniform way of doing that for different kinds of containers?

Solution

Unfortunately, there isn't a single uniform interface or pattern for erasing elements from STL containers. But three behaviors emerge:

std::vector Pattern

To erase elements that fulfill a certain condition from a std::vector, a common technique is the so called erase-remove idiom.

If v is an instance of std::vector, and we want to erase elements with value x from the vector, code like this can be used:

// Erase elements having value "x" from vector "v"
v.erase( std::remove(v.begin(), v.end(), x), v.end() );

If the criterion to be fulfilled for erasing elements is more complex than the simple "element to be erased == x", the std::remove_if() algorithm can be used instead of std::remove():

// Erase elements matching "erasing_condition" from vector "v"
v.erase( std::remove_if(v.begin(), v.end(), erasing_condition), v.end() );

where erasing_condition is a unary predicate, that can be expressed in several forms: e.g. it can be a bool-returning function taking vector element type as input (so if the returned value is true, the element will be erased from the vector; if it's false, it won't); or it can be expressed in-line as a lambda; it can be a functor; etc.

(Both std::remove() and std::remove_if() are generic algorithms from <algorithm> header.)

Here is a clear explanation from Wikipedia:

The algorithm library provides the remove and remove_if algorithms for this. Because these algorithms operate on a range of elements denoted by two forward iterators, they have no knowledge of the underlying container or collection. Thus, no elements are actually removed from the container. Rather, all elements which don't fit the remove criteria are brought together to the front of the range, in the same relative order. The remaining elements are left in a valid, but unspecified state. When this is done, remove returns an iterator pointing one past the last unremoved element.

To actually eliminate elements from the container, remove is combined with the container's erase member function, hence the name "erase-remove idiom".

Basically, std::remove() and std::remove_if() compact the elements that do not satisfy the erasing criteria to the front of the range (i.e. to the beginning of the vector), and then erase() actually eliminates the remaining elements from the container.

This pattern applies also to other containers like std::deque.

std::list Pattern

To erase elements from a std::list, simple remove() and remove_if() methods are available:

// Erase elements having value "x" from list "l"
l.remove( x )

// Erase elements satisfying "erasing_condition" from list "l"
l.remove_if( erasing_condition );

(Where erasing_condition is a unary predicate, with the same characteristics discussed for std::remove_if() in the above section.)

The same pattern can be applied to similar containers, like std::forward_list.

Associative Containers (e.g. std::map, std::set, ...) Pattern

Associative containers like std::map, std::set, std::unordered_map, etc. follow the common pattern described here:

1. If the erasing condition is a simple key-matching (i.e. "erase the element having key x"), then a simple erase() method can be called:

   // Erase element having key "k" from map "m":
   m.erase( k );
   

2. If the erasing condition is more complex, and is expressed by some custom unary predicate (e.g. "erase all odd elements"), then a for loop can be used (with an explicit erasing condition checking in loop body, and call to erase(iterator) method):

   //
   // Erase all elements from associative container "c", satisfying "erasing_condition":
   //
   for (auto it = c.begin(); it != c.end(); /* "it" updated inside loop body */ )
   {
       if ( erasing_condition(*it) )
       {   
           // Erase the element matching the specified condition 
           // from the associative container.
           it = c.erase(it);
   
           // Note:
           // erase() returns an iterator to the element 
           // that follows the last element removed, 
           // so we can continue the "for" loop iteration from that position.
       }
       else
       {
           // Current element does _not_ satisfy erasing condition,
           // so we can just move on to the next element.
           ++it;
       }       
   }     
   

The Need for a Unified Approach

As it can be noted from the above analysis, unfortunately there isn't a uniform common approach for erasing elements from STL containers.

The following table summarizes the aforementioned patterns:

----------------+------------------------------------------             
   Container    |            Erasing Pattern
----------------+------------------------------------------                
                |
 vector         |    Use erase-remove idiom.
 deque          |
                |
----------------+------------------------------------------               
                |
 list           |    Call remove()/remove_if() methods.
 forward_list   |
                |
----------------+------------------------------------------  
                |
 map            |    Simple erase(key) method call, 
 set            |    or 
 unordered_map  |    loop through the container,
 multimap       |    and call erase(iterator) on matching
                |    condition.
 ...            |
                |
----------------+------------------------------------------

Writing different specific code based on the particular container is error-prone, hard to maintain, hard to read, etc.

However, it's possible to write function templates with common names (e.g. erase() and erase_if()) overloaded for different container types, and embed the aforementioned pattern implementations in those functions.
So, the client can simply call those erase() and erase_if() generic functions, and the compiler will dispatch the call to proper implementation (at compile time), based on container type.

A more elegant approach, using a template meta-programming technique, is presented by Stephan T. Lavavej here.

Comments

[Joseph Mansfield]

It'll be much easier to write an overloaded erase when we have template constraints.

[Mike Seymour]

Note that this answer only describes erasing by value (or by properties of values). There is a uniform interface across all sequence and associative containers (except array) for erasing by iterator or iterator range.

[Mr.C64]

@MikeSeymour: Yes, I was focusing on erasing by value or property of values (which is common in code). I edited the question text to make it more clear. Thanks.

[Christian Rau]

Good answer, just one little inaccuracy. The std::map::erase you present doesn't search for a whole value (key-value-pair), but only a key (which for maps is not the whole value). While this is indeed the usual use case, some clarification in the answer might be a good idea.

[Mr.C64]

@ChristianRau: Thanks for the note. I've updated the answer to make it more clear.

[alexrider]

Perhaps adding link to Iterator invalidation rules can be helpful. Since lots of people having problem with that, right after learning about how remove and erase work.

[Pete Becker]

The "std::vector Pattern" applies to any sequence designated by a pair of random-access iterators. In general, containers are the wrong thing to focus on; iterators define an abstraction that should be the first approach to generic programming issues. Sometimes the iterator abstraction isn't sufficient, which is why std::list, which has bidirectional iterators, provides several member functions that do the same thing as generic algorithms that take random-access iterators.

[EML]

You should point out that your erase loop for associative containers only works for C++11 and later.

[Adrian Maire]

For those worried about performance, the remove and remove_if idiom are ordered by shifting (using the move assignment). For removing several items from an std::vector, it is faster than iterating and removing each of them.

[KeyC0de]

forgot to mention that erase/remove call the destructor of the element in the container (unless of course that element is a pointer); for completeness sake