如何根据元素的某些属性删除 std::vector 的元素？

Question

例如，如果您有一个 std::vector，其中 MyClass 有一个公共方法：bool isTiredOfLife()，您如何删除返回 true 的元素？

Answer 1

我更喜欢remove_if

v.erase(remove_if(v.begin(), v.end(), 
                 mem_fun_ref(&MyClass::isTiredOfLife)), 
        v.end());

remove_if 返回一个指向后面的迭代器仍在序列中的最后一个元素。 erase 删除从第一个参数到最后一个参数（两个迭代器）的所有内容。

Answer 2

使用remove_if是执行此操作的“正确”方法。 请注意不要使用迭代器来循环和擦除，因为删除项目会使迭代器失效。 事实上，任何使用擦除（）作为其主要方法的示例对于向量来说都是一个坏主意，因为擦除的时间复杂度为 O(n)，这将使您的算法为 O(n^2)。 这应该是一个 O(n) 算法。

我下面给出的方法可能比remove_if更快，但与remove_if不同，它不会保留元素的相对顺序。 如果您关心维护顺序（即您的向量已排序），请使用remove_if，如上面的答案所示。 如果您不关心顺序，并且要删除的项目数通常小于向量的四分之一，则此方法可能会更快：

for( size_t i = 0; i < vec.size(); )
   if( vec[i].isTiredOfLife() )
   {
      vec[i] = vec.back();
      vec.pop_back();
   }
   else
      ++i;