在迭代向量时附加到向量？

Question

我有一个正在迭代的向量。在迭代时，我可能会向向量附加新值。它看起来像：

struct Foo
{
   bool condition;
};

void AppendToVec(vector<Foo>& v)
{
   ...
   v.push_back(...);
}

vector<Foo> vec;
...
for (vector<Foo>::size_type i = 0; i < vec.size(); ++i)
{
   if (vec[i].condition) AppendToVec(vec);
}

这工作得很好，实际上优雅地处理了新添加的元素递归地需要添加更多元素的情况，但感觉有点脆弱。如果其他人出现并调整循环，它很容易被打破。例如：

//No longer iterates over newly appended elements
vector<Foo>::size_type size = vec.size();
for (vector<Foo>::size_type i = 0; i < size; ++i)
{
   if (vec[i].condition) AppendToVec(vec);
}

或者

//Vector resize may invalidate iterators
for (vector<Foo>::iterator i = vec.begin(); i != vec.end(); ++i)
{
   if (vec->condition) AppendToVec(vec);
}

是否有处理此类案例的最佳实践？用“警告：此循环在迭代时有意附加到向量。谨慎更改”来评论循环是最好的方法吗？如果这能让事情变得更加健壮，我也愿意切换容器。

Answer 1

我解决这个问题的方法通常是创建一个队列，向其中添加任何新元素，然后在迭代原始容器之后，处理队列中的元素和/或将它们附加到原始容器中。

这种方法的优点是，发生的事情是显而易见的，并且它适用于多个线程可能对新元素进行排队的情况。

Answer 2

如果其他人出现并调整循环，它很容易被破坏。

那么不要使用for循环，而是使用while循环。对我来说，for 循环始终意味着使用计数器的简单迭代循环。但是，如果我遇到 while 循环，我觉得事情一定太复杂了，无法用简单的 for 循环来表达它们。我会仔细观察，并且对“优化”while 循环比“优化”for 循环更加小心。

Answer 3

如果已使用旧向量中的相对位置重新分配了 vec (i-vec.begin( ））。

代码：

void AppendToVec(vector<int> & vec, vector<int>::iterator & i)
{
    const int some_num = 1;
    const size_t diff = i-vec.begin();
    vec.push_back(some_num);
    i = vec.begin()+diff;
}

int main(int argc, char* argv[])
{    
     const size_t arbit_size = 10;
     const size_t prior_size = 3;
     vector<int> vec;

     // Fill it up with something
     for(size_t i = 0; i < prior_size; ++i) vec.push_back(static_cast<int>(i));

     // Iterate over appended elements
     vector<int>::iterator i = vec.begin();
     while(i != vec.end())
     {
      cout<<*i<<","<<vec.size()<<endl;
      if(vec.size()<arbit_size) AppendToVec(vec,i);
      ++i;
     }

     return 0;
}

输出：

0,3
1,4
2,5
1,6
1,7
1,8
1,9
1,10
1,10
1,10

Answer 4

正如已经指出的，正如您所感觉到的，这里存在一个问题。不过，您有多种可能的解决方案，因此不要盲目充电。

• 循环顶部的大注释，带有 WARNING 标记或您的编码标准所需的任何内容，以警告未来的维护人员其中涉及欺骗。最好不要使用，但可以工作。
• 如果您能够提前知道将添加多少元素（或者您有一个相对严格的上限），则可以使用 reserve 并完全防止重新分配。
• 使用std::deque。大多数性能特征都是相似的，但是您可以在不使迭代器/引用等无效的情况下预先添加和附加新值...看起来很自然地适合这里
• 使用单独的队列和双循环

我认为deque是这里更好的解决方案。它适合您的算法，您不必担心这些问题。您可能可以用 deque 替换代码中的大部分 vector。如果您不想更改接口：

• 将 vector 复制到 deque
• 计算
• 将 deque 内容分配到 vector

不会涉及比重新分配向量 两次更多的副本。所以随意吧！

void treat(std::vector<int>& vec)
{
   // WARNING: we use a deque because of its iterator invalidation properties
   std::deque<int> deq(vec.begin(), vec.end());

   for (std::deque<int>::const_iterator it = deq.begin(); it != deq.end(); ++it)
   {
     if (it->condition()) deq.push_back(func(*it));
   }

   vec.assign(deq.begin(), deq.end());
}

Answer 5

内联注释通常足以阐明这一点，例如

for (vector<Foo>::size_type i = 0; i < vec.size() /* size grows in loop! */; ++i)
{
   if (vec[i].condition) AppendToVec(vec);
}

Answer 6

您需要随机访问该向量吗？如果不是，std::list 更合适。我个人认为，在迭代向量时附加到向量并不是一个好主意。

Answer 7

您可以追加到双端队列，而无需使其元素的迭代器无效。随机访问的效率接近向量，因此通常是替代它的不错选择。

Answer 8

和原来的没有太大区别。只是在这里明确一些事情：

for (vector<Foo>::size_type i = 0, n = vec.size(); i < n; ++i)
  if (vec[i].condition){
    AppendToVec(vec);
    n = vec.size();
  }