[자료구조] C++ Container Library : Sequential Containers - deque

C++ 표준 라이브러리(STL)의 일부인 컨테이너 라이브러리 중 순차 컨테이너(Sequeential Containers)에 해당하는 std::deque에 대해 정리한 글입니다.

---

📚 std::deque

📖 std::deque

• Double Ended Queue
• 앞쪽(Front)과 뒤쪽(Back) 둘 다 빠르게 삽입 및 삭제할 수 있는 자료 구조

➡️ vector처럼 메모리가 연속적이지는 않지만, 양쪽 끝 삽입 및 삭제가 $ O(1) $ 성능을 가지는 컨테이너

📌 std::deque 사용 예시 코드

#include <iostream>
#include <deque>   // 필수 헤더

using namespace std;

int main() {
    deque<int> dq;       // 덱 생성

    dq.push_back(1);     // 뒤에 추가
    dq.push_front(0);    // 앞에 추가
    dq.push_back(2);     // 뒤에 추가

    dq.pop_front();      // 앞에 하나 제거 (0 제거)

    // 출력 (임의 접근)
    for (size_t i = 0; i < dq.size(); ++i) {
        cout << dq[i] << " ";  // Random Access 가능
    }
    
    return 0;
}

• <deque> 헤더를 추가하여 사용 가능
• 인덱스를 이용한 임의 접근(Random Access) 가능

---

📖 std::vector vs std::deque

구분	vector	deque
메모리 구조	완전 연속적인 메모리	블록(block) 배열
끝 삽입 및 삭제	빠름 $ O(1) $	빠름 $ O(1) $
앞 삽입 및 삭제	느림 $ O(N) $	빠름 $ O(1) $
중간 삽입 및 삭제	느림 $ O(N) $	느림 $ O(N) $
임의 접근	빠름 $ O(1) $	빠름 $ O(1) $ ➡️ block map 계산

✅ deque는 앞 뒤 둘다 바르게 삽입 및 삭제할 수 있다.

✅ vector와 달리 메모리가 완전 연속적인 것은 아니다.

---

📖 std::deque의 내부 구조

• deque은 거대한 배열 하나로 이루어진 구조가 아닌, 여러 개의 고정 크기 배열(블록)을 연결한 구조

std::deque의 내부 구조

• 각 블록들은 포인터 배열(map)로 관리
• 필요할 때 블록을 새로 추가하면서 양쪽 끝에 삽입 및 삭제 ➡️ vector는 할당된 공간이 모두 차면 배열을 통째로 새롭게 할당하는 반면, deque는 새로운 버퍼를 추가하면 되기 때문에 데이터 삽입은 항상 $ O(1) $ 시간이 소요

컴포넌트	설명
map	블록들의 포인터를 저장하는 배열
block	실제 데이터가 저장된 고정 크기 배열
start	첫 번째 원소가 들어있는 블록과 그 인덱스
finish	마지막 원소가 들어있는 블록과 그 인덱스

📌 std::vector vs std::deque 내부 구조 비교

vector	deque
✅ start, finish, end_of_stroage 3개의 포인터로 관리	✅ start (block + index), finish (block + index), map (block array)로 관리

📌 블록(block) 크기

• 일반적으로 한 블록은 수십 개의 원소를 저장할 수 있도록 크기가 정해짐 ➡️ 정확한 블록의 크기는 구현체마다 다를 수 있음
• 대략 512 byte ~ 4 KB 정도 되는 블록을 많이 사용

---

📖 std::deque의 시간 복잡도

• push_back() / push_front() : $ O(1) $
• pop_back() / pop_front() : $ O(1) $
• operator[], at() 접근 : $ O(1) $
• 중간 삽입 및 삭제 : $ O(N) $

---

📖 deque의 주요 함수

• push_front(val) / push_back(val) : 맹 앞 / 맨 뒤 원소(val) 추가
• pop_back() / pop_front() : 맨 앞 / 맨 뒤 원소 제거
• operator[pos] / at(pos) : 임의 위치(pos)의 원소 접근
• insert(pos, val) : 해당 인덱스(pos)에 원소(val) 삽입
• erase(pos) : 해당 인덱스(pos)의 원소 제거

---

📖 deque 사용 시 주의할 점

• 메모리가 완전 연속적이지 않음
  • 포인터 연산을 vector와 같이 사용하면 안됨
  • iterator만 안전하게 사용해야 함

iterator
iterator는 컨테이너 내부 데이터를 가리키는 포인터 비슷한 개념
단순히 인덱스 접근이 아니라, 컨테이너 구조에 맞게 앞으로 가기 또는 뒤로 가기 기능을 제공하는 객체

• 중간 삽입 및 삭제는 vector와 동일하게 시간이 많이 소요됨
• 매우 많은 수의 push_front와 push_back이 있을 때 성능이 좋음

📌 vector와 deque 선택 기준

• deque이 vector보다 대부분의 상황에서 유리하게 보일 수 있지만, deque은 메모리 연속성을 보장할 수 없음 ➡️ C 배열의 라이브러리와 상호작용을 하거나, 공간지역성을 고려해야 하는 경우 deque이 불리함
  • 주로 뒤쪽에서만 원소 추가 및 삭제가 이루어짐 ➡️ vector 사용
  • 앞과 뒤 모두 자주 원소 추가 및 삭제가 이루어짐 ➡️ deque 사용
  • 메모리 연속성이 보장되어야 함 ➡️ vector 사용
  • 매우 큰 데이터 + 빠른 양쪽 삽입 ➡️ deque 사용

---