deque

시퀀스 컨테이너

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

vector list deque

 

vector : 동적배열

[     이어진 데이터      ]

list : 이중연결 리스트

[ ] <-> [ ] <-> [ ] <-> [ ] <->header

 

deque: double-ended queue 데크

[        ]

[        ]

[        ]

vector 와 list 가 짬뽕된 느낌이지만 vector에 조금 더 가깝다

vector 와 마찬가지로 배열 기반으로 동작

다만 메모리 할당 정책이 다르다

메모리를 늘릴때

vector 는

[    기존 ] 확장  ] 확장시 기존걸 복사 후 확장해서 붙여넘

deque는

[     기존     ]

[     확장     ] 추가영역을 만들어서 확장 이라고 보면 됨

 

#include <deque> 필요

 

 

중간 삽입/삭제 (Bad / Bad)

처음/끝 삽입/삭제(Good / Good)

임의접근 (Good)

 

각 몇번째 데이터라는것을 테이블로 관리하다보니 임의접근이 list 처럼 어렵지 않음