C++ 의 List와 Vector의 차이

https://thispointer.com/difference-between-vector-and-list-in-c/

이 문서는 C++의 std::vector 와 std::list의 다른 점에 대하여 논의할 것이다.

Vector와 List는 C++에서 Sequential한 Container이다.
Standard Template Library 이다.
이 두 Container의 내부 구현은 다른점이 많다.

List는 연속적이지 않은 Memory 장소에 각 요소들을 저장하고 있다. 다른말로 하면 double linked list로 구현이 되어 있다.

반면에 Vector는 각 요소들을 연속적인 Memory 장소에 저장하고 있다.

std::vector vs std::list
1.) Insertion and Deletion
List는 Vector에 비하여 삽입과 삭제가 효율적이다. 앞, 뒤, 중간 어디에서 작업을 하던지 몇개의 pointer만을 바꿔주면 되기 때문이다.

반면에 Vector는 앞이나 중간에 삽입이나 삭제를 하면 전체 요소들이 전부 이동을 해야 한다. 새로운 장소를 찾아야 하고 모든 값들이 복사되어야 한다.

2.) Random Access:
List가 내부적으로 Double Linked List로 구현되어 있기 때문에, random access 는 허용되지 않는다. 예를 들어 15번째 요소에 접근하려고 하면 iterator를 통하여 14개의 요소를 통과해야 한다는 것이다.

반면에 Vector는 Array 처럼 요소들을 연속된 Memory에 저장하고 있다. 그래서 Vector는 random access 가 가능하다. 예를 들어 15번째 요소에 접근 하려면
std::vector<int> vec(2);
vec[15] = 10;

그래서, List는 random access 가 필요한 STL algorithm 은 사용하지 못한다.

3.) Iterator Invalidation
List에서는 삭제나 삽입작업이 interator를 무효화 하는 경우가 없다. 왜냐하면 삽입이나 삭제할 경우에도 요소가 움직이는 경우가 없이 몇개의 포인터만 변경되기 때문이다.

4.) Special Member Fucntion

std::list 가 random access 를 제공하지 않기 때문에 많은 random access 를 사용하는 많은 STL 알고리즘들이 List에서 사용되지 못한다. 그래서 std::lisst에서는 추가적인 함수들을 제공하는데 이들은 Sorting, Spicing, Removing 인 것들이다.