C++ Erase-remove 관용구란 무엇인가?

Erase-remove 관용구(idiom)란 무엇인가?

Erase-remove 관용구는 컨테이너(주로 std::vector)에서 특정 조건에 맞는 원소들을 효율적이고 안전하게 제거하기 위해 사용하는 표준적인 방법이다. 단순히 erase만 사용했을 때에 발생하는 성능 저하와 복잡성을 해결해 주는 아주 중요한 기법이다.

왜 필요한가?

std::vector는 배열과 같이 연속된 메모리 구조를 가지고 있다. 그래서 중간에 있는 원소를 하나 제거하면, 그 뒤에 있는 모든 원소를 앞으로 한 칸씩 당겨야 하는 비효율이 발생한다. 또한, 반복문 안에서 erase를 잘못 사용하면 무효화된 반복자(Iterator Invalidation) 문제로 인해 프로그램이 충돌할 위험 또한 가지고 있다. 이때 이러한 문제를 해결하기 위해서 Erase-remove 관용구를 사용하는 것이다.

관용구 사용 방법

• 1단계 - std::remove() 또는 remove_if()
  • 유효한 원소들을 컨테이너 앞으로 당긴다.
  • 컨테이너의 실제 크기는 변하지 않지만, 유효한 데이터가 끝나는 지점의 반복자(Iterator)를 반환한다. 이 지점을 포함해서 컨테이너의 끝까지는 쓰레기 데이터가 남게 된다.
• 2단계 - erase()
  • std::remove가 반환한 지점부터 컨테이너의 진짜 끝(end())까지의 범위를 실제로 메모리에서 제거하고 크기를 줄인다.

코드 예시

#include <iostream>
#include <vector>
#include <algorithm> // std::remove를 사용하기 위해 필요

int main() 
{
    std::vector<int> v = {1, 3, 2, 3, 4, 3, 5};

    // Erase-remove 관용구 사용
    v.erase(std::remove(v.begin(), v.end(), 3), v.end());

    for (int n : v)
    {
        std::cout << n << " "; // 출력: 1 2 4 5
    }
}

std::remove() 

std::remove()는 앞에 std::가 붙은 걸로 알 수 있듯이 std::vector의 멤버 함수가 아니라 xmemory.h에 포함된 함수이다.

std::remove()는 주어진 범위 내에서 특정 값과 일치하지 않는 원소들을 앞으로 이동시켜서, 지우고 싶은 값을 덮어쓰거나 뒤로 밀어내는 역할을 한다.

• 실제 동작: 원소들을 재배치할 뿐, 컨테이너의 크기(size)는 변경하지 않는다.
• 반환 값: 유효한 원소들이 끝난 바로 다음 지점, 즉 새로운 끝(New End)을 가리키는 반복자(Iterator)를 반환한다.

std::remove() 예제 코드

int main()
{
	std::vector<int> v1 = { 1, 3, 2, 3, 4, 3, 5 };

	std::cout << "초기 값" << std::endl;
	for (const auto& i : v1)
	{
        	std::cout << i << " ";
	}

	std::cout << "\n";

	// remove 사용
	auto iter = std::remove(v1.begin(), v1.end(), 3);

	std::cout << "remove 후" << std::endl;
	for (const auto& i : v1)
	{
        	std::cout << i << " ";
	}

	std::cout << "\n";

	// erase 사용
	v1.erase(iter, v1.end());

	std::cout << "erase 후" << std::endl;
	for (const auto& i : v1)
	{
        	std::cout << i << " ";
	}
}

초기 값에서 std::remove()를 사용한 이후에는 3을 제외한 원소들이 앞쪽으로 이동한 것을 알 수 있다. 원소들만 재배치되었을 뿐, 컨테이너의 실제 크기는 변하지 않았다. 그리고 반환값으로 새로운 끝은 반환해서 해당 새로운 끝에서부터 컨테이너의 end()까지 제거하면 우리가 원하는 원소들만 남기는 게 가능하다.

시간 복잡도 비교

결론부터 이야기하자면 O(n^2)의 문제를 O(n)으로 해결하는 수준의 엄청난 차이가 발생한다.

• erase만 사용하는 경우: 원소를 지울 때마다 뒤쪽 원소들을 매번 앞으로 당기는 작업이 필요(O(n^2)의 복잡도)
• Erase-remove 관용구를 사용하는 경우: 모든 원소를 딱 한 번씩만 방문하거나 이동시킨 후 마지막에 한 번에 자른다.(O(n)의 복잡도)

C++ 20에서의 변화

C++ 20부터는 이 과정이 훨씬 더 간편해졌다. std::erase()와 std::erase_if()라는 전역 함수가 도입되어, 복잡한 구문 없이도 한 줄로 처리가 가능하다.

// C++20 방식
std::erase(v, 3); 
std::erase_if(v, [](int n) { return n % 2 != 0; });

정리하자면

• std::vector에서 erase() 사용 시에 효과적으로 erase()를 사용하기 위해서 Erase-remove 관용구를 사용한다.
• 해당 관용구를 통해서 효율적으로 원소를 제거하는 게 가능하다.
• 이는 std::vector가 연속된 메모리 구조를 가지고 있기 때문에 발생하는 구조적 이슈이다.
• C++ 20에서는 해당 과정이 std::erase() 함수를 사용하면 한방에 해결된다.