在 std::vector::begin() 之前对 std::vector::iterator 进行递减操作

Question

在 std::vector::begin() 之前对 std::vector::iterator 进行递减操作

3

在一个向量上使用“遍历时删除”的模式之一，我不明白为什么这段代码能够工作，或者它是否利用了未定义的行为：

代码：

#include <vector>
#include <iostream>

int main(int argc, char* argv[], char* envz[])
{
  std::vector<std::string> myVec;
  myVec.push_back("1");
  myVec.push_back("2");
  myVec.push_back("3");

  for (std::vector<std::string>::iterator i = myVec.begin();
       i != myVec.end();
       ++i)
  {
    if ("1" == *i)
    {
      std::cout << "Erasing " << *i << std::endl;
      i = myVec.erase(i);
      --i;
      continue;
    }
    std::cout << *i << std::endl;
  }

  return 0;
}

输出结果:

>g++ -g main.cpp
>./a.out 
Erasing 1
2
3

问题:

考虑for循环的第一次迭代：

i 是 myVec.begin()，指向 1。
我们进入条件块。
1 被删除，i 被设置为已删除元素后面的一个，也就是现在被 myVec.begin() 指向的 2
我将 i 减少，现在它指向 ... myVec.begin() 之前的一个元素？？？

我对为什么这似乎有效产生了疑惑，正如输出所证明的那样，但是在迭代器减少时感觉不太对劲。如果条件是 if ("2" == *i)，那么这段代码就很容易理解，因为迭代器减量仍然将其置于向量中的有效条目。换句话说，如果我们有条件地删除了 2，则 i 将被设置为指向 3，但然后手动减量并且指向 1，随后进行 for 循环增量，使其再次指向 3。有条件地删除最后一个元素也同样容易理解。

我尝试的其他方法：

这个观察让我假设在 vector::begin() 之前减量是幂等的，因此我尝试了额外的减量，如下所示：

#include <vector>
#include <iostream>

int main(int argc, char* argv[], char* envz[])
{
  std::vector<std::string> myVec;
  myVec.push_back("1");
  myVec.push_back("2");
  myVec.push_back("3");

  for (std::vector<std::string>::iterator i = myVec.begin();
       i != myVec.end();
       ++i)
  {
    if ("1" == *i)
    {
      std::cout << "Erasing " << *i << std::endl;
      i = myVec.erase(i);
      --i;
      --i;      /*** I thought this would be idempotent ***/
      continue;
    }
    std::cout << *i << std::endl;
  }

  return 0;
}

但是这导致了段错误：

Erasing 1
Segmentation fault (core dumped)

有人可以解释一下为什么第一个代码块是有效的，特别是为什么在删除第一个元素后进行单个减少是有效的吗？

- StoneThrow

4

使用未定义行为并不能保证程序会崩溃，有时它可能会表现正常。 - interjay

相关链接：http://stackoverflow.com/questions/18225651/is-stdvectorbegin-1-undefined 和 http://www.cplusplus.com/forum/general/84609/ - qxz

3

未定义行为的一个可能效果是“看起来工作正常”，但实际上并不起作用。如果 --i; ++i; 的结果是 i 没有改变，这并不是完全令人惊讶的。 - Bo Persson

1

你为什么认为--i是幂等的呢？无论如何，如果你使用支持调试迭代器的实现（例如这个），并查看它以有用的错误消息中止，那么你将节省很多时间。 - Jonathan Wakely

@JonathanWakely 只是为了回答你的问题，我想知道当--i指向vector::begin()时，它是否是幂等的，或者它是否指向某个神奇的“pre-begin()”保留位置，从那里合法地增加回到begin()。但这既不是这里也不是那里：这段代码似乎依赖于未定义的行为。 - StoneThrow

3个回答

1

这在一些编译器中可能有效，但在其他编译器中可能会失败（例如，编译器实际上可能会在运行时检查您是否在begin()下面进行了递减，并在这种情况下抛出异常 - 我相信至少有一个编译器这样做，但不记得是哪一个）。

在这种情况下，通常的模式是不在for中进行递增，而是在循环内部进行递增：

  for (std::vector<std::string>::iterator i = myVec.begin();
       i != myVec.end();
       /* no increment here */)
  {
    if ("1" == *i)
    {
      std::cout << "Erasing " << *i << std::endl;
      i = myVec.erase(i);
      continue;
    }
    std::cout << *i << std::endl;
    ++i;
  }

使用向量可能会使错误的迭代在更多情况下实际上起作用，但如果您尝试在std::map或std::set中进行此操作，则会遇到很大问题。

- EmDroid

-1

关键在于在递减之后立即使用continue。通过调用它，在解引用i之前，循环迭代将触发++i。

- Telokis

2

这并不安全，它是未定义的行为。在许多平台上可能什么都不会发生，但在其他平台上会崩溃（例如，一些标准库在调试模式下进行边界检查）。 - interjay

为什么会这样？我不明白指针怎么可能是未定义的。 - Telokis

正是因为迭代器未定义的原因。 - M.M

好的，我不是很明白，但我删除了那部分。但我认为没有人回答原始问题：

有人能解释一下为什么第一个代码块有效，特别是在删除第一个元素后进行单个递减为什么是有效的吗？

他确实在问为什么，而不仅仅是想知道是否“可以”。 - Telokis

@Ninetainedo - 你对我关于第一个和第二个代码块的疑惑是正确的。但我认为答案归结为未定义行为。 - StoneThrow

是的，我完全同意这一点。我也刚学到了这个。我知道的越多。 - Telokis

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kerrek SB · Accepted Answer

不，你的代码存在未定义行为：如果i == myVec.begin()，那么i = myVec.erase(i);会导致i再次成为（新值的）myVec.begin()，并且--i的行为是未定义的，因为它超出了迭代器的有效范围。

如果你不想使用erase-remove习惯用法（即myVec.erase(std::remove(myVec.begin(), myVec.end(), "1"), myVec.end())），那么手动循环-同时变异看起来像这样：

for (auto it = myVec.begin(); it != myVec.end(); /* no increment! */) {
  if (*it == "1") {
    it = myVec.erase(it);
  } else {
    ++it;
  }
}

无论如何，关键点在于你的原始代码中和这里都是 erase 会使迭代器无效，因此在删除后必须重新分配一个有效值给该迭代器。我们可以通过erase 的返回值来实现这一点，它恰好就是我们需要的新的有效迭代器。