[C++ STL] 1.7 std::dequeue

std::deque

• 배열 기반 컨테이너와 리스트 기반 컨테이너 두 가지 방식이 섞여있는 형태
  • 각각의 장점을 적당히 가지고 있다
• vector에서 push_front(), pop_front() 에서 비용이 많이 드는 단점을 극복할 수 있다
• deque : 양방향 큐(double-ended-queue)의 약자

덱의 구조

• C++ 표준은 덱의 동작에 있어 다음 조건을 만족해야 한다고 규정한다.
  • push_front(), pop_front(), push_back(), pop_back() 동작이 O(1) 시간 복잡도로 동작해야 함
  • 모든 원소에 대해 임의 접근 동작이 O(1) 시간 복잡도로 동작해야 함
  • 덱 중간에서 원소 삽입 또는 삭제는 O(n) 시간 복잡도로 동작해야 하며, 실제로는 최대 n / 2 단계로 동작하며 여기서 n은 덱의 크기임
• 덱은 양방향으로 매우 빠르게 확장할 수 있어야 하며, 모든 원소에 임의 접근을 제공해야 한다
  • 벡터와 비슷하다고 볼 수 있지만, 앞쪽과 뒤쪽으로 모두 확장할 수 있다는 점이 다르다

덱의 삽입/삭제

• 원소의 삽입/삭제 시 n / 2 단계를 허용한다는 점에서 이 연산이 모든 원소를 이동시키는 동작을 수행한다는 점을 예상할 수 있다
  • 어느 방향으로든 확장가능하므로, 삽입 시 나머지 원소를 항상 오른쪽으로 이동해야하는 것이 아니다
    • 가장 가까운 끝 쪽으로 나머지 원소를 이동해도 된다
    • 따라서 최대 n / 2 단계의 시간 복잡도를 갖는다

원소의 임의 접근

• 덱은 단일 메모리 청크를 사용하지 않는다
• 대신 크기가 같은 여러개의 메모리 청크를 사용하여 데이터를 저장한다
  • 청크의 인덱스 및 크기를 이용하여 특정 위치의 원소가 어느 청크에 저장되어 있는지 알 수 있다
• 모든 메모리 청크 주소를 연속적인 메모리 구조에 저장해놓고 사용하면 O(1)의 시간 복잡도로 원소의 임의 접근이 가능해진다
  • 포인터 배열과 유사한 구조를 가질 것 같다
  • 따라서 덱의 구조는 배열 또는 벡터와 유사하다고 가정한다

맨 앞에 새로운 원소를 추가하는 경우

• 첫 번째 메모리 청크에 여유 공간이 없다면 새로운 청크를 할당하고, 이 메모리 청크 주소를 맨 첫 번째 메모리 청크 주소로 설정한다
• 메모리 공간은 새로 할당해야 하지만, 실제 원소 데이터를 전혀 이동시키지 않아도 된다
  • 메모리 재할당을 최소화하려면 중간 위치의 청크부터 원소를 저장할 수 있다
  • 일정 횟수의 push_front() 함수에 대해 메모리 재할당을 피할 수 있다

제공하는 함수

• push_front(), push_back(), insert(), emplace_front(), emplace_back(), emplace(), pop_front(), pop_back(), erase() 등의 함수를 제공
• 벡터에서 저장 용량 최적화를 위해 사용되는 shirnk_to_fit() 같은 함수도 제공
  • capacity() 함수는 구현 방법에 의존적이므로 지원되지 않는다
• 임의 접근 반복자도 제공된다

exmaple: std::deque를 이용하여 원소 삽입/삭제

// 덱 선언
std::deque<int> deq = { 1, 2, 3, 4, 5 };

// 맨 앞에 0 추가 : { 0, 1, 2, 3, 4, 5 }
deq.push_front(0);

// 맨 뒤에 6 추가 : { 0, 1, 2, 3, 4, 5, 6 }
deq.push_back(6);

// 맨 앞에서 2칸 뒤에 10 추기 : { 0, 1, 10, 2, 3, 4, 5, 6 }
deq.insert(deq.begin() + 2, 10);

// 맨 뒤 원소 삭제 : { 0, 1, 10, 2, 3, 4, 5 }
deq.pop_back();

// 맨 앞 원소 삭제 { 1, 10, 2, 3, 4, 5 }
deq.pop_front();

// { 1, 2, 3, 4, 5 }
deq.erase(deq.begin() + 1);

// { 1, 2, 3 }
deq.erase(deq.begin() + 3, deq.end());

컨테이너마다 차이점/공통점 정리

• 덱은 데이터 맨 뒤 뿐만 아니라 맨 앞에서도 매우 바르게 원소를 삽입/삭제할 수 있다
• 데이터 중간에서의 삽입/삭제에 대한 시간 복잡도는 벡터와 동일하지만, 실제론 벡터보다 약간 빠르게 동작한다
• std::deque도 사용자 정의 할당자를 지정할 수 있다
  • 할당자가 객체의 일부가 아니라 타입의 일부이다!!!
  • 서로 다른 할당자를 사용하는 두 개의 벡터 또는 덱 객체를 서로 비교할 수 없고, 할당 또는 복사 생성자를 사용할 수 없다

결론) std::deque는 매우 빠른 push_front()와 push_back() 동작과 효과적인 임의 접근을 제공하는 유일한 컨테이너이다