Vector
array 기반의 구조지만, 크기가 유동적임
- 장점
- 데이터 추가/삭제가 매우 빠르다. => O(1)
- 메모리가 연속적이기 때문에 iterator 연산자를 이용한 접근이 가능하다.
- 동적으로 확장/축소가 가능한 동적 배열(dynamic array)로 구현되어 있다.
- 단점
- 컨테이너 중간에서 삽입/제거 효율이 떨어진다. (모든 원소들을 한 칸씩 이동) => O(n)
- 확장 시 비용이 크다.
List
Double linked list이며, 노드 기반 컨테이너
- 장점
- 모든 위치에서 삽입/삭제가 빠르다. => O(1)
- 단점
- 랜덤 접근이 안 된다. 선형 탐색으로 접근해야 하며, 때문에 인덱스 직접 접근도 불가능
- 연결 정보를 저장하기 위해 메모리가 추가 사용된다.
정리하자면...
1. 벡터는 임의 접근에 강하며, 리스트는 순차 접근에 강함. 검색적인 측면에선 벡터가 우위를 가짐.
2. 그러나 벡터는 임의 위치에 대한 insert 연산이 약함. 이때에는 리스트가 시간 복잡도의 우위를 가짐.
Array
생성하는 시점에 반드시 배열의 크기를 지정해 주어야 하며, 생성한 후에는 그 크기를 변경할 수 없음.
- 장점
- 검색이 빠름.
- 인덱스를 통한 임의 접근 가능
- 단점
- 컴파일 시점에 크기가 확정되므로, 배열의 크기를 미리 선언해 주어야 함.
