如何从 stl 向量中删除具有特定值的项目？

Question

我正在查看 stl 矢量的 API 文档，并注意到矢量类上没有允许删除具有特定值的元素的方法。 这似乎是一个常见的操作，并且没有内置的方法来执行此操作似乎很奇怪。

Answer 1

如果你想在没有任何额外内容的情况下做到这一点：

vector<IComponent*> myComponents; //assume it has items in it already.
void RemoveComponent(IComponent* componentToRemove)
{
    IComponent* juggler;

    if (componentToRemove != NULL)
    {
        for (int currComponentIndex = 0; currComponentIndex < myComponents.size(); currComponentIndex++)
        {
            if (componentToRemove == myComponents[currComponentIndex])
            {
                //Since we don't care about order, swap with the last element, then delete it.
                juggler = myComponents[currComponentIndex];
                myComponents[currComponentIndex] = myComponents[myComponents.size() - 1];
                myComponents[myComponents.size() - 1] = juggler;

                //Remove it from memory and let the vector know too.
                myComponents.pop_back();
                delete juggler;
            }
        }
    }
}

Answer 2

类似于擦除删除惯用语，用于向量 可以使用 resize 和 remove 并使用迭代器距离计算：

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

经过测试 此处。

Answer 3

一个更短的解决方案（不会强迫您重复向量名称 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

Answer 4

有两种方法可以用来专门删除某个项目。
让我们取一个向量

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）非有效的方式：虽然它看起来相当有效，但这并不是因为擦除函数删除了元素并将所有元素向左移动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 idioms em>。

• std::remove 将给定范围转换为一个范围，其中所有不等于给定元素的元素都移至容器的开头。
• 所以，实际上不要删除匹配的元素。
  它只是将不匹配的部分转移到起始位置，并为新的有效末端提供一个迭代器。
  它只需要 O(n) 复杂度。

删除算法的输出是：

10 20 30 50 40 50 

因为删除的返回类型是到该范围的新末尾的迭代器。

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)

Answer 5

*

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

Answer 6

另请参阅 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".

Answer 7

从c++20开始：

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

前任：

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

Answer 8

其他答案涵盖了如何做好这一点，但我想我还要指出，这不在向量 API 中并不奇怪：它是低效的，通过向量线性搜索值，然后是一堆复制以将其删除。

如果您密集地执行此操作，出于这个原因，可能值得考虑使用 std::set 。

Answer 9

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

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

Answer 10

将全局方法 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 指出我的错误。

Answer 11

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

Answer 12

如果您想删除一个项目，下面的方法会更有效一些。

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 方法在幕后做的。