[Effective STL] 9. 컨테이너별 요소 삭제

항목 9. 데이터를 삭제할 때에도 조심스럽게 선택할 것이 많다

 

 

 

특정 요소 삭제하기

• 컨테이너의 요소 중 1963이라는 값을 모두 삭제하고 싶다면?
• 컨테이너 종류에 따라 삭제 방법이 다르다.

연속 메모리(시퀀스) 컨테이너(vector, deque, string)

• erase-remove 합성문

// erase-remove 합성문
// remove : 제거한 요소들을 컨테이너 뒤로 이동시킨다.
//          마지막 유효한 값 다음 반복자를 리턴한다.
//          컨테이너의 크기는 변하지 않는다.
// erase : 반복자 및 반복자의 범위를 컨테이너에서 제거한다.
//         삭제된 요소 다음 반복자를 리턴한다.
//         컨테이너의 크기가 변한다.
c.erase(remove(c.begin(), c.end(), 1963), c.end());

• 이 방법은 양방향 반복자를 지원하는 list에도 통하지만,
• list는 remove 멤버 함수를 쓰는 것이 더 좋은 방법이다.(항목 44 참조)

연관 컨테이너(set, multiset, map, multimap)

• remove라는 이름을 가진 어떤 것도 소용이 없다.
  • remove 류의 멤버 함수를 포함하고 있지 않다.
  • remove 알고리즘을 사용하면 컨테이너 값을 덮어써서 컨테이너를 변형시켜버린다.(항목 32, 22 참조)
• erase 멤버 함수를 사용해야 한다.

c.erase(1963);

• erase의 특징
  • 로그 시간을 소모한다.
    • 선형 시간이 걸리는 시퀀스 컨테이너의 remove 보다 효율적이다.
  • 상등성(equality)이 아니라 동등성(equivalence)에 기반하고 있다.(항목 19 참조)

 

 

 

predicate로 삭제하기

• 술어 구문(predicate)(항목 39 참조)이 true를 반환하는 요소를 모두 없애는 방법을 알아보자.

시퀀스 컨테이너

bool badValue(int x); // x를 삭제해야 하면 true 반환

// vector, string, deque의 경우
c.erase(remove_if(c.begin(), c.end(), badValue), c.end());

// list의 경우
c.remove_if(badValue);

연관 컨테이너

• 첫 번째 방법(쉬운 방법) 
  • remove_copy_if를 사용한다.
  • 주어진 범위에서 조건을 만족하는 요소를 제거하고, 나머지 요소를 다른 범위에 복사하는 함수
  • 삭제되지 않는 요소를 모두 복사했다가 옮기기에 비효율적이다.(비싸다)

AssocContainer<int> c;
...
AssocContainer<int> goodValues; // 삭제하면 안될 값을을 위한 임시 컨테이너

remove_copy_if(c.begin(),
               c.end(),
               inserter(goodValues, goolValues.end()),
               badValue);
c.swap(goodValues);

 

• 두 번째 방법
  • 원래의 컨테이너에서 요소를 직접 삭제한다.
  • 허나 직관적인 방법으로 작성하다가 실수할 여지가 있다.

// 잘못 작성된 코드
AssocContainer<int> c;
...
for(AssocContainer<int>::iterator i = c.begin() ; i != c.end() ; ++i)
{
    if(badValue(*i))
        c.erase(i); // 삭제 시 기존 반복자(i)가 무효화된다!
    
    // i가 무효화 되었으므로 ++i가 동작하지 못한다.
}

• 무효화 되기 전에 다음 요소를 가리키도록 하면 된다.

AssocContainer<int> c;
...
for(AssocContainer<int>::iterator i = c.begin() ; i != c.end() ; )
{
    if(badValue(*i))
    {
        // i를 넘기고, side-effect로 증가시킨다.
        // i를 넘기고, erase가 수행되기 전에 i를 증가시킨 것이다.
        c.erase(i++);
    }
    else
    {
        ++i; // 그냥 증가시킨다.
    }
}

 

 

 

 

predicate로 삭제하되, 로그 파일에 기록도 하도록 하기

연관 컨테이너

• 두 번째 방법을 택하면 아주 쉽게 가능하다.

AssocContainer<int> c;
...
for(AssocContainer<int>::iterator i = c.begin() ; i != c.end() ; )
{
    if(badValue(*i))
    {
        logFile << "Erasing " << *i << '\n'; // 로그 기록
        c.erase(i++);
    }
    else
    {
        ++i;
    }
}

시퀀스 컨테이너

• erase-remove 합성문으로는 달성이 불가능하다.
• 연관 컨테이너처럼 루프를 사용할 수도 없다.
  • 연속 메모리 컨테이너는 erase 시 지워진 요소의 반복자 뿐 아니라 기존, 그 외의 모든 반복자가 무효화된다.
• erase를 사용한다.
  • erase 멤버 함수는 수행 후, 삭제된 요소의 바로 뒤 요소를 가리키는 반복자를 반환한다.
  • 이는 유효한 반복자이다.

for(SeqContainer<int>::iterator i = c.begin() ; i != c.end() ; )
{
    if(badValue(*i))
    {
        logFile << "Erasing " << *i << '\n';
        i = c.erase(i);
    }
    else
    {
        ++i;
    }
}

• 동작하지만, 표준 시퀀스 컨테이너에서만 동작한다는 것이 흠이다.
  
  • 연관 컨테이너는 erase 함수의 반환값이  void이기 때문이다.(실은, 모던 C++에서는 그렇지 않음!)

list의 경우

• 모든 방법을 사용할 수 있다.
• 보통은 표준 시퀀스 컨테이너의 방법을 쓸 것이다.
  • list 역시 시퀀스 컨테이너이므로 통일성과 직관성을 위해서.

 

 

 

정리

• 컨테이너에서 특정한 값을 가진 객체를 모두 없애려면
  • list가 아닌 시퀀스 컨테이너의 경우
    • erase-remove 합성문
  • list의 경우
    • remove 멤버 함수
  • 연관 컨테이너의 경우
    • erase 멤버 함수
• 컨테이너에서 predicate를 만족하는 객체를 모두 없애려면
  • list가 아닌 시퀀스 컨테이너의 경우
    • erase-remove_if 합성문
  • list의 경우
    • remove_if 멤버 함수
  • 연관 컨테이너의 경우
    • remove_copy_if와 swap 함수
    • 루프와 erase 함수
• 루프 안에서 무엇인가를 하려면
  • 시퀀스 컨테이너
    • 루프와 erase 멤버 함수
  • 연관 컨테이너
    • 루프와 erase 멤버 함수