c++ - 顺序容器 || C++ Primer 第五版习题 9.22

Question

我对这个练习感到困惑。

Exercise 9.22: Assuming iv is a vector of ints, what is wrong with the following program? How might you correct the problem(s)?

vector<int>::iterator iter = iv.begin(),
                      mid  = iv.begin() + iv.size()/2;

while(iter != mid)     
    if(*iter == some_val)
        iv.insert(iter, 2 * some_val)

我要做的第一件事就是去问这个程序的目的是什么。由于我不确定这本书的这一部分是谁写的，并且不想因为一些可能微不足道的事情打扰作者，所以我开始猜测。

我假设他们想在 vector 中插入第一个值的两倍，直到该值位于中间。 (因为他们将 iter 指向开头并且从不在 vector 中移动以查找实际值(然后他们再次将其命名为 some_val，查找不在开头的值是一个微不足道的修复，但随后必须验证该值实际上在容器的前半部分))

所以 a) vector 会像这样增长？

{1,2,3,4,5}
{(2),1,2,3,4,5}
{2,(2),1,2,3,4,5}
{2,2,(2),1,2,3,4,5}

在这种情况下的第一个问题是，插入 vector 很可能会立即使迭代器失效。 我们可以改用列表，但是这样我们就不能使用迭代器算法来计算中间值。 像示例中那样只计算一次 mid 是不够的，因为在像 a.) 这样的列表中它会指向 3 并一直指向 3，只是因为我们调用了迭代器 mid 并用 mid 中的元素初始化了他并不意味着在所有这些插入之后它仍然指向中间。

这就是我所做的:

vector<int>::iterator iter=iv.begin();

while(iter!=iv.begin()+iv.size()/2){    //calculating mid each time
    if(*iter==some_val)
        iv.insert(iter,2*some_val);

    iter=iv.begin();                        //revalidate iter
    while(*iter!=some_val)                  //find the original first element
        ++iter;
}

我看到练习如何迫使您考虑使用哪个顺序容器以及迭代器在不断增长的容器中的行为方式，但练习的呈现方式仍然让我感到困惑。我是否遗漏了一些明显的要点？

PS:由于整章都在讨论顺序容器，所以我没有关注 while 循环中的条件所引起的问题(就像他们忘记了几章前教过的一切一样)。

Answer 1

让我们一步步过一遍程序，将代码风格更新为现代C++:

auto iter = iv.begin(); // type will be std::vector<int>::iterator
const auto mid  = iv.begin() + iv.size()/2; // type will be std::vector<int>::iterator

while(iter != mid)
{
  if(*iter == some_val)
    iv.insert(iter, 2 * some_val);
}

前两行创建迭代器对。 循环迭代直到到达 vector 的中间。 循环内的条件检查 iter 指向的位置的值是否等于某个预定义值 someval。 下一行代码向 vector 中插入一个新项，等于 some_val 值的两倍。

现在回答你的问题:插入行确实使所有迭代器失效，这确实是程序中的问题。此外，迭代器不会迭代，因为它永远不会递增。 可以通过使用 insert 调用的返回值使 iter 再次有效和可用来解决一个失效问题:

iter = iv.insert(iter, 2*some_val);

但这仍然留给我们 mid。您的问题中没有足够的信息来解决这个问题，但可能的选择是:

while(std::distance(iter, iv.end()) > iv.size()) // shift the middle when the vector grows

const auto half = iv.size()/2;
while(std::distance(iter, iv.begin()) < half) // only iterate until iter is halfway the original length by insertion

因此，示例解决方案可能如下所示:

auto iter = iv.begin();

while(std::distance(iter, iv.begin()) < iv.size()/2) // iterate until halfway the current vector
{
  if(*iter == some_val)
    iter = iv.insert(iter, 2 * some_val);
  else
    ++iter;
}

但这当然可能不是预期的解决方案。