STL vectors and erase

This is a discussion on STL vectors and erase within the C++ Programming forums, part of the General Programming Boards category; Hey everybody. I understand that erasing elements in the vector invalidates the iterators. If you consider the following code: Code: ...

  1. #1
    Registered User
    Join Date
    Jun 2007
    Posts
    34

    STL vectors and erase

    Hey everybody. I understand that erasing elements in the vector invalidates the iterators. If you consider the following code:

    Code:
    #include <iostream>
    #include <vector>
    using namespace std;
    
    int main()
    {
      vector<int> vec, vec2;
      
      vec.push_back(1);
      vec.push_back(2);
      vec.push_back(3);
      vec.push_back(4);
      vector<int>::iterator it;
      vec2 = vec;
      it = vec.begin();
      for(;;)
      {
        
        vec.erase(vec.begin());
        vec = vec2;
        cout << *it << endl;
      }
      
      return 0;
    }
    It works for me if I run it, but theoretically speaking, would it be possible for the iterator it to ever become invalidated, and cause an error such as the segmentation fault? The reason I ask is because I believe I have this problem in one of my serious programs. Ideas would be cool.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,258
    it is indeed invalid as soon as you call vec.erase(). That it "works" is mere coincidence.

    EDIT:
    Oops, sorry, I think that I am wrong. The standard states that erase() "invalidates all the iterators and references after the point of the erase" (emphasis mine). Since the point of the erase is where the iterator points to, the iterator is not invalidated.
    Last edited by laserlight; 07-19-2007 at 04:35 AM.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Jun 2007
    Posts
    34
    This confirms it, thank you.

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,344
    I think it is invalid and the fact that it works is coincidence.

    >> vec = vec2;
    That line could invalidate all iterators, since vec2 could be larger than vec and new memory might need to be allocated.

    Even without that line I think that erase will invalidate the iterator. This is why erase returns an iterator, because the one you erased has been invalidated. I don't have the standard to look up more details for confirmation, though. Just because the standard says that all iterators after the erase are invalidated doesn't mean that other iterators can't also be invalidated.

  5. #5
    Registered User
    Join Date
    Apr 2006
    Posts
    2,053
    A vector will never give memory back to the OS, so as long as the vector does not grow beyond it's reserved or previously greatest size, and as long as the iterator continues to point to a valid index, there is no way the iterator can become invalidated.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Now I don't have a copy of the standard available, but I would think that quite clearly using the assignment operator on a vector would technically invalidate ALL iterators from that vector. That certainly has to be the case when they are of significantly varying sizes.

    Is the inifinite loop intentional?

    KingMir, I presume you are purposefully ignoring the "swap with a temporary vector" case in your statement?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,258
    I think Daved is right. I corrected my "it is indeed invalid as soon as you call vec.erase()" but neglected to point out that the copy assignment on the next line would then cause the iterator to become invalidated.

    There appears to be nothing explicitly mentioned in the standard about std::vector's copy assignment operator invalidating iterators, but for the insert member function: "if no reallocation happens, all the iterators and references before the insertion point remain valid". Then it is stated that the assign member function has the effect:
    Code:
    erase(begin(), end());
    insert(begin(), first, last);
    It is reasonable to say that if it has the effect of inserting from the beginning, then it has the effect of invalidating iterators from the beginning. Since copy assignment should behave like this->assign(that.begin(), that.end()), it would be reasonable to say that such iterator and reference invalidation also occurs for copy assignment.

    That said, creativeinspira wrote "this confirms it" before I could make my edit, so I suppose he/she is oblivious to the change. Heheh.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Registered User manofsteel972's Avatar
    Join Date
    Mar 2004
    Posts
    317
    Vector reallocation occurs when a member function must grow the controlled sequence beyond its current storage capacity. Other insertions and erasures may alter various storage addresses within the sequence. In all such cases, iterators or references that point at altered portions of the controlled sequence become invalid.
    http://www.dinkumware.com/manuals/?m...#vector::erase
    "Knowledge is proud that she knows so much; Wisdom is humble that she knows no more."
    -- Cowper

    Operating Systems=Slackware Linux 9.1,Windows 98/Xp
    Compilers=gcc 3.2.3, Visual C++ 6.0, DevC++(Mingw)

    You may teach a person from now until doom's day, but that person will only know what he learns himself.

    Now I know what doesn't work.

    A problem is understood by solving it, not by pondering it.

    For a bit of humor check out xkcd web comic http://xkcd.com/235/

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,258
    This is why erase returns an iterator, because the one you erased has been invalidated.
    I think the reason why that iterator is not invalidated is because it is now the "one past the last element" iterator. So it is not invalid, but it cannot be dereferenced.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User
    Join Date
    Jan 2005
    Posts
    7,344
    >> I think the reason why that iterator is not invalidated is because it is now the "one past the last element" iterator.

    This doesn't sound right. I don't think erase modifies the passed in iterator, so how would it suddenly point to one past the end?

  11. #11
    Registered User manofsteel972's Avatar
    Join Date
    Mar 2004
    Posts
    317
    Code:
        vec.erase(vec.begin());  <--there is no  reallocation so vec same capacity as vec2
        vec = vec2;                   <---copying contents of vec2 back into vec making it same as before erase no reallocation 
                                                   since capacity is not exceeded
        cout << *it << endl;
    The only reason why this works is because there is no reallocation. Since all elements are guaranteed to be contiguous in memory with a vector, the iterator should point to the same address for the first element as long as there is no reallocation. If you were to change the capacity of the vector, then reallocation will invalidate all iterators. If you erase the first element, you invalidate all the iterators after the point of erasure. The first element's address doesn't change and all the values are moved up by one. What you do is copy the original vector back into the vector you erased the first element from so the values are restored to their original state. This will not cause a reallocation because you are not exceeding the capacity. If you were to copy a larger vector that would cause reallocation, as Daved said, then it would invalidate all iterators.
    Last edited by manofsteel972; 07-22-2007 at 07:07 PM.
    "Knowledge is proud that she knows so much; Wisdom is humble that she knows no more."
    -- Cowper

    Operating Systems=Slackware Linux 9.1,Windows 98/Xp
    Compilers=gcc 3.2.3, Visual C++ 6.0, DevC++(Mingw)

    You may teach a person from now until doom's day, but that person will only know what he learns himself.

    Now I know what doesn't work.

    A problem is understood by solving it, not by pondering it.

    For a bit of humor check out xkcd web comic http://xkcd.com/235/

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,258
    This doesn't sound right. I don't think erase modifies the passed in iterator, so how would it suddenly point to one past the end?
    Oops, I forgot to edit that after I left the house, heheh. What I had in mind was what happens after a vec.erase(vec.begin(), vec.end()), but this is faulty thinking since it is the returned iterator that points one past the end in such a case.

    The only reason why this works is because there is no reallocation.
    I posit that it works by coincidence, since assignment should have the effect of the assign member function which should have the effect of invalidating all iterators.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Question about erase()
    By Sharke in forum C++ Programming
    Replies: 8
    Last Post: 06-10-2009, 02:22 AM
  2. vector problem with erase()
    By JukeBoxHero in forum C++ Programming
    Replies: 5
    Last Post: 10-03-2006, 08:02 PM
  3. vectors with same iterators
    By strickey in forum C++ Programming
    Replies: 3
    Last Post: 02-10-2005, 05:34 AM
  4. vector::pop_back & erase problems
    By codec in forum C++ Programming
    Replies: 7
    Last Post: 03-31-2004, 05:55 PM
  5. mistake in tutorial re: stl vector
    By ygfperson in forum C++ Programming
    Replies: 4
    Last Post: 04-20-2002, 12:50 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21