[C++/STL] deque (덱)

deque는 입력과 출력이 양쪽 끝에서 이루어지는 자료구조입니다. 큐와는 다르게 뒤에서 삭제가 가능하고 앞에서 입력이 가능합니다. 뒤에서만 입력과 출력이 가능한 스택과 달리 앞에서도 입력과 출력이 가능합니다. 그러나, 벡터와는 달리 내부 요소들이 연결만 유지한 상태이기에, 다른 공간에 흩어져 존재할 수도 있습니다.

 

이러한 덱을 C++에서 라이브러리로 제공합니다.

 

---

 

 

#Include <deque>

#include <deque>

template < class T, class Alloc = allocator<T> > class deque;

 

선언 방법

deque<int> d1;                                // 빈 int형 덱
deque<int> d2(4,100);                         // 4개의 100을 기본으로 넣은 덱
deque<int> d3(d2.begin(), d2.end());          // d2의 반복자
deque<int> d4(d3);                            // d3를 복사

 

---

 

멤버 함수 목록

 

1. Iterators(반복자)

begin() : 시작 지점의 주소값을 반환합니다.
end() : 마지막 + 1 지점의 주소값을 반환합니다.
rbegin() rend() : begin()과 end()의 역순입니다.
cbegin(), cend(), crbegin(), crend() : 각각의 반복자를 const_iterators로 받아옵니다.

 

예시

#include <deque>
#include <iostream>

using namespace std;

int main () {
    deque<int> d(4, 0);
    deque<int>::iterator itor = d.begin();
    
    int i = 0;
    for (itor = d.begin(); itor != d.end(); itor++) {
        *itor = ++i;               // 1, 2, 3, 4
    }
    
    for (itor = d.begin(); itor != d.end(); itor++) {
        cout << *itor << endl;     // 출력 : 1, 2, 3, 4
    }
    
    return 0;
}

 

---

 

2. Capacity(용량)

size() : 덱의 크기를 반환합니다.
max_size() : 덱의 최대 크기를 반환합니다.
resize(size_type n, value_type val = value_type()) : 덱의 크기를 n으로 변경합니다. val의 기본값은 기본 생성자입니다. (정수의 경우에는 0) 만약, 원래 크기보다 커진다면 남은 부분이 val로 채워지게 됩니다.
empty() : 덱이 비었는지 확인합니다.
shrink_to_fit() : 덱의 용량을 크기에 맞게 줄여줍니다.

 

예시

#include <deque>
#include <iostream>

using namespace std;

int main () {
    deque<int> d = { 1, 2, 3, 4 };
    
    d.size();                       // 4
    d.resize(5, 5);                 // d = { 1, 2, 3, 4, 5 }

    return 0;
}

 

---

 

3. Element access(요소 접근)

operator[] : 배열에서 요소에 접근하기 위해 사용한 []와 동일합니다.
at(i) : []와 같으나, 인덱스 범위를 벗어난다면 out_of_range 예외를 발생시킵니다.
front() : 덱의 첫 번째 요소를 참조합니다.
back() : 덱의 마지막 요소를 참조합니다.

 

예시

#include <deque>
#include <iostream>

using namespace std;

int main () {
    deque<int> d = { 1, 2, 3, 4 };
    
    cout << d[0] << endl;         // 출력 : 1
    cout << d.at(2) << endl;      // 출력 : 3
    cout << d.front() << endl;    // 출력 : 1
    cout << d.back() << endl;     // 출력 : 4

    return 0;
}

 

---

 

4. Modifiers(수정자)

assign : 덱을 새로 할당합니다.
assign(InputIterator first, InputIterator last) : first부터 last 전까지의 요소로 덱을 새로 할당합니다.
assign(size_type n, const value_type& val) : val을 n개 복사해 덱을 새로 할당합니다.

push_back(const value_type& val) : val을 덱의 마지막에 추가합니다.
push_front(const value_type& val) : val을 덱의 앞에 추가합니다.
pop_back() : 덱의 마지막 요소를 제거합니다.
pop_front() : 덱의 첫 번째 요소를 제거합니다.

insert : 덱의 특정 부분에 요소를 추가합니다.
insert(iterator position, const value_type& val) : position에 val을 추가합니다.
insert(iterator position, size_type n, const value_type& val) : position에 val을 n개 추가합니다.
insert(iterator position, InputIterator first, InputIterator last) : position에 first부터 last까지의 요소를 추가합니다.

erase : 덱의 특정 부분의 요소를 제거합니다.
erase(iterator position) : position의 요소를 제거합니다.
erase(iterator first, iterator last) : first에서 last전까지의 요소를 제거합니다.

swap(deque& x) : 덱을 서로 바꿉니다.
clear() : 덱의 모든 요소를 제거합니다.
emplace (const_iterator position, Args&&... args) : position에 값을 추가합니다.
emplace_front(Args&&... args) : 덱의 앞에 요소를 추가합니다.
emplace_back(Args&&... args) : 덱의 마지막에 요소를 추가합니다.

 

예시

#include <deque>
#include <iostream>

using namespace std;

int main () {
    deque<int> d = { 1, 2, 3, 4 };
    
    d.push_back(5);                       // d = { 1, 2, 3, 4, 5 }
    d.push_front(0);                      // d = { 0, 1, 2, 3, 4, 5 }
    
    d.pop_front();                        // d = { 1, 2, 3, 4, 5 }
    d.pop_back();                         // d = { 1, 2, 3, 4 }
    
    d.assign(4, 5);                       // d = { 5, 5, 5, 5 }
    
    d.insert(d.begin(), 4);               // d = { 4, 5, 5, 5, 5 }
    
    d.erase(d.begin() + 2, d.end());      // d = { 4, 5 }

    return 0;
}

 

 

 

Reference

https://www.cplusplus.com/reference/deque/deque/