deque

deque은 이전에 알아본 vector와 매우 유사하다.

deque도 vector와 마찬가지로 시퀀스 컨테이너이자, 배열 기반 컨테이너다.
따라서 컨테이너 내부 원소들이 순차적인 순서를 가지며, 임의 접근 반복자([])를 사용할 수 있다.

vector와의 차이점

deque은 vector와 동일한 인터페이스를 제공한다.
따라서 deque의 인터페이스를 다시 정리할 필요는 없다.

vector는 원소가 추가될 때 메모리 재할당, 이전 원소 복사가 동반된다.
이는 매우 비효율적인 연산이었다.

deque은 vector와는 조금 다른 좀 더 효율적인 전략을 사용한다.

현재 deque의 capacity()를 초과하면서 원소가 추가된다면 새로운 메모리 블럭을 덧붙인다.

매번 메모리 재할당이 발생하지 않으며, 이전 원소를 복사하지도 않는다.

인터페이스

deque은 vector가 가지고 있는 인터페이스를 모두 가지고 있다.
하지만 deque의 특성으로 몇 개의 인터페이스가 더 추가된다.

맨 앞에서의 원소의 삽입/제거

deque은 stack과 queue를 합친 특성을 가진다.
따라서 맨 뒤에서의 삽입/삭제도 가능하고 맨 앞에서의 삽입/삭제도 가능하다.

push_front()는 deque의 맨 앞에 원소를 삽입한다.
pop_front()는 deque의 맨 앞의 원소를 제거한다.

#include <iostream>
#include <deque>

using namespace std;

int main(void)
{
    deque<int> deq;

    deq.push_back(10);
    deq.push_back(20);
    deq.push_back(30);
    deq.push_back(40);
    deq.push_back(50);

    // 10 20 30 40 50이 출력된다.
    for(deque<int>::size_type i = 0; i < deq.size(); i++)
        cout << deq[i] << ' ';
    cout << endl;

    deq.push_front(100);
    deq.push_front(200);

    // 200 100 10 20 30 40 50이 출력된다.
    for(deque<int>::size_type i = 0; i < deq.size(); i++)
        cout << deq[i] << ' ';
    cout << endl;

    deq.pop_front();

    // 100 10 20 30 40 50이 출력된다.
    for(deque<int>::size_type i = 0; i < deq.size(); i++)
        cout << deq[i] << ' ';
    cout << endl;
}

deque의 push_front()도 push_back()과 비슷한 전략을 가진다.

모든 원소를 한 칸씩 밀어내어 자리를 만들어내는 것이 아니다.
새로운 메모리 블럭을 할당하여 deque의 맨 앞에 이어 붙인다.

임의 접근 반복자

deque도 vector와 마찬가지로 배열 기반 컨테이너다.
따라서 deque도 임의 접근 반복자를 가지며 []연산이 가능하다.

#include <iostream>
#include <deque>

using namespace std;

int main(void)
{
    deque<int> deq;

    for(int i = 0; i < 5; i++)
        deq.push_back(10 * (i + 1));

    for(deque<int>::size_type i = 0; i < deq.size(); i++)
        cout << deq[i] << ' ';
    cout << endl;

    deque<int>::iterator iter = deq.begin() + 2;
    cout << *iter << endl;  // 30이 출력된다.
    
    iter += 2;
    cout << *iter << endl;  // 50이 출력된다.
    
    iter -= 3;
    cout << *iter << endl;  // 20이 출려된다.
}

중간 요소의 삽입/삭제

deque은 vector와 마찬가지로 중간 요소의 삽입/삭제가 가능하다.
vector와 동일하게 insert()와 erase()를 사용한다.

하지만 작동 방식이 조금 다르다.

vector는 삽입한 지점부터 모든 원소가 한 칸씩 밀린다.

deque은 삽입한 지점에서 앞과 뒤를 확인하여 어느 쪽의 원소가 더 적은지 확인한다.
그리고 더 적은 원소의 방향으로 밀어내는 전략을 취한다.

중간 요소의 삭제도 삽입과 마찬가지로 비슷하게 동작한다.

#include <iostream>
#include <deque>

int main(void)
{
    deque<int> deq;

    for(int i = 0; i < 5; i++)
        deq.push_back(10 * (i + 1));

    // 10 20 30 40 50이 출력된다.
    for(deque<int>::size_type i = 0; i < deq.size(); i++)
        cout << deq[i] << ' ';
    cout << endl;

    deque<int>::iterator iter = deq.begin() + 2;
    deq.insert(iter, 100);

    // 10 20 100 30 40 50이 출력된다.
    // deque의 맨 앞에 메모리 블럭이 추가되며 10이 앞으로 밀린다.
    for(deque<int>::size_type i = 0; i < deq.size(); i++)
        cout << deq[i] << ' ';
    cout << endl;

    iter = deq.begin();
    deq.erase(iter);

    // 20 100 30 40 50이 출력된다.
    // deque의 맨 앞의 메모리 블럭이 텅 비므로 해제된다.
    for(deque<int>::size_type i = 0; i < deq.size(); i++)
        cout << deq[i] << ' ';
    cout << endl;
}

정리

• deque은 시퀀스 컨테이너이자, 배열 기반의 컨테이너다.
• deque은 stack과 queue의 특징을 모두 가지고 있는 컨테이너다.
• deque은 삽입 연산은 메모리 블럭을 덧붙이는 방식으로 동작한다.
• deque은 임의 접근 반복자를 사용하므로 []을 사용할 수 있다.