[Effective STL] 32. remove-erase 관용구

항목 32. 요소를 정말로 제거하고자 한다면 remove 류의 알고리즘에는 꼭 erase를 붙여 사용하자

 

 

 

remove 알고리즘

• 선언부

template<typename ForwardIterator, typename T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value);

• 보다시피, 컨테이너 자체를 받지 않는다.
• 그렇다면 remove가 삭제를 처리하기 위해서는?
  • 삭제를 위해 제공되는 해당 컨테이너의 멤버 함수를 호출하는 방법 뿐일 것이다.
• 하지만 실제 동작은 아래와 같다..

vector<int> v;
v.reserve(10);
for(int i = 1 ; i <= 10 ; ++i)
{
    v.push_back(i);
}
cout << v.size(); // 10을 출력한다.
v[3] = v[5] = v[9] = 99;
remove(v.begin(), v.end(), 99); // 99 값을 모두 삭제?
cout << v.size(); // 여전히 10개이다..

• 왜냐하면 remove는 어느 것도 '진짜로' 없애지 않기 때문이다.
  • remove는 자신이 제거하려고 하는 요소를 가진 컨테이너가 무엇인지 모르기 때문에,
  • 진짜로 요소를 제거할 때 필요한 멤버 함수를 호출할 방법을 전혀 모른다.
• remove의 진짜 동작법
  1. 삭제하지 않을 요소들을 범위의 앞쪽으로 옮긴다.(상대적인 위치는 보존한다. stable)
  2. 앞으로 옮긴 요소들의 마지막 반복자를 리턴한다.

 

 

 

그림으로 예제 훑기

처음 컨테이너 상태

auto newEnd = remove(v.begin(), v.end(), 99); 로 리턴한 반복자의 위치

• 그렇다면 여기서 제거된 요소는 newEnd와 v.end() 사이에 있어야 할 것이다.
  • 하지만 꼭 그렇지만도 않다는 것이 문제이다.
• remove는 삭제하지 않을 요소를 앞으로 옮기는 것만 보장해줄 뿐이다.
• 그래서 대개 이런 형태로 남아있게 된다...

newEnd 반복자 뒷부분은 그다지 신경쓰지 않는 remove

• 아마 remove는 대충 아래 방식으로 삭제하지 않을 요소들을 앞으로 옮겼을 것이다.

• 즉, 컨테이너의 요소를 진짜로 제거할 수 있는 장본인은 오직 그 컨테이너의 멤버 함수 뿐이다.
• 그러므로 진짜 제거하고 싶다면 remove 사용 시에는 반드시 erase를 붙여야 한다.

 

 

 

remove 사용법

vector<int> v;
...
v.erase(remove(v.begin(), v.end(), 99), v.end());

cout << v.size(); // 이제 7 출력

• list는 이 둘을 합친 알고리즘을 포함하고 있는 remove 멤버함수를 제공한다.(항목 44 참조)

list<int> li;
...
li.remove(99); // erase-remove와 완전히 동일한 동작

• 이와 비슷한 동작을 하는 다른 알고리즘도 알아두는 것이 좋다.
  • remove_if
  • unique