1-6. std::deque

서론

지금까지 배열 기반과 연결 리스트 기반 컨테이너를 살펴봤다. 

std::deque은 두 가지 방식이 섞여 있는 형태이며, 각각의 장점을 적당히 가지고 있다. 

앞서 살펴봤듯이 벡터는 가변 길이 배열이고, push_front() 또는 pop_front() 같은 함수는 비용이 많이 드는 작업이다. (원소 삽입 후 모든 원소를 한 칸씩 뒤로 이동시켜야 하기 때문이다.)

std::deque을 사용하면 이런 단점을 극복할 수 있다. 

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 이상 떨어져 있을 수 없기 때문에 최대 n/2 단계의 시간 복잡도를 가진다. 

 

원소의 임의 접근과  맨 앞에 원소 추가에 대해 생각해보자. 

덱은 단일 메모리 청크를 사용하지 않는다. 대신 크기가 같은 여러 개의 메모리 청크를 사용하여 데이터를 저장한다. 

이 경우, 청크의 인덱스 및 크기(또는 하나의 청크에 저장된 원소 개수)를 이용하여 특정 위치의 원소가 어느 청크에 저장되어 있는지를 알 수 있다. 

모든 메모리 청크 주소를 연속적인 메모리 구조에 저장해놓고 사용하면 O(1)의 시간 복잡도로 원소의 임의 접근이 가능해진다. 따라서 덱의 구조는 배열 또는 벡터와 유사하다고 가정한다. 

 

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

 

덱은 벡터와 리스트에서 제공되는 함수를 조합한 것 이상의 기능을 제공한다. 벡터와 같은 임의 접근 반복자도 제공된다. 

• push_front()
• push_back()
• insert()
• emplace_front()
• emplace_back()
• emplace()
• pop_front()
• pop_back()
• erase()
• shrink_to_fit() : 저장 용량 최적화
• capacity() : 구현 방법에 의존적일 수 있으므로 지원되지 않는다

std::deque<int> deq = {1, 2, 3, 4, 5};
deq.push_front(0);  //맨 앞에 0 추가 : {0, 1, 2, 3, 4, 5}
deq.push_back(6);  //맨 뒤에 6 추가 : {0, 1, 2, 3, 4, 5, 6}
deq.insert(deq.begin()+2, 10);  //맨 앞에서 2칸 뒤에 10 추가 : {0, 1, 10, 2, 3, 4, 5, 6}
deq.pop_back();  //맨 뒤 원소 삭제 : {0, 1, 10, 2, 3, 4, 5}
deq.pop_front();  //맨 앞 원소 삭제 : {1, 10, 2, 3, 4, 5}
deq.erase(deq.begin()+1);  //{1, 2, 3, 4, 5}
deq.erase(deq.begin()+3, deq.end());  //{1, 2, 3}

 

각각의 컨테이너마다 유일하게 다른 점은 성능과 메모리 요구 사항이다. 

덱은 데이터 맨 뒤뿐만 아니라 맨 앞에서도 매우 빠르게 원소를 삽입하거나 삭제할 수 있다. 

데이터 중간에서의 삽입 또는 삭제에 대한 시간 복잡도는 벡터와 동일하지만, 실제로는 벡터보다 약간 빠르게 동작한다. 

 

std::vector와 마찬가지로 std::deque도 사용자 정의 할당자를 지정할 수 있다. 덱을 초기화할 때 템플릿 두 번째 매개변수에 할당자를 지정할 수 있다. 

주의할 점은 할당자가 객체의 일부가 아니라 타입의 일부라는 점이다. 이는 서로 다른 할당자를 사용하는 두 개의 벡터 또는 두 개의 덱 객체를 비교할 수 없음을 의미한다. 마찬가지로 서로 다른 할당자를 사용하는 객체에 대해 할당 또는 복사 생성자를 사용할 수도 없다. 

 

지금까지 살펴본 바와 같이 std::deque은 앞 절에서 나왔던 컨테이너에 비해 다소 복잡한 구조를 가지고 있다. 

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

덱은 앞으로 설명할 몇몇 자료 구조의 구현을 위한 용도로도 사용된다.