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.

Solution 1

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

The 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.

Solution 2

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.

Solution 3

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

Solution 4

An inline comment is often enough to make this clear, e.g.

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

Solution 5

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

View more solutions

Comments

[tenfour]

inserting into a vector will invalidate your iterators; there's no way around that. and you can't prevent people from writing code that breaks things. your original way is the best way to do this.

[Harsh Pathak]

My answer stackoverflow.com/questions/3443434/… bypasses this problem.

[rubenvb]

This is exactly the use case I asked this question for: stackoverflow.com/questions/3175972/…

[Martin York]

The only way to prevent subsequent developers breaking your code is to use unit tests (regression tests). Then make sure that the unit tests are run and pass before the code is checked into source control.

[kevinthompson]

I'm not sure that the iterator i will stay valid after something gets appended.

[endorphin]

@Kristopher Johnson: It won't if the vector re-allocates. If it doesn't re-allocate, he'll probably get away with it.

[Harsh Pathak]

The whole point of passing i is to use the relative information to update it in the new vector.

[Admin]

Don't. Changing the container contents will invalidate the iterators, and may cause your program to crash.

[kevinthompson]

FWIW, I wrote my comment before Jacob added the new definition for AppendToVec(). If he is updating the iterator properly there, then maybe it will work, but the fact that I can't tell at a glance whether it is right is troubling to me.

[Ben Voigt]

I don't think I would use the name diff for the index, but the new code is correct.

[Harsh Pathak]

@All: I hadn't included the definition for AppendToVec but I figured my description of it would be enough. The code merely implements what I suggested.

[JRM]

I don't need random access, so a list would work. My only concern would be in the stability of end(). I'd guess that the following would be undefined behaviour: list<Foo>::iterator end = myList.end(); for (list<Foo>::iterator i = myList.begin(); i != end; ++i) { if (myList->condition) AppendToList(myList); } Yeah, it's probably unlikely to happen, but I'd like to write the most robust code I can, and doing something unusual like appending while iterating seems to lead to code that's ripe for errors.

[JRM]

I think this is very true. Seeing while certainly makes someone think twice.

[Matthieu M.]

std::list is the container you don't want to use. It really is the last resort container because of its performance characteristics and is only useful for the O(1) splice method, when appropriate.

[Sjoerd]

+1. I would add a comment "size() could change in the loop, so do not cache it" on the line above the while, to explain why a simple for wouldn't do.

[Sjoerd]

deque::push_back() can invalidate iterators, so it's as bad as a vector in this case. (It's true that deque::push_back() will not invalidate references to elements - but we cannot use that fact in this case).

[StuartLC]

+1 - Take a leaf out of the managed .NET collections (which will throw exceptions if changed during iteration) - the iterator is invalidated as soon as the contents of the collection changes.