c++ - 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?

Answer 1

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.