C++从序列容器中删除元素的四种方法_C/C++

一、简介

本文讨论从集合中删除元素的stl算法。从c++集合中删除一个元素可能不复杂，也可能有点复杂。

删除元素的方法在序列容器和关联容器之间是非常不同的。在序列容器中，vector 和 string 是最常用的。但这里也会介绍 deque 和 list 以供全面了解，尽管在一般情况下可能不会使用它们。

至少有四种方法可以指定从任何容器中删除哪些值：

在给定位置（或在两个给定位置之间）删除元素；
删除等于某个值的元素；
删除满足某个谓词的元素
以及删除重复项。

下面来看看如何在stl序列容器中实现这四种命令。

二、移除给定位置的元素

这是最简单的方法。如果是一个序列容器，可以通过调用erase。比如：

c.erase(position);

要移除由迭代器first和last组成的子范围中的元素，可以这么调用：

c.erase(first, last);

与stl中迭代器表示的所有范围一样，子范围包括first，而不包括last。last指向“past-the-end”元素，类似于容器的结束迭代器。

注意，对于vector和string，所有指向被移除对象所在位置和之后元素的迭代器都无效。因为所有这些元素都被erase函数调用移除了。

对于deque来说，会有一点点不同：参考cppreference.com，所有迭代器和引用都无效，除非被删除的元素位于容器的末尾或开头，在这种情况下，只有迭代器和对被删除元素的引用无效。

如果删除的元素位于deque的中间位置，则所有指向该元素以及之后位置的迭代器和引用都会失效。
如果删除的是末尾元素，那么仅仅指向这个末尾元素的迭代器和引用会失效，其余保持有效。
如果删除的是开头元素，同样只有指向这个开头元素的迭代器和引用会失效。

这erase很简单，只是热身。下面还有复杂的，接着阅读学习吧。

三、移除与某个值相等的元素

3.1、序列容器vector、deque、string

这些容器没有删除值的方法，因此需要使用std::remove算法。该算法取一个要删除的范围和一个值，并上移所有要保留的元素。

例如，在这个整数范围内调用std::remove并带值42，会有以下行为：

注意，在范围末尾剩下的元素的值是未指定的。尽管有些实现可以将最初位于集合末尾的元素保留下来，但这是不可靠的。

要记住，在stl的设计中，算法只与迭代器交互，而不直接与容器交互，因此容器并不知道算法的效果。例如，它的size并没有缩小。

为了有效地从集合中删除元素，需要使用在本文前面讲到的erase方法。为此，要注意到std::remove返回一个迭代器，该迭代器指向不应被删除的元素范围内的“past-the-end”元素。即，要删除的元素位于std::remove返回的迭代器定义的范围和集合的末尾。

因此，要有效地从vector、deque或string对象中删除值，可以这样写：

v.erase(std::remove(begin(v), end(v), 42), end(v));

3.2、封装成模板方法

这是c++的习惯用法，如果在代码中遇到它，必须知道。但是，坦白地讲，不觉得用这么多代码来表达这么简单的事情有点多吗？难道不喜欢像下面这样写吗?

v.remove(42);
// or
v.erase(42);

也可以给它添加一些重载来操作deque和string对象：

template<typename t>
void erase(std::deque<t>& deque, t const& value)
{
    deque.erase(std::remove(begin(deque), end(deque), value), end(deque));
}

void erase(std::string& string, char letter)
{
    string.erase(std::remove(begin(string), end(string), letter), end(string));
}

非常建议实现这些辅助函数，特别是对于最常用的vector。这可以避免标准习惯用法所带来的迭代器的纠缠。

甚至在c++标准中，就有学者提出了一个增加这种泛型函数的建议。很遗憾的是，它还没有在c++ 17中实现。

3.3、list的remove成员函数

为了全面起见，这里提一下要从list中删除一个元素，有一个叫做remove的方法，例如：

l.remove(42);

由于它不提供随机访问迭代器，在列表上使用std::remove算法会使列表变得比现在更慢。

四、删除满足谓词的元素

前面已经看到了如何从序列容器中删除所有等于某个值的元素，比如42。那么，如何移除满足谓词func的元素？其实，这完全一样，只是需要使用 remove_if 而不是 remove。

所以只需要替换：

remove为remove_if；
42为func。

std::remove_if(begin(string), end(string), func)

和上一节一样。依然建议编写一个名为erase_if的自由函数，以避免大量迭代器的出现；并且list同样有一个名为remove_if的成员方法。因此，为了遵循“不要重复”的原则和避免文章篇幅过长，这里不再对remove_if进行更多讨论。

五、从序列容器中删除重复项

从序列容器中删除重复项的stl算法是std::unique。但是要注意！unique只删除相邻的重复项，而不删除整个集合中的重复项。它具有线性复杂度。

除此之外，unique和remove非常相似。它只压缩集合的元素，而不能改变容器本身size。因此，需要在容器上调用erase才能有效地删除重复项：

vector.erase(std::unique(begin(v), end(v)), end(v));

和remove一样，封装一个方便的函数是必要的：

template<typename t>
void unique(std::vector<t>& vector)
{
    vector.erase(std::unique(begin(vector), end(vector)), end(vector));
}

template<typename t>
void unique(std::deque<t>& deque)
{
    deque.erase(std::unique(begin(deque), end(deque)), end(deque));
}

void unique(std::string& string)
{
    string.erase(std::unique(begin(string), end(string)), end(string));
}

与remove类似，std::list有一个unique的成员方法。

六、总结

这就是c++中从序列容器中删除元素的方法。

在c++中，从序列容器中删除元素的方法多种多样，每种方法都有其适用的场景和使用方式。

移除给定位置的元素：可以使用erase方法，通过指定要删除的元素位置或者给定范围的迭代器来实现。
移除与某个值相等的元素：对于vector、deque和string等序列容器，可以使用std::remove算法，并结合erase方法来删除指定值的元素；或者封装成模板函数来简化操作。
删除满足谓词的元素：使用std::remove_if算法结合erase方法，可以删除满足指定谓词条件的元素。
从序列容器中删除重复项：利用std::unique算法可以删除相邻的重复项，但需要注意该算法只删除相邻的重复项，并且不能改变容器的大小，需要配合erase方法来实现删除整个容器中的重复项。