如何从STL容器中删除元素？

Question

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

是否存在适用于不同类型容器的单一通用方法来完成此操作？

- Mr.C64

---

可能适合于C++常见问题解答。 - Luchian Grigore

@LuchianGrigore 这个一般是怎么工作的呢？通常是由社区基于评论讨论来决定，还是每个人都可以随意标记为 c++-faq（当然，每个人都可以，但也许这被认为是不好的礼仪，因为这个标签的内容控制要求更严格）。或者应该只是打上标签，让社区负责在不同意时删除标签。 - Christian Rau

@ChristianRau，这通常在休息室中讨论。 - Luchian Grigore

Answer 1

很不幸，没有一种单一的统一接口或模式可以从STL容器中删除元素。但是有三种行为出现：

std :: vector 模式

从std :: vector 中删除满足某些条件的元素的常见技巧是所谓的 删除-移动结构。

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

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

如果要满足删除元素的条件比简单的“要删除的元素 == x”更复杂，可以使用std::remove_if()算法来代替std::remove()：

// Erase elements matching "erasing_condition" from vector "v"
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()从容器中真正消除剩余的元素。

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

std::list模式

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

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

// Erase elements satisfying "erasing_condition" from list "l"
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. 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;
       }       
   }     
   

统一方法的必要性

从上面的分析可以看出，不幸的是，目前没有一种统一的常见方法可以从STL容器中删除元素。

以下表格总结了上述模式：

----------------+------------------------------------------             
   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.
 ...            |
                |
----------------+------------------------------------------

根据特定容器编写不同的代码很容易出错，难以维护、难以阅读等问题。然而，可以编写具有共同名称（例如erase()和erase_if()）的函数模板，对不同的容器类型进行重载，并在这些函数中嵌入上述模式实现。因此，客户端可以简单地调用这些通用函数erase()和erase_if()，编译器将根据容器类型在编译时将调用分派到适当的实现。更优雅的方法是使用模板元编程技术，由Stephan T. Lavavej在此处介绍。

- Mr.C64

---

请注意，此答案仅描述按值（或值属性）进行删除。所有序列和关联容器（除了“array”）均具有通过迭代器或迭代器范围进行删除的统一接口。 - Mike Seymour

很好的回答，只有一个小错误。您提供的std::map::erase并不是搜索整个值（键值对），而只是搜索键（对于映射而言，并非整个值）。虽然这确实是通常的用例，但在回答中进行一些澄清可能是一个好主意。 - Christian Rau

@ChristianRau：谢谢提醒。我已经更新了答案，使其更加清晰明了。 - Mr.C64

你应该指出，你的关联容器的删除循环仅适用于C++11及更高版本。 - EML

对于那些担心性能的人来说，使用“remove”和“remove_if”惯用语是通过移位（使用移动赋值）进行排序的。对于从“std::vector”中删除多个项，它比迭代并逐个删除它们要快。 - Adrian Maire