Re: vector iterator invalidity

Discussion in 'C++' started by klaas, Aug 28, 2003.

  1. klaas

    klaas Guest

    Alf P. Steinbach wrote:
    > On Thu, 28 Aug 2003 01:36:54 +0200, klaas <> wrote:
    >if I had an array of vector<int>
    >and I would do this
    >
    >vector<int> foo[100];
    >foo[30].push_back(2);
    >foo[30].push_back(3);
    >
    >vector<int>::iterator f=foo[30].begin();
    >
    >foo[29].push_back(*f);
    >foo[30].erase(f); //<- this gives a problem with segmentation

    |In that case your compiler, or implementation of the standard library,
    |or both, are broken.

    >>would I get in trouble if foo[29]'s size had to be changed?


    |No.
    >and actually it can't be modified without modifying all the elements if
    >>it would have to be array semantics correct, true?


    |Not true.

    but how come that object in an array can arbitrarily altered in size?
    when I do:
    vector<int>* iterator = &foo[29];

    then when I increment iterator as in:
    iterator++;

    is the value of iterator not incremented by size_of(vector<int>), to
    point to the next vector<int>?
    meaning
    iterator++ does
    iterator=iterator+size_of(vector<int>).

    if this is not the case, how is such a structure manged internally?
    because the code really hangs on the erase part...

    following is the codepiece and an attempt in duplicating the stacktrace,
    you can see it hangs in memmove??!!

    any illumination possible with this info?

    regards,

    klaas

    for(vector<int>::iterator f=B[aaa].begin();
    229 f != B[aaa].end();
    230 f++
    231 )
    232 {if((*f)==linked_vertex)
    233 {/*here the opposite goes as for when it
    234 should be in gain hash A. So put this
    235 vertex in a gainhash that's two levels
    236 up instead of down*/
    237 B[aaa+2].push_back(*f);//<-no, not that line, it checks the offset
    238 B[aaa].erase(f);//<-this line :-(
    239 }
    240 }

    stacktrace:
    main
    genepool<parse_graph, truncation, hamming_one_point, simple_mutation,
    cut_size, std::vector<int, std:: allocator<int> >, ...
    truncation<std::pair<state<simple_mutation,hamm...
    Fiduccia_Mattheyses<std::pair..
    Fiduccia_Mattheyses<std::pair..

    leads to this erase statement :-(
    std::vector<int, std::allocator<int>
    >::erase(__gnu_cxx::__normal_iterator<int*, std::vector<int,

    std::allocator<int> > >)
    __gnu_cxx...
    __gnu_cxx...
    __gnu_cxx...
    int * std::__copy_aux2<int>(int*,int*,__truetype)
    int * std::__copy_aux2<int>(int const*,int const*,int *)
    memmove
    klaas, Aug 28, 2003
    #1
    1. Advertising

  2. klaas

    klaas Guest

    klaas wrote:

    > Alf P. Steinbach wrote:
    > > On Thu, 28 Aug 2003 01:36:54 +0200, klaas <> wrote:
    > >if I had an array of vector<int>
    > >and I would do this
    > >
    > >vector<int> foo[100];
    > >foo[30].push_back(2);
    > >foo[30].push_back(3);
    > >
    > >vector<int>::iterator f=foo[30].begin();
    > >
    > >foo[29].push_back(*f);
    > >foo[30].erase(f); //<- this gives a problem with segmentation

    > |In that case your compiler, or implementation of the standard library,
    > |or both, are broken.
    >
    > >>would I get in trouble if foo[29]'s size had to be changed?

    >
    > |No.
    > >and actually it can't be modified without modifying all the elements if
    > >>it would have to be array semantics correct, true?

    >
    > |Not true.
    >
    > but how come that object in an array can arbitrarily altered in size?
    > when I do:
    > vector<int>* iterator = &foo[29];
    >
    > then when I increment iterator as in:
    > iterator++;
    >
    > is the value of iterator not incremented by size_of(vector<int>), to
    > point to the next vector<int>?
    > meaning
    > iterator++ does
    > iterator=iterator+size_of(vector<int>).
    >
    > if this is not the case, how is such a structure manged internally?
    > because the code really hangs on the erase part...


    The reason I ask this is because vector::erase is defined as:
    from stl_vector.h
    645 iterator erase(iterator __position) {
    646 if (__position + 1 != end())
    647 copy(__position + 1, end(), __position);
    648 --_M_finish;
    649 _Destroy(_M_finish);
    650 return __position;
    651 }

    well if also foo[30] would be reallocated then after
    foo[29].push_back(*f);

    f would not anylonger point to the offset in foo[30],
    so as a consequence also not __position + 1 == end()
    then the lot would copy(__invalid memory +1. end(), to invalid memory)
    now end will probably give a value really from foo[30] but f nolonger.
    then memmove can't succeed so...

    real code once again:
    for(vector<int>::iterator f=B[aaa].begin();
    229 f != B[aaa].end();
    230 f++
    231 )
    232 {if((*f)==linked_vertex)
    233 {/*here the opposite goes as for when it
    234 should be in gain hash A. So put this
    235 vertex in a gainhash that's two levels
    236 up instead of down*/
    237 B[aaa+2].push_back(*f);//<-no, not that line, it checks the

    **question:
    how can f be invalidated if B[aaa+2].push_back(*f), does not cause any
    change in B[aaa], considering the code from erase ?

    offset
    238 B[aaa].erase(f);//<-this line
    239 }
    240 }

    stacktrace:
    main
    genepool<parse_graph, truncation, hamming_one_point, simple_mutation,
    cut_size, std::vector<int, std:: allocator<int> >, ...
    truncation<std::pair<state<simple_mutation,hamm...
    Fiduccia_Mattheyses<std::pair..
    Fiduccia_Mattheyses<std::pair..

    leads to this erase statement
    std::vector<int, std::allocator<int>
    >::erase(__gnu_cxx::__normal_iterator<int*, std::vector<int,

    std::allocator<int> > >)
    __gnu_cxx...
    __gnu_cxx...
    __gnu_cxx...
    int * std::__copy_aux2<int>(int*,int*,__truetype)
    int * std::__copy_aux2<int>(int const*,int const*,int *)
    memmove
    klaas, Aug 28, 2003
    #2
    1. Advertising

  3. On Thu, 28 Aug 2003 03:22:14 +0200, klaas <> wrote:

    >klaas wrote:
    >
    >> Alf P. Steinbach wrote:
    >> > On Thu, 28 Aug 2003 01:36:54 +0200, klaas <> wrote:
    >> >if I had an array of vector<int>
    >> >and I would do this
    >> >
    >> >vector<int> foo[100];
    >> >foo[30].push_back(2);
    >> >foo[30].push_back(3);
    >> >
    >> >vector<int>::iterator f=foo[30].begin();
    >> >
    >> >foo[29].push_back(*f);
    >> >foo[30].erase(f); //<- this gives a problem with segmentation

    >> |In that case your compiler, or implementation of the standard library,
    >> |or both, are broken.
    >>
    >> >>would I get in trouble if foo[29]'s size had to be changed?

    >>
    >> |No.
    >> >and actually it can't be modified without modifying all the elements if
    >> >>it would have to be array semantics correct, true?

    >>
    >> |Not true.
    >>
    >> but how come that object in an array can arbitrarily altered in size?
    >> when I do:
    >> vector<int>* iterator = &foo[29];
    >>
    >> then when I increment iterator as in:
    >> iterator++;
    >>
    >> is the value of iterator not incremented by size_of(vector<int>), to
    >> point to the next vector<int>?
    >> meaning
    >> iterator++ does
    >> iterator=iterator+size_of(vector<int>).
    >>
    >> if this is not the case, how is such a structure manged internally?


    A std::vector uses dynamically allocated memory for its internal buffer,
    at least when the logical size grows beyond an initial buffer size.



    >> because the code really hangs on the erase part...


    In the original posting you had no loop.

    You then amended that to include a loop, plus more.

    That's an entirely different situation; in the loop you're
    using an iterator after erasing the element it points to.



    >The reason I ask this is because vector::erase is defined as:
    >from stl_vector.h
    >645 iterator erase(iterator __position) {
    >646 if (__position + 1 != end())
    >647 copy(__position + 1, end(), __position);
    >648 --_M_finish;
    >649 _Destroy(_M_finish);
    >650 return __position;
    >651 }


    The internal implementation of erase is of no concern.
    Alf P. Steinbach, Aug 28, 2003
    #3
  4. klaas

    klaas Guest

    Alf P. Steinbach wrote:

    >
    > You then amended that to include a loop, plus more.
    >
    > That's an entirely different situation; in the loop you're
    > using an iterator after erasing the element it points to.
    >

    yes that's it, I should have seen that, thanks

    klaas
    klaas, Aug 28, 2003
    #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. pmatos
    Replies:
    6
    Views:
    23,723
  2. Replies:
    8
    Views:
    1,890
    Csaba
    Feb 18, 2006
  3. Rajesh S R

    Validity/Invalidity of the code

    Rajesh S R, Mar 24, 2007, in forum: C Programming
    Replies:
    1
    Views:
    309
    =?utf-8?B?SGFyYWxkIHZhbiBExLNr?=
    Mar 24, 2007
  4. Javier
    Replies:
    2
    Views:
    542
    James Kanze
    Sep 4, 2007
  5. zl2k
    Replies:
    27
    Views:
    1,550
    Francesco S. Carta
    Sep 7, 2010
Loading...

Share This Page