STL의 vector(이하, 벡터), deque(이하, 덱), list(이하, 리스트)를 정리해보았습니다.

벡터는 쉽게 생각해서 가변 길이가 지원되는 배열이라고 보면됩니다. 배열이기 때문에 임의 접근(random access)가 가능합니다. 그리고 언어 레벨의 배열과 달리 가변 길이가 지원되며, 시퀀스의 끝 쪽에 원소를 추가하는 경우 상수 시간(amortized constant time) 수행이 가능합니다. (사실상 STL의 벡터는 C++ 언어가 지원하는 배열과 비교해서 성능의 손실이 거의 없기 때문에 대안으로써 사용이 가능합니다.)

그러나 벡터의 경우 시퀀스의 앞쪽이나 중간에 원소를 삽입하는 경우 선형 시간 만큼 효율이 떨어집니다. 왜냐하면 추가된 원소의 뒷부분을 한 칸씩 시프트(shift)해야하기 때문입니다. 따라서 벡터에서는 push_front 함수를 제공하지 않습니다. (그러나 insert 함수를 이용해서 제일 앞쪽에 원소 추가는 가능합니다.)

덱은 스퀀스의 앞 쪽과 끝 쪽의 추가 및 삭제에 최적화된 컨테이너입니다. 덱의 양 쪽에 추가 및 삭제를 하는 경우 벡터의 보다 빠르게 수행됩니다. 그리고 벡터와 마찬가지로 임의 접근이 가능하지만, 그 성능은 벡터의 상수 시간과 동일하거나 그 상수 배만큼 느릴 수 있습니다. 또한 시퀀스의 중간에 원소를 삽입하는 것이 가능하지만, 벡터와 마찬가지로 선형 시간이 소요됩니다.

임의 접근이 필요하지만 스퀀스의 앞쪽에 원소가 추가되는 경우에는 덱을 적용하도록 합니다. 이 경우가 아니라면 임의 접근이 자주 발생하는지, 아니면 스퀀스의 끝 쪽에 추가가 자주 발생하는지를 비교해보아야 합니다. 만약 전자라면 벡터가 적합하며, 후자라면 덱이 적합합니다.

만약 시퀀스의 중간에 원소를 추가하는 빈도가 높다면 리스트를 적용하도록 합니다. 리스트의 경우 시퀀스 중간에 원소를 추가가 상수 시간이 소요됩니다. 리스트는 양방향 반복자를 지원합니다. (내부적으로 doubly linked list로 구현되어 있는 것 같습니다.) 그러나 임의 접근 반복자가 지원되지 않습니다. 이는 곧 정렬을 포함한 일부 알고리즘을 리스트에 적용할 수 없다는 것을 의미합니다. (그러나 리스트는의 멤버 함수로 sort를 제공합니다)