[C++] STL Deque 알아보기

deque은 vector처럼 랜덤 액세스가 가능하고 list처럼 양방향 push, pop이 가능한 자료구조로
double ended queue의 약자입니다.

이번 포스트에서는 deque의 특징과 멤버 함수에 대해 알아보겠습니다.

Deque 메모리 공간 확보 방법

deque은 벡터처럼 랜덤 액세스가 가능해 닮아보이지만, 원소 추가에 대한 메모리 공간 확보 방법이 다릅니다.
벡터는 새로운 원소가 추가(push_back())될 때, 현재 메모리에 붙여서 사용하지 않고 새로운 메모리 공간 을 할당받고
모든 원소와 새로운 원소를 새로 할당 받은 메모리 공간에 복사합니다.
따라서 벡터에서 원소가 반복되어 추가될 경우, 메모리 재할당이 자주 발생할 수 있습니다.
(그래서 벡터는 메모리 공간 함수인 capacity()가 있습니다.)

그러나 deque은 사용중인 메모리 공간을 그대로 사용 하고 새로운 메모리 공간을 할당받아 새로운 원소를 넣습니다.
메모리 공간에서는 연속되지 않은 여러 블록(할당받은 메모리 공간)을 사용하지만
사용자는 연속된 블록처럼 deque을 사용할 수 있습니다.
(그래서 deque은 메모리 공간 함수인 capacity()가 없습니다.)

아래의 코드는 벡터와 deque에 100’000번 원소를 추가한 뒤 시작 주소를 비교하는 코드입니다.

#include <iostream>
#include <vector>
#include <deque>

#define MAX 100'000

using namespace std;

void add_vec_element(vector<int>& vec) {
    for(int i = 0; i < MAX; ++i) {
        vec.push_back(i);
    }
}

void add_dq_element(deque<int>& dq) {
    for(int i = 0; i < MAX; ++i) {
        dq.push_back(i);
    }
}

int main() {
    vector<int> vec(MAX, 1);
    cout << "Vector start addr: " << &vec[0] << " -> ";
    add_vec_element(vec);
    cout << &vec[0] << "\n";
    
    deque<int> dq(MAX, 1);
    cout << "Deque start addr: " << &dq[0] << " -> ";
    add_dq_element(dq);
    cout << &dq[0] << "\n";

    return 0;
}

벡터의 경우, add_vec_element() 함수를 실행한 뒤 시작 주소가 변경되었지만
deque은 add_dq_element() 함수 뒤에도 동일한 시작 주소를 갖고 있습니다.

Deque 원소 추가하기

deque이 double ended queue 의 약자인 만큼 양방향에서 원소의 삽입, 삭제 연산을 수행할 수 있습니다.

멤버 함수	설명
push_front()	새로운 원소를 시작위치에 삽입합니다.
pop_front()	첫 번째 원소를 제거합니다.
push_back()	새로운 원소를 마지막 위치에 추가합니다.
pop_back()	마지막 원소를 제거합니다.

Deque 멤버 함수

멤버 함수	설명
assign()	특정 원소로 채우기
at()	특정 위치의 원소의 참조를 리턴 (outofbound 확인때문에 []연산자보다 느림)
begin()	첫 번째 원소의 반복자를 반환
clear()	모든 원소 삭제
empty()	원소가 없으면 true 반환
end()	마지막 원소 다음의 반복자 반환 (원소를 가르키는 반복자가 아니다.)
erase()	특정 위치의 원소 혹은 지정 범위의 원소 삭제
front()	첫 번째 원소의 참조자 반환
back()	마지막 원소의 참조 반환
insert()	특정 위치에 원소 삽입
push_front()	새로운 원소를 시작위치에 삽입
pop_front()	첫 번째 원소를 제거
push_back()	새로운 원소를 마지막 위치에 추가
pop_back()	마지막 원소를 제거
rbegin()	역방향으로 첫 번째 원소의 반복자 반환 (정방향의 마지막 원소와 같다.)
rend()	역방향으로 마지막 원소 다음의 반복자 반환 (정방향의 첫 번째 원소와 같다.)
reserve()	지정된 크기의 메모리 공간 확보
size()	원소의 개수를 리턴
swap()	두 deque의 원소를 서로 교환

참고자료

Deque, cppreference.com
[C++] deque container 정리 및 사용법, 개발자지망생님 블로그
[C++] STL Deque, 도빵님 블로그