[STL] 벡터(Vector)와 리스트(List)의 장단점과 차이점

 

벡터(vector)

• 벡터는 동적배열을 만드는 연산을 수행한다. 따라서 연속적인 메모리를 확보한다.
• 자신의 요소를 내부의 동적 배열 ( dynamic array )로 복사한다.
• 임의 접근 연산자를 제공([])하기 때문에 어떠한 값에 접근하든 상수시간이 소요된다
• 동적 배열이기 때문에 배열의 중간에 새로 추가하거나 삭제하면 많은 값이 이동해야하기 때문에 오랜 시간이 걸린다
• 중간에 추가하는 것이 오버헤드가 크기 때문에 보통 뒷부분에 추가한다 ( push_back )
• 동적 배열이기 때문에 크기의 확장과 축소가 자유롭지만 재할당 비용은 크다.

 

• 장점
  • 임의접근을 상수시간에 가능하다. 따라서 읽기에 매우 강하다.

• 단점
  • 중간에 값을 추가/제거하는 비용이 크다
  • 재할당 비용이 크다

 

---

 

리스트(list)

• 리스트는 요소들을 양방향 연결리스트의 형태로 관리한다.(Doubly Linked List)
• 리스트 객체는 앵커라 불리는 포인터 2개를 제공하는데 이는 head와 tail을 가리킨다.
• 새로운 요소를 삽입하기 위해서는 이 포인터(앵커)를 조작한다.
• 리스트는 임의 접근을 제공하지 않는다. ( n번째 요소에 접근하기 위해서 노드들을 거쳐야 하기 때문 )
• 특정 위치에 추가/삭제가 자유롭다. ( 특정 위치를 찾는 시간은 제외 )
• 재할당 연산이 없다. 연속적인 메모리가 아니기 때문에 ( 메모리가 제공되는 한 ) 무한히 추가할 수 있다.

 

• 장점
  • 임의의 위치에 요소를 추가하는 것이 자유롭다 ( 찾아가는 시간 제외 ) 따라서 쓰기에 매우 강하다
• 단점
  • 임의접근이 불가능하기 때문에 선형 탐색하여 위치를 찾는다
  • 원소간의 연결을 위해 추가적인 메모리를 소모한다 ( 다음 노드의 포인터 메모리 )

---

    두 컨테이너의 가장 큰 차이는 각 컨테이너의 장점과 단점으로 볼 수 있다.

    리스트의 장점은 벡터의 단점이고 리스트의 단점은 벡터의 장점이다.

    벡터는 특정 위치에 접근하는 것이 상수시간에 가능하지만 중간에 데이터를 삽입하는 것이 오버헤드가 크지만 리스트는 데이터를 중간에 삽입하는 것에 오버헤드가 크지 않지만 해당 위치를 탐색하는데 시간이 오래 걸린다.

    데이터의 추가, 제거가 잦다면 리스트가, 새로운 데이터의 추가, 삭제보다 기존 데이터의 수정 및 탐색이 많다면 배열이 더 유리하다. 다만, 순차적으로 모든 데이터를 탐색해야하는 상황이 많은 경우에는 큰 차이가 나지 않을 수 있다.