• 참고자료
  : 씹어먹는 c++, 코드없는 프로그래밍

덱이란?

: 벡터의 기능에 덧붙여 앞에 삽입, 삭제가 시간복잡도가 O(1)인 컨테이너

push_front, pop_front 함수 사용가능!

메모리 할당정책

• 여러개의 포인터가 있는 메모리가 있고, 각각의 포인터들은 고정된 사이즈의 블록을 가리키도 있다. 떨어져 있는 블록은 연속적인 메모리를 가지고 있지 않다.

vector에 비하여 장점은?

1.벡터에서 앞에서 삽입,삭제를 할 경우 시간복잡도는 O(n)이지만,
컨테이너 앞에서 데이터를 삽입,삭제할수 있는 덱을 쓰면
O(1)만에 가능하다.
2.벡터의 경우 재할당이 이루어지고, 복사가 이루어 지지만,
덱의 경우에는 새로운 블록을 생성하고, 하나의 포인터가 그 블록을
가리키는 방식이어서, 삽입시 성능이 좋다

자체적인 단점은?

1. 서로 다른 블록의 요소를 참조할 경우, 캐시미스가 발생해서 효율이 떨어질 수 잇다.

2. 인덱스 접근을 할 경우, 포인터 집합에서 해당 인덱스가 있는 포인터를 참고, 포인터로 역참조를 해야하므로 성능이 좋지 않다.

3. 메모리를 많이 차지하고 있는 컨테이너이다.

결론

deque이 vector보다 메모리 삽입 시에는 성능이 좋을지는 몰라도,,
메모리 비용 때문에 vector가 deque보다 훨씬 좋다.