Как удалить смежные записи из набора во время итерации по нему

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 но если я попытаюсь стереть и левую сторону соседнего смежного пара, а также правую сторону * std :: next (adjIter), код выйдет из строя с недопустимым итератором.

C++ 11 и выше (как вы используете auto с, я думаю, что это достаточно хорошо):

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

Примечание: код выше больше не падает, но алгоритмическую ошибку, в примере, при условии, -не будет удален (т.к. 4 будет удалено на 3 раньше), но это не подлежит сомнению (или вы хотите, чтобы я нашел решение для этого тоже?) - coliru.

Правильное решение: удаляет все числа, которым предшествует номер-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