[C++] deque 라이브러리

deque는 vector, list 와 비슷하다고 보면 된다.

여기에서 비슷하다고 하는 점은 서로 다르다.

vector의 배열 구조, list의 맨 뒤, 맨 앞 삽입이 비슷한 것이다.

그러니까 vector의 장점, list의 장점이 합쳐진 자료구조라고 생각해야 한다.

 

deque가 작동하는 방식에 대해 먼저 설명하고, list, vector와의 차이에 대해 설명하겠다.

 

1. deque 방식

그러니까. push는 새로운 일정 크기의 배열을 생성하여 push해준다. push_front는 앞쪽에, push_back은 뒤쪽에 생성을 하고 넣어주는 것이다. 

만약 push_front의 배열이 꽉차 있다면 위 처럼 6칸 크기의 배열을 새로 생성하여 push_front를 해준다.

이해가 되는가!?

 

2. vector와의 차이점

vector는 push_back을 할 경우 새로운 크기의 배열을 만들어 복사를 하는 비용이 든다.

그림으로 그리면 다음과 같다.

하지만, deque의 경우 복사를 하지 않고, 새로운 일정 크기의 배열을 생성하여 연결시킨다. 그러므로 크기가 부족할 경우 복사를 하는 비용이 줄어든다.

 

3. list와의 차이점

뭐 거창하게 제목으로 붙이고 했지만, 그냥 list는 임의 접근이 불가하다.

하지만, deque는 임의접근이 가능하여 []형태로 접근이 가능하다.

Good.

 

4. method

일반적으로 vector와 비슷하다.

front(): 1(첫 번째 원소)

back(): 1(마지막 원소)

begin(): 첫번째 위치(iterator)

end(): 마지막의 다음 위치(iterator)

size(): 원소의 개수

capacity(): 용량

 

push_back(a): 마지막 자리 다음에 a원소 추가

push_front(a): 맨 앞 자리에 a원소 추가

pop_back(): 마지막 위치에 있는 원소 삭제

pop_front(): 맨 앞에 위치에 있는 원소 삭제

(vector의 함수에서 front()부분만 추가한 것이다)

 

empty(): 비어있으면 true, 아니면 false

clear(): 초.기.화.