[STL] Deque Container

📌 deque container

• deque (double ended queue)
• sequence container
• vector container와 매우 유사한 배열 기반 컨테이너
• 여러 메모리 블록을 가진 불연속적인 형태
  • 앞뒤로의 원소 추가/제거가 효율적
  • 메모리 공간을 효율적으로 사용하여 메모리 확장에 유리

---

✔ deque 사용

#include <deque>
using namespace std;

• <deque> header
• std::deque

---

✔ deque 생성

deque<[type]> [name]

// 비어있는 정수형 타입 deque d1를 생성
deque<int> d1;

// 기본값으로 초기화된 10개의 원소를 가지는 deque d2 생성
deque<int> d2(10);

// 'A'로 초기화된 5개의 원소를 가지는 deque d3 생성
deque<char> d3(5, 'A');

// 'A', 'B', 'C' 원소를 가지는 deque d4 생성
deque<char> d4 = { 'A', 'B', 'C' };

• deque에 저장될 타입을 명시
• deque의 크기만 지정한 경우, 기본값(0)으로 초기화
• 배열처럼 하드코딩 방식으로 초기화 가능

---

✔ deque 연산자

deque<int> d1(5, 7);
deque<int> d2 = { 7, 7, 7, 7, 7 };
deque<int> d3 = { 7, 7, 7, 8 };

if (d1 == d2)  // true
    cout << "동일한 deque";
if (d2 < d3)  // true
    cout << "d3이 d2보다 큰 deque";

• 비교 연산자 사용 가능

---

✔ deque 멤버 함수

1) element access & capacity

function	description
d[index]	index에 해당하는 원소 반환
d.at(index)	index에 해당하는 원소 반환
d.front()	첫번째 원소 반환
d.back()	마지막 원소 반환
d.size()	deque d의 크기 반환
d.empty()	비어있으면 true, 그렇지 않으면 false 반환

deque<int> d1 = { 10, 20, 30, 40, 50 };
deque<int> d2;

cout << d1[1];          // 20
cout << d1.at(2);       // 30
cout << d1.front();     // 10
cout << d1.back();      // 50

cout << d1.size();      // 5
cout << d2.size();      // 0

if (d2.empty())  // true
    cout << "d2 size is 0";

2) iterators

function	description
d.begin()	첫번째 원소를 가리키는 iterator
d.end()	마지막 원소의 다음을 가리키는 iterator
d.rbegin()	마지막 원소를 가리키는 iterator
d.rend()	첫번째 원소의 이전을 가리키는 iterator

iterator(반복자) : 컨테이너에 저장된 요소를 반복적으로 순회하여 각 요소에 접근할 수 있도록 하는 객체

deque<int> d = { 10, 20, 30, 40, 50, 60, 70, 80 };

deque<int>::iterator iter;

for (iter = d.begin(); iter != d.end(); iter++)
{
    cout << *iter << " ";  // output : 10 20 30 40 50 60 70 80
}  

deque<int>::reverse_iterator r_iter;

for (r_iter = d.rbegin(); r_iter != d.rend(); r_iter++)
{
    cout << *r_iter << " ";  // output : 80 70 60 50 40 30 20 10
}  

3) modifiers (수정)

function	description
d.push_front(x)	원소 x를 첫번째 원소 앞에 추가
d.push_back(x)	원소 x를 마지막 원소 뒤에 추가
d.pop_front()	첫번째 원소 제거
d.pop_back()	마지막 원소 제거
d.insert(iter, x)	원소 x를 iter 위치에 삽입
d.insert(iter, n, x)	n개의 원소 x를 iter 위치에 삽입
d.erase(iter)	iter 위치의 원소 제거
d.erase(iter1, iter2)	iter1 부터 iter2 이전까지 위치의 원소 제거
d.clear()	모든 원소 제거

deque<int> d = { 10, 20, 30 };

d.push_front(40);                   // 40 10 20 30
d.pop_back();                       // 40 10 20
d.push_back(50);                    // 40 10 20 50
d.pop_front();                      // 10 20 50

d.insert(d.begin(), 60);            // 60 10 20 50
d.insert(d.begin() + 3, 70);        // 60 10 20 70 50
d.insert(d.end(), 3, 50);           // 60 10 20 70 50 50 50 50
d.erase(d.begin() + 5);             // 60 10 20 70 50 50 50
d.erase(d.begin() + 4, d.end());    // 60 10 20 70