deque는 O(1)의 random access를 지원한다.
deque는 double ended queue의 약자이다.
- random access O(1)
- 시작과 끝에 원소 삽입, 삭제 O(1) (emplace_back, pop_back, emplace_front, pop_front)
- 시작 끝 제외 원소 삽입, 삭제 O(n)
vector에서는 시작에 삽입하기위해서 모든 원소를 하나씩 밀어야하므로 O(n)의 시간복잡도를 가진다.
deque에서는 2번의 포인터 dereferecing을 통해 동작한다
여러개의 메모리 청크를 가리키는 포인터들을 가지고 있으며 random access는 몇번째 포인터의 메모리 청크의 몇번째 원소인지 알려준다.
첫번째 메모리 청크의 중간부터 사용하여 시작에 원소를 집어넣어도 O(1)의 시간복잡도를 가지는 것이다.
만약 메모리 청크를 가득채우면 추가로 메모리청크를 생성하여 원소를 집어넣는다.
포인터 레퍼런싱덕에 원소를 집어넣을 때 move대신 copy가 일어나는 일은 존재하지 않는다.
단점으로는 원소가 중간에 끊어지므로 cache miss가 일어날 수 있다.
