[C++] 덱(Deque)
👻 Deque
이번 시간에는 시퀀스 컨테이너(Sequence Container)의 마지막 요소인 덱(deque)에 대해 알아볼 것이다. 시퀀스 컨테이너란, 데이터가 삽입 순서대로 나열되는 형태의 구조를 의미한다. 벡터, 리스트, 덱이 있다.
#include <deque>
deque<int> d(3, 1);
사용방법은 벡터, 리스트와 동일하다. deque 라이브러리를 사용한다.
🌱 deque의 동작 원리
덱은 double-ended queue의 축약어로 ‘양쪽을 모두 사용할 수 있는 큐’ 정도로 해석할 수 있다. 일정 크기의 메모리를 우선 할당받은 후 벡터처럼 연속하여 데이터를 저장하지만, 데이터가 모두 찼을 때 앞 뒤로 데이터를 추가하게되면 해당 방향으로 자유롭게 새 메모리를 할당받아 저장하는 식이다. 양 옆으로 사용이 가능한 벡터 같은 느낌이 강하고 이는 곧 벡터쪽에 더 가깝다고 볼 수 있다. 다만, 덱은 벡터와 마찬가지로 배열 기반으로 동작하지만 메모리 할당 정책이 다르다.
🌱 삽입과 삭제
-
중간 삽입과 삭제
벡터와 동일하게 동작하기 때문에 비효율적이다. 중간에 값을 건드리게되면 양 옆으로 존재하는 수많은 데이터의 이동이 이루어지게 된다. -
처음, 끝의 삽입과 삭제
현재 메모리 블록의 데이터가 전부 찼다고 해도 양 옆으로 새 메모리를 할당받아 저장하기 때문에 처음, 끝의 삽입과 삭제는 빠른편이다. 그리고 벡터와 같이 임의 접근이 가능하다.
🌱 vector와 비교해보기
vector<int> v(3, 1);
deque<int> d(3, 1);
// vector
// [1 1 1]
// deque
// [ 3 3]
// [1 1 1 2]
// [2 ]
v.push_back(2);
v.push_back(2);
d.push_back(2);
d.push_back(2);
d.push_front(3);
d.push_front(3);
벡터는 capacity보다 더 많은 데이터를 추가하게되면 데이터의 복사, 이동이 이루어지지만 덱의 경우 이미 추가된 데이터의 메모리는 그대로 유지하되 새로운 메모리 구간을 할당받아 데이터를 추가한다. 조각나있지만 그 안에서 데이터들이 연속되어 있는 것이다.
👻 글을 마치며
이번 시간에는 덱에 대해 알아보았다. 친숙하지 않은 문법이었는데 동작 원리를 알아보고나니 이해가 빨랐다. 다만 어떤 식으로 사용해야할지는 아직까진 감이 잘 잡히지 않는 것 같다. 굳이 필요한가 싶기도 하고..?
Leave a comment