Appending to a vector while iterating over it?

Question

I have a vector that I am iterating over. While iterating, I may append new values to the vector. It looks something like:

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

This works fine, and in fact elegantly handles the case where the newly appended elements recursively require even more elements to be added, but it feels a little fragile. If someone else comes along and tweaks the loop, it can easily be broken. For example:

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

or

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

Are there any best practices to handle cases like this? Is commenting the loop with a "Warning: This loop is intentionally appends to the vector while iterating. Change cautiously" the best approach? I am open to switching containers too if that makes things more robust.

Answer 1

Do you need random access to this vector? If no, an std::list is more appropriate. It's my personal opinion that appending to a vector while iterating over it isn't a good idea.

Answer 2

Allow AppendToVec to update i if vec has been reallocated by using the relative position in the old vector (i-vec.begin()).

Code:

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

Output:

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

Answer 3

My own approach to this is often to create a queue to which I add any new elements, and then at the end of iterating over the original container, process the elements in the queue and/or append them to the original.

The main good points to this approach are that what is going on is obvious, and it works in scenarios where multiple threads could be enqueuing new elements.

Answer 4

If someone else comes along and tweaks the loop, it can easily be broken.

Then don't use a for loop, use a while loop instead. For me, a for loop always implies a simple, iterative loop using a counter. However, if I encounter a while loop, I feel like things must have been too complicated to to express them in a simple for loop. I will look closer and I'm more careful with "optimizing" while loops than with for loops.

Answer 5

You can append to a deque without invalidating iterators to its elements. Random access is close to the efficiency of vector, so its often a good choice to replace it.

Answer 6

As has been pointed out, and as you sensed, there is an issue here. You have several possible solutions though, so don't charge blindly.

• A big fat comment at the top of the loop, with the WARNING tag or whatever your coding standard requires, to warn future maintainer that there is a trickery involved. Best not used, but could work.
• If you are able to know in advance how many elements will be added (or you have a relatively tight upper bound), you can use reserve and prevent reallocation altogether.
• Using a std::deque. Most of the performance characteristics are similar, however you can prepend and append new values without invalidating iterators / references etc... looks like the natural fit here
• Using a separate queue and a double loop

I think that deque is the better solution here. It fits your algorithm and you don't have to worry about the issues. You could probably replace most of the vector in your code by deque. And if you don't want to change the interface:

• Copy the vector into the deque
• Compute
• Assign the deque content into the vector

won't involve much more copies than just reallocating the vector twice. So feel free!

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 7

Not too different from the original. Just making a few things explicit here:

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