[Basic C++] #53_STL 알고리즘, remove + erase, 옮기고 삭제하기

[Basic C++] #53_STL 알고리즘, remove + erase, 옮기고 삭제하기

STL 알고리즘 중 "remove 알고리즘"에 대해 알아보겠습니다.

"전문가를 위한 C"의 17 항목, "STL 알고리즘 마스터하기"에 해당하는 내용입니다.

 

 

---

 

remove()

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
	vector<string> vStr{ "", "one", "", "two", "three", "four" };

	cout << "Original Elements : ";
	for (const auto& str : vStr)
		cout << str << " " << '/' << " ";

	cout << '\n';
	
   	  // remove_if (원본 범위 첫 번째, 원본 범위 마지막, 프레디킷)
	auto it = remove_if(begin(vStr), end(vStr), [](const string& str) { return str.empty(); });
	
	vStr.erase(it, end(vStr));

	cout << "Changed Elements : ";
	for (const auto& str : vStr)
		cout << str << " " << '/' << " ";

}

* 결과 화면

"remove_if" 알고리즘은 컨테이너의 특정 구간 내 항목들을 프레디킷 조건과 일치하는 항목들 그리고 일치하지 않는 항목들을 분할합니다.

따라서, "remove_if" 알고리즘은 구간 내 분할 지점을 가리키는 반복자를 반환하며, 이를 통해 "erase" 알고리즘으로 합치하지 않는 항목들을 삭제할 수 있습니다.

 

옮기고 삭제하기 개념, remove + erase 

 

왜 "erase" 알고리즘을 바로 적용하지 않을까?

 

 

이유는 간단합니다.

잘 알다시피, "vector" 컨테이너는 "erase" 메서드를 지원하기 때문에, 항목을 바로 삭제하는 것이 가능합니다.

 

하지만, 이러한 방법은 매우 비효율적입니다!

왜냐하면, 우리가 배열 자료구조의 단점을 먼저 공부했듯이, "vector" 또한 항목의 삭제 혹은 추가는 기존에 저장된 항목들을 이동시키는 작업이 필수적이기 때문이죠!

이때 발생하는 메모리 할당과 해제 작업이 "erase" 알고리즘의 상당히 느린 시간 성능 복잡도에 기인합니다.

 

따라서, 우리는 "옮기고 삭제하기 개념"을  "remove" + "erase"를 통해 구현합니다.

위 코드에서 잘 알 수 있듯이, "remove" 알고리즘은 프레디킷 조건과 합치하는 항목들과 불 합치하는 항목들을 분할하고, 합치하지 않는 항목들 중 첫 번째 항목을 가리키는 반복자를 반환합니다( 위 그림을 참조하세요 ㅎㅎ ).

결과적으로, "반환 값 ~ end" 구간의 항목들을 삭제함으로써, 우리가 원하는 "erase" 작업을 -> "remove + erase"로 작성할 수 있습니다!