반복하는 동안 STL 세트에서 요소 삭제

반복하는 동안 STL 세트에서 요소 삭제

---

미리 정의 된 기준에 맞는 요소를 설정하고 제거해야합니다.

이것은 내가 작성한 테스트 코드입니다.

#include <set>
#include <algorithm>

void printElement(int value) {
    std::cout << value << " ";
}

int main() {
    int initNum[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    std::set<int> numbers(initNum, initNum + 10);
    // print '0 1 2 3 4 5 6 7 8 9'
    std::for_each(numbers.begin(), numbers.end(), printElement);

    std::set<int>::iterator it = numbers.begin();

    // iterate through the set and erase all even numbers
    for (; it != numbers.end(); ++it) {
        int n = *it;
        if (n % 2 == 0) {
            // wouldn't invalidate the iterator?
            numbers.erase(it);
        }
    }

    // print '1 3 5 7 9'
    std::for_each(numbers.begin(), numbers.end(), printElement);

    return 0;
}

처음에는 반복하는 동안 집합에서 요소를 지우면 반복자가 무효화되고 for 루프의 증분에는 정의되지 않은 동작이 있다고 생각했습니다. 그럼에도 불구 하고이 테스트 코드를 실행했는데 모두 잘 진행되었으며 이유를 설명 할 수 없습니다.

내 질문 : 이것은 std 세트에 대해 정의 된 동작입니까, 아니면 구현에 특정한 것입니까? 그런데 우분투 10.04 (32 비트 버전)에서 gcc 4.3.3을 사용하고 있습니다.

감사!

제안 된 해결책:

이것이 세트에서 요소를 반복하고 지우는 올바른 방법입니까?

while(it != numbers.end()) {
    int n = *it;
    if (n % 2 == 0) {
        // post-increment operator returns a copy, then increment
        numbers.erase(it++);
    } else {
        // pre-increment operator increments, then return
        ++it;
    }
}

편집 : 선호하는 솔루션

나는 정확히 똑같아도 나에게 더 우아해 보이는 해결책을 찾았습니다.

while(it != numbers.end()) {
    // copy the current iterator then increment it
    std::set<int>::iterator current = it++;
    int n = *current;
    if (n % 2 == 0) {
        // don't invalidate iterator it, because it is already
        // pointing to the next element
        numbers.erase(current);
    }
}

while 안에 여러 테스트 조건이있는 경우, 각각의 조건은 반복자를 증가시켜야합니다. 반복자가 한 곳에서만 증가하기 때문에이 코드가 더 좋습니다. 오류가 적고 읽기 쉽습니다.

---

이것은 구현에 따라 다릅니다.

표준 23.1.2.8 :

삽입 부재는 이터레이터의 유효성과 컨테이너에 대한 참조에 영향을 미치지 않아야하며, 소거 부재는 소거 된 요소에 대한 반복자와 참조 만 무효화해야합니다.

아마도 당신은 이것을 시도 할 수 있습니다-이것은 표준 준수입니다.

for (auto it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
        numbers.erase(it++);
    }
    else {
        ++it;
    }
}

++는 postfix이므로 삭제하기 위해 이전 위치를 전달하지만 먼저 연산자로 인해 새로운 위치로 이동합니다.

2015.10.27 업데이트 : C ++ 11에서 결함이 해결되었습니다. iterator erase (const_iterator position);제거 된 마지막 요소 다음에 오는 요소 (또는 set::end마지막 요소가 제거 된 경우)에 반복자를 리턴합니다 . 따라서 C ++ 11 스타일은 다음과 같습니다.

for (auto it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
        it = numbers.erase(it);
    }
    else {
        ++it;
    }
}

---

