[STL] vector, deque, list

<vector>

- 배열과 동일하게 연속적인 메모리 공간에 저장한다. 하여 원소들간의 포인터 연산이 가능하다.

- 개별 원소들에 대해서 iterator 접근 외에도 position index를 통하여 접근이 가능하다.

- 어떠한 순서로도 원소 순회가 가능하다. random access iterating이 가능하다.

- 동적으로 할당이 가능한 dynamic array로 구현되어 있다.

- 원소 끝부분에 삽입/삭제는 빠르나, 그 외 부분에서의 삽입/삭제는 deque, list에 비해 현저히 느리다.

- 동적으로 컨테이너의 크기가 확장/축소가 가능하나, 확장시 전체 메모리 크기만큼 reallocating이 발생함으로 비용이 크다.

- capacity를 확장시켜줄 수 있도록 적절한 크기의 reserve로 인한 메모리 확보가 중요하다.

 

<deque>

- vector와는 다르게 처음부터 끝까지 연속적인 메모리 공간에 저장되지는 않으므로, 원소들간의 포인터 연산이 불가능하다.

- vector와 동일하게 개별 원소들에 대해서 iterator 접근 외에도 position index를 통한 접근은 가능하다.

- vector와 동일하게 random access iterating이 가능하다.

- vector와 동일하게 동적으로 할당이 가능하지만, 확장시 전체 메모리 크기만큼 재할당되는 것이 아니라 늘어나야 될 크기만큼 chunk 단위로 늘어나므로 확장 비용이 절감된다.

- vector와는 다르게 원소 끝부분만이 아니라 제일 앞부분에 삽입/삭제시에도 빠르다. 이로인해 STL의 스택이나 힙 클래스 같은 경우 기본 클래스는 deque이다.

 

<list>

- 어느 위치에서나 요소의 삽입/삭제가 빠르다.

- 원소들의 컨테이너 내에서 순서 이동이 빠르다.

- vector, deque와는 다르게 position index를 통한 접근이 불가능하다. 특정 요소 접근시 처음이나 끝에서 선형 탐색을 해야한다.

- 원소 순회는 forward/reverse 순회만 가능하며, 느리다.

- 원소들간의 상호 연결 정보를 위하여 추가적인 메모리가 사용된다. 요소가 적을수록 상대적으로 비율이 클 것이다.