通过迭代器从 std::vector 中删除

Question

为了从 std::vector 中删除迭代器，我可以做以下两件事：

std::vector<int>& vec = myNumbers; // use shorter name
vec.erase(std::remove(vec.begin(), vec.end(), number_in), vec.end());

或者我可以这样做：

auto it = find(vec.begin(), vec.end(), number_in);
vec.erase(it);

我猜第二种更直观，但哪个更快？

编辑： vector 中的元素是唯一的，我们不必担心一次删除多个元素。

Answer 1

第二个更快 - 第一个将尝试找到所有个等于 number_in 的元素，尽管它已经找到了一个。但是，第二个会在找到一个时停止。

Answer 2

第一个保证可以正常工作，而您的第二个版本可能更快（由于 std::find 在匹配的第一个项目处停止），但它肯定不安全。

auto it = find(vec.begin(), vec.end(), number_in);
if (it != vec.end())
   vec.erase(it);

这将确保您不会擦除无效的迭代器。

所以这取决于你的需求。如果您想要一个正确的程序，第一个程序无需进一步干预即可运行，但是第二个程序需要您的客户提供错误票，然后您必须修复它（如上所述）。

Answer 3

std::vector::erase

Removes the element at pos.

Removes the elements in the range [first; last).

Invalidates iterators and references at or after the point of the erase, including the end() iterator. The iterator pos must be valid and dereferenceable. Thus the end() iterator (which is valid, but is not dereferencable) cannot be used as a value for pos. The iterator first does not need to be dereferenceable if first==last: erasing an empty range is a no-op.

http://en.cppreference.com/w/cpp/container/vector/erase

第一种方法会比较慢，因为要在整个向量中搜索数字。但它也是更安全的方式。考虑 number_in 不是向量的元素。第一种方法将尝试擦除已定义且安全的空范围。第二种方法会尝试擦除不安全且 UB 的向量的结束迭代器。

Answer 4

您似乎对性能感兴趣。查找（第一个）匹配元素不能比 O(n) 更快。因此，您可以尝试提高性能的部分是删除，可以是 O(1)、if 你允许要更改的向量元素的顺序。例如

// find requires up to O(n)
auto it = std::find(v.begin(),v.end(),value);
// remove in O(1) but don't preserve order
if(it!=v.end()) {
  std::iter_swap(it,--(v.end()));
  v.pop_back();
}

请注意，使用 std::remove() and/or vector::erase() 的解决方案将保留剩余元素的顺序，因此不可避免地 仍然会压缩剩余元素 （引自 Tony D 的评论），这几乎总是比找到匹配元素更昂贵，因此在计算成本中占主导地位。

只需尝试哪种解决方案更快 - 布丁的证明就在吃中！

通过迭代器从 std::vector 中删除

Remove by iterator from std::vector

c++

vector

std