473,327 Members | 1,919 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,327 software developers and data experts.

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

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.

Jun 13 '06 #1
7 6529
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<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.


Jun 13 '06 #2
li*****@hotmail.com wrote:
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.

--
Alan Johnson
Jun 13 '06 #3
li*****@hotmail.com wrote:
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).

--
Alan Johnson
Jun 13 '06 #4
In message <11*********************@h76g2000cwa.googlegroups. com>,
Sharpdew <sh**********@gmail.com> writes

[top-posting corrected]
li*****@hotmail.com wrote:
Hi,
The following is a psudo code to describe my question:

vector<int> ints;
vector<int>::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
On Mon, 12 Jun 2006 23:25:34 -0700, Alan Johnson
<al****@no.spam.stanford.edu> wrote:
li*****@hotmail.com wrote:
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.

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 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.


Jun 13 '06 #6
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!!!
}


Jun 13 '06 #7
In message <4f*************@individual.net>, Gernot Frisch
<Me@Privacy.net> writes
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:


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<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.
}


--
Richard Herring
Jun 13 '06 #8

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
by: John Black | last post by:
Hi, I just found out that in looping the vector, you can not push_back() to the vector even in some "safe" cases. Here is the code snippet, vector<pair<UINT32, UINT32> >::iterator itr; for (itr...
3
by: Brett Irving | last post by:
Hi people, was curious if there was a way to change all the elements in a vector without having to loop through and access every one and then change them. for example. I have a vector that is 10...
6
by: Matthias | last post by:
Hi, say I have a vector v1: std::vector<SomeType> v1; and I need a vector v2 of pointers to v1's elements: std::vector<SomeType*> v2;
10
by: The Cool Giraffe | last post by:
I got a hint recently (guess where, hehe) and was directly pointed to the vector class. Now, i have no issues using that way but i'm concerned about the performance issue. Which is fastest...
16
by: kaferro | last post by:
What is the typical way to loop through a vector while deleting certain elements during the loop process? The code below works, but I am wondering if there is a better solution. ...
10
by: Jess | last post by:
Hello, I have a program that stores dynamically created objects into a vector. #include<iostream> #include<vector> using namespace std;
8
by: Ray D. | last post by:
I'm trying to write a C function to compute the compressed row storage (CRS) vectors of a 2-d matrix. This is used primarily for increasing computing efficiency of matrices whose main elements are...
10
by: arnuld | last post by:
It is quite an ugly hack but it is all I am able to come up with for now :-( and it does the requires work. I want to improve the program, I know you people have much better ideas ;-) /* C++...
3
by: Samant.Trupti | last post by:
HI, I want to dynamically allocate array variable of type LPWSTR. Code looks like this... main() { LPWSTR *wstr; int count = Foo (wstr); for (int i = 0; i < count; i++) //print each...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.