valgrind를 통해 프로그램을 실행하면 많은 읽기 오류가 표시됩니다. 다시 말해서, 반복자가 무효화되고 있지만 예제에서 운이 좋지 않습니다 (정의되지 않은 동작의 부정적인 영향을 보지 못해 운이 좋지 않습니다). 이에 대한 한 가지 해결책은 임시 반복자를 작성하고, 온도를 높이고, 대상 반복자를 삭제 한 다음 대상을 임시로 설정하는 것입니다. 예를 들어, 다음과 같이 루프를 다시 작성하십시오.

std::set<int>::iterator it = numbers.begin();                               
std::set<int>::iterator tmp;                                                

// iterate through the set and erase all even numbers                       
for ( ; it != numbers.end(); )                                              
{                                                                           
    int n = *it;                                                            
    if (n % 2 == 0)                                                         
    {                                                                       
        tmp = it;                                                           
        ++tmp;                                                              
        numbers.erase(it);                                                  
        it = tmp;                                                           
    }                                                                       
    else                                                                    
    {                                                                       
        ++it;                                                               
    }                                                                       
} 

---

"정의되지 않은 동작"의 의미를 오해합니다. 정의되지 않은 동작은 "이 작업을 수행하면 프로그램 이 충돌하거나 예기치 않은 결과 가 발생 함"을 의미하지 않습니다 . "이 작업을 수행하면 프로그램 이 충돌하거나 예기치 않은 결과가 발생할 수 있습니다"또는 컴파일러, 운영 체제, 달의 위상 등에 따라 다른 작업을 수행 할 수 있습니다.

충돌없이 무언가가 실행되고 예상대로 작동 하는 경우 정의되지 않은 동작 이 아니라는 증거는 아닙니다. 모든 특정 운영 체제에서 특정 컴파일러로 컴파일 한 후 해당 특정 동작에 대해 해당 동작이 관찰 된 것으로 나타났습니다.

집합에서 요소를 지우면 이터레이터가 지워진 요소로 무효화됩니다. 무효화 된 반복자를 사용하는 것은 정의되지 않은 동작입니다. 관찰 된 행동이이 특정한 예에서 의도 한 것이 었습니다. 코드가 정확하다는 의미는 아닙니다.

---

deque 컨테이너의 경우 deque iterator가 numbers.end ()와 동일한 지 확인하는 모든 솔루션은 gcc 4.8.4에서 실패 할 것입니다. 즉, deque 요소를 지우면 일반적으로 numbers.end ()에 대한 포인터가 무효화됩니다.

#include <iostream>
#include <deque>

using namespace std;
int main() 
{

  deque<int> numbers;

  numbers.push_back(0);
  numbers.push_back(1);
  numbers.push_back(2);
  numbers.push_back(3);
  //numbers.push_back(4);

  deque<int>::iterator  it_end = numbers.end();

  for (deque<int>::iterator it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
      cout << "Erasing element: " << *it << "\n";
      numbers.erase(it++);
      if (it_end == numbers.end()) {
    cout << "it_end is still pointing to numbers.end()\n";
      } else {
    cout << "it_end is not anymore pointing to numbers.end()\n";
      }
    }
    else {
      cout << "Skipping element: " << *it << "\n";
      ++it;
    }
  }
}

산출:

Erasing element: 0
it_end is still pointing to numbers.end()
Skipping element: 1
Erasing element: 2
it_end is not anymore pointing to numbers.end()

이 특정한 경우에는 deque 변환이 올바른 반면 종료 포인터는 그 과정에서 무효화되었습니다. 다른 크기의 deque를 사용하면 오류가 더 분명합니다.

int main() 
{

  deque<int> numbers;

  numbers.push_back(0);
  numbers.push_back(1);
  numbers.push_back(2);
  numbers.push_back(3);
  numbers.push_back(4);

  deque<int>::iterator  it_end = numbers.end();

  for (deque<int>::iterator it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
      cout << "Erasing element: " << *it << "\n";
      numbers.erase(it++);
      if (it_end == numbers.end()) {
    cout << "it_end is still pointing to numbers.end()\n";
      } else {
    cout << "it_end is not anymore pointing to numbers.end()\n";
      }
    }
    else {
      cout << "Skipping element: " << *it << "\n";
      ++it;
    }
  }
}

