首页 文章

std :: remove with vector :: erase和undefined behavior

提问于
浏览 次
29

在整个网络上我看到人们使用erase/remove idiom为C矢量，如下所示：

#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 的向量中的数字5），那么我将 std::remove 或 std::remove_if 与 vector.erase 结合使用，如下所示：

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

这一般很好用; std::remove （和 remove_if ）将复制（或使用C 11中的移动语义）要删除的元素到向量的末尾，因此我们上一个示例中的向量现在将如下所示：

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

元素 5 以粗体显示，因为它已被移动到最后 .

现在， std::remove 将返回一个迭代器，然后我们在 erase 中使用它来清除元素 . 尼斯 .

但是下面的例子怎么样？

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;
}

这似乎在我运行它的所有平台上按预期工作（不擦除任何东西，而不是segfaulting等），但我知道只是因为某些东西工作，并不意味着它不是未定义的行为 .

vector.erase 的快速reference说（强调我的）：

iterator erase (const_iterator first, const_iterator last);

first, last 是

迭代器指定要移除的向量中的范围：[first，last） . 即，范围包括第一个和最后一个之间的所有元素，包括由第一个指向的元素而不是由最后一个指向的元素 . 成员类型iterator和const_iterator是指向元素的随机访问迭代器类型 .

那么是vector.erase（vector.end（），vector.end（））未定义的行为？

以下是关于异常安全的快速参考说明：

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

所以，答案，至少在我看来似乎是"YES"，this StackOverflow answer似乎支持它 .

因此，常见的成语是错误的吗？

假设它是未定义的行为，那么对 remove 的任何调用都可以返回 vector.end() 的迭代器，在调用 vector.erase 之前应该检查它，并且在空向量上调用remove似乎返回 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()";
}

最后，我的问题：

实际的删除/删除成语应该是这样的吗？

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

3 回答

  • 5

    24.2.1 / 7大多数在数据结构上运行的库的算法模板都有使用范围的接口 . 范围是一对指定计算开始和结束的迭代器 . 范围[i，i]是空范围;通常，范围[i，j]是指数据结构中的元素，以i指向的元素开始，但不包括j指向的元素 .

    强调我的 .

    此外，您引用的 erase 的描述不是标准中的规范性文本 . 标准就是这样说的（表100）：

    a.erase（q1，q2）效果：删除[q1，q2]范围内的元素 .

    这不要求 q1 可解除引用 . 如果[q1，q2）是空范围（每24.2.1 / 7），则该范围内没有元素，因此不会删除任何元素 .

    回复于
  • 28

    我认为你的引用更重要的是：

    迭代器指定要移除的向量中的范围：[first，last） . 即，范围包括第一个和最后一个之间的所有元素，包括由第一个指向的元素而不是由最后一个指向的元素 . 成员类型iterator和const_iterator是指向元素的随机访问迭代器类型 .

    正如我们在评论中发现的那样，来自cpluspluc.com的引用不正确 . 这不会违反 ( v.end, v.end) 的规则，但如果是，则不正确

    #include <vector>

int main()
{
    std::vector<int> v = { 1, 2, 3 };

    v.erase( v.begin(), v.begin());
}

    因为与之相矛盾的陈述

    范围包括（...），包括v.begin（）指向的元素，但不包括v.begin（）指向的元素 .

    不能是一个有效的声明 .

    C标准n3337 in § 23.2.2序列容器要求表100指定了

    a.erase(q1,q2) 返回 iterator . 请注意：

    要求：对于vector和deque，T应为MoveAssignable . 效果：删除[q1，q2]范围内的元素 .

    这就是它在_2896785中的说法 § 24.2.1 / 7迭代器要求

    在数据结构上运行的大多数库的算法模板都具有使用范围的接口 . 范围是一对指定计算开始和结束的迭代器 . 范围[i，i]是空范围;在通常，范围[i，j]是指数据结构中的元素，以i指向的元素开始，但不包括j指向的元素 . 当且仅当j可从i到达时，Range [i，j]才有效 . 将库中的函数应用于无效范围的结果是未定义的 .

    从而回答你的问题

    但是下面的例子怎么样？

    cplusplus.com在这种情况下是错误的

    vector.erase（vector.end（），vector.end（））未定义的行为是什么？

    No, no undefined behavior is triggered.

    因此，常见的成语是错误的吗？

    不，这是对的 .

    实际删除/删除成语应该是这样吗？

    没有必要，虽然它也没关系 .

    回复于
  • 4

    vector.erase（vector.end（），vector.end（））未定义的行为是什么？

    不可以 . 因为您所使用的声明旁边的声明：

    迭代器指定要移除的向量中的范围：[first，last） . 即，范围包括第一个和最后一个之间的所有元素，包括由第一个指向的元素而不是由最后一个指向的元素 .

    因此， vector.erase(vector.end(),vector.end()) 不会尝试擦除 vector.end() ，因为参数 last 指向它 .

    当然，这个定义含糊不清，这些陈述可以解释为矛盾 . 标准未使用引用的措辞 .

    回复于

相关问题