[C++ STL] 덱 (Deque)

개요

벡터와 비슷하지만 양방향으로 원소를 삽입 / 제거할 수 있는 컨테이너

시간 복잡도

• 임의 위치 원소 접근: O(1)
• 맨 앞/뒤에 원소 추가 및 제거: O(1)
• 중간에 원소 삽입 및 제거: O(n)
  • 벡터보다 빠르게 동작함

주요 기능 및 특징

벡터보다 빠른 이유 (덱의 구조)

덱은 벡터와 다르게 원소들이 실제로 메모리 상에서 연속적으로 존재하지 않는다. 이 때문에 원소들이 어디에 저장되어 있는 지에 대한 정보를 보관하기 위해 추가적인 메모리를 더 필요로 한다. (즉, 덱은 속도를 위해 메모리를 희생함)

덱의 원소가 저장된 구조

덱의 원소들은 일정 크기로 잘려서 각각의 블록에 저장된다. 그리고 그 블록들의 시작 주소를 가리키는 포인터들의 벡터가 존재한다. 

 

크기를 늘리는 경우에서도 차이를 보이는데, 벡터의 경우 벡터가 가득 찬 상태에서 새로운 원소를 삽입하면 크기가 더 큰 새로운 벡터를 할당하고, 그곳에 모든 원소를 복사한다.

덱의 경우에는 복사할 필요 없이 새로운 블록을 만든 후 블록 포인터 벡터가 그 주소를 가리키게만 하면 된다.

물론 블록 포인터 벡터가 꽉 차게 되면 새로운 공간에 복사해야 한다는 점은 어쩔 수 없다. 하지만 벡터가 원소들을 모두 복사하는 것과 달리 덱은 주소값만 복사하면 되기 때문에 평균적으로 덱이 훨씬 빠르다.

반복자

덱의 반복자는 벡터와 동일한 RandomAccessIterator 타입이다.

임의 원소 접근

벡터와 같다.

• [] 사용
• at 함수 사용
• front, back 함수 사용

맨 뒤에 원소 삽입 / 제거

벡터와 같다.

원소 삽입에 push_back(), 원소 제거에 pop_back()을 사용한다.

맨 앞에 원소 삽입 / 제거

원소 삽입에 push_front(), 원소 제거에 pop_front()를 사용한다.

 

참고 및 이미지 출처

모두의 코드 - 씹어먹는 C++ PDF [https://modoocode.com/312]