41

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

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

4

1 回答 1

59

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

std::vector 模式

要从 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() );

whereerasing_condition是一个一元谓词，可以用多种形式表示：例如，它可以是一个以向量元素类型为输入的返回bool函数（因此，如果返回值为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()擦除标准的元素压缩到范围的前面（即到 的开头），然后实际上从容器中消除剩余的元素。vectorerase()

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

std::list 模式

要从 astd::list中删除元素，可以使用 simpleremove()和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 );

（Whereerasing_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在此处介绍了一种更优雅的方法，使用模板元编程技术。

于 2013-04-15T11:03:13.680 回答