Wie wiederhole ich eine Liste und lösche sie?

Question

Ich habe eine Menge Probleme mit List-Iteratoren, und ich habe vorher eine Frage gestellt, konnte aber nicht die Lösung finden, die ich suchte.

Ich habe eine kreisförmige Liste, und ich muss den Wert von Knoten n durch Knoten n + ersetzen (Schritt). Ich muss dann Knoten n + (Schritt) löschen. Wenn ich es lösche, setzt der Iterator auf das Element nach dem gelöschten Element. Ich brauche den Iterator zurück am Knoten n. Wie zum Teufel kann ich das tun, weil jedes Mal, wenn ich n + (Schritt) lösche ich einen ungültigen Iterator bekomme. Meine Eingabe ist 5 und 2.

Bitte lassen Sie mich wissen, wenn es eine bessere Datenstruktur mit dies zu tun, wenn es keine Möglichkeit gibt, von einer Liste zu iterieren und zu löschen. Ich dachte an einen Vector, aber ich würde Elemente verschieben müssen, und das wäre teuer, wenn es viele Elemente gibt.

#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

Sie sind nicht das Ergebnis Ihrer erase() Anruf korrekt verwenden, noch sind die Überprüfung Sie .end() vor der nächsten Iteration. Ich bin mir ziemlich sicher, dass das Folgende zumindest das ist, was Sie versuchen zu tun. Und beachten Sie, dass dies immer noch brüchig ist, da es alles andere als bereit ist für Grenzfälle (wie eine anfängliche leere Liste, ein 0-Schritt-Wert, 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; 
} 

Answer 2

Werfen wir einen sehr einfachen Fehler beheben in deinem Code. advanceList ändert es Argument ist, wenn Sie

auto tempIterator = advanceList(iterator, step); 

rufen beide iterator und tempIterator geändert werden. Wollen Sie das erreichen?

Auch in Ihrem advanceList wenn Start war am Ende, als Sie die Funktion eingegeben haben, müssen Sie es durch begin vor dem Eintritt in die Schleife ersetzen.

Answer 3

Sie nähern sich dieses Problem nicht in der richtigen Weise, glaube ich.

Der beste Weg zu tun, was Sie wollen, ist zuerst zu trennen, was gelöscht werden muss, was zu halten ist. Sie können das mit Std :: Partition oder Std :: Stable_partition in Header Algorithmus tun. Dann können Sie eine Reihe von Elementen aus Ihrem Container einfach und sauber löschen.

Beispiel:

#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()); 

Ich verwende stable_partition hier, weil es die relative Position zwischen den Elementen hält. Wenn Sie sich nicht darum kümmern, können Sie stattdessen Partition verwenden.