STL deque 정리

deque - Double - ended queue // 데크

- 말 그대로 Double ended queue, "앞과 뒤에서 삽입, 삭제가 가능"

 

deque를 쉽게 이해하기 위해선

deque를 "list와 vector의 짬뽕"이라고 생각하면된다.

 

deque를 이해하기 위한 짤막한 vector, list 메모리 할당 설명

-vector

할당 받은 메모리를 다 사용하면 "1.5배 더 큰 메모리를 새로 할당"받고 데이터 이전

 

-list

아무 위치나 메모리를 할당받은 다음 "논리적으로 서로를 연결"

 

deque 설명

deque는 16byte의 메모리를 할당받고 그 메모리를 "vector처럼 사용함" ( 임의 접근 가능 )

이후 메모리를 다 사용하면 다른 위치에

16byte의 "메모리를 추가로 할당" 받는데 list처럼 "논리적으로 서로를 연결"

+ push_front를 하면 또 다른 위치에 메모리를 할당받고 논리적으로 앞에 있는것처럼 연결함

	deque<int> dq(3, 1); // deque를 3개 만들고 1로 초기화

	dq.push_back(2);
	dq.push_back(2);

	dq.push_front(4);
	dq.push_front(4);
    
// 저장된 모습
[    4 4]
[1 1 1 2]
[2 ]

deque는 vector와 흡사하게 임의 접근이 가능한데 ( dq[0] <-- 의 방식으로 )

임의접근을 위해서 할당받은 메모리 중간중간을 비워둘 수가 없음 ( dq[0], dq[1]의 원리 때문)

 

그렇기 때문에

"중간 삽입/ 삭제"는 뒤의 모든 데이터를 옮겨야 하기에 정말 "비효율적"임

 

하지만

"앞, 뒤에서의 삽입/ 삭제는 아주 굳"