1.8.1 덱의 구조

C++ 표준은 어떤 기능의 동작만을 정의할 뿐이며, 어떻게 구현해야 하는지는 정의하지 않습니다. 앞에서 살펴본 컨테이너들은 매우 단순해서 그 구현을 충분히 예측할 수 있습니다. 그러나 덱은 약간 더 복잡합니다. 먼저 덱의 필요조건을 살펴본 후, 실제 구현 방법에 대해 알아보겠습니다.

C++ 표준은 덱의 동작에 있어서 다음 조건을 만족해야 한다고 규정합니다.

이 요구 사항을 살펴보면 덱은 양방향으로 매우 빠르게 확장할 수 있어야 하며, 모든 원소에 임의 접근을 제공해야 합니다. 그러므로 자료 구조가 벡터와 비슷하지만, 앞쪽과 뒤쪽으로 모두 확장할 수 있다는 점이 다릅니다. 원소 삽입과 삭제 시 n/2 단계를 허용한다는 점에서 이 연산이 모든 원소를 이동시키는 동작을 수행한다는 점을 예상할 수 있으며, 이러한 원소 이동은 벡터에서 삽입 또는 삭제를 할 때에도 발생하는 연산입니다. 다만 덱은 어느 방향으로든 빠르게 확장할 수 있으므로 원소 삽입 시 나머지 원소를 항상 오른쪽으로 이동해야만 하는 것은 아닙니다. 원소 삽입 위치에서 가장 가까운 끝 쪽으로 나머지 원소를 이동해도 됩니다. 특정 위치에서 가장 가까운 끝은 컨테이너 내부의 삽입 위치에서 n/2 이상 떨어져 있을 수 없기 때문에 최대 n/2 단계의 시간 복잡도를 가집니다.