[C++][STL Container] 시퀀스 컨테이너 #3. 데크(deque)

시퀀스 컨테이너란?

• 시퀀스 컨테이너(Sequence Container)는 C++에서 제공하는 STL 컨테이너 종류(시퀀스 컨테이너, 연관 컨테이너, 컨테이너 어뎁터) 중 하나로, 원소들을 순차적으로 저장하는 컨테이너이다.

 

시퀀스 컨테이너의 종류

• 벡터(vector)
• 리스트(list, forward_list)
• 데크(deque) - [현재 글]
• 배열(array)

---

데크(deque, double ended queue)란?

데크 구조

• 데크(deque)는 일정 크기의 작은 메모리 블록들을 가리키는 포인터 벡터와 같은 자료구조이다.
  • 동과 호수로 구분된 아파트 모양과 비슷하다.
• 임의의 위치에 대한 데이터 접근이 빠르다. ( 시간복잡도 O(1) )
• “맨 앞, 맨 뒤”에 원소를 삽입 / 삭제하는 작업이 빠르다. ( 시간복잡도 O(1) )
• “임의의 위치”에 원소를 삽입 / 삭제하는 작업이 느리다. ( 시간복잡도 O(N) )
  • vector와 마찬가지로 삽입 / 삭제한 원소 뒤에 있는 원소들을 한 칸씩 이동
  • 메모리가 꽉 차면 새로운 메모리 공간을 할당하여 사용한다.

 

---

데크 멤버 함수

 

원소 접근 관련(Element access)

at()	i번째 원소에 접근 (범위 검사 O)
operator []	i번째 원소에 접근 (범위 검사 X)
front()	첫번째 원소에 접근
back()	마지막 원소에 접근

 

 

수정 관련(Modifiers)

push_back()	맨 끝에 원소 삽입
pop_back()	맨 끝에 원소 삭제
push_front()	맨 앞에 원소 삽입
pop_front()	맨 앞에 원소 삭제
insert()	지정한 위치에 원소 삽입
erase()	지정한 위치에 원소 삭제
clear()	deque를 비운다.
resize()	deque의 크기(size)를 재조정한다.
emplace()	지정한 위치에 원소 삽입 (insert와 유사. 사용 추천 X)
emplace_back()	맨 끝에 원소 삽입 (push_back과 유사. 사용 추천 X)
emplace_front()	맨 앞에 원소 삽입 (push_front와 유사. 사용 추천 X)
swap()	해당 deque와 swap한다.

 

 

크기 관련(Capacity)

empty()	vector의 size가 0인지 확인한다(bool 타입 반환)
size()	vector의 크기(원소의 개수)
max_size()	가능한 최대 size 반환.
shrink_to_fit()	capacity와 size를 같게 만든다. (메모리 절약 효과. 거의 안 쓴다)

 

 

더 자세한 내용은 아래 링크 참조

https://en.cppreference.com/w/cpp/container/deque

std::deque - cppreference.com

 

---

알아두어야 할 점

작은 메모리 블록(chunks)

작은 메모리 블록

• 메모리 블록이 꽉 찬 경우, 새로운 메모리 블록을 할당해서 포인터로 가리키면 되기 때문에, 벡터와 다르게 원소 삽입시 복사 비용이 발생하지 않는다.
• 새롭게 할당한 메모리 블록은 맨 앞과 맨 뒤에 있는 메모리 공간을 비워둔다. (벡터는 뒤에만 비워둠)

실행 속도를 위해 메모리를 희생한 컨테이너

• 데크의 각 블록(Chunk)은 연속된 메모리를 가지지만, 전체적으로 보면 연속되지 않은 메모리 블록들의 집합이다.
• 이러한 이유로 데크는 1) 원소들이 저장된 위치에 대한 정보를 보관하기 위해 추가적인 메모리를 사용하며, 2)  벡터보다 캐시 효율이 낮다(캐시 미스율이 높음)는 단점이 있다.   

---

참고 자료

https://modoocode.com/314

https://modoocode.com/223

https://en.cppreference.com/w/cpp/container/deque