[[TableOfContents]]

시퀀스 컨테이너: vector, deque, list

{{{+1 알아두면 좋은 점: vector와 list의 차이 }}}

== vector ==
일반적인 배열처럼 vector는 개체들을 연속적인 메모리 공간에 저장한다.
즉, 반복자 뿐 아니라 position index(operator [])로도 접근이 가능하다.

vector는 동적으로 확장/축소가 가능한 dynamic array로 구현되어 있다.

=== 강점 ===
개별 원소들을 position index(operator [])로 접근이 가능하다(상수 시간).
원소를 컨테이너 끝에 삽입/제거하는 것이 빠르다.
어떤 순서로도 원소를 순회할 수 있다. 즉, Random access iterating이 가능하다.
일반적으로 다른 두 개의 시퀀스 컨테이너인 deque, list에 비해 개별 원소에 대한 접근 속도와 컨테이너 끝에서 삽입/제거 속도가 훨씬 빠르다.

=== 약점 ===
컨테이너 끝 위치가 아닌 곳에서 삽입/제거 수행 시 성능은 deque/list에 비해 현저히 떨어진다.

=== 주의 ===
동적으로 컨테이너 크기가 확장/축소되기는 하나, 확장 시 reallocation의 비용이 크다. capacity에 따라 적절한 크기의 reserved 메모리 크기 확보가 중요할 수 있다.


== deque (double ended queue) ==
vector와 비슷하지만 삽입/제거와 동적 확장 방식에서 차이가 있다.
=== 강점 ===
개별 원소들을 position index로 접근이 가능하다
원소를 컨테이너 끝 뿐 아니라, 앞에서도 삽입/제거하는 속도가 빠르다.
어떠한 순서로도 원소를 순회할 수 있다.

=== 약점 ===
컨테이너 끝 위치가 아닌 곳에서 삽입/제거 수행 시 성능은 list에 비해 현저히 떨어진다.

=== vector와의 차이 ===
두 번째 강점인 앞에서도 삽입/제거 속도가 빠르다. 이런 특징으로 STL의 스택과 큐의 base 클래스는 deque다.
컨테이너의 동적 확장/축소 방식이 다르다. vector의 경우 내부 capacity가 고갈되면 전체 메모리 크기만큼 reallocation이 발생한다. 하지만 deque는 일정 크기를 가지는 chunk 단위로 확장된다. 이런 차이에서 다음 같은 장단점이 있다.

''' 장점 '''
메모리 할당량이 큰 경우 vector에 비해 확장 비용이 절감된다.
''' 단점 '''
컨테이너 처음부터 끝까지 연속 메모리 공간이 아니므로 vector에서 가능했던 포인터 연산이 불가능하다.

== list ==
list는 이중 연결 리스트로 구현되어 있다.

=== 강점 ===
컨테이너 어느 위치에서도 삽입/제거가 빠르다(상수 시간).
원소들의 컨테이너 내 순서 이동이 빠르다(상수 시간).

=== 약점 ===
원소의 position index로 직접 접근이 불가능하다. - 특정 원소에 접근하려면 처음이나 끝부터 선형 탐색을 해야만 한다.
컨테이너 내 원소 순회는 forward / reverse 순회만 가능하다. 느리다.
원소들 간 연결을 위해 추가적인 메모리가 사용된다.

----
CategoryDocument