Vector
#include <vector>[ 특징 & 장점 ]
흔히 사용하는 vector는 일반 배열처럼 연속적인 메모리 공간에 저장합니다.
그렇기에 iterator 뿐 아니라 index로도 접근이 가능합니다.
또한, 동적으로 확장/축소가 가능한 Dynamic Arrary로 구현되어 있습니다.
연속적인 메모리 공간에 저장되기에 deque, list에 비해서 개별 원소에 대한 접근 속도가 빠릅니다.
그리고 컨테이너 끝에서 삽입/제거하는 속도가 셋 중 가장 빠릅니다. - Q1
[ 단점 & 주의 ]
동적으로 컨테이너의 크기가 확장/축소되는 것이 편하긴 하지만, 확장시의 재할당 비용은 꽤 큽니다. - Q2
그렇기에 Capacity를 확장 시켜줄 수 있는 적절한 크기의 reserve로 인한 메모리 확보가 중요합니다. - Q2
Q1. 왜 끝에서 삽입/제거하는 속도만 빠른가?
가운데 C를 제거한다고 가정하면 연속적인 배열이기 때문에 한칸씩 다시 당겨야하는 상황이 벌어집니다.
지금은 요소가 5개 뿐이지만 수천 수만개일 경우 엄청난 낭비가 발생하게 되겠죠. 구조상 끝에서 삽입/삭제가 빠른 이유도 이 때문입니다.
Q2. 확장시 비용이 왜 큰가?
vector의 특징은 메모리 상의 시퀀스를 유지하려고 합니다. 그렇기에 빠른 이유이기도 하구요.
하지만 확장을 하게된다면? 공간이 부족하게 되면 기존에 있던 요소들과 함께 새로운 메모리를 할당 받아야 합니다.
시퀀스를 유지하기 위해서요.
(집에 방을 하나 더 갖고 싶어서 더 큰 집으로 이사를 가는 것과 같다고 보시면 됩니다)
결과적으로 vector는 더 큰 공간을 새로 할당하면서 적지 않은 오버헤드가 발생했었습니다.
이런 문제를 reserve라는 함수로 미리 할당후 재할당 방지를 해야 했었습니다.
하지만!
C++11부터 Move semantic이 등장해 이 동작의 비용이 크게 감소했다고 합니다.
Deque (double ended queue)
#include <deque>[ 특징 & 장점 ]
Random access iterator를 통한 index로 접근이 가능합니다. (추가설명 - 반복자)
또한, 동적으로 확장/축소가 가능한 Dynamic Arrary로 구현되어 있습니다.
vector와 비슷한 점이 많지만 deque는 컨테이너 끝 뿐만 아니라 첫 부분의 삽입/제거도 효율이 높습니다.
그리고 가장 큰 차이점은 연속된 메모리에 올라가 있지 않습니다. 몇 바이트 단위의 chunk로 쪼개져 있으며 이 chunk는 내부적으로 관리가 됩니다.
[추가설명] 반복자
- 입력 반복자(input iterator) : 현 위치의 원소를 한 번만 읽을 수 있는 반복자 (istream)
- 출력 반복자(output iterator) : 현 위치의 원소를 한 번만 쓸 수 있는 반복자 (ostream)
- 순방향 반복자(forward iterator) : 입력, 출력 반복자 기능에 순방향으로 이동(++)이 가능한 재할당될 수 있는 반복자
- 양방향 반복자(bidirectional iterator) : 순방향 반복자 기능에 역방향으로 이동(--)이 가능한 반복자 ( list, set, mulitset, map, multimap)
- 임의 접근 반복자(random access iterator) : 양방향 반복자 기능에 +, -, += , -=, [] 연산이 가능한 반복자 (vector, deque)
모든 컨테이너는 양방향 반복자 이상을 제공하며, 배열 기반 컨테이너인 vector와 deque는 임의 접근 반복자를 제공
즉, 저장 원소가 많고 메모리 할당량이 큰 경우 vector에 비해 확장 비용이 절감됩니다. 전체가 재할당되는 vector보다는 늘어나야 하는 크기만큼의 chunk가 하나 더 할당되기 때문입니다.
[ 단점 & 주의 ]
연속적인 메모리 공간이 아니므로, vector에서 가능했던 원소들간 포인터 연산이 불가능 합니다.
(이해가 안되신다면 포인터 개념에 대해 학습하시길 권장합니다!)
List
#include <list>[ 특징 & 장점 ]
자료구조에서 꼭 나오는 linked list가 바로 이 친구 입니다.
list는 doubly linked list로 구현되어 있습니다.
linked list를 이해하셨다면 아래의 특징을 이해하시는데 어렵지 않습니다!
컨테이너의 어느 위치에서도 삽입/제거가 빠릅니다.
[ 단점 & 주의 ]
원소의 index로 접근이 불가능합니다.
(접근을 하기 위해서는 처음 또는 끝에서 선형 탐색을 해야합니다.)
컨테이너 내 원소 순회는 forward / reverse 순회만 가능하며 느립니다.
원소들간 상호 연결 정보를 위해 추가적인 메모리가 사용됩니다.
정리
| vector | deque | list | |
| 강점 | - 끝쪽에 삽입/제거가 가장 빠름 - 원소에 대한 접근 속도가 가장 빠름 |
- 끝 뿐만 아니라 앞에서도 삽입/제거가 빠름 | - 어느 위치에서도 삽입/제거가 빠름 - 원소들의 컨테이너 내 순서 이동이 빠름 |
| 장점 | - 개별 원소에 index로 접근 가능 - 어떠한 순서로도 원소를 순회할 수 있음 |
- 개별 원소에 index로 접근 가능 - 어떠한 순서로도 원소를 순회할 수 있음 |
|
| 단점 | - 끝이 아닌 곳에서의 삽입/제거 속도는 느림 | - 앞과 끝이 아닌 곳에서의 삽입/제거 속도는 list보다 느림 | - 개별 원소에 index로 접근이 불가능 - 원소 순회는 forward/reverse 순회만 가능하며, 느림 |
| 주의 | - 확장시의 비용이 큼 | - 연속 메모리 공간이 아니기에 vector에서 가능했던 원소들 간 포인터 연산이 불가능 |
결론
어떤 상황에서도 안정적인 성능을 보이는 것은 deque입니다.
deque는 vector의 단점인 복사와 단편화를 줄였고 원소가 추가될 때 공간이 부족하면 새로운 메모리 블록을 할당합니다.
vector 보다는 지역성이 떨어지지만, vector보다 일관된 성능을 가지게 됩니다.
참고한 포스트
[1] egloos.zum.com/sweeper/v/2817817
[2] http://blog.naver.com/PostView.nhn?blogId=sssang97&logNo=221405464057&parentCategoryNo=&categoryNo=15&viewDate=&isShowPopularPosts=true&from=search
[3] hyeonstorage.tistory.com/318