changing vector while processing one of its elements?

Discussion in 'C++' started by Markus Dehmann, Jun 9, 2008.

  1. 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<int> s;
    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<int> tmp;
    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
     
    Markus Dehmann, Jun 9, 2008
    #1
    1. Advertising

  2. Markus Dehmann

    Kai-Uwe Bux Guest

    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<int> s;
    > 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<int> tmp;
    > 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
     
    Kai-Uwe Bux, Jun 9, 2008
    #2
    1. Advertising

  3. Markus Dehmann

    Triple-DES Guest

    On 9 Jun, 23:43, Kai-Uwe Bux <> wrote:
    > 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
     
    Triple-DES, Jun 10, 2008
    #3
  4. Markus Dehmann

    James Kanze Guest

    On Jun 9, 11:43 pm, Kai-Uwe Bux <> wrote:
    > 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<int> s;
    > > 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<int> tmp;
    > > 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:
    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
     
    James Kanze, Jun 10, 2008
    #4
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    8
    Views:
    1,927
    Csaba
    Feb 18, 2006
  2. thunk
    Replies:
    1
    Views:
    315
    thunk
    Mar 30, 2010
  3. thunk
    Replies:
    0
    Views:
    488
    thunk
    Apr 1, 2010
  4. thunk
    Replies:
    14
    Views:
    626
    thunk
    Apr 3, 2010
  5. Replies:
    8
    Views:
    159
Loading...

Share This Page