[C++] 정렬되지 않은 벡터(vector) O(1)시간으로 요소 삭제하기

0. 벡터의 소개

• 벡터는 배열 형태의 저장소가 필요할 때 다양한 크기로 변할 수 있다.
• 힙(heap)메모리를 이용해서 객체를 저장한다.
• 벡터의 한계에 다다르면 새로 배당된 메모리 영역으로 옮긴 뒤 기존 메모리 영역은 삭제한다.
• 요소를 추가하거나, 삭제하면 그에 맞춰 기존 요소를 앞뒤로 이동시킨다.
• 벡터의 한가운데에서의 요소 제거는 O(n)의 시간이 걸린다. (삭제 후 생긴 공백을 요소를 옮기면서 채운다.)

 

 

1. 정렬되지 않은 벡터 O(1) 시간으로 삭제하기

• 원리는 간단하다.
• 삭제하고 싶은 부분의 인덱스를 가져온다. 
• 벡터의 끝에 있는 값을 삭제할려는 인덱스에 덮어 씌운다.
• 벡터의 끝 값은 삭제한다.

 

ex) 예제

• 100, 200, 300를 가지는 벡터가 있다고 가정해보자.
• 여기서 인덱스 1번을 지우고 싶다. 즉 200을 지우고 싶다. (벡터는 인덱스가 0부터 시작하므로)
• 100, 300, 300으로 끝 값을 삭제하려는 곳에 덮어 씌운다.
• 100, 300  파란색의 300은 삭제된다.

 

 

 

2. 인덱스를 이용해서 삭제하기 (삭제시간 O(1))

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

using namespace std;

template <typename T>
void quick_remove_at(vector<T>& v, size_t idx)
{
	if (idx < v.size()) {
		v[idx] = move(v.back()); //마지막 원소를 이동
		v.pop_back();            //맨 끝 데이터 삭제
	}
}

int main()
{
	vector<int> v{ 100,200,300,400,500 };

	quick_remove_at(v, 2); //인덱스 2번 300을 삭제

	for (int i : v) {
		cout << i <<", ";
	}
	cout << '\n';

}

Output :

100, 200, 500, 400

 

출력값이 100, 200, 400, 500으로 나오지 않은 이유는 500을 300의 자리로 이동시켰기 때문이다.

삭제 후의 벡터 순서는 100, 200, 500, 400의 순서가 된다.

마지막 요소를 이용해 제거하는 이유는 비용이 아주 적게 들기 때문이다.

 

다음 코드는 300을 지우고 싶지만, 해당 인덱스를 모를 경우 처리하는 방법이다.

 

 

 

 

3. 특정값 삭제하기 (삭제시간 O(1))

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

using namespace std;

template <typename T>
void quick_remove_at(vector<T>& v, typename vector<T>::iterator it)
{
	if (it != end(v)) {
		*it = move(v.back());
		v.pop_back();
	}
}

int main()
{
	vector<int> v{ 100,200,300,400,500 };

	quick_remove_at(v, find(begin(v), end(v), 300)); //300의 인덱스를 찾고 삭제

	for (int i : v) {
		cout << i <<", ";
	}
	cout << '\n';

}

Output:

100, 200, 500, 400

 

아까와 다른 점은 find을 통해 특정 값의 범위를 받고 위치를 탐색한다.

이 경우 300의 값을 가리키는 반복자를 반환하게 된다.

그리고 quick_remove_at에서 vector<T>의 반복자를 받는다.

처리 방식은 반복자가 end 위치를 가리킬 때 허용하지 않는 것 말고는 같다.

 

 

 

 

참고문헌

C++17 표준 라이브러리를 활용하는 90가지 레시피/ 야체크 갈로비치 지음