如何在迭代時從一組中刪除相鄰條目

Question

如何在迭代集合時從集中刪除所有相鄰條目。在我的情況下，我有一個自定義比較器，將相鄰條目定義爲從左到右相差1的條目。因此，對於集std::set<int> mySet = {1,2,3,4,5,7,9,10}我想刪除條目{1,2,3,4,5,9,10}，因爲這些滿足我的比較。 （注意7是剩下的，因爲它是系列中唯一一個不是相鄰對中的元素之一）

下面的代碼（也在coliru）顯示我可以找到正確添加相鄰條目，但是如果我嘗試擦除兩個相鄰一對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 cent條目正確，但是如果我嘗試擦除相鄰的pair對的左側和右側* std :: next（adjIter），則代碼將與無效的迭代器一起崩潰。

C++ 11日起（以您使用auto S，我想這是不夠好）：

set::erase(const_iterator first, const_iterator last) - 見（2）次形成，因爲它返回指向過去的最後一個元素的迭代刪除。

所以我想它會是：

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。您可以通過使用一個標誌del以更簡單的方式實現它（時刪除之前的迭代器），與O(1)空間複雜度：

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