[c++] erase-remove idiom

어떤 vector에서 특정 값을 갖는 원소들을 제거하고 싶을 때 어떻게 코드를 작성하면 될까? 쉽게 생각하면 O(n2)의 방법을 떠올릴 수 있을 것이다. 하지만 O(n)으로 이것을 가능하게 할 수 있다. 이 방법을 erase-remove idiom이라고 한다. 아래 코드는 erase-remove idiom으로 vector에 존재하는 값 중 0인 값을 모두 제거하는 코드이다. 이번 포스트에서는 이와 같은 작업을 가능하게 해주는 std::remove, std::vector<T,Allocator>::erase에 대해서 알아보고자 한다.

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
	std::vector<int> nums{0, 1, 0, 1, 0, 1, 0};
	nums.erase(std::remove(nums.begin(), nums.end(), 0), nums.end());

	for (int num: nums) {
		std::cout << num << " ";
	}
	std::cout << std::endl;
}

std::remove

cppreference에서 remove의 구현을 보면 다음과 같다.

template< class ForwardIt, class T >
ForwardIt remove(ForwardIt first, ForwardIt last, const T& value)
{
    first = std::find(first, last, value);
    if (first != last)
        for(ForwardIt i = first; ++i != last; )
            if (!(*i == value))
                *first++ = std::move(*i);
    return first;
}

3번째 인자로 value를 받고 첫번째 iterator부터 두번째 iterator전까지 순회하며 value와 같은 같이 있으면 제거한다.
따라서 다음코드가 실행되면 nums의 값은 다음과 같다.

1. 첫번째 iter부터 두번째 iter전까지를 순회하며 처음으로 value와 값이 같은 수를 가리키는 iter를 찾는다.
2. 조건문
   2-1. 그런 iter가 존재하지 않으면 삭제할 원소가 존재하지 않다는 뜻이므로 종료한다.
   2-2. 그런 iter가 존재하면 3을 진행한다.
3. 두개의 iter를 가지고 vecotor를 순회한다. iter i는 vector를 순회하면서 value가 아닌 값을 만나면 그 값을 iter first가 가리키는 값에 이동시킨다. 이동을 완료했으면 iter first는 다음 원소를 가리킨다.
4. iter first를 반환한다.

위와 같은 알고리즘으로 i가 vector 순회를 마치면, iter first가 가리키는 원소 이전까지는 모두 value가 아닌 값들로 채워져있을 것이다. 다음 코드를 살펴보고 output값을 예측해보자.

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
	std::vector<int> nums{0, 1, 0, 1, 0, 1, 0};
	std::remove(nums.begin(), nums.end(), 0);

	for (int num: nums) {
		std::cout << num << " ";
	}
	std::cout << std::endl;
}
    // output : 1, 1, 1, 1, 0, 1, 0

std::vector<T,Allocator>::erase

cppreference에서 std::vector<T,Allocator>::erase의 정의를 보면 다음과 같다.

iterator erase( iterator first, iterator last );

erase는 [first, last) 범위의 요소를 모두 제거한다. std::remove의 반환값은 first였는데 이때 first의 이전 원소까지가 유효한 원소들이였으므로 first부터 지우는 것이 합당함을 알 수 있다. 다음 코드를 살펴보고 output값을 예측해보자(본문의 처음코드와 같음)

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
	std::vector<int> nums{0, 1, 0, 1, 0, 1, 0};
	nums.erase(std::remove(nums.begin(), nums.end(), 0), nums.end());

	for (int num: nums) {
		std::cout << num << " ";
	}
	std::cout << std::endl;
}
	// output : 1, 1, 1

이로써 우리가 처음 목표로했던 결과를 얻을 수 있다.