[C++]Vector와 List의 차이

C++의 STL에는 Vector와 List라는 컨테이너가 있다.

언뜻보기에는 두 컨테이너에는 차이가 없는것 처럼 보이지만 사실 큰 차이점이 있다.

 

1. Vector

• Vector 컨테이너는 일반적인 배열처럼 연속적인 메모리 공간에 저장하는 방식.
• 후에 들어올 요소들을 대비해 미리 예비 공간을 할당함.
• 배열과 달리 크기의 제한을 받지않음.(32bit 기준으로 10억개 정도는 있긴함)
• 맨뒤에 추가하는건 빠르지만 중간에 삽입할 시 O(n)만큼의 시간이 걸림. 
• 중간에 삽입시 원소들을 뒤로 밀어냄.
• [1] 과 같이 랜덤 접근이 가능함.
• 동적으로 크기가 확장되지만 비용이 큼

 

2. List

• List 컨테이너는 더블 링크드 리스트로 구현되어 있음.
• 값을 추가할 때마다 메모리를 할당함
• 중간에 있는 특정 원소를 찾기 위해서 앞에서 부터 순서대로 찾아야함.
• 추가 삭제에 비용이 적음
• [1] 같은 랜덤 접근 불가능

 

벡터는 연속적인 주소에 할당되어 링크드 리스트 처럼 next 변수가 없으므로 메모리가 리스트보다 더 적다.

 

 

컨테이너 끝 외에 곳에서 추가나 삭제가 많다면 리스트를 사용하고 랜덤 접근이 필요하다면 벡터를 사용하는 것이 좋다.

리스트의 메모리가 더 크긴 하지만 더 빠르다.

 

벡터는 리스트보다 더 좋은 CPU 캐시 지역화를 가지는데 한 요소에 접근하는 것은 캐시 안에 다음 요소가 존재하고 다음 캐시가 느린 RAM을 읽을 필요없이 검색될 수 있을 가능성을 높게 하기 때문에 요소 추가가 많지 않다면 벡터를 사용하는게 좋다.

출처: https://theemeraldtablet.tistory.com/entry/list와-vector-차이점 [에메랄드 타블릿]