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

Question

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

对于不同种类的容器，是否有一种通用或统一的方法？

Answer 1

不幸的是，没有一个单一的uniform 接口(interface)或模式可用于从 STL 容器中删除元素。 但出现了三种行为:

std::vector 模式

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

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

// 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 -返回函数 以 vector 元素类型为输入(所以如果返回值为 true ，该元素将从 vector 中删除；如果是 false ，则不会)；或者它可以in-line表示为一个lambda；可以是 functor ;等等

(std::remove() 和 std::remove_if() 都是来自 <algorithm> header 的通用算法。)

这里有明确的解释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".

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

这种模式也适用于其他容器，例如 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. 如果删除条件是简单的键匹配(即“删除元素 有键 x")，然后可以调用一个简单的 erase() 方法:

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

2. 如果删除条件比较复杂，用一些习惯来表示 一元谓词(例如“删除所有奇数元素”)，然后是 for可以使用循环 (在循环体中检查明确的删除条件，并调用 erase(iterator) 方法):

   //
   // 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()泛型函数，编译器将根据容器类型将调用分派(dispatch)给正确的实现(在编译时)。

介绍了一种更优雅的方法，使用模板元编程技术by Stephan T. Lavavej here .