item 9 : Choose carefully among erasing options

이번편은 컨테이너의 종류에 따라 효과적으로 원소를 삭제하는 방법들을 소개합니다.

1. 특정 원소(값) 지우기.

하나의 원소를 지우려고 할땐 각 컨테이너마다 다음의 멤버함수를 이용하면 됩니다.

Container<int> c

(1) contiguous memory container

c가 vector, deque, string의 경우에는 멤버함수인 erase를 이용하면 됩니다.

단, erase의 경우 삭제할 위치인 iterator를 매개변수로 받으므로 

algorithim의 함수인 remove를 이용하여 다음과 같이 사용합니다.

c.erase( remove(c.begin(), c.end(), 1992));

range erase의 경우 erase함수의 두번째 매개변수에 end위치를 넘겨줍니다.

시간복잡도는 

Linear on the number of elements erased (destructions) plus the number of elements after the last element deleted (moving).

라고 설명되어 있네요.

삭제할 갯수와 더불어 삭제되면서 그 뒤에 있던 원소들을 앞으로 옮기는데 시간이 추가로 소요됩니다.

소멸자가 호출되고 복사생성자가 호출되는것 역시 이 과정에 포함되어 있구요.

(2)sequence containers

c가 list인 경우에는 remove 멤버함수를 이용합니다. 

선형 컨테이너 특징 답게 시간복잡도로는 O(n)입니다.

(3) associative containers

c가 map,set, multimap, multiset의 경우에는 erase 함수를 곧바로 이용합니다.

이 경우의 시간복잡도는 O(logN)입니다.

연관컨테이너는 내부적으로 이진트리를 이용하고 있기 때문이죠.

2. 특정 조건하에서 특정 원소 지우기

bool badValue(int)

다음 함수를 이용하여 특정 조건의 값을 지운다고 했을때는 다음과 같은 방법들을 이용합니다.

(1) contiguous memory container

vector와 같은경우는 앞서 설명한바와 같이 위치를 매개변수로 받으므로

remove_if를 이용합니다.

c.erase(remove_if(c.begin(), c.end(), badValue));

(2)sequence containers

list는 아예 멤버함수로 remove_if를 지원합니다. 매우 간편하네요.

(3) associative containers

연관컨테이너에는 두가지 전략이 있습니다.

remove_copy_if를 이용하는 방법과 for문을 도는 방법입니다.

전자의 remove_copy_if는 다음 링크에 자세히 소개 되어있습니다.

http://www.cplusplus.com/reference/algorithm/remove_copy_if/?kw=remove_copy_if

이 알고리즘은 주의깊게 사용하는 점이 새로운 컨테이너에 조건에 적합한 원소들을 새로 복사한다는 점입니다.

따라서 새로운 컨테이너에 넣고 끝날거라면 상관없겠지만

원본 컨테이너에 이를 다시 넣어야한다면 swap이 이용되어야 하기때문에 메모리와 시간의 낭비가 발생합니다.

다음의 예제를 살펴보세요.

전자의 낭비를 미연에 방지하고자 한다면 결국엔 후자의 for문을 사용하는 방법밖엔 없습니다.

이전의 장에서 for문을 직접 도는것은 그다지 추천되는 방법이 아님을 이미 언급하였으나

연관컨테이너의 특성상 지금처럼 불가피한 경우 적극 사용하는데 주저하지 않도록 합시다.

for문을 이용하여 연관컨테이너의 원소를 지우는 방법은 다음과 같이 이용합니다.

for문이 두개 준비되어 있는데 위의 for문은 사용하지 말아야할 안티패턴으로 작성하였습니다.

그 이유로는 erase가 발생하면 기존의 iterator, pointer는 모두 invalidation되기 때문입니다.

다시말해 for문에서 사용되던 변수 it는 erase를 들어가고 나오면 무효화 되어 더 이상 사용불가입니다.

그런데 이를 이후에 증감 시킨다면? 컴파일이야 되었지만 런타임에러를 만나게 됩니다.

때문에 erase함수는 하단의 for문 처럼 반환값을 다시 it에 대입하는 방법으로 이용하며 

for의 증감문을 비워 두는 방법을 채택해야합니다.

위와 같은 방법으로 연관 컨테이너에서 erase를 안전하게 사용할 수 있습니다.