如何从STL向量中删除一个特定值的项目？

Question

我正在查看STL vector的API文档，注意到vector类中没有允许移除某个特定值元素的方法。这似乎是一种常见操作，也很奇怪为什么没有内置方法可以实现这个功能。

- bradtgmurray

---

我知道我以前已经提到过这个问题，但是Scott Meyer的书 Effective STL 以清晰明了的方式涵盖了这些陷阱。 - Rob Wells

相关链接：https://dev59.com/wHA75IYBdhLWcg3wRWyc - bobobobo

这可能是对您有趣的阅读内容：http://en.wikipedia.org/wiki/Erase%E2%80%93remove_idiom - sergiol

Answer 1

std::remove并不实际从容器中删除元素：它会覆盖容器开头不应被删除的元素，并返回指向它们之后下一个元素的迭代器。这个迭代器可以传递给container_type::erase来实际删除现在位于容器末尾的额外元素。

std::vector<int> vec;
// .. put in some values ..
int int_to_remove = n;
vec.erase(std::remove(vec.begin(), vec.end(), int_to_remove), vec.end());

- Jim Buck

---

这个“一句话形式”的表达方式是否依赖于编译器评估参数的顺序，或者 vec.end() 在调用std::remove之前和之后保证是相同的？从我阅读网上其他部分的内容来看，这看起来是安全的，但应明确说明。 - dmckee --- ex-moderator kitten

vec.end()不需要相同，但没关系，因为std::remove不会改变它。如果它改变了它（并使旧值无效），那么会有问题：参数的求值顺序是未指定的，因此您不知道第二个vec.end()在使用时是否仍然有效。其相同的原因很简单，std::remove不会改变容器的大小，它只是移动内容。 - Steve Jessop

我认为这个问题很重要，因为我也有同样的问题。但是，我的 Visual Studio 只接受一个参数 const char *_Filename 的 std::remove() 函数。我需要调用哪个方法呢？ - Victor

这是删除文件的remove版本。为了访问用于处理容器的remove版本，您需要包含<algorithm>。 - Jim Buck

为了让使用std::remove的解决方案起作用，需要有#include <algorithm>，否则会出现错误：error: cannot convert 'std::basic_string<char>::iterator …' to 'const char* for argument '1' …' on my Ubuntu 16.04。 - Yu Shen

Answer 2

如果你想要移除一个项目，下面的方法会更加高效。

std::vector<int> v;


auto it = std::find(v.begin(), v.end(), 5);
if(it != v.end())
    v.erase(it);

或者如果对您来说顺序不重要，您可以避免移动物品的开销：

std::vector<int> v;

auto it = std::find(v.begin(), v.end(), 5);

if (it != v.end()) {
  using std::swap;

  // swap the one to be removed with the last element
  // and remove the item at the end of the container
  // to prevent moving all items after '5' by one
  swap(*it, v.back());
  v.pop_back();
}

这就是Jim的方法std::vector::erase+std::remove在底层执行的操作。

- Etherealone

---

请注意，这不会删除重复的项目，如果存在的话，而使用std::remove_if方法则会。 - Den-Jason

Answer 3

使用全局方法 std::remove 与 begin 和 end 迭代器，然后使用 std::vector.erase 实际删除元素。

文档链接 std::remove http://www.cppreference.com/cppalgorithm/remove.html std::vector.erase http://www.cppreference.com/cppvector/erase.html

std::vector<int> v;
v.push_back(1);
v.push_back(2);

//Vector should contain the elements 1, 2

//Find new end iterator
std::vector<int>::iterator newEnd = std::remove(v.begin(), v.end(), 1);

//Erase the "removed" elements.
v.erase(newEnd, v.end());

//Vector should now only contain 2

感谢Jim Buck指出我的错误。

- bradtgmurray

---

这个功能可以防止向量中间元素被擦除时其他元素的移动，因此速度更快。它首先将它们移动到向量的末尾，然后你只需要从向量末尾丢弃即可。 - Etherealone

Answer 4

来自 c++20:

引入了一个非成员函数std::erase，它接受向量和要删除的值作为输入。

