[C++]Vector와 List의 차이점

1.Array Vs List 차이점

Array : 메모리 상에 데이터가 연속적으로 저장됨

List : 메모리 상에 데이터가 비연속적으로 저장됨

 

2.Vector Vs List 차이점

99퍼센트는 벡터를 씀 (벡터가 더 빠름)

	랜덤 접근	삽입/삭제	뒤쪽 삽입/삭제
벡터	O(1)	O(n) - 하나하나 다 밀어야함	O(1)
리스트	O(n) - iterator를 사용해야함	O(1)	O(1)

위 벡터/ 아래 리스트

if find함수를 쓸 때는 둘 다 O(n) 시간복잡도가 필요함

but vector의 find가 훨씬 빠름

<list보다 vector를 써야 하는 이유>

실제 저장 공간은 격자구조.

vector는 순차적으로 저장됨 -> 다 cache안에 들어감

list는 여기저기 끊어져있음 -> cache miss가 일어남

자료구조의 성능을 비교할 때는 원소의 크기, 지역성에 대한 케시미스 입니다.
vector는 연속적으로 데이터를 저장하기 때문에 지역성이 높아 캐시 효율이 좋습니다. .
원시 타입이나 간단한 구조체에 대해서는 vector가 list에 비해 성능이 좋습니다.
반면에 list는 많은 상황에서 캐시 미스가 발생해 크기가 작은 원소에 대해서는 vector에 비해 느립니다.

	특징	장점	단점
vector	- 연속적인 메모리 - 각 요소는 요소 타입 그 자체만큼의 공간 요구함(주소 필요 x) - 요소 추가 시 언제나 전체 vector의 메모리 재할당 가능 - 랜덤하게 vector요소에 접근 가능	-개별 원소들 접근 가능 -원소를 마지막에 삽입하는 것이 빠름	-컨테이너 끝이 아닌 곳에 삽입, 제거 시 성능이 현저히 떨어짐 -동적이라 확장/축소가 편하나 확장 시 비용이 큼 (재할당 비용 큼)
list	-비연속적인 메모리 -Double linked list로 구현되어있음 -리스트 안의 요소는 이후, 이전의 요소를 가리키는 포인터를 가지고 있어 추가 공간이 필요함 - 요소 추가 시 전체 리스트의 메모리를 재할당할 필요가 없음 -요소에 랜덤으로 접근할 수 없기 때문에 특정한 요소에서 얻는 것의 비용이 비쌀 수 있음	- 컨테이너 어느 위치에서라도 삽입/제거 빠름 - 원소들의 컨테이너 내 이동 빠름	- 원소의 인덱스로 직접 접근 불가(array와 헷갈리지 말 것) - 원소간 상호 연결 정보를 위해 추가적 메모리 비용 발생