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

L

linq936

Hi,
The following is a psudo code to describe my question:

vector<int> ints;
vector<int>::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.
 
A

Alan Johnson

Hi,
The following is a psudo code to describe my question:

vector<int> ints;
vector<int>::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<int> ints;
vector<int>::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.
 
A

Alan Johnson

Hi,
The following is a psudo code to describe my question:

vector<int> ints;
vector<int>::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).
 
R

Richard Herring

In message <[email protected]>,

[top-posting corrected]
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.
 
R

rossum

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.
If the maximum possible size is known in advance, then a call to
reserve() would avoid the possibility of reallocation during the loop.

rossum
 
G

Gernot Frisch

vector<int> ints;
vector<int>::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<int>::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!!!
}
 
R

Richard Herring

Gernot Frisch said:
instead of iterators you could use indices:

So where are they? I don't see anything looking like ints 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<int>::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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top