[C++STL] 시퀀스 컨테이너 - deque

deque는 vector와 기능의 가장 비슷한 컨테이너이다. 둘의 차이는 vector의 하나의 메모리 블록 할당 정책은 배열처럼 정수 연산만으로 원소에 접근하고 빠르게 값을 읽고 쓸 수 있다. 하지만 새로운 원소가 추가될 때 메모리 재할당과 이전 원소 복사 문제가 발생하여 성능이 저하된다. deque는 vector의 단점을 해결하기 위해 여러 개의 메모리 블록을 할당한다. 여기서 중요하게 봐야할 것은 vector는 하나의 메모리 블록을, deque는 여러개의 메모리 블록을 할당한다는 것이다. 원소 추가 시 메모리가 부족할 때마다 일정한 크기의 새로운 메모리 블록을 할당하여 전체 메모리를 재할당 한다거나 이전 원소를 복사하는 등의 연산을 수행하지 않는다. 아래는 deque의 push_front() 멤버 함수를 사용한 예제이다.

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

int main()
{	
	deque<int> dq;
	dq.push_back(10);
	dq.push_back(20);
	dq.push_back(30);
	dq.push_back(40);
	dq.push_back(50);
	for (deque<int>::size_type i = 0; i < dq.size(); ++i) 
	{
		cout << dq[i] << " ";
	}
	cout << endl;
	dq.push_front(100);
	dq.push_front(200);
	for (deque<int>::size_type i = 0; i < dq.size(); ++i)
	{
		cout << dq[i] << " ";
	}
	cout << endl;
	dq.pop_front(); 
	dq.pop_front();
	for (deque<int>::size_type i = 0; i < dq.size(); ++i)
	{
		cout << dq[i] << " ";
	}
	cout << endl;

	return 0;
}

위 예제처럼 push_front()로 원소를 앞쪽에 추가하면 기존 메모리 블록 앞에 메모리 블록을 할당하고 원소를 저장해 나간다. 10 앞에 새로운 메모리 블록이 할당되고 100을 채우고 100 앞에 200을 채우는 방식이다. 그리고 pop_front()로 맨 처음 원소를 제거할 수 있다. 개인적인 의견으로는 vector와 비슷하게 동작하나 맨 앞의 원소를 추가하거나 제거할 일이 있으면 deque를 쓰는게 성능면에서 더 좋을것 같다는 생각이 든다.

deque, vector 모두 insert와 erase 함수는 비효율적으로 동작하나 deque가 조금 더 효율적이다.