How to iterate a list and erase from it?

Question

I'm having a lot of trouble with List iterators, and I asked a question previously but was not able to get the solution I was looking for.

I have a circular list, and I must replace the value of node n with node n + (step). I must then erase node n + (step). When I erase it puts the iterator to the element after the erased element. I need the iterator back at node n. How the heck can I do this because everytime I erase n + (step) I get an invalid iterator. My input is 5 and 2.

Please let me know if there is a better datastructure to do this with, if there is no way to iterate and erase from a list. I thought of using a Vector, but I would have to shift elements down and that would be costly if there are a lot of elements.

#include "roulette.h"
#include <iostream>

uint roulette(uint people, uint step)
{
    std::list<uint>::iterator iterator;
    for(uint i = people; i > 0; i--)
        gl_myList.push_front(i);

    iterator = gl_myList.begin();
    while(people > 1)
    {
        iterator = advanceList(iterator, step - 1);
        uint replaceValue = *iterator; // Node n's value

        auto tempIterator = advanceList(iterator, step);
        uint newValue = *tempIterator; //Node n + step value

        iterator = gl_myList.erase(tempIterator);
        //Makes it past the erase function ONCE.

        //Puts the iterator back to the correct spot, and sets it value
        while(*iterator != replaceValue)
        {
            advanceList(iterator, 1);

        }
        *iterator = newValue;

        people--;
    }

    return *iterator;
}

advanceList

#include "roulette.h"
std::list<uint>::iterator advanceList(std::list<uint>::iterator& start, uint step)
{
    for(uint i = 0; i < step; i++)
    {
        start++;
        if(start == gl_myList.end())
        {
            start = gl_myList.begin();
        }
    }

    return start;
}

Answer 1

You're not using the result of your erase() call correctly, nor are you checking for .end() prior to the next iteration. I'm all-but-certain the following is what you're at least attempting to do. And note, this is still brittle, as it is anything-but-ready for edge cases (like an initial empty list, a 0-step-value, etc.):

std::list<uint>::iterator advanceList(std::list<uint>::iterator& start, uint step)
{
    for(uint i = 0; i < step; i++)
    {
        if(++start == gl_myList.end())
            start = gl_myList.begin();
    }

    return start;
}

uint roulette(uint people, uint step)
{
    std::list<uint>::iterator it;
    for(uint i = people; i > 0; i--)
        gl_myList.push_front(i);

    it = gl_myList.begin();
    while (gl_myList.size() > 1)
    {
        it = gl_myList.erase(advanceList(it, step - 1));
        if (it == gl_myList.end())
            it = gl_myList.begin();
    }

    return *it;
}