deque
deque (std::deque — 양방향 큐)
앞과 뒤 양쪽 끝에서 빠른 삽입/삭제가 가능한 인덱스 시퀀스 컨테이너예요. double-ended queue라고도 불러요. <deque> 헤더에 있어요.
출처: cppreference
본문
std::deque는 양쪽 끝에서의 삽입·삭제가 빠른 인덱스 시퀀스 컨테이너예요.
template<
class T,
class Allocator = std::allocator<T>
> class deque;
C++17부터 std::pmr::deque 별칭(폴리모픽 할당자)도 있어요.
핵심 특징을 정리하면:
- 앞과 뒤 어느 쪽에서도 요소 삽입/삭제가 빠르고, 어느 한쪽 끝에서의 삽입/삭제는 나머지 요소를 가리키는 포인터나 참조를 무효화하지 않아요.
std::vector와 달리 요소가 연속적으로 저장되지 않아요. 전형적인 구현은 고정 크기 블록들의 시퀀스로 요소를 나눠 담고요.- 임의 접근(indexing)은 상수 시간에 가깝지만 벡터만큼 빠르진 않아요.
- 중간 삽입/삭제는 선형 시간이고, 삽입 시 필요하면 재할당·재배치가 일어나요.
어떤 면에서 std::vector와 std::list의 중간 성격이에요. 양쪽 끝에서 큐/스택처럼 쓰기 좋고, push_front가 필요한 상황에서 vector보다 적합해요.
std::deque<int> dq;
dq.push_back(1);
dq.push_front(0); // vector에 없는 연산, deque는 상수 시간
반복자 무효화 규칙이 벡터와 달라서 양끝 조작이 잦은 코드에 적합하지만, 중간 원소의 잦은 접근·수정이 필요하면 vector가 더 좋아요.