CODEWITHSUNDEEP
c++stl
JRM
JRM

Reputation: 1184

Appending to a vector while iterating over it?

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.

Upvotes: 24

Views: 14480

Answers (8)

JDiMatteo
JDiMatteo

Reputation: 13130

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

Upvotes: 1

Kristopher Johnson
Kristopher Johnson

Reputation: 82535

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.

Upvotes: 20

Agnel Kurian
Agnel Kurian

Reputation: 59456

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

Upvotes: -1

Matthieu M.
Matthieu M.

Reputation: 299750

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

Upvotes: 1

ergosys
ergosys

Reputation: 49019

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.

Upvotes: 0

Jacob
Jacob

Reputation: 34601

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

Upvotes: 5

sbi
sbi

Reputation: 224039

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.

Upvotes: 14

Collin Dauphinee
Collin Dauphinee

Reputation: 13973

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.

Upvotes: 0

Related Questions