[C++] 리스트(list)와 벡터(vector)의 차이

 

C++에서 리스트와 벡터는 각각 무엇이고 둘은 어떻게 다른지 알아보자.

 

C++의 Standard Template Library(STL)에 있는 컨테이너(모든 타입의 객체 보관)는 크게 두 개로 나뉜다.

객체들을 순차적으로 보관하는 시퀀스 컨테이너 (sequence container) 와

키를 바탕으로 대응되는 값을 찾아주는 연관 컨테이너 (associative container)다.

 

 

---

 

시퀀스 컨테이너에 해당하는 리스트와 벡터는 무엇이 다를까?

 

 

벡터(vector)는 동적 배열(dynamic array)로 구현되어 있고,

리스트(list)는 이중 연결 리스트(Double Linked List)로 구현되어 있다.

이에 따라 벡터는 연속적으로 값을 저장하고, 리스트는 불연속적으로 값을 저장한다.

또 벡터는 Random Access가 가능하지만 리스트는 불가능하다.

 

좀 더 쉽게 풀어 이야기해보면,

벡터는 '인덱스'로 접근이 가능한데 중간에 요소를 삽입하려면 뒤의 것들을 밀어내고 이른바 '끼워넣기'를 해야 하고,

리스트에 있는 요소에는 '포인터'를 이용해 접근할 수 있는데

Linked 되어 있는 구조 때문에 15번째 요소에 접근하려면 iterator를 통해 14개의 요소를 통과해야만 한다.

'인덱스' 접근과 달리 '포인터'를 이용한 접근은 처음 또는 끝에서 출발해 선형 탐색을 해야하기 때문이다.

 

결론적으로 삽입, 삭제에 있어서는 리스트가 효율적이고, 검색에 있어서는 벡터가 효율적이다.

 

(하지만 끝 값을 삽입, 삭제 하는 경우 시퀀스 컨테이너 list, vector, deque 중 vector가 가장 빠르다.)