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

Question

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

对于不同类型的容器,是否有单一的通用或统一的方法？

Answer 1

不幸的是,没有单一的统一接口或模式来从STL容器中擦除元素.但是出现了三种行为:

std :: vector Pattern

为了从a中擦除满足特定条件的元素,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-returning功能服用向量元素类型作为输入(因此,如果返回值true时,元件将被从载体擦除;如果它是false,它赢得"T); 或者它可以在线表示为lambda ; 它可以是一个算子 ; 等等

(这两个std::remove()和std::remove_if()从通用算法<algorithm>报头.)

以下是维基百科的明确解释:

该algorithm库 为此提供了算法remove和remove_if算法.因为这些算法在由两个前向迭代器表示的一系列元素上运行,所以它们不知道底层容器或集合.因此,实际上没有元素从容器中移除.相反,所有不符合移除标准的元素以相同的相对顺序汇集到范围的前面.其余元素保留在有效但未指定的状态.完成此操作后,remove返回一个迭代器,指向一个经过最后一个未删除元素的迭代器.

实际上从容器中删除元素,remove与容器的erase成员函数结合,因此名称为"erase-remove idiom".

基本上,std::remove()和std::remove_if()紧凑那些要素不满足擦除标准的范围内的前部(即,的开始vector),然后erase()实际上消除了从容器中剩余的元素.

这种模式也适用于其他容器std::deque.

std :: list Pattern

要删除从元素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()

Stephan T. Lavavej在此提出了一种更优雅的方法,使用模板元编程技术.