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 approaching this problem in the right way, I believe.

The best way to do what you want, is first to separate whathever has to be deleted from what has to be kept. You can do that with std::partition or std::stable_partition in header algorithm. Then you can delete a range of elements from your container easy and clean.

Example:

#include <vector>
#include <algorithm>
using namespace std;

// ...
bool differentFrom3(int n) { return n != 3; }

vector<int> v = { 1, 3, 4, 2, 1, 3, 4, 3, 7, 3, 1 };

// move all the 3's to one end of the vector
vector<int>::iterator it = stable_partition(v.begin(), v.end(), differentFrom3);

// v is now arranged in the following order:
// { 1, 4, 2, 1, 4, 7, 1, 3, 3, 3, 3 }
//                        ^
//                        +--- it
//
// and it points to the first element whose value is 3 (in this case, v[7])
// Now you can delete everything from the it to the end of the vector.
v.erase(it, v.end());

I'm using stable_partition here because it keeps the relative position between elements. If you don't care about that you can use partition instead.

Answer 2

Let's fix a very simple bug in your code. advanceList modifies it's argument, when you call

auto tempIterator = advanceList(iterator, step);

both iterator and tempIterator are changed. Is it what you want to achieve?

Also in your advanceList if start was at the end as you entered teh function you must replace it with begin before entering loop.

Answer 3

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;
}