例如:

std::vector<int> v = {90,80,70,60,50};
std::erase(v,50);

- Pavan Chandaka

---

不仅如此，它还针对每个特定的容器进行了重载！ - HolyBlackCat

...并利用容器特定的属性，如map::erase！ - L. F.

Answer 5

另请参阅std::remove_if，以便使用谓词...

这是上面链接中的示例:

vector<int> V;
V.push_back(1);
V.push_back(4);
V.push_back(2);
V.push_back(8);
V.push_back(5);
V.push_back(7);

copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
    // The output is "1 4 2 8 5 7"

vector<int>::iterator new_end = 
    remove_if(V.begin(), V.end(), 
              compose1(bind2nd(equal_to<int>(), 0),
                       bind2nd(modulus<int>(), 2)));
V.erase(new_end, V.end()); [1]

copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
    // The output is "1 5 7".

- Xavier Nodet

---

请在此帖子中添加更多细节。目前，大部分内容来自链接，如果链接失效，将会丢失大量信息。 - Mick MacCallum

bind2nd在C++11中已被弃用，在C++17中已被移除，这个怎么办？ - Idan Banani

Answer 6

如果您有一个未排序的向量，则可以简单地与最后一个向量元素交换，然后使用resize()。

对于有序容器，最好使用std::vector::erase()。请注意，在<algorithm>中定义了std::remove()，但它实际上并没有执行删除操作。（请仔细阅读文档）。

- nsanders

Answer 7

其他答案已经涵盖了如何做到这一点，但我认为我也应该指出，这在向量API中并不奇怪：它是通过向量进行线性搜索来查找值，然后进行大量复制以删除它，这是低效的。

如果您需要频繁执行此操作，出于这个原因，考虑使用std::set可能会更值得。

- Luke H

Answer 8

*

C++社区听到了你的请求 :)

*

C++ 20现在提供了一种简单的方法。 它变得如此简单：

#include <vector>
...
vector<int> cnt{5, 0, 2, 8, 0, 7};
std::erase(cnt, 0);

您应该查看std::erase和std::erase_if。

它不仅可以删除所有值（这里是“0”）的元素，而且还可以在O(n)时间复杂度下完成。这是您可以获得的最佳效果。

如果您的编译器不支持C++ 20，则应使用erase-remove idiom：

#include <algorithm>
...
vec.erase(std::remove(vec.begin(), vec.end(), 0), vec.end());

- Harshad Sharma

Answer 9

一种更短的解决方案（不需要重复4次向量名称）是使用Boost库：

#include <boost/range/algorithm_ext/erase.hpp>

// ...

boost::remove_erase(vec, int_to_remove);

请参见http://www.boost.org/doc/libs/1_64_0/libs/range/doc/html/range/reference/algorithms/new/remove_erase.html。

- jhasse

Answer 10

有两种方法可以用来特别删除一个项目。让我们以向量为例。

std :: vector < int > v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(40);
v.push_back(50);

1）非高效方法：尽管它看起来相当高效，但实际上并不是，因为 erase 函数会删除元素，并将所有元素向左移动 1 个位置。 因此，它的复杂度为 O(n^2)

std :: vector < int > :: iterator itr = v.begin();
int value = 40;
while ( itr != v.end() )
{
   if(*itr == value)
   { 
      v.erase(itr);
   }
   else
       ++itr;
}

2) 高效的方法（推荐）：也被称为ERASE-REMOVE习语。

• std::remove将给定范围转换为一个范围，其中所有与给定元素不相等的元素都移动到容器的开头。
• 所以，实际上并没有删除匹配的元素。 它只是将不匹配的元素移到开头，并给出一个新的有效迭代器。 它只需要O(n)的复杂度。

remove算法的输出是：

10 20 30 50 40 50 

由于remove的返回类型是指向该范围新结尾的迭代器，因此需要注意。

template <class ForwardIterator, class T>
  ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& val);

现在使用向量的删除函数从向量的新端点到旧端点删除元素。它需要O(1)的时间。

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

所以这个方法的时间复杂度是O(n)

- DecPK