산출:

Erasing element: 0
it_end is still pointing to numbers.end()
Skipping element: 1
Erasing element: 2
it_end is still pointing to numbers.end()
Skipping element: 3
Erasing element: 4
it_end is not anymore pointing to numbers.end()
Erasing element: 0
it_end is not anymore pointing to numbers.end()
Erasing element: 0
it_end is not anymore pointing to numbers.end()
...
Segmentation fault (core dumped)

이 문제를 해결하는 방법 중 하나는 다음과 같습니다.

#include <iostream>
#include <deque>

using namespace std;
int main() 
{

  deque<int> numbers;
  bool done_iterating = false;

  numbers.push_back(0);
  numbers.push_back(1);
  numbers.push_back(2);
  numbers.push_back(3);
  numbers.push_back(4);

  if (!numbers.empty()) {
    deque<int>::iterator it = numbers.begin();
    while (!done_iterating) {
      if (it + 1 == numbers.end()) {
    done_iterating = true;
      } 
      if (*it % 2 == 0) {
    cout << "Erasing element: " << *it << "\n";
      numbers.erase(it++);
      }
      else {
    cout << "Skipping element: " << *it << "\n";
    ++it;
      }
    }
  }
}

---

This behaviour is implementation specific. To guarantee the correctness of the iterator you should use "it = numbers.erase(it);" statement if you need to delete the element and simply incerement iterator in other case.

---

I think using the STL method 'remove_if' from could help to prevent some weird issue when trying to attempt to delete the object that is wrapped by the iterator.

This solution may be less efficient.

Let's say we have some kind of container, like vector or a list called m_bullets:

Bullet::Ptr is a shared_pr<Bullet>

'it' is the iterator that 'remove_if' returns, the third argument is a lambda function that is executed on every element of the container. Because the container contains Bullet::Ptr, the lambda function needs to get that type(or a reference to that type) passed as an argument.

 auto it = std::remove_if(m_bullets.begin(), m_bullets.end(), [](Bullet::Ptr bullet){
    // dead bullets need to be removed from the container
    if (!bullet->isAlive()) {
        // lambda function returns true, thus this element is 'removed'
        return true;
    }
    else{
        // in the other case, that the bullet is still alive and we can do
        // stuff with it, like rendering and what not.
        bullet->render(); // while checking, we do render work at the same time
        // then we could either do another check or directly say that we don't
        // want the bullet to be removed.
        return false;
    }
});
// The interesting part is, that all of those objects were not really
// completely removed, as the space of the deleted objects does still 
// exist and needs to be removed if you do not want to manually fill it later 
// on with any other objects.
// erase dead bullets
m_bullets.erase(it, m_bullets.end());

'remove_if' removes the container where the lambda function returned true and shifts that content to the beginning of the container. The 'it' points to an undefined object that can be considered garbage. Objects from 'it' to m_bullets.end() can be erased, as they occupy memory, but contain garbage, thus the 'erase' method is called on that range.

---

C++20 will have "uniform container erasure", and you'll be able to write:

std::erase_if(numbers, [](int n){ return n % 2 == 0 });

And that will work for vector, set, deque, etc. See cppReference for more info.

---

I came across same old issue and found below code more understandable which is in a way per above solutions.

std::set<int*>::iterator beginIt = listOfInts.begin();
while(beginIt != listOfInts.end())
{
    // Use your member
    std::cout<<(*beginIt)<<std::endl;

    // delete the object
    delete (*beginIt);

    // erase item from vector
    listOfInts.erase(beginIt );

    // re-calculate the begin
    beginIt = listOfInts.begin();
}

참고URL : https://stackoverflow.com/questions/2874441/deleting-elements-from-stl-set-while-iterating