vector와 list의 차이점

vector

• 연속적인 메모리.
• 미래에 들어갈 요소를 위해 선할당을 한다
• 각 요소는 요소 타입 그자체만큼의 공간을 요구한다 (포인터들을 포함하지 않는다).
• 당신이 요소를 추가하는 어느 때나, 전체 vector의 메모리를 재할당 할 수 있다.
• 끝에 요소를 추가하는 것은 상수(상환 시간)지만, 다른곳에서 추가하는 것은 O(n) 값이 든다.
• 끝에 요소를 제거하는 것은 상수 시간이지만, 다른곳에서 제거하는 것은 O(n)이다.
• 랜덤하게 vector 요소에 접근 할 수 있다.
• vector에 혹은 vector로 부터 요소를 추가하거나 제거하면, iterator는 무효화된다.
• 당신이 요소의 배열을 필요로 한다면, 근본적인 배열에서 쉽게 얻을 수 있다.

 

장점

1. 개별 원소들 접근 가능

2. 원소를 마지막에 삽입 하는 것이 빠름

3. 랜덤으로 원소 순회가 가능

4. 개별 원소에 대한 접근 속도가 빠름

 

단점

1. 컨테이너 끝이 아닌 곳에 삽입/제거시 성능이 현전히 떨어짐

2. 동적이라 확장/축소가 편하나 확장시 비용이 크다.

 

 

---

list

• 비연속적인 메모리
• 리스트는 double linked list로 구현되어 있다.
• 메모리 선할당을 하지 않는다. 메모리 그 자신을 위한 메모리 오버헤드는 상수다.
• 리스트 안에 각 요소는 이후와 이전의 요소를 가리키는 포인터를 가지고 있어 추가 공간이 필요하다.
• 당신이 요소를 추가할 때, 전체 리스트의 메모리를 재할당할 필요가 없다.
• 추가와 제거에 비용이 싸고, 리스트 어디서든 일어날 수 있다.
• 요소에 랜덤 접근 할 수 없기 때문에, 특정한 요소에서 얻는것이 비용이 비쌀 수 있다.
• 리스트에서 요소를 추가 제거 할때, iterator은 유효하게 남아 있다.
• 만약 요소의 배열이 필요하다면, 당신은 새로운 배열을 만들어야만 하며 새로운 배열에 요소들을 추가해야 한다, 이는 근본적인 배열이 없기 때문이다.

 

장점

1. 컨테이너 어느 위치에서라도 삽입/제거가 빠름

2. 원소들의 컨테이너 내 이동이 빠름

 

단점

1. 원소의 인덱스로 직접 접근이 불가능함

2. 특정 원소에 접근하려면 처음이나 끝부터 선형 탐색을 해야함

3. 컨테이너 내 순회가 forward / reverse만 가능하여 느림

4. 원소간 상호 연결 정보를 위해 추가적 메모리 비용 발생

 

 

 

---

vector와 list의 차이점

1.  vector를 중간삽입시 원소를 밀어내지만 list는 노드를 연결만 하기 때문에,

삽입 삭제 부분에서 시간복잡도의 우위를 가진다.

 

2. vector는 랜덤부분접근이 가능하지만 list는 더블링크드리스트로 되어 있기 때문에

x[2]와 같은 랜덤 접근이 되지 않는다. 검색적인 측면에서는 vector가 우위에 있다.

 

 

출처: https://loadofprogrammer.tistory.com/76

★ 1. STL Vector와 List 설명 및 장단점

 

참고자료 : http://stackrefactoring.blogspot.com/2020/07/c-list-vector.html

C++ 의 List와 Vector의 차이