std::deque

코딩 테스트를 위한 자료 구조와 알고리즘 with C++

 

 

std::deque

• STL에서 제공하는 양방향 큐(Double-ended Queue) 컨테이너다.
• 크기가 같은 여러 개의 메모리 청크로 나누어 데이터를 저장하는 일종의 페이징 기법을 사용한다.
• std::vector와 달리 용량 부족으로 추가 메모리 할당 시 전체 원소를 이동시키지 않아도 된다.
• 내부적으로 첫 번째 청크가 아닌 중간 위치의 청크부터 원소를 저장하여 메모리 재할당을 최소화하는 등의 최적화 기법이 적용되어 있다.
• size()는 제공하나 capacity()는 구현 방법에 의존적이므로 제공하지 않는다.

 

C++ 표준에서 규정하는 std::deque의 구현 조건

• push_front(), pop_front(), push_back(), pop_back()은 O(1) 시간에 수행된다.
• 모든 원소에 대한 임의 접근은 O(1) 시간에 수행된다.
• 중간에 원소를 삽입, 삭제하는 경우 O(n) 시간에 수행된다.
  (실제로는 최대 n/2이 소요된다.)

 

그럼 std::vector보다 std::deque가 무조건 좋은 것인가?

그렇지 않다.

std::vector는 단일 메모리 청크를 사용한다.
삽입, 삭제보다 단순 접근이 많은 경우 std::vector가 유리할 수 있다.

std::deque는 여러 개의 메모리 청크로 나누어 관리하는 페이징 기법을 사용한다.
용량 부족으로 추가 메모리 할당 시 전체 원소를 이동시키지 않아도 되기 때문에 삽입이 많은 경우 std::deque이 유리할 수 있다.
특히 앞이나 중간에서도 삽입, 삭제가 빈번한 경우에도 마찬가지이다.

 

#include <iostream>
#include <deque>

using namespace std;

ostream& operator<<(ostream& os, const deque<int>& deq)
{
    for (int e : deq)
        os << e << ' ';

    return os;
}

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

    // 맨 앞에 0 추가
    deq.emplace_front(0);
    cout << deq << endl;

    // 맨 뒤에 6 추가
    deq.emplace_back(6);
    cout << deq << endl;

    // 3번째 위치에 7, 8 추가
    deq.insert(deq.begin() + 2, {7, 8});
    cout << deq << endl;

    // 맨 뒤 원소 삭제
    deq.pop_back();
    cout << deq << endl;

    // 맨 앞 원소 삭제
    deq.pop_front();
    cout << deq << endl;

    // 4번째 원소부터 끝까지 삭제
    deq.erase(deq.begin() + 3, deq.end());
    cout << deq << endl;

    // 용량을 크기와 맞춘다.
    // 더 이상 원소 개수에 변화가 없는 경우 유용
    deq.shrink_to_fit();

    // 현재 크기
    cout << "크기: " << deq.size() << endl;

    // capacity()는 제공하지 않는다.
    // cout << "용량: " << deq.capacity() << endl;
}

 

출력

0 1 2 3 4 5
0 1 2 3 4 5 6
0 1 7 8 2 3 4 5 6
0 1 7 8 2 3 4 5
1 7 8 2 3 4 5
1 7 8
크기: 3