왜 list말고 vector를 더 많이 쓰는지 궁금해서 찾아봄.

Vector

메모리상 위치가 연속되어있고, 선할당을 한다. 이 때, 각 요소의 타입에 비례하는 공간을 요구한다. 포인터를 안쓴다는 뜻. stack방식이라서, rear에 요소를 추가, 삭제하는 것은 O(1)이지만, 다른 곳에 추가, 삭제할 때는 O(n)이다. iterator중에 vector의 내용이 바뀌면 iterator는 무효화된다.

개별 원소에 array처럼 접근이 가능하며, 빠르다. 접근이랑 수정은 빠른데, 추가, 삭제는 빠르지 않음.

또한 동적 할당이기 때문에 확장, 축소가 용이하지만 비용이 크다. 요소의 추가, 삭제가 일어나면 벡터 자체를 재할당할 수 있다?

벡터의 벡터같은 구성일 때, 바로 떼어올 수 있다.

List

메모리상 위치가 비연속이고 선할당을 하지 않는다. next에 다음 포인터를 저장하는 방식이기 때문에 데이터 외에도 포인터를 위한 추가 메모리가 필요하다. C++의 List는 double linked list이다.

추가, 제거 비용이 저렴하고, 리스트 내부 어디서든 할 수 있다. iteration 중에 추가, 제거가 일어나도 iterator는 유효하다.

인덱스로 접근할 수 없다. 처음과 끝에서만 선형 탐색을 통해 접근 가능하기 때문에 다소 느리다.

리스트의 리스트같은 구성일 때, 바로 떼어올 수 없다. 근본적으로 배열이 아니기 때문.