[C++] 벡터(Vector)와 리스트(List)

벡터(Vector)

벡터(vector)는 기본적으로 동적 배열이다. 즉 매번 size를 확인하며 배열이 꽉 차게되면 자동으로 capacity를 늘린다. 물론 이 과정엔 메모리를 해제했다가 다시 할당하고 값을 복사하는 오버헤드가 포함되어 있다. 또한 메모리의 잦은 할당은 fragmentation을 초래한다. 따라서 사용 전 reserve를 통해 어느정도 capacity를 정하는 것이 좋다. 배열이기 때문에 인덱스를 지원하며 임의의 요소에 상수 시간으로 접근이 가능하다.(물론 인덱스를 알고 있다고 가정할 때) 하지만 임의의 요소가 삭제되거나 추가될 때 요소의 순서를 유지하기 위해 백터는 재정렬을 해야하는 오버헤드가 있다. 따라서 맨뒤에 요소를 삽입하거나 삭제하는 연산이 아닌 중간에 삽입 삭제가 빈번하게 발생하는 경우 성능이 떨어진다. 하지만 벡터는 연속된 메모리 구조를 가지는 배열이기 때문에 cpu의 cache와 잘 맞는 컨테이너이다.

---

리스트(List)

리스트(list)는 요소의 빠른 삽입 및 삭제 작업에 최적화되어 있다. 따라서 처음이든 중간이든 끝이든 삽입 및 삭제는 빠르지만 인덱스를 지원하지 않아 임의의 요소에 빠르게 접근할 수 있는 방법은 없다.