[C++/STL] - deque

1. deque란

deque는 C++ STL에서 제공하는 자료구조 중 하나로, Double-Ended Queue의 약자이다. deque도 vector와 마찬가지로 배열기반의 구조이다.

2. 특징

• deque는 시퀀스 컨테이너이다. 즉, 임의의 원소에 접근 가능한 구조이다.
• deque는 배열 기반 컨테이너로, 여러 개의 메모리 블록에 나뉘어 저장된다. 이는 vector와 유사하다.
• deque는 메모리가 연속적으로 할당되지 않아서, 원소를 추가할 때에 기존 원소들을 복사하여 새로운 메모리 공간을 만드는 작업을 할 필요가 없다. 그래서 원소의 삽입과 삭제에 있어서 vector보다 효율적이다.
• deque는 양쪽 끝에서 원소를 추가하거나 삭제할 수 있는 자료구조이다. push_front(), pop_front(), push_back(), pop_back() 함수를 사용하여 양쪽 끝에서 원소를 삽입하거나 삭제할 수 있다.
• deque는 vector보다 메모리를 더 사용하지만, deque는 중간에 데이터를 삽입하거나 삭제하는 경우에 vector보다 더 빠르다. 반면, vector는 원소를 순차적으로 삽입하거나 삭제하는 경우에 더 빠르다.

3. 장단점

장점 :

deque는 양쪽 끝에서 원소를 추가하거나 삭제할 수 있는 자료구조이므로, 큐와 스택을 모두 구현할 수 있다.
deque는 중간에 데이터를 삽입하거나 삭제하는 경우에 vector보다 더 빠르다.
deque는 메모리가 연속적으로 할당되지 않아서, 원소를 추가할 때에 기존 원소들을 복사하여 새로운 메모리 공간을 만드는 작업을 할 필요가 없기 때문에 vector보다 효율적이다.
deque는 메모리를 동적으로 할당하기 때문에, 크기를 동적으로 조절할 수 있다.

단점 :

4. 시간복잡도

1. 접근 - O(1)
   vector와 마찬가지로 O(1)이다.
2. 검색 - O(n)
   선형 검색을 수행하므로 O(n)이다.
3. 삽입 및 삭제 - 양쪽 끝 삽입 및 삭제 O(1) / 중간에 삽입 및 삭제 O(n)
   deque의 양쪽 끝에서 원소를 추가하거나 삭제할 수 있으므로, 양쪽에서 삽입 및 삭제하는 경우 O(1)이다. 반면, 중간에 삽입 및 삭제를 하는 경우 vector보다 빠르지만, 여전히 O(n)의 시간복잡도를 갖는다.

5. 사용법

1) 초기화

deque<int> dq1; // 빈 deque 생성

deque<int> dq2(4); // 크기가 4인 deque 생성, 모든 원소는 0으로 초기화됨

deque<int> dq3 = { 1, 2, 3 }; // 중괄호 초기화

deque<int> dq4 = { 1, 2, 3 };
deque<int> dq5 = move(dq4); // dq4를 dq5로 이동

deque<int> dq6 = { 1, 2, 3 };
deque<int> dq7(dq6); // dq6를 복사하여 dq7 생성

deque<int> dq8{ 1, 2, 3 }; // 중괄호 초기화, C++11 이상에서 가능

2) 멤버 함수

Iterators
begin() : 첫 번째 원소를 가리키는 반복자를 리턴한다.
cbegin() : 첫 번째 원소를 가리키는 상수 반복자를 리턴한다.
end() : 마지막 원소를 가리키는 반복자를 리턴한다.
cend() : 마지막 원소를 가리키는 상수 반복자를 리턴한다.
rbegin() : 역 순차열의 첫 번째 원소를 가리키는 반복자를 리턴한다.
crbegin() : 역 순차열의 첫 번째 원소를 가리키는 상수 반복자를 리턴한다.
rend() : 역 순차열의 마지막 원소를 가리키는 반복자를 리턴한다.
crend() : 역 순차열의 마지막 원소를 가리키는 상수 반복자를 리턴한다.

Element access
at(n) : n번째 원소를 참조할 때 사용하며 범위 점검을 하므로 []보다 느리다.
operator[n] : n번째 원소를 참조할 때 사용하며 범위 점검을 안하므로 at보다 빠르다.
back() : 마지막 원소를 리턴한다.
front() : 첫번째 원소를 리턴한다.

Capacity
empty() : 원소 존재 유무를 체크한다. 아무것도 없으면 true, 있으면 false를 리턴한다.
size() : 원소의 개수를 리턴한다.
max_size() : 담을 수 있는 원소의 최대 개수를 리턴한다.
resize(size, value) : deque의 크기를 변경하고 default 값이나 임의 값으로 초기화한다.
shrink_to_fit() : 사용되지 않는 capacity size를 제거한다.

Modifiers
clear() : deque의 모든 원소를 제거한다.
assign() : 기존 원소들은 모두 제거 후, 임의 값으로 n개의 원소를 할당한다.
assign(InputIterator first, InputIterator last) : first부터 last까지
assign(size_type n, const T& u) : n의 크기만큼 u로 꽉채움
insert() : 임의 위치에 임의 값을 삽입한다.
insert(iterator position, const T& x) : position에 x넣음
insert(iterator position, size_type n, const T& x) : position부터 n의 크기만큼 x를넣음
insert(iterator position, InputIterator first, InputIterator last) : position에 first부터 last까지 넣음
emplace() : 원소 삽입시 컨테이너 내부에서 생성 후 임의 위치에 임의 값을 삽입한다.
erase() : 임의 위치의 원소나 지정 범위의 원소를 삭제한다.
erase(iterator pos) : pos위치의 원소 제거
erase(iterator first, iterator last) : first부터 last까지 제거
push_back() : deque의 끝에 원소를 추가한다.
push_front() : deque의 앞에 원소를 추가한다.
★emplace_back() : 원소 삽입시 컨테이너 내부에서 생성 후 컨테이너의 끝에 원소를 추가한다.
★emplace_front() : 원소 삽입시 컨테이너 내부에서 생성 후 컨테이너의 앞에 원소를 추가한다.
pop_back() : deque의 마지막 원소를 제거한다.
pop_front() : deque의 처음 원소를 제거한다. 나머지 원소들은 자동으로 앞당겨진다.