1

What will happen if I expand a container while iterating through it, may I meet the new elements or just the old ones

std::vector<int> arr(0);
arr.push_back(1);
arr.push_back(2);
arr.push_back(3);

for (auto& ele : arr) {
    if (4 == ele) std::cout << "meet new eles" << endl;
    arr.push_back(4);
}
Long_GM
  • 181
  • 1
  • 10
  • 1
    Adding items to a vector generally invalidates all iterators, and the range-for loop is implemented using iterators. So this example will lead to *undefined behavior*. – Some programmer dude Sep 25 '15 at 07:06
  • 1
    Even if the behaviour for this scenario were well defined: doing this would make your code more difficult to maintain. Anyone maintaining this code at a later date would have to ask the same question as you to understand what the code is doing. I strongly recommend keeping things simple by first preparing the changes you want make during iteration. Then applying those changes as a separate step. – Disillusioned Sep 25 '15 at 07:39

2 Answers2

7

push_back may invalidate any iterator to the vector, what you have there is undefined behaviour.

std::vector internally allocates an array with its elements stored contiguously in memory. To do so it needs to preallocate an estimate of the size it may need, that's known as the capacity of the vector. At push_back if the capacity is reached it allocates a new bigger array, copies/moves all the contents of the previous array to the new one and then deletes the old one. That invalidates the iterators, that keep pointing to a deleted array.

Also worth mentioning that the allocation of the new array adds a considerable performance hit. If you know the size that your vector will have always use reserve() to preallocate memory.

Now, true is that if you reserve capacity before hand and never push back exceeding that capacity the iterators won't be invalidated (only the past-end iterator) and you can keep incrementing them since they point to an array of contiguous elements. But I wouldn't advice to do so, IMO the risk of reallocating the vector by mistake is not worth it.

nsubiron
  • 913
  • 4
  • 15
2

If you are guaranteed to never remove elements the simplest solution would still be to use a regular for loop.

for(size_t i=0, n=arr.size(); i<n; ++i)
{
  if(/* something */)
  {
    arr.push_back(/* ... */);
    ++n;
  }
}

I know it's a trivial solution, but others maybe searching and will find this question.

Good note from @Long_GM. This will not work on every container. std::map for example cannot be iterated in this manner whether or not you insert any values.

v010dya
  • 5,296
  • 7
  • 28
  • 48
  • Why not `if(size_t i=0; i – DawidPi Sep 25 '15 at 08:39
  • @DawidPi Because you are not calling a function on each loop. And removing is a completely different thing, since you need to check where the removal happens (before or after your position). But i agree with the fact that i probably should be size_t, so i'll change the code now. – v010dya Sep 25 '15 at 08:50
  • True. Didn't think of removing items from the middle of the vector since it's generally bad idea, I think that using iterators may also present problem with deleting items before current position? Am I right? – DawidPi Sep 25 '15 at 08:55
  • 1
    the standard way to iterate STL container should be **for(auto it=arr.begin(), it != arr.end(); ++it) ...** though you code still work as will, this style is more general, you can switch to other containers such as **std::map** without modifying the iteration code block – Long_GM Sep 25 '15 at 08:59
  • ***the standard way to iterate STL container should be for(auto it=arr.begin(), it != arr.end(); ++it) ... though you code still work as will*** Doesn't that get into the same iterator invalidation? – drescherjm Oct 06 '20 at 18:33