C++ STL 벡터, 리스트, 덱 비교
벡터
vector<pair<int,int>> v;
// 컴파일러 버전에 따라 vector<pair<int, int> > v;로 써야 인식이 되는 경우도 있다.
vector<int> v;
1) Vector 특징
- 배열과 유사하다.
- 배열의 크기는 고정이지만, 벡터의 크기는 동적으로 변한다.
- 중간에 데이터 삽입, 삭제가 용이하지 않다.
- 데이터를 순차적으로 저장한다.
- 검색 속도가 느리다.
- 랜덤 접근이 용이하다.
2) Vector를 사용해야 하는 경우
- 중간의 데이터 삽입이나 삭제가 없을 경우
- 순차적으로 저장된 데이터를 빈번하게 검색하지 않을 경우
- 특정 데이터가 저장된 위치를 파악하여 랜덤 접근할 경우 ex) v [5]
3) 장점
- 개별 원소들을 인덱스로 접근이 가능하다.
- 원소를 컨테이너의 끝에 삽입 / 삭제하는 것이 빠르다.
- 어떠한 순서로도 원소들을 순회할 수 있다.
- 일반적으로 vector는 deque, list에 비해 원소에 대한 접근 속도와 컨테이너의 끝에서 삽입 / 삭제하는 속도가 가장 빠르다.
4) 단점
- 맨 끝이 아닌 임의의 다른 위치에서의 삽입 삭제는 느리다.
리스트
list<int> l;
list<pair<int, int>> l;
1) List 특징
- 연결 리스트를 템플릿으로 구현한 것이다.
- 길이가 가변적이다.
- 중간에 데이터 삽입, 삭제가 용이하다.
- 랜덤 접근은 용이하지 않다.
2) List를 사용해야 하는 경우
- 중간의 데이터 삽입이나 삭제가 자주 발생할 경우
- 순차적으로 저장된 데이터를 빈번하게 검색하지 않을 경우
- 특정 데이터가 저장된 위치를 파악하여 랜덤 접근을 하지 않는 경우
3) 장점
- 컨테이너의 어느 위치에서도 삽입 / 삭제가 빠르다
- 원소들의 컨테이너 내 순서 이동이 빠르다.
- vector와 deque와 다르게 list의 가장 큰 장점은 컨테이너 내 어느 위치에서도 원소의 삽입 / 삭제가 빠르다.
4) 단점
- 원소의 인덱스로 직접 접근이 불가능하다.
- 특정 원소에 접근하려면 처음이나 끝에서부터 선형 탐색을 하여야만 한다.
- 컨테이너 내 원소 순회는 forward / reverse 순회만 가능하고 느리다.
- 원소들 간 상호 연결 정보를 위해 추가적인 메모리가 사용된다. (앞, 뒤 요소를 가리키는 포인터)
덱
deque<int> dq;
deque<pair<int, int>> dq;
1) Deque 특징
- Deque(Double Ended Queue)은 두 개의 큐를 가지고 있는 자료구조이다.
- 스택과 큐의 역할을 수행할 수 있다. 데이터 검색은 하지 않는다.
- list에서도 push_back, push_front, pop_back, pop_front를 제공하므로, 사실상 deque을 사용할 수 있다.
- 앞/뒤의 데이터 삽입, 삭제가 용이하다.
- 중간의 삽입, 삭제는 용이하지 않다.
2) Deque를 사용해야 하는 경우
- 중간의 데이터 삽입이나 삭제가 자주 발생하지 않아야 한다.
- 앞/뒤의 데이터 삽입 삭제가 자주 발생할 경우 사용한다.
- 순차적으로 저장된 데이터를 빈번하게 검색하지 않을 경우
- 특정 데이터가 저장된 위치를 파악하여 랜덤 접근을 하지 않는 경우
3) 장점
- 개별 원소들을 인덱스로 직접 접근이 가능하다.(d [5])
- 원소를 컨테이너의 끝뿐 아니라, 앞에서도 삽입/삭제하는 것이 빠르다.
- 어떠한 순서로도 원소들을 순회할 수 있다.
4) 단점
- 접근시간은 벡터보다 느리고, 중간에서의 삽입/삭제는 리스트보다 느리다.
Vector, List, Deque 정리
- 검색 속도 : vector > deque > list
- 삽입 삭제 : list > deque > vector