CODEWITHSUNDEEP
c++vectorstliteratorruntime-error
user13561240
user13561240

Reputation:

why am i getting: "cannot seek vector iterator after end"

So I am trying to solve josephus problem using c++

First input is number of people and second is position for killing next person

I am getting run-time error as: "cannot seek vector iterator after end"

code:

// josephus.cpp : This file contains the 'main' function. Program execution begins and ends there.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int people = 0, pos = 0;

    cin >> people >> pos;

    vector<int> vp;

    for (int i = 1; i <= people; ++i)
    {
        vp.push_back(i);
    }

    int index = 0;

    while (vp.size() != 1)
    {

        index += pos - 1;

        if (index >= vp.size())
        {
            index -= vp.size();
        }

        vp.erase(vp.begin() + index);
        
    }

    cout << vp[0] << endl;
    return 0;
}

Funny thing is for input data 10 3 (people = 10, pos = 3) there is no error. It gives correct answer 4.

But for input 94 31 (people = 94, pos = 31) It gives me run-time error. I think problem occurs at erase function.

I have tried everything I can. Any help is appreciated.

Upvotes: 1

Views: 2215

Answers (2)

Vlad from Moscow
Vlad from Moscow

Reputation: 310940

The program has undefined behavior because according to the requirements for sequence containers the argument of the member function erase shall be a valid dereferenceable iterator. However due to this statement

index += pos - 1;

the value of index can be greater than or equal to the value of the expression 2 * ( current size of the vector).

In this case in the next if statement

    if (index >= vp.size())
    {
        index -= vp.size();
    }

index will get a value that is greater than or equal to the value of vp.size().

As a result this call

vp.erase(vp.begin() + index);

will not use a valid dereferenceable iterator.

Upvotes: 1

user13690398
user13690398

Reputation:

As 1201ProgramAlarm mentions is the comments, index can be greater than vp.size(), which means that when you try to erase vp.begin() + index, it will fail because there is no element after vp.end() - 1. vp.begin() and vp.end() are iterators, so when you try to seek an iterator after end (vp.end()), it fails tells you exactly that.

Upvotes: 0

Related Questions