덱(deque)

개요

• 헤더 파일: <deque>
• STL 시퀀스 컨테이너 (sequence container): 시퀀스 블록 집합 컨테이너
• 탐색 시간: $O(1)$
• 요소 추가/삭제
  • 양쪽 끝에서의 추가/삭제: $O(1)$
  • 중간에서의 요소 추가/삭제: $O(N)$

덱(Deque, Double-Ended Queue)는 양쪽 끝에서 빠른 삽입 및 삭제가 가능한 자료 구조를 말합니다.

기존의 큐 자료 구조가 한쪽 방향에서 삽입하고 한쪽 방향에서 삭제되는 FIFO 구조라면, 덱은 양쪽 방향에서 자유롭게 삽입하고 삭제할 수 있는 구조입니다.

양쪽에서 삽입 삭제가 가능한 덱

덱은 그 구현 방식에 따라 임의 접근이나 임의 위치에서의 삽입 삭제에 대한 시간 복잡도가 달라질 수 있겠으나, 기본적으로는 자료 구조의 기본 목적에 따라 양쪽 끝에서의 삽입/삭제나 탐색을 $O(1)$로 만드는 편입니다.

C++에서의 deque

C++ 에서의 <deque>는 고정 크기의 시퀀스를 블럭으로 하여, 해당 블럭들을 시퀀스로 가진 컨테이너 입니다.

마치 <vector>와 <list>를 섞어놓은 것처럼 모든 요소들이 메모리에 연속되지 않고, 요소들이 나열된 <vector>를 <list>로 나열한 것처럼 되어있습니다.

때문에, <vector>와는 다르게 맨 앞에 요소를 추가/삭제 하는 작업이 기본적으로 제공되며, $O(1)$의 시간 복잡도를 가질 수 있습니다.

다만, 이러한 구조 때문에 각 블럭들이 위치한 메모리를 참조하기 위해 주소를 저장하기 위한 메모리가 추가로 필요하며, 인덱스 접근 시 두 번의 포인터 역참조가 필요합니다. (블럭 + 해당 요소의 위치)

새로운 메모리 할당시 vector보다 빠르다!

이렇게 구조를 만들면 어떤 점이 이점일까요?

바로, 메모리가 추가로 필요할 때, 메모리의 확장과 축소에 들어가는 비용이 vector보다 적다는 점입니다.

기존 std::vector는 메모리를 확장해야 할 때, 새롭게 필요한 메모리를 추가로 할당하고, 데이터들을 전부 복사한 뒤, 옮겨줘야 했습니다.

그러나, std::deque는 메모리를 확장해야 할 때, 고정 크기의 동일한 메모리 공간을 새롭게 추가해주기만 하면 됩니다.

특징

1. 양쪽 끝에서 빠른 삽입 및 삭제가 가능한 자료 구조입니다.
2. 동적 크기 조정: 구현에 따라 다르겠지만, 블럭을 관리하는 블럭 포인터 배열이 꽉 찬 경우 재할당을 하게 되지만, 기본적으로 블럭을 추가/삭제하는 것으로 메모리 재할당 없이 동적인 크기 조절이 가능합니다.
3. 컨테이너 특성: 덱은 STL 시퀀스 컨테이너이며, STL의 이터레이터와 다양한 알고리즘을 사용할 수 있습니다.

장단점

장점

• 동적 크기의 선형 자료 구조: 덱은 정해진 크기 없이 동적으로 메모리 공간을 확장/축소 할 수 있습니다.
  • vector에 비해 메모리 확장 비용이 적게 들어갑니다.
• 빠른 접근: 양쪽 끝에서의 접근은 매우 빠르게 이루어지며, 중간에 접근하더라도보다 빠르게 중간 요소에 접근할 수 있습니다.

단점

• 추가적인 메모리: vector와는 다르게 여러 블록에 분산해 저장하기 때문에, 각 블럭 위치를 저장하는 블럭 포인터가 추가로 필요합니다.
• 접근 시간: vector와는 다르게 각 요소에 접근하기 위해 두 단계의 포인터 역참조가 필요합니다. 첫 번째는 중앙 제어 구조에서 해당 요소가 있는 블록의 포인터를 찾는 것이고, 두 번째는 해당 블록 내에서 요소에 접근하는 것입니다.
• 캐시 효율성: 연속된 고정 크기의 블록으로 관리되긴 하지만, 고정 크기의 블록이 서로 다른 위치에 저장되기 때문에, 전체적으로 연속적인 vector보다는 캐시 효율성이 떨이질 수 있습니다.

사용법

생성자

std::deque<typename _Ty> dq(); // 기본 생성자
std::deque<typename _Ty> dq(size_t _Count, _Ty & _Val); // 특정 _Count만큼 _Val을 할당해서 초기화
std::deque<typename _Ty> dq(std::deque<typename _Ty> _Right); // 다른 deque의 복사본을 생성

멤버 함수

멤버 함수	설명
dq.size()	요소의 수를 반환합니다.
dq.empty()	덱이 비어있으면 true를 반환합니다.
dq.front()	첫 번째 요소에 대한 참조를 반환합니다.
dq.back()	마지막 요소에 대한 참조를 반환합니다.
dq.push_front(x) / dq.pop_front()	첫 번째 원소 앞에 x를 삽입하거나 첫 번째 원소를 제거합니다.
dq.push_back(x) / dq.pop_back()	마지막 원소 뒤에 x를 삽입하거나 마지막 원소를 제거합니다.
dq.clear()	모든 요소를 제거합니다.
dq.begin() / dq.end()	컨테이너의 시작과 끝을 가리키는 이터레이터를 반환합니다.
dq.rbegin() / dq.rend()	컨테이너의 시작과 끝을 가리키는 역방향 이터레이터를 반환합니다.
dq[i]	i번째 요소를 참조합니다. 범위 검사를 수행하지 않습니다.
dq.at(i)	i번째 요소를 참조합니다. 유효 범위 검사를 수행합니다.
dq.resize(n, x)	크기를 n으로 변경합니다. 크기가 커졌을 경우, 새 요소는 x로 초기화됩니다.
dq.swap(deque)	다른 덱과 요소를 교환합니다.
dq.insert(iter, n, x)	iter가 가리키는 위치에 x의 값을 가진 n개의 요소를 삽입합니다.
dq.erase(iter)	iter가 가리키는 요소를 제거합니다. 제거한 위치의 이터레이터를 반환합니다.
dq.assign(n, x)	x의 값으로 n개의 요소를 할당합니다.