隣接するエントリを繰り返して削除する方法

Question

隣接するすべてのエントリを、そのセットを反復しながら消去するにはどうすればよいですか？私の場合、左から右に1だけ異なるものとして隣接する項目を定義するカスタムコンパレータがあります。したがって、セットstd::set<int> mySet = {1,2,3,4,5,7,9,10}については、これらのエントリが私のコンパレータを満たすので、{1,2,3,4,5,9,10}のエントリを削除したいと思います。 （シリーズの唯一のものは、隣接するペアの要素の1つではありませんので注意してください）

以下のコードでは、隣接するエントリを正しく追加することができます私は、隣接する対adjIterとも右側無効イテレータと*std::next(adjIter)コードのクラッシュの左側の両方を消去しようとした場合

int main() {  
    std::set<int> mySet = {1,2,3,4,5,7,9,10}; 
    static const auto gPred = [](const auto& lhs, const auto& rhs) { 
     return rhs == lhs+1; 
    }; 
    auto adjIter = mySet.begin(); 
    std::set<int> adjacentEntries; 
    while ((adjIter = std::adjacent_find(adjIter, mySet.end(), 
     gPred)) != mySet.end()) { 
     adjacentEntries.insert(*adjIter); 
     // peek at the second entry that should be 1 greater than adjIter   
     adjacentEntries.insert(*std::next(adjIter)); 
     // how do I erase both *std::next(adjIter) & adjIter 
     ++adjIter; 
    } 
    std::cout << adjacentEntries << std::endl; 
} 

Answer 1

保存と削除続けるの簡単な方法述語が真である間要素の

void remove_adjacent_entries() 
{ 
    std::set<int> mySet = { 1,2,3,4,5,7,9,10 }; 
    static const auto gPred = [](const auto& lhs, const auto& rhs) { 
     return rhs == lhs + 1; 
    }; 

    auto adjIter = mySet.begin(); 
    std::set<int> adjacentEntries; 
    while ((adjIter = std::adjacent_find(adjIter, mySet.end(), gPred)) != mySet.end()) { 
     for (auto next = std::next(adjIter); next != mySet.end() && gPred(*adjIter, *next); ++next) { 
      //save and delete the first of the pair of elements found 
      adjacentEntries.insert(*adjIter); 
      mySet.erase(adjIter++); 
     } 
     //save and delete the second element 
     adjacentEntries.insert(*adjIter); 
     mySet.erase(adjIter++); 
    } 
    //print 
    for(auto& i : adjacentEntries) 
     std::cout << i << std::endl; 
} 

Answer 2

に答える：。

以下のコードを（もでcoliru）を見ると、私はadjaを見つけることができます隣のペアの左辺と右辺* std :: next（adjIter）の両方を消去しようとすると、コードが無効なイテレータでクラッシュします。

以降C++ 11を（あなたがauto Sを使用しているとして、私は、これは十分だと思います）：

set::erase(const_iterator first, const_iterator last) - それは最後の要素を過ぎ指すイテレータを返すとして参照（2）NDを形成削除されました。

だから私はそれが可能だろうと思います：

while ((adjIter = std::adjacent_find(adjIter, mySet.end(), gPred)) != mySet.end()) { 
    adjacentEntries.insert(*adjIter); 
    // peek at the second entry that should be 1 greater than adjIter   
    adjacentEntries.insert(*std::next(adjIter)); 

    // here's how to erase both *std::next(adjIter) & adjIter 
    adjIter=mySet.erase(adjIter, std::next(std::next(adjIter))); 
} 

注：もはやクラッシュ上記のコードが、アルゴリズムのバグがあり、提供された例では、5はを削除されません（ので、 4は以前は3で削除されていましたが）それは疑問を超えています（または私にもその解決策を見出せますか？） - coliru。

---

正しい解決策：num-1より前にあるすべての数字を削除するか、num + 1の後にあるすべての数字を削除します。 {1,2,3,4,5,7,9,10}の例では、7のみがmySetに残ります。

See it on coliru

int main() {  
    std::set<int> mySet = {1,2,3,4,5,7,9,10}; 
    static const auto gPred = [](const auto& lhs, const auto& rhs) { 
     return rhs == lhs+1; 
    }; 
    std::set<int> adjacentEntries; 

    auto adjIter = mySet.begin(); 
    auto prevDelete = mySet.end(); 

    while ((adjIter = std::adjacent_find(adjIter, mySet.end(), gPred)) != mySet.end()) { 
     adjacentEntries.insert(*adjIter); 
     // peek at the second entry that should be 1 greater than adjIter   
     adjacentEntries.insert(*std::next(adjIter)); 
     if(prevDelete!=adjIter && prevDelete!=mySet.end()) { 
      // the prevDelete is the rhs of a pair which is followed by a "hole" 
      mySet.erase(prevDelete, std::next(prevDelete)); 
     } 
     prevDelete=mySet.end(); 

     // erase the lhs but delay the erasure of rhs, 
     // let rhs participaye in the next round of search 
     adjIter=mySet.erase(adjIter, std::next(adjIter)); 
     prevDelete=adjIter; 
    } 
    if(prevDelete!=mySet.end()) { 
     mySet.erase(prevDelete, std::next(prevDelete)); 
    } 
    std::cout << adjacentEntries << std::endl; 
    std::cout << mySet << std::endl; 
} 

Answer 3

あなたはセットadjacentEntriesのために余分なスペースを使用する必要はありません。 （前のイテレータを消去するとき）あなたは、はるかに簡単な方法でO(1)スペースの複雑さと、フラグdelを使用してそれを達成することができます

std::set<int>::iterator prevItr = mySet.begin(), nextItr, currItr; 
int prevVal = *prevItr; 
int del = 0; 
currItr = next(mySet.begin()); 
while (currItr != mySet.end()) { 
    nextItr = std::next(currItr); 
    if(prevVal+1 == *currItr || del == 1){ 
     mySet.erase(prevItr); 
     if(prevVal+1 == *currItr) del = 1; 
     else del = 0; 
    } 
    prevItr = currItr; 
    prevVal = *currItr; 
    currItr = next(currItr); 
} 
if(del == 1){ 
    mySet.erase(prevItr); 
} 

Demo