[C++] Deque

1. 개요

std::deque(double-ended queue)는 양쪽 끝에서 삽입과 삭제가 가능한 시퀀스 컨테이너입니다. <deque> 헤더에 정의되어 있으며, 내부적으로 블록 단위로 메모리를 관리합니다.

 #include <deque>
 std::deque<int> dq = {1, 2, 3};

2. 주요 특징

• 양쪽 끝에서 삽입/삭제가 O(1) 시간에 가능
• 임의 접근(random access) 가능
• 메모리는 연속적이지 않음 (블록 기반)
• 중간 삽입/삭제는 느림
• 반복자 무효화: 삽입/삭제 시 일부 반복자 무효화 가능

  3. 주요 생성자

생성자	설명
deque()	빈 덱 생성
deque(size_type n)	n개의 기본값 요소 생성
deque(size_type n, const T& val)	n개의 val로 초기화
deque(InputIterator first, InputIterator last)	범위 기반 초기화
deque(const deque& other)	복사 생성자

4. 주요 멤버 함수

🔹 크기 관련

함수	설명
size()	요소 수
max_size()	최대 요소 수
empty()	비었는지 확인
resize(n)	크기 조절
shrink_to_fit()	메모리 최적화
clear()	모든 요소 삭제

🔹 접근

함수	설명
operator[], at(i)	인덱스를 통한 요소 접근
front() / back()	양 끝 요소
data()	내부 배열 포인터 (C++17~)

🔹 삽입/삭제

함수	설명
push_front(val) / push_back(val)	앞/뒤에 요소 추가
pop_front() / pop_back()	앞/뒤 요소 제거
insert(pos, val)	특정 위치에 삽입
erase(pos)	특정 위치 요소 제거
emplace(pos, args...)	위치에 직접 생성
emplace_front(args...) / emplace_back(args...)	앞/뒤에 직접 생성
assign()	범위 또는 값으로 전체 초기화
swap()	두 덱 교환

5. 반복자 관련

함수	설명
begin() / end()	정방향 반복자
rbegin() / rend()	역방향 반복자
cbegin() / cend()	const 반복자

6. 예제 코드

 #include <iostream>
 #include <deque>
 using namespace std;
 
 int main() {
     deque<int> dq = {2, 3};
 
     dq.push_front(1);
     dq.push_back(4);
 
     for (int v : dq) {
         cout << v << " ";
     }
     cout << endl;
 
     dq.pop_front();
     dq.pop_back();
 
     for (int v : dq) {
         cout << v << " ";
     }
     cout << endl;
 
     return 0;
 }

7. std::vector vs std::deque

항목	std::deque	std::vector
메모리	블록 분산	연속적
앞 삽입/삭제	빠름	느림
뒤 삽입/삭제	빠름	빠름
임의 접근	O(1)	O(1)
메모리 오버헤드	있음	적음

8. 주의사항

• 메모리가 연속적이지 않아 C 배열처럼 사용은 제한적
• 반복자 사용 시 삽입/삭제로 인한 무효화에 주의
• 다방향 삽입/삭제가 필요한 경우 유용