(C++) Deque

Posted by : C++ at Apr 7, 2021

Category : Cpp

Sequence Container
요소가 삽입된 순서대로 놓여있는 컨테이너

#include <iostream>
#include <deque>

using namespace std;

int main() {
	deque<int> dq{4, 2, 3, 5, 1};
	dq.push_back(4);
	dq.push_back(2);
	dq.push_front(1);
	dq.push_front(5);
	dq.push_front(3);

	for (auto& it: dq) {
		cout << it << ",";
	}
}

vector와 마찬가지로 배열 기반으로 동작
단, 메모리 할당 정책이 다르다.

vector의 경우 메모리를 새롭게 계속 할당
deque의 경우 메모리를 쌓아 나간다

vector<int> v(3, 1);
deque<int> dq(3, 1);

// vector 
// [1 1 1]

// deque
// [1 1 1]

v.push_back(2);
v.push_back(2);
dq.push_back(2);
dq.push_back(2);

// vector 
// [1 1 1 2 2]

// deque
// [1 1 1 2] [2     ]

dq.push_front(3);

// deque
// [     3] [1 1 1 2] [2     ]

메모리 통을 추가/삭제 하기에 시작/끝 삽입/삭제는 빠르다.
중간 삽입/삭제의 경우 재 정렬이 필요하기에 느리다.
임의접근의 경우 정해진 메모리가 있기에 빠르다.

deque<int> dq;

dq.push_back(1);
dq.push_front(2);
// dq.capacity();   // 없음

dq[0];  // 임의접근 가능