445,918 Members | 2,258 Online Need help? Post your question and get tips & solutions from a community of 445,918 IT Pros & Developers. It's quick & easy.

# Can I dynamically add new elements to vector while looping it?

 P: n/a Hi, The following is a psudo code to describe my question: vector ints; vector::iterator itr; while (itr != ints.end()){ int j = some_function(*i); if (j>0){ ints.push_back(j); } ints.erase(itr); } Can it work? I dynamically add new element into a vector while I am looping the vector. Jun 13 '06 #1
7 Replies

 P: n/a Because it pushes the new element into tail of vector, that is OK! li*****@hotmail.com wrote: Hi, The following is a psudo code to describe my question: vector ints; vector::iterator itr; while (itr != ints.end()){ int j = some_function(*i); if (j>0){ ints.push_back(j); } ints.erase(itr); } Can it work? I dynamically add new element into a vector while I am looping the vector. Jun 13 '06 #2

 P: n/a li*****@hotmail.com wrote: Hi, The following is a psudo code to describe my question: vector ints; vector::iterator itr; while (itr != ints.end()){ int j = some_function(*i); if (j>0){ ints.push_back(j); } ints.erase(itr); } Can it work? I dynamically add new element into a vector while I am looping the vector. In general the answer is no. If insert causes reallocation to happen (because it causes size() to exceed capacity()), then your iterator itr will become invalid. In your specific case, it looks as if you always decrease the size by 1 during a loop iteration, and sometimes increase the size by 1 (for a net change of 0). I suggest you move the erase call ahead of the push_back, in which case you can be certain that the size never increases during an iteration, which will make the reallocation behavior predictable. That is: vector ints; vector::iterator itr; while (itr != ints.end()){ int j = some_function(*i); ints.erase(itr); if (j>0){ ints.push_back(j); } } Note that in your version, during the first iteration of the loop the size of the vector may increase, which may cause reallocation, which may invalidate your iterator. -- Alan Johnson Jun 13 '06 #3

 P: n/a li*****@hotmail.com wrote: Hi, The following is a psudo code to describe my question: vector ints; vector::iterator itr; while (itr != ints.end()){ int j = some_function(*i); if (j>0){ ints.push_back(j); } ints.erase(itr); } Can it work? I dynamically add new element into a vector while I am looping the vector. As an additional note to my other response, if your problem allows it, you might consider going through the vector in reverse order. The complexity of erase is linear in the number of elements after the one you are erasing, meaning that going forward through the vector erasing elements is an O(n^2) algorithm, but going through it in reverse would be O(n). -- Alan Johnson Jun 13 '06 #4

 P: n/a In message <11*********************@h76g2000cwa.googlegroups. com>, Sharpdew writes [top-posting corrected] li*****@hotmail.com wrote: Hi, The following is a psudo code to describe my question: vector ints; vector::iterator itr; itr = ints.begin(); while (itr != ints.end()){ int j = some_function(*i); int j = some_function(*itr); if (j>0){ ints.push_back(j); } ints.erase(itr); itr = ints.erase(itr); } Can it work? I dynamically add new element into a vector while I am looping the vector.Because it pushes the new element into tail of vector, that is OK! Wrong. The call of erase(itr) invalidates itr, and push_back() may trigger a reallocation, invalidating all iterators. -- Richard Herring Jun 13 '06 #5

 P: n/a On Mon, 12 Jun 2006 23:25:34 -0700, Alan Johnson wrote: li*****@hotmail.com wrote: Hi, The following is a psudo code to describe my question: vector ints; vector::iterator itr; while (itr != ints.end()){ int j = some_function(*i); if (j>0){ ints.push_back(j); } ints.erase(itr); } Can it work? I dynamically add new element into a vector while I am looping the vector.In general the answer is no. If insert causes reallocation to happen(because it causes size() to exceed capacity()), then your iterator itrwill become invalid. If the maximum possible size is known in advance, then a call to reserve() would avoid the possibility of reallocation during the loop. rossum In your specific case, it looks as if you always decrease the size by 1during a loop iteration, and sometimes increase the size by 1 (for a netchange of 0). I suggest you move the erase call ahead of the push_back,in which case you can be certain that the size never increases during aniteration, which will make the reallocation behavior predictable. That is: vector ints; vector::iterator itr; while (itr != ints.end()){ int j = some_function(*i); ints.erase(itr); if (j>0){ ints.push_back(j); } }Note that in your version, during the first iteration of the loop thesize of the vector may increase, which may cause reallocation, which mayinvalidate your iterator. Jun 13 '06 #6

 P: n/a vector ints; vector::iterator itr; while (itr != ints.end()){ int j = some_function(*i); if (j>0){ ints.push_back(j); } ints.erase(itr); } instead of iterators you could use indices: int count = (int)ints.size(); while(itr != ints.begin() + count) { vector::iterator ii(ints.begin() + i); int j=some_function(*ii); if(j>0) ints.push_back(j); ints.erase(itr); // Now you want a --i; as well!!! } Jun 13 '06 #7

 P: n/a In message <4f*************@individual.net>, Gernot Frisch writes vector ints; vector::iterator itr; while (itr != ints.end()){ int j = some_function(*i); if (j>0){ ints.push_back(j); } ints.erase(itr); }instead of iterators you could use indices: So where are they? I don't see anything looking like ints[i] anywhere in the following, and it's still full of iterators. How is it supposed to be an improvement?int count = (int)ints.size();while(itr != ints.begin() + count) That's no different from saving the value of ints.end() and comparing against the saved value. And itr hasn't been initialised yet. { vector::iterator ii(ints.begin() + i); int j=some_function(*ii); if(j>0) ints.push_back(j); push_back() can invalidate all iterators. The following line is now UB. ints.erase(itr); // Now you want a --i; as well!!! erase(itr) invalidates itr. The idiom is itr = ints.erase(itr) which leaves itr pointing to the element after the one erased, or ints.end() if there is no such element. } -- Richard Herring Jun 13 '06 #8

### This discussion thread is closed

Replies have been disabled for this discussion. 