By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,206 Members | 1,020 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,206 IT Pros & Developers. It's quick & easy.

changing vector while processing one of its elements?

P: n/a
Hi,

I observed a behavior that I didn't expect: I have a vector of sets. I
iterate over the first of these sets, and while I iterate over it, I
add another set at the end of the vector. I thought that shouldn't
affect the first set I am iterating over, but it does, and I get a
segmentation fault.

See the example program below.

It works fine if I make set0 a *copy* of v[0], instead of a reference
or a pointer, but I would rather not copy it (this routine is called
very often in my program and I don't see why I should make an
expensive copy).

How can I fix this? Thanks!

int main(int argc, char** argv){
std::vector<std::set<int v;
std::set<ints;
s.insert(1);
s.insert(2);
v.push_back(s);
std::set<int>& set0 = v[0]; // using reference because we don't want
to copy to local var (too expensive)
for(std::set<int>::const_iterator it = set0.begin(); it !=
set0.end(); ++it){
std::cout << *it << std::endl;
std::set<inttmp;
tmp.insert(10);
v.push_back(tmp); // will be v[1], so it shouldn't change set0 or
its
iterator?
}
return 0;
}

As output I get:
1
10
1
10
1
10
....
Segmentation fault
Jun 27 '08 #1
Share this Question
Share on Google+
3 Replies


P: n/a
Markus Dehmann wrote:
Hi,

I observed a behavior that I didn't expect: I have a vector of sets. I
iterate over the first of these sets, and while I iterate over it, I
add another set at the end of the vector. I thought that shouldn't
affect the first set I am iterating over, but it does, and I get a
segmentation fault.
It does not affect the first set _as a value_. However, it affects the first
set _as an object (region of memory)_ because inserting an element into the
vector can trigger a re-allocation of the vector and then all current
elements are moved around.
>
See the example program below.

It works fine if I make set0 a *copy* of v[0], instead of a reference
or a pointer, but I would rather not copy it (this routine is called
very often in my program and I don't see why I should make an
expensive copy).

How can I fix this? Thanks!

int main(int argc, char** argv){
std::vector<std::set<int v;
std::set<ints;
s.insert(1);
s.insert(2);
v.push_back(s);
std::set<int>& set0 = v[0]; // using reference because we don't want
to copy to local var (too expensive)
You are using a reference. Insertions into a vector can invalidate all
references, pointers, and iterators into the vector (for the reasons
mentioned above).
for(std::set<int>::const_iterator it = set0.begin(); it !=
set0.end(); ++it){
std::cout << *it << std::endl;
std::set<inttmp;
tmp.insert(10);
v.push_back(tmp); // will be v[1], so it shouldn't change set0 or
its
iterator?
}
return 0;
}

As output I get:
1
10
1
10
1
10
...
Segmentation fault
Yup, that the undefined behavior from using an invalidated reference.
Your options include:

a) Use std::list instead of std::vector.
b) Instead of inserting the new sets right away, put them on hold.
c) Use std::vector< some_smart_pointer< std::set<int >.
Best

Kai-Uwe Bux
Jun 27 '08 #2

P: n/a
On 9 Jun, 23:43, Kai-Uwe Bux <jkherci...@gmx.netwrote:
Markus Dehmann wrote:
Hi,
I observed a behavior that I didn't expect: I have a vector of sets. I
iterate over the first of these sets, and while I iterate over it, I
add another set at the end of the vector. I thought that shouldn't
affect the first set I am iterating over, but it does, and I get a
segmentation fault.
[snip]
Your options include:

a) Use std::list instead of std::vector.
b) Instead of inserting the new sets right away, put them on hold.
c) Use std::vector< some_smart_pointer< std::set<int >.
Depending on your program, you may get away with
d) If possible, use the reserve() member function of vector to ensure
that no reallocation takes place.

Like this:

std::vector<std::set<int v;
v.reserve(10) // If you know beforehand that no more than 10
elements will be inserted.

Note that you can also check size() vs. capacity() to determine
whether a push_back() will trigger a reallocation (invalidating all
references)

DP
Jun 27 '08 #3

P: n/a
On Jun 9, 11:43 pm, Kai-Uwe Bux <jkherci...@gmx.netwrote:
Markus Dehmann wrote:
I observed a behavior that I didn't expect: I have a vector
of sets. I iterate over the first of these sets, and while I
iterate over it, I add another set at the end of the vector.
I thought that shouldn't affect the first set I am iterating
over, but it does, and I get a segmentation fault.
It does not affect the first set _as a value_. However, it
affects the first set _as an object (region of memory)_
because inserting an element into the vector can trigger a
re-allocation of the vector and then all current elements are
moved around.
See the example program below.
It works fine if I make set0 a *copy* of v[0], instead of a reference
or a pointer, but I would rather not copy it (this routine is called
very often in my program and I don't see why I should make an
expensive copy).
How can I fix this? Thanks!
int main(int argc, char** argv){
std::vector<std::set<int v;
std::set<ints;
s.insert(1);
s.insert(2);
v.push_back(s);
std::set<int>& set0 = v[0]; // using reference because we don't want
to copy to local var (too expensive)
You are using a reference. Insertions into a vector can
invalidate all references, pointers, and iterators into the
vector (for the reasons mentioned above).
for(std::set<int>::const_iterator it = set0.begin(); it !=
set0.end(); ++it){
std::cout << *it << std::endl;
std::set<inttmp;
tmp.insert(10);
v.push_back(tmp); // will be v[1], so it shouldn't change set0 or
its
iterator?
}
return 0;
}
As output I get:
1
10
1
10
1
10
...
Segmentation fault
Yup, that the undefined behavior from using an invalidated reference.
Your options include:
a) Use std::list instead of std::vector.
b) Instead of inserting the new sets right away, put them on hold.
c) Use std::vector< some_smart_pointer< std::set<int >.
d) Use v[0] each time you need it, rather than saving the
reference.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Jun 27 '08 #4

This discussion thread is closed

Replies have been disabled for this discussion.