cpp STL deque

deque(double-ended queue)

양방향 큐라는 deque는 vector와 유사하다.

vector의 메모리 할당 정책은 기존 메모리 영역이 가득찬다면, 기존 메모리에 들어있던 데이터를 복사한 뒤에 기존 영역을 삭제한다. 그리고 기존 메모리 영역보다 더 큰 새로운 메모리 영역을 생성한다. 여기에 복사한 데이터를 붙여넣는다. 

deque는 새로운 메모리 영역을 만든 후 해당 메모리에 데이터를 넣는다. 이때 새로운 메모리 영역은 기존 메모리 영역과 용량이 같다.

새로운 메모리 영역과 기존 메모리 영역이 list처럼 연결되어 있지 않다. 특정 테이블에서 각 메모리 위치를 관리한다. 아파트 주소를 생각하면 된다.

코드 아파트(테이블)
1동[..., 1013,	...]
2동[..., 2013,	...]
3동[..., 3013,	...]

 

#include <deque>

deque<int> dq(3, 1);	// dq [ 1, 1, 1 ]

dq.push_back(2);
dq.push_front(2);
cout << dq[0] << endl;

위 코드를 보면 deque의 중간 삽입/삭제, 처음/끝 삽입/삭제, 임의 접근 허용 여부를 알 수 있다.

vector와 마찬가지로 중간 삽입/삭제를 지원하지 않는다. 매우 비효율적이기 때문이다. 연속적인 메모리 블록을 가지기 때문에 메모리 중간에 삽입/삭제 연산이 일어나면 기존 데이터의 자리를 이동해줘야 한다. 때문에 느리지만 임의 접근을 허용한다.

처음/끝 삽입/삭제를 지원한다.

dq1 : [ 1, 1, 1, 1 ]
dq2 : [    3, 3, 3 ]

deque의 기존 메모리 용량이 4이며, 가득찬 상태라고 가정하자. 여기서 메모리 가장 첫 번째에 삽입/삭제가 일어나는 과정을 살펴보자.

// 2를 삽입
// dq1
[         2]
[1, 1, 1, 1]

// dq2
[2, 3, 3, 3]

// 삭제
// dq1
[   1, 1, 1]

// dq2
[      3, 3]

이처럼 처음 삽입/삭제 연산이 아주 쉽게 이뤄지는 것을 알 수 있다.

 

 

출처

https://www.inflearn.com/course/%EC%96%B8%EB%A6%AC%EC%96%BC-3d-mmorpg-1/dashboard

[C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈] Part1: C++ 프로그래밍 입문 - 인프런 | 강의