[C++] STL - deque

deque

덱은 벡터와 비슷한 배열 기반 시퀀스 컨테이너로서 반복자 및 멤버 함수가 거의 유사하다.

벡터와 다른 점은 덱은 push_front()와 pop_front()가 가능하다는 점이다.

#include <iostream>
#include <deque>
using namespace std;

int main(){
    deque<int> dq;
    dq.push_back(3); // 3
    dq.push_front(5); // 5 3
    dq.push_back(4); // 5 3 4
    dq.push_front(1); // 1 5 3 4

    dq.pop_front(); // 5 3 4

    for(int i: dq){
        cout << i << " ";
    }
    cout << "\n";

    cout << "덱 길이 : " << dq.size() << endl;
}

 

덱은 벡터와 같이 임의의 원소에 접근하거나 맨 뒤에 원소를 추가 / 제거하는 작업을 O(1)에 수행할 수 있다.

또한 임의의 위치에 원소를 추가 / 제거하는 작업도 벡터와 마찬가지로 O(n)에 수행한다.

 

	방법	시간복잡도
임의의 위치 원소 접근	[], at()	O(1)
맨 앞에 원소 추가 / 제거	push_front(), pop_front()	O(1)
맨 뒤에 원소 추가 / 제거	push_back(), pop_back()	O(1)
임의의 위치 원소 추가 / 제거	insert(), erase()	O(n)

 

다만 맨 처음과 맨 끝에 원소를 추가하는 속도는 벡터보다 더 빠르다.

그 이유는 덱의 구조에 있다.

 

 

덱은 벡터와 다르게 원소들이 메모리에 연속되어 존재하는 것이 아니라 일정 크기로 잘려서 블록 속에 존재한다.

그리고 이 블록들의 주소를 저장하는 벡터가 따로 필요하다. 

 

벡터의 기존에 할당한 메모리가 꽉찬 상태에서 원소를 추가하면 기존의 모든 원소들을 새로운 공간에 복사해야한다.

하지만 덱의 경우 그냥 새로운 블록을 만든 후 새로운 원소를 넣어주면 된다.

 

따라서 맨 처음과 끝에 원소들을 추가하는 작업을 많이 수행한다면 덱을 사용하는 것이 좋다.

---