リストを反復して削除するにはどうすればいいですか？

Question

Listイテレータで問題が発生しています。以前は質問しましたが、私が探していた解決策を手に入れることができませんでした。

私は循環的なリストを持っており、ノードnの値をノードn +（ステップ）に置き換える必要があります。私はノードn +を消去しなければならない（ステップ）。消去すると、消去された要素の後の要素にイテレータが配置されます。ノードnにイテレータを戻す必要があります。何度もn +を消去するたびに（ステップ）無効なイテレータが得られます私の入力は5と2です。

リストを反復して消去する方法がない場合、これを行うためのより良いデータ構造があるかどうか教えてください。私はVectorを使うことを考えましたが、要素をシフトさせなければならず、多くの要素があればコストがかかります。

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

あなたは正しくerase()呼び出しの結果を使用していない、またあなたが.end()前に次の反復のためにチェックしている

#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

advanceList。私はすべてのことを確信していますが、少なくとも次のことはあなたがやろうとしていることです。

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

はのは非常に単純なバグを修正してみましょう：それは何も-が、対応エッジケースのための（初期の空のリストのように、0-ステップ値、など）であるように、これはまだ脆弱で、注意してくださいあなたのコードで。 advanceListは、それはあなたが

auto tempIterator = advanceList(iterator, step); 

iteratorとtempIterator変更されているの両方を呼び出し、引数、だ修正します。それはあなたが達成したいものですか？

また、advanceListでは、開始時に最後に終了した場合は、ループに入る前にbeginに置き換える必要があります。

Answer 3

あなたは正しい方法でこの問題に近づいていないと思います。

あなたが望むことを実行する最良の方法は、まず何を削除しなければならないかを分離することです。 std :: partitionまたはstd :: stable_partitionヘッダーアルゴリズムでこれを行うことができます。次に、あなたのコンテナから簡単に、そしてきれいな要素の範囲を削除することができます。

例：

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

それは要素間の相対的な位置を保持しますので、私はここにstable_partitionを使用しています。気にしない場合は、代わりにパーティションを使用してください。