std :: remove使用vector :: erase和未定义的行为 [英] std::remove with vector::erase and undefined behavior

问题描述

在网络上，我看到人们使用擦除/删除惯用语用于C ++向量像这样：

All over the web I see people use the erase/remove idiom for C++ vectors like so:

#include <vector> // the general-purpose vector container
#include <iostream>
#include <algorithm> // remove and remove_if
int main()
{
  // initialises a vector that holds the numbers from 0-9.
  std::vector<int> v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

  // removes all elements with the value 5
  v.erase( std::remove( v.begin(), v.end(), 5 ), v.end() );

  return 0;
}

也就是说，如果我要删除所有符合某些条件的元素（例如从 int s的向量中得出5），然后我使用 std :: remove 或 std :: remove_if 结合 vector.erase 像这样：

That is, if I want to erase all elements matching some criteria (e.g. the number 5 from a vector of ints), then I use std::remove or std::remove_if in conjunction with vector.erase like so:

vector.erase( std::remove( vector.begin(), vector.end(), <some_value>), vector.end());

总体上来说效果很好； std :: remove （和 remove_if ）将复制（或在C ++ 11中使用移动语义）将被删除到向量的末尾，因此我们前面示例中的向量现在将如下所示：

This works nicely in general; std::remove (and remove_if) will copy (or use move semantics in C++11) the elements that are to be deleted over to the end of the vector, so the vector from our previous example will now look like this:

{0， 1，2，3，4，6，7，8，9， 5 };

元素 5 被加粗，因为它已移到末尾。

With the element 5 bolded because it's been moved to the end.

现在， std :: remove 将向其返回一个迭代器，然后在 erase 中使用它来清除元素。很好。

Now, std::remove will return an iterator to it, which we then use in erase to clear the elements out. Nice.

int main()
{
  // initialises an empty vector.
  std::vector<int> v = {};

  // removes all elements with the value 5
  v.erase( std::remove( v.begin(), v.end(), 5 ), v.end() );

  return 0;
}

这似乎按预期工作（不删除任何内容，不进行段隔离等）。 ）在所有平台上运行，但我知道仅仅是因为某些功能在起作用，并不意味着它不是未定义的行为。

This seems to work as expected (not erasing anything, not segfaulting, etc.) on all platforms I run it on, but I know that just because something is working, doesn't mean it's not undefined behavior.

快速的 vector.erase 的http://www.cplusplus.com/reference/vector/vector/erase/ rel = noreferrer>参考表示（强调矿井）：

The quick reference for vector.erase says this (emphasis mine):

iterator erase (const_iterator first, const_iterator last);

第一个，最后一个是

要在向量中指定范围的迭代器]： [first，last）。也就是说，范围包括第一和最后之间的所有元素，包括第一指向的元素，但不是 last 所指向的那个。
成员类型 iterator 和 const_iterator 是指向元素的随机访问迭代器类型。

Iterators specifying a range within the vector] to be removed: [first,last). i.e., the range includes all the elements between first and last, including the element pointed by first but not the one pointed by last. Member types iterator and const_iterator are random access iterator types that point to elements.

vector.erase（vector.end（），vector.end（））也是如此

以下是快速参考中关于异常安全性的内容：

So is vector.erase(vector.end(),vector.end()) undefined behavior?

Here's what the quick reference says about exception safety:

如果删除的元素包括容器中的最后一个元素，不引发任何异常（无抛出保证）。
否则，保证容器以有效状态结束（基本保证）。
无效的位置或范围会导致未定义的行为。

If the removed elements include the last element in the container, no exceptions are thrown (no-throw guarantee). Otherwise, the container is guaranteed to end in a valid state (basic guarantee). An invalid position or range causes undefined behavior.

因此，至少在我看来，答案似乎是是，并且

So, the answer, at least to me appears to be "YES", and this StackOverflow answer seems to support it.

假设这是未定义的行为，那么对 remove 的任何调用都可以将迭代器返回到 vector.end（），应在进行检查之前调用 vector.erase ，然后在空向量上调用remove似乎会返回 vector.end ：（ 适用于下面代码的IDEOne ）

Assuming it's undefined behavior, then any call to remove could return an iterator to vector.end() which should be checked before calling vector.erase, and calling remove on an empty vector does seem to return vector.end: (IDEOne for code below)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
   vector<int> myInts;
   auto anIter = std::remove(myInts.begin(),myInts.end(),5);
   if (anIter == myInts.end())
      std::cout << "iterator = myInts.end()";
}

最后，我的问题：

实际的删除/擦除习惯用法应该是这个吗？

Finally, my question:

Should the actual remove/erase idiom be this?

auto endOfRangeIterator = std::remove(vector.begin(), vector.end(), <value>);
if (endOfRangeIterator != vector.end())
   vector.erase(endOfRangeIterator, vector.end())

推荐答案

24.2.1 / 7 大多数用于数据结构的库算法模板具有使用范围的接口。范围是一对
的迭代器，它们指定计算的开始和结束。
范围 [i，i）是空范围；通常，范围 [i，j）指的是数据结构中的元素，其起始元素为 i ，直到但不包括 j 指向
的元素。

24.2.1/7 Most of the library’s algorithmic templates that operate on data structures have interfaces that use ranges. A range is a pair of iterators that designate the beginning and end of the computation. A range [i,i) is an empty range; in general, a range [i,j) refers to the elements in the data structure starting with the element pointed to by i and up to but not including the element pointed to by j.

强调我的。

此外，您引用的删除的描述不是标准中的规范性文本。该标准说（表100）：

Further, the description of erase you cite is not the normative text in the standard. The standard has this to say (Table 100):

a.erase（q1，q2）

效果：擦除[q1，q2）范围内的元素。

Effects: Erases the elements in the range [q1, q2).

这不需要取消引用 q1 。如果[q1，q2）是一个空范围（根据24.2.1 / 7），则该范围内没有元素，因此不会擦除任何元素。

This doesn't require that q1 be dereferenceable. If [q1, q2) is an empty range (per 24.2.1/7), then no elements are in the range, and so none are erased.

这篇关于std :: remove使用vector :: erase和未定义的行为的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！