STL vectors and erase

[creativeinspira]

Hey everybody. I understand that erasing elements in the vector invalidates the iterators. If you consider the following 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.

[laserlight]

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.

[creativeinspira]

This confirms it, thank you.

[Daved]

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.

[King Mir]

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.

[iMalc]

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?

[laserlight]

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:

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.

[manofsteel972]

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

[laserlight]

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.

[Daved]

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

[manofsteel972]

    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.

[laserlight]

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.