CODEWITHSUNDEEP
c++iterationcontainers
Long_GM
Long_GM

Reputation: 191

C++ Iterate through an expanding container

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

Upvotes: 1

Views: 962

Answers (2)

v010dya
v010dya

Reputation: 5848

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.

Upvotes: 2

nsubiron
nsubiron

Reputation: 923

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.

Upvotes: 7

Related Questions