std::list와 std::vector의 차이점

내부 구조

vector

• 메모리가 연속하게 배치
• 동적 배열 기반

list

• 메모리가 비연속
• 각 노드가 포인터로 연결된 이중 연결 리스트

접근 속도

vector

연속된 메모리 -> 임의 접근 (Random Access) O(1)

list

임의 접근 불가능 -> 매번 노드를 따라가야 해서 O(n)

삽입·삭제 성능

vector

• 중간 삽입/삭제 시 요소를 한 칸씩 밀어내야 해서 O(n)
• 하지만 마지막(push_back)은 O(1)

list

• 노드 연결만 바꾸면 되므로 중간 삽입·삭제 자체는 O(1)
• 단, 삽입 위치까지 이동해야 하므로 전체적으로는 O(n)

캐시 히트

vector

• CPU는 데이터를 읽을 때 캐시 라인 단위(보통 64byte)로 가져옴
• vector는 요소들이 연속되어 있어 순차 탐색 시 캐시 히트율이 높음
• 이론적으로 O(n)이어도 실제 성능은 훨씬 빠르게 나옴

list

• 각 노드가 힙의 아무 위치에나 흩어져 있음
• 순차 탐색조차 매번 포인터를 쫒아 다른 메모리 위치로 이동 -> 캐시 미스 연속 발생
• 이 때문에 list는 실제 성능이 vector보다 훨씬 느린 경우가 많음