1.8 deque

덱 (deque) : 양방향 큐(double-ended queue)

c++ 표준은 덱의 동작에 있어서 다음 조건을 만족해야 한다고 규정한다.

1. push_front(), pop_front(), push_back(), pop_back() 동작이 O(1) 시간 복잡도로 동작

2. 모든 원소에 대해 임의 접근 동작이 O(1) 시간 복잡도로 동작해야 한다.

3. 덱 중간에서 원소 삽입 또는 삭제는 O(n) 시간 복잡도로 동작해야 하며, 실재로는 최대 n/2단계의 시간 복잡도로 동작한다. 

 

덱은 크기가 같은 여러 개의 메모리 청크를 사용하여 데이터를 저장한다. 모든 메모리 청크 주소를 연속적인 메모리 구조에 저장해놓고 사용하면 O(1) 시간 복잡도로 원소의 임의 접근이 가능해진다.

 

덱의 멤버함수

push_front(), push_back(), insert(), emplace_front(), emplace_back(), emplace(), pop_front(), pop_back(), erase(), shrink_to_fit() 등의 함수 제공

capacity()함수는 지원되지 않는다.

임의 접근 반복자 제공

 

std::deque은 매우 빠른 push_front()와 push_back()동작과 효과적인 임의 접근을 제공하는 유일한 컨테이너이다.