deque
deque는 vector와 list의 중간 정도의 컨테이너로, 여러 개의 메모리 블록을 할당하여 하나처럼 사용합니다.
1. vector처럼 capacity를 늘이는 과정에서 전체 copy가 일어나지 않습니다. (chunk 단위로 메모리 블록을 새로 할당 후 연결함)
2. 인덱스 접근은 가능하나, 연속적인 메모리가 아니기 때문에 포인터 연산은 불가합니다.
3. vector와 같이 처음, 끝이 아닌 중간에 삽입, 삭제하는 경우 요소를 밀어내면서 오버 헤드가 발생합니다 - O(N)
stack과 queue
LIFO의 stack과 FIFO의 queue는 위의 deque로 구현되어 있다. (STL 기준)
1. 두 컨테이너 모두 접근, 삽입, 삭제의 시간 복잡도가 O(1)로 아주 우수합니다. (front 혹은 back으로만 컨테이너를 제어할 수 있으므로)
2. 스택의 경우, front, back 중 하나만 top으로 사용합니다.
3. STL 큐의 경우, 원형 큐 형태를 취하지 않습니다.
priority_queue
최대 heap(default)으로 항상 정렬되는 vector(default), deque 기반 컨테이너입니다.
1. 최대 heap 형태를 띄므로, 접근, 삽입, 삭제가 O(log n)의 시간 복잡도를 갖습니다.
2. 그 외의 오버 헤드는 기반 컨테이너에 따라 달라집니다.
'C++' 카테고리의 다른 글
[C++] vector의 push_back, emplace_back 비교하기 (0) | 2021.12.01 |
---|---|
[C++] vector와 list (0) | 2021.12.01 |
[C++] map과 unordered_map (0) | 2021.12.01 |