[1. 리스트, 스택, 큐] C++ std::deque

std::deque

---

벡터는 가변 길이 배열이고, push_front() 또는 pop_front() 같은 함수는 비용이 많이 든다. (다 하나씩 밀어줘야 함)

std::deque를 통해 이런 단점을 극복할 수 있다. (double-ended queue)

 

덱(deque)의 구조

- push_front(), pop_front(), push_back(), pop_back() 동작이 O(1) 시간 복잡도로 동작해야 한다.
- 모든 원소에 대해 임의 접근 동작이 O(1) 시간 복잡도로 동작해야 한다.
- 덱 중간에서 원소 삽입 또는 삭제는 O(n) 시간 복잡도로 동작해야 하며, 실제로는 최대 n/2 단계로 동작한다. (n: 덱의 크기)

- 덱은 자료구조가 벡터와 비슷하지만 앞쪽과 뒤쪽으로 보두 확장할 수 있다.

- 원소 삽입 시 해당 위치에서 가장 가까운 끝 쪽으로 나머지 원소를 이동하기에 n/2 단계의 시간 복잡도를 갖는다.

- 크기가 같은 여러 개의 메모리 청크를 사용하여 데이터를 저장한다.

- 청크의 인덱스 및 크기를 이용하여 특정 위치의 원소가 어느 청크에 저장되어 있는지 알 수 있다.

- 벡터와 리스트에서 제공되는 함수를 조합한 것 이상의 기능을 제공한다. (capacity() 함수는 지원되지 않는다.)

- 임의 접근 반복자도 제공된다.

 

예제 코드는 다음과 같다.

#include <iostream>
#include <deque>
using namespace std;
int main(){
    deque<int> deq = {1, 2, 3, 4, 5};
    deq.push_front(0); // {0, 1, 2, 3, 4, 5}
    deq.push_back(6); // {0, 1, 2, 3, 4, 5, 6}

    deq.insert(deq.begin() + 2, 10); // {0, 1, 10, 2, 3, 4, 5, 6}

    deq.pop_back(); // {0, 1, 10, 2, 3, 4, 5}
    deq.pop_front(); // {1, 10, 2, 3, 4, 5}

    deq.erase(deq.begin() + 1); // {1, 2, 3, 4, 5}

    deq.erase(deq.begin() + 3, deq.end()); // {1, 2, 3}

    for(auto i : deq)
        cout << i << " ";
    return 0;
}

 

덱은 데이터 맨 뒤와 맨 앞에서도 매우 빠르게 원소의 삽입과 삭제가 가능하다.

또한 데이터 중간에서의 삽입 또는 삭제에 대한 시간복잡도는 벡터와 같지만, 실제로는 벡터보다 약간 더 빠르다.