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

Reference:

• "전문가를 위한 C++" / 마크 그레고리 / 한빛 미디어
• "Optimized C++" / 커트 건서로스 / 한빛 미디어

1. std::deque

std::deque은 배열 기반과 연결 리스트 기반의 두 가지 방식이 섞여 있는 형태이며, 각각의 장점을 적당히 갖고 있다.

std::vector에서 항목을 맨 앞에 삽입/삭제하는 작업은 비용이 많이 드는 작업이다. std::deque는 이러한 단점을 극복할 수 있다. 덱(deque)은 양방향 큐, double-ended queue의 약자이다.

c++ 표준에 있어 덱의 동작이 만족해야할 조건

• push_front(), pop_front(), push_back(), pop_back() 동작이 O(1) 시간 복잡도로 동작해야 한다.

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

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

위 요구 사항을 정리해보면, 덱은 양방향으로 매우 빠르게 확장할 수 있어야 하며, 모든 원소에 임의 접근을 제공해야 한다. 그러므로 자료구조가 벡터와 비슷하지만, 앞쪽과 뒤쪽으로 모두 확장할 수 있다는 점이 다르다.

원소 삽입과 삭제 시 n/2 단계를 허용한다는 점에서 이 연산이 모든 원소를 이동시키는 동작을 수반한다는 것을 예상할 수 있으며, 이러한 원소 이동은 벡터 삽입 또는 삭제를 할 때도 발생하는 연산이다.
다만, 원소 삽입 시 나머지 원소를 항상 오른쪽으로 이동해야 하는 것은 아니고, 삽입 위치에서 가장 가까운 끝으로 나머지 원소를 이동할 수 있다. 이에 따라 최대 n/2 단계의 시간 복잡도를 가지는 것이다.

덱의 메모리 구조

source: https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl

덱은 단일 메모리 청크를 사용하지 않는다. 대신 크기가 같은 여러 개의 메모리 청크를 사용하여 데이터를 저장한다. 청크의 인덱스 및 크기(하나의 청크에 저장된 원소 갯수)를 이용하여 특정 위치의 원소가 어느 청크에 저장되어 있는지를 알 수 있다. 모든 메모리 청크 주소를 연속적인 메모리 구조에 저장해놓고 사용하면 O(1)의 시간 복잡도로 원소의 임의 접근이 가능해진다. 따라서 덱의 구조는 배열 또는 벡터와 유사하다.

덱의 맨 앞에 새로운 원소를 추가할 경우, 만약 첫 번째 메모리 청크에 여유 공간이 없다면 새로운 청크를 할당하고, 이 메모리 청크 주소를 첫 번 째 메모리 청크 주소로 설정한다(Chunk 0).

deque는 벡터와 같은 임의 접근 반복자도 당연히 제공된다.

std::vector vs std::deque

std::deque는 std::vector와 같이 맨 뒤 항목 삽입과 색인에 있어 상수 시간을 갖으면서, 동시에 맨 앞 항목 삽입까지 상수 시간을 갖기에 굳이 std::vector를 사용할 이유가 없어 보인다.
그러나 deque에서 수행하는 모든 연산의 비례 상수는 벡터보다 크다는 것을 인지하여야 한다. deque의 일반적인 연산의 수행 시간은 vector보다 3~10배 정도 느리고, 반복/정렬/검색 시간은 30% 더 느리다.

deque는 여러 배열을 저장하는 배열 형태이다. 따라서 저장된 항목을 얻으려면 간접 참조를 두 번 해야 하는데 이는 캐시 지역성을 감소시킨다.

또한 deque는 메모리 할당자가 두 번 호출될 수 있다. deque의 앞이나 뒤에 항목을 삽입할 때, 한 번은 항목을 다른 블록에 추가할 때 호출되고, 다른 한 번은 내부 배열을 확장할 때 호출된다(자주 발생하지는 않음). 이러한 할당 작동은 벡터보다 더 복잡하며 추론하기 어렵다. 이러한 이유인지 std::deque는 std::vector의 멤버 함수인 reserve()처럼 내부 자료구조를 할당하는 함수를 제공하지 않는다.

결과적으로 deque의 성능과 특성을 살펴볼 때 FIFO 큐를 구현하는 컨테이너로 적합해 보인다.

---

2. std::deque 멤버 함수 사용법

#include <iostream>
#include <deque>

using namespace std;

int main(){
    std::deque<int> deq = {1, 2, 3, 4, 5};

    deq.push_front(0);

    deq.push_back(6);

    auto it = deq.begin();
    deq.insert(it+2, 10);   // 맨 앞에서 두 칸 뒤 10 삽입

    for(int i=0; i<deq.size(); i++){
        cout << deq[i] << ' ';
    }  
    cout << endl;

    // 1, 2, 10, 2, 3, 4, 5, 6

    deq.pop_back();

    deq.pop_front();

    for(int i=0; i<deq.size(); i++){
        cout << deq[i] << ' ';	// 임의접근 가능, O(1)
    }  
    cout << endl;

    // 1, 10, 2, 3, 4, 5

    // it == deq.begin()
    deq.erase(it+1);    // 맨 앞 다음 원소 삭제

    deq.erase(deq.begin()+3, deq.end());

    for(int i=0; i<deq.size(); i++){
        cout << deq[i] << ' ';
    }  
    cout << endl;

    // 1, 2, 3

}