Deque §
- Double-ended queue
- 즉, 앞뒤로의 삽입 삭제가 가능한 큐를 의미한다.
Requirements §
- C++ 표준에서 요구하는 deque 의 요구사항은 다음과 같다
- 앞뒤로의 삽입 삭제가(
push_front(), pop_front(), push_back(), pop_back()) O(1) 로 작동해야 한다.
- 모든 원소에 대해 임의 원소 접근이 O(1) 로 작동해야 한다.
- 중간에서의 삽입 삭제는 O(n) 로 작동해야한다.
Implementation §
- 데크는 구현이 벡터와 리스트를 섞은거마냥 되어 있다.
- 즉, 리스트처럼 연결지어놓긴 하되 원소 하나하나를 연결한게 아니고 일정 갯수의 원소를 묶은 메모리 청크를 연결지어놓는 형태로 구현이 되어 있다.
- 이 성질을 이용해 (1) 번 요구사항이 어떻게 해결되나 보자.
- 첫 원소를 삽입할때 메모리 청크의 가운데에 원소를 삽입하고
~back() 의 연산에는 해당 원소의 오른쪽에 넣거나 빼고~front() 의 연산에는 해당 원소의 왼쪽에 넣거나 빼는 식이다.- 만일 메모리 청크의 한쪽방향이 다 차면 메모리 청크를 하나 더 만들어서 리스트맹키로 붙여준 다음 원소를 삽입해주면 된다.
- 이 방법은 더블링의 관점에서 보면 벡터에 비해 장점이 있다.
- 벡터의 경우 Capacity 가 다 차면 더블링을 해야 되서 가끔씩 O(n) 의 연산이 들어가지만
- 데크의 경우 메모리 청크만 새로 할당하면 되기 때문에 현저히 더 적은 오버헤드가 들어간다.
- 또한 벡터와 비슷한 정도의 Spatial locality 도 가질 수 있다.
- 데크도 결국에는 하나의 메모리 청크에 대해서는 연속된 메모리에 존재하므로 spatial locality 을 살려 캐쉬 히트율을 높일 수 있다.
- 또한 (2) 번 요구사항은 다음과 같이 해결된다.
- 메모리 청크 하나당 원소의 갯수는 일정하기 때문에 메모리 청크가 위치한 메모리 주소만 테이블 형식으로 갖고 있으면 단순 연산을 통해 임의 원소 접근이 가능하다.
- 러프한 예를 들면 청크 하나당 크기가 10이면 인덱스 43 에 접근하기 위해서는 5번째 청크의 3번째 원소에 접근하면 된다.
- 마지막으로 (3) 번 요구사항은 다음과 같이 해결된다.
- 아쉽게도 리스트랑은 다르게 원소 하나하나가 연결된 형태가 아니기 때문에 결국에는 원소를 미는 과정이 필요해 O(n) 의 복잡도는 필수적이다.
- 하지만 그럼에도 불구하고 벡터보다는 빠르게 작동한다.
- 왜냐면 벡터의 경우에는 전체를 다 밀어야 하지만 데크의 경우에는 중간 지점의 위치를 알고 있기 때문에 밀어야 되는 원소의 갯수는 최대 N/2 가 되기 때문이다.
Not supported for deque §
- 데크는 전체가 연속된 메모리에 저장되지는 않기 때문에 포인터 연산을 통한 접근은 불가능하다.
- 또한 Capacity 와 관련된 기능들 (
capacity() 와 reserve()) 는 구현 방법에 의존적이어서 기본 라이브러리로는 제공되지 않는다.