[Vector]
C++의 vector는 C++ 표준라이브러리(Standard Template Library)에 있는 컨테이너로 사용자가 사용하기 편하게 정의된 class를 말합니다.
vector를 생성하면 메모리 heap에 생성되며 동적 할당됩니다.
물론 속도적인 측면에서 array(배열)에 비해 성능은 떨어지지만 메모리를 효율적으로 관리하고 예외처리가 쉽다는 장점이 있어 많이 사용하고 있습니다.
[Vector와 List]
vector와 list 모두 std 함수에 포함되어 있습니다.
공통점은 연속된 데이터의 집합입니다. 차이점은 vector는 다음 데이터가 바로 옆에 있는 주소에 입력되어 있고 list는 어디에 다음데이터 있다는 정보를 가지고 있으나 임의의 메모리 공간에 자리 잡고 있다는 점입니다.
이 구조를 이해하려면 double linked list 구조를 파악하는게 좋습니다만 저희는 시간이 없고 그래서 어느 걸 쓰는 게 더 효율적인지 궁금하죠.
결론적으로 말씀드리면 Vector가 좋습니다. 왜냐? 속도가 더 빨라요.
표를 하나 보여드릴게요.
| 시간복잡도 | Search | Insert | Delete |
| Vector | O(n) | O(n) | O(n) |
| Linked List | O(n) | O(1) | O(1) |
이렇게 보면 list가 좋아보입니다. 차이는 삽입과 삭제에서 발생합니다. 끝부분데이터를 삭제하고 삽입하는 데는 차이가 없습니다. 다만 중간에 데이터를 삽입하고 삭제하는 과정에서 복잡도가 늘어나는 구조입니다.
list는 메모리를 조금 더 쓰는 대신 이전 데이터는 어디있는지 다음데이터는 어디 있는지 정보를 가지고 있으나 공간의 제약이 없으니 중간에 데이터를 삽입해도 이전데이터와 다음데이터가 어디 있는지만 수정되면 되니 부담이 없습니다.
삭제에도 마찬가지로 적용되죠. 하지만 vector는 연속적으로 데이터가 구성되어 있기 때문에 삽입을 하기 위해서는 중간에 데이터 자리를 확보해야 합니다. 물리적으로 연결되어있는 기차 중간에 열차칸 하나를 삽입한다고 생각하시면 됩니다.
물리적으로 허리를 끊어 분리시킨다음 새로운 열차칸을 삽입하고 이어주어야 성립합니다. 비용이 크게 발생됩니다.
그러나 우리는 장점과 단점보다 내가 어떤 식으로 사용하고 싶은지에 집중해야 합니다.
대부분 리스트나 배열을 사용하면 끝부분에 데이터를 추가하고 삭제하는일을 합니다. 그렇다면 Insertion과 Deletion 모두 복잡도는 O(1)로 동일하다고 생각할 수 있습니다.
관건은 연속된 데이터에서 내가 원하는 데이터가 어디있는지 찾아내는 Search인데 해당 복잡도는 이론상 Vector와 List 동일합니다.
다만 실험을 해보면 달라집니다.
여기 Vector와 List에 데이터 각각 100만개를 넣어놓고 읽는 데 걸리는 시간을 측정해 보겠습니다.
그냥 대충 봐도 두 배차이가 나는 걸 확인할 수 있습니다.
이런 현상이 나타나는 이유 중 가장 큰 것은 CPU메모리 계층 구조 때문에 발생됩니다. 일반적으로 CPU는 캐시구역과 RAM구역으로 나눠져 있는데요. 최근에는 3개까지 캐시메모리가 확장되었습니다.
구간이 늘어난다는 건 List에서 아무리 링크로 묶여있어 어디 있는지 위치를 안다고 해도 메모리나 캐시구간에 접근하는데 시간이 더 걸린다는 의미입니다. List의 경우 동일 캐시메모리가 아닌 L1 -> L2 -> L1 -> L3 -> L1 이런 식으로 랜덤 한 순서로 데이터가 있는 경우 더 많은 리소스와 시간을 소비하는 것이지요.
vector가 list보다 메모리 관리적, 시간적 효율, 시스템적 등등 다양한 측면에서 List보다 좋습니다.
물론 예외의 경우도 있지만 중간중간에 데이터를 꼽아 넣을 일은 프로그램하면서 많이 없을 거라고 생각합니다.
왜냐면 search의 영역은 DB Linq나 다양한 알고리즘으로 지속적인 개선이 이루어지고 있기 때문이죠.
