C++：cannot seek vector iterator before begin

Question

I was doing a uva problem uva 10935 throwing cards away, and my code is as follows. when i ran it, it said An unhandled exception was raised: read access conflict, and it also shows "cannot seek vector iterator before begin", i don't know where is the problem in my code:

#include<vector>
#include<iostream>
using namespace std;
int n;
vector<int> out;


int main() {
    freopen("data.txt", "r", stdin);
    while (scanf("%d", &n) == 1 && n) {
        vector<int> cards;
        for (int i = 1; i <= n; i++)cards.push_back(i);
        vector<int>::iterator it = cards.begin();
        vector<int>::iterator end = cards.end();
        while (it != (end-1)) {
            out.push_back(*it);
            it++;
            cards.push_back(*it);
            it++;
            end++;
        }
        cout << "Discarded cards: ";
        for (int j = 0; j < out.size(); j++) {
            if(j!=(out.size()-1))cout << out[j] << ", ";
            else cout << out[j] << endl;

        }
        cout << "Remaining card: " << *it << endl;
    }
    return 0;
}

Answer 1

I think there is a problem with end++, and others iterators.

If the vector cards grows, its memory location may be changed, and end++ will be pointing to an invalide position. Similar happens with it++.

I propose you to use lists instead:

#include<bits/stdc++.h>
using namespace std;
int n;

int main() {
    //freopen("a.in", "r", stdin);

    while (scanf("%d", &n) == 1 && n) {

        list<int> out;

        list<int> cards;
        for (int i = 1; i <= n; i++)
          cards.push_back(i);
        list<int>::iterator it = cards.begin();

        list<int>::iterator end = cards.end();
        end--;
        while (it != (end)) {
            out.push_back(*it);
            it++;
            cards.push_back(*it);
            it++;
            end++;
        }
        cout << "Discarded cards: ";
        list<int>::iterator it2 = out.begin();
        for (int j = 0; j < out.size(); j++, it2++) {
            if(j !=(out.size()-1))
               cout << *it2 << ", ";
            else
              cout << *it2 << endl;
        }
        cout << "Remaining card: " << *it << endl;
    }
    return 0;
}

NOTE: I haven't read the UVA problem.

Answer 2

The problem here remains in the while() loop, where you are pushing new element in the vector while holding it's old "end" address as terminal reference.

When a vector pushes a new element, it may need to reallocate it's whole array to a new location. In that case, the "end" reference that you are holding will become obsolete as you are increasing it linearly, but the whole vector after that push may have shifted somewhere else.

I added some debug lines in your code, so you can see how this happens. Just run the code with an input value of 4. And you will see the "end" value probably will not relate with the vector's reallocated address anymore (if reallocation happens, it basically depends on the system to decide).

#include<vector>
#include<iostream>
using namespace std;
int n;
vector<int> out;

void printVectorElementAddresses(vector<int> &v){
    cout<<"==== Vector Element Addresses ====\n";
    for(auto itr = v.begin(); itr != v.end(); itr++)
    {
        cout<<&(*itr);
        if(itr == v.end()-1){
            cout<<endl;
        }
        else{
            cout<<" ";
        }
    }
    cout<<endl;
}

void printIteratorAddressWithTag(char* tag, vector<int> :: iterator & it, bool printNewLine){
    cout<<tag<<&*it<<"; ";
    if(printNewLine){
        cout<<endl;
    }
}

int main() {
//    freopen("data.txt", "r", stdin);
    while (scanf("%d", &n) == 1 && n) {
        vector<int> cards;
        for (int i = 1; i <= n; i++)cards.push_back(i);
        vector<int>::iterator it = cards.begin();
        vector<int>::iterator end = cards.end();

        //print vector addresses after initial pushes are done
        printVectorElementAddresses(cards);

        while (it != (end-1)) {
            printIteratorAddressWithTag("it initial = ", it, false);
            out.push_back(*it);
            it++;

            printIteratorAddressWithTag("it after first increment = ", it, false);
            cards.push_back(*it);
            it++;

            printIteratorAddressWithTag("it after second increment = ", it, true);

            printIteratorAddressWithTag("end initially in loop = ", end, false);
            end++;

            printIteratorAddressWithTag("end after increment = ", end, true);

            cout<<"Vector Addresses after a new push"<<endl;
            printVectorElementAddresses(cards);
        }
        cout << "Discarded cards: ";
        for (int j = 0; j < out.size(); j++) {
            if(j!=(out.size()-1))cout << out[j] << ", ";
            else cout << out[j] << endl;

        }
        cout << "Remaining card: " << *it << endl;
    }
    return 0;
}

Just change the logic in your while loop to keep track of the old "end" reference after the push happens. And if the other logic are fine, it should work.