deque vs vector vs list

deque

deque 는 double-ended queue의 약자로, 앞/뒤로 모두 삽입/제거 할 수 있는 큐를 의미한다.

deque 는 메모리 공간에 연속적으로 존재한다는 보장이 되어 있지 않지만, Random access iterator를 통한 개별 원소에 대한 접근이 가능하다. 따라서 C의 배열과 같은 [] 연산자를 이용한 특정 원소에 대한 접근도 가능하다.

deque는 앞/뒤 삽입/제거에 드는 비용이 거의 차이나지 않는다.

단 임의의 위치에 원소를 삽입할 경우 성능이 저하된다.

vector

vector는 동적인 배열로 구현되어 있으며 C의 동적배열의 단점을 보완해준다.

컨테이너의 뒤에서 삽입/제거할 시 일반적으로 다른 컨테이너에 비해 빠른 성능을 갖고 있다. 그러나 컨테이너의 앞, 임의의 위치에 삽입/삭제를 시도하는 경우 성능이 저하된다. 이는 구현에 사용된 배열의 특징을 생각해보면 그 원인을 쉽게 알 수 있다.

배열을 대체하기 위해 나온 컨테이너이므로 [] 연산자를 이용해 특정 원소에 대한 접근이 가능하다.

list

list 컨테이너의 구현은 doubly-linked list 로 되어 있다. 따라서 링크드리스트의 장점과 단점을 그대로 가진다. 장점은 어느 공간에나 삽입/삭제를 효율적으로 할 수 있다는 점이다.

그러나 원소에 인덱스로 접근하는 것이 불가능하고, 원소의 탐색을 위해서는 앞/뒤 방향의 순회탐색을 해야 한다는, 링크드리스트의 단점을 그대로 답습한다.