STL - deque

Dohun Lee·2025년 8월 12일

목록 보기

29/34

deque

deque는 vector, list와 같은 시퀀스 컨테이너이다. 시퀀스 컨데이너란, 데이터가 삽입 순서대로 선형적으로 나열된 형태의 컨테이너를 말한다.

deque는 vector와 비슷한 구조와 접근 방법을 지닌다. 하지만 내부적으로는 다르게 동작한다.

deque의 동작 원리

deque는 vector처럼 내부의 용량이 다 차게되면 추가적으로 메모리를 할당하여 컨테이너의 용량을 증설한다. 하지만 vector가 새롭게 할당된 메모리 공간에 기존의 데이터를 복사하고 공간을 증설 하는것과 달리, deque는 기존의 메모리 공간 만큼의 또 다른 공간을 할당하여, 기존의 공간은 유지한채 새로운 원소를 새롭게 증설한 공간에 넣는다.

쉽게 비유하자면, vector가 내용물을 담는데 기존에 있던 통이 부족하면, 새로운 더 넓은 통을 가져와서 기존의 내용물을 거기에 옮긴다면, deque는 통의 용량이 부족하면, 기존 통과 같은 크기를 지닌 또 다른 통을 가져와서 새로운 내용물은 이제부터 거기에 담는것이다.

여기서 deque에 등장한 통의 개념이 바로 Block이다. 이러한 방식으로 데이터를 가변적인 용량으로 저장하는 deque는 vector와 달리 증설 시점에 데이터 복사가 일어나지 않으니 오버헤드가 적다.

원소 삽입과 삭제

deque는 vector와 같이 컨테이너 끝에 원소를 추가하는 것은 효율적으로 동작하고, 중간에 삽입 혹은 삭제 하는것은 vector와 마찬가지의 이유로 비효율적으로 동작한다.

하지만 vector와 다른점은 push_back 뿐만 아니라 push_front도 가능하다는 것이다. 이러한 처음 지점의 원소 추가가 가능한 이유는 deque에 제일 앞에 원소를 추가하게 되면, 제일 앞에 Block을 하나 더 생성 해서 넣기 때문에, 제일 뒤에 원소를 넣는것과 같이 효율적으로 동작 하기 때문이다.

[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 10, 11, 12]
-> 이렇게 block 단위로 원소들이 나열되어 있다.

만약 제일 앞에 원소를 삽입하면,
아래와 같이 제일 앞에 새로운 block이 생성되고, 원소가 삽입된다.
[         0]
[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 10, 11, 12]

deque 내부 원소 접근

deque는 vector와 마찬가지로 원소의 임의 접근이 가능하다. vector와 같이 모든 원소가 하나의 메모리 공간에 나열되어 있지는 않지만, 각 block이 가지는 원소의 개수가 같고, 중간에 빈 공간 없이 연속적으로 나열되기 때문에, 내부 연산을 통해 [] 연산자를 통한 임의 접근이 가능하다.

deque의 원소 임의 접근은 내부의 offset을 기준으로 해당 원소가 들어있는 block을 찾은 뒤, 몇번 block에 해당 원소가 들어있는지를 통해 원소에 접근하는 방식이다.