Problem with Iterators

[agajantorayev]

I got an unusual problem, source code is:

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

int main()
{
    ifstream fin("beads.in");
    ofstream fout("beads.out");
    int n;
    char c;
    fin>>n;
    vector<char> beads;
    for(int i=0; i<n; i++) {fin>>c; beads.push_back(c);}
    
    typedef vector<char>::iterator iter;
    for(int i=0; i<n; i++){
            iter it=beads.begin();
            beads.push_back(*it);
            beads.erase(it);//bug
                           }
}

this program runs for all values of n except 8, but it does not run for n=8.
when I replace
beads.erase(it);//bug by
beads.erase(beads.begin());//OK
it runs for all values of n.
Can anyone explain why when I use
beads.erase(it);//bug
it does not run just for n=8?????

[Mythios]

I'm going to presume your beads.in file looks something like:

8
a
b
c
d
e
f
g
h

If thats the case I'm not getting any problems with your code. In you're loop all you are doing is making your iterator equal the first char in your vector. Push back a copy of what ever the first char is to the back of the vector. Then delete the char you pushed back at the end of the vector?

[Disch]

it's just dumb luck that it was working at all.

Whever you add/remove elements from a vector, all existing iterators become invalid.

Therefore:

    for(int i=0; i<n; i++){
            iter it=beads.begin();
            beads.push_back(*it);  // <- since we're adding an element to 'beads'
                // now 'it' is invalid (like a bad pointer) and must not be used
            beads.erase(it); // therefore this is a bug -- we're trying to call erase with a bad iterator 

The reason for this is because vectors guarantee the data remains contiguous in memory. Therefore when you add/remove elements, the vector might have to copy the entire chunk of data to somewhere else in memory in order to make sure it's all still contiguous.

Existing iterators are unaware that the data has been moved, and therefore may be left "pointing" to data that no longer exists.

EDIT:

Also note, not all containers have this problem. If you need iterators to remain valid between element additions/removals, you can consider other containers, like std::list.

[Mythios]

Disch wrote:

If you need iterators to remain valid between element additions/removals, you can consider other containers, like std::list.

I didn't realize they worked that much different from one another. Thanks, I learn't something new today Woohoo, Thanks Disch :D