9-6. STL - Deque

0. 시퀀스 컨테이너 (Sequence Container)

데이터가 삽입한 순서대로 나열되는 형태

ex) vector, list, deque

 

1. Deque(Double-ended Queue ; 데크)

큐와 스택의 특징을 모두 가지는 형태.

동적 배열의 형태이지만 vector와는 조금 다르게 작동함.

이중 연결 리스트의 형태이지만 list와는 다르게 임의 접근이 가능함.

각 블록이 메모리 영역에 연속적으로 있지 않기 때문에 포인터 연산이 불가능함.

 

2. vector와의 차이점

 

- vector : size가 capacity보다 커지면 메모리 영역을 제거하고 더 큰 메모리 영역을 재할당하고 데이터를 복사 / 이동시킴.

- deque : size가 capacity보다 커지면 다음 데이터 부터는 다른 메모리 영역에 저장.

 

3. 처음과 끝 삽입 및 삭제

양 끝이 뚫린 큐처럼 되어 있기 때문에 처음과 끝에서 데이터 삽입과 삭제가 용이함.

 

4. 중간 삽입 및 삭제

블록에서 중간의 데이터가 제거되면 뒤에 있는 블록에서 데이터를 하나씩 당겨와서(복사/이동) 저장함 -> 속도가 느림.

(단, vector보다는 빠를 수 있음)

 

5. 임의 접근

데이터가 블록 단위로 저장되어 있기 때문에 임의 접근은 빠르게 작동함.