如何从 STL 容器中擦除元素?

如何从 STL 容器中删除具有指定值或满足某些条件的元素?

对于不同种类的容器，是否有一种通用或统一的方法来做到这一点?

解决方案

不幸的是，没有一个统一界面或模式用于从 STL 容器中擦除元素.但是出现了三种行为:

std::vector 模式

要从 std::vector 中删除满足特定条件的元素，一种常用技术是所谓的 erase-remove idiom.

如果 v 是 std::vector 的一个实例，我们想从向量中删除值为 x 的元素，代码如下这可以使用:

//从向量v"中删除值为x"的元素v.erase( std::remove(v.begin(), v.end(), x), v.end() );

如果擦除元素要满足的标准比简单的要擦除的元素 == x" 更复杂，则 std::remove_if() 算法可以用来代替 std::remove():

//从向量v"中删除匹配erasing_condition"的元素v.erase(std::remove_if(v.begin(), v.end(),erasing_condition), v.end());

其中 erasing_condition 是一元谓词，可以用多种形式表示:例如它可以是一个 bool 返回函数，以向量元素类型作为输入(所以如果返回值为 true，元素将从向量；如果它是 false，则不会)；或者它可以内联表示为lambda；它可以是 函子；等

(std::remove() 和 std::remove_if() 都是来自 标头的通用算法.)

这里有一个清晰的解释来自维基百科:

<块引用>

algorithm 库提供了 remove 和 remove_if为此的算法.因为这些算法在一系列由两个前向迭代器表示的元素，它们不知道底层容器或集合.因此，实际上没有元素从容器中取出.相反，所有不适合的元素删除条件放在范围的前面，在相同的相对顺序.其余元素留在一个有效的，但未指定的状态.完成后，remove 返回一个迭代器指向最后一个未删除的元素.

为了真正从容器中消除元素，结合了remove使用容器的 erase 成员函数，因此得名擦除-删除习语".

基本上，std::remove() 和 std::remove_if() 将不满足擦除条件的元素压缩到范围的前面(即到 vector 的开头)，然后 erase() 实际上从容器中消除了剩余的元素.

此模式也适用于其他容器，例如 std::deque.

std::list 模式

要从 std::list 中删除元素，简单的 remove() 和 remove_if()方法可用:

//从列表l"中删除值为x"的元素l.remove( x )//从列表l"中删除满足erasing_condition"的元素l.remove_if(erasing_condition);

(其中 erasing_condition 是一元谓词，具有与上一节中讨论的 std::remove_if() 相同的特征.)

相同的模式可以应用于类似的容器，例如 std::forward_list.

关联容器(例如 std::map、std::set、...)模式

关联容器，如std::map、std::set、std::unordered_map 等遵循此处描述的常见模式:

1. 如果擦除条件是简单的键匹配(即擦除元素具有键 x")，则可以调用一个简单的 erase() 方法:

   //从映射m"中删除键为k"的元素:m.erase(k);

2. 如果擦除条件比较复杂，并且由一些自定义表示一元谓词(例如擦除所有奇数元素")，然后可以使用 for 循环(在循环体中进行显式擦除条件检查，并调用 erase(iterator) 方法):

   <代码>////擦除关联容器c"中的所有元素，满足erasing_condition"://for (auto it = c.begin(); it != c.end();/* "it" 在循环体内部更新 */){if (erasing_condition(*it)){//删除符合指定条件的元素//来自关联容器.它 = c.erase(it);//笔记://erase() 返回元素的迭代器//在最后一个被移除的元素之后，//所以我们可以从那个位置继续for"循环迭代.}别的{//当前元素_不_满足擦除条件，//所以我们可以继续下一个元素.++它;}}

需要统一的方法

从上面的分析中可以看出，遗憾的是没有统一的通用方法来擦除 STL 容器中的元素.

下表总结了上述模式:

<块引用>

----------------+------------------------------------------集装箱 |擦除图案--+------------------------------------------|矢量 |使用擦除-删除习语.双语 ||--+------------------------------------------|列表 |调用 remove()/remove_if() 方法.forward_list ||--+------------------------------------------|地图 |简单的擦除(键)方法调用，设置 |或者unordered_map |循环通过容器，多图 |并在匹配时调用 erase(iterator)|状况.... ||--+------------------------------------------

根据特定的容器编写不同的特定代码容易出错、难以维护、难以阅读等.

但是，可以为不同的容器类型编写具有通用名称的函数模板(例如 erase() 和 erase_if())重载，并将上述模式实现嵌入到这些函数中.
因此，客户端可以简单地调用那些 erase() 和 erase_if() 通用函数，编译器会将调用分派到正确的实现(在编译时)，基于容器类型.

一种更优雅的方法，使用模板元编程技术，介绍了 作者 Stephan T. Lavavej 在这里.

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?

解决方案

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.