1.9 컨테이너 어댑터

컨테이너 어댑터(container adaptor)

종류: std::stack, std::queue, std::priorty_queue

 

std::stack

LIFO(Last In First Out) 후입선출 구조를 사용

std::deque을 기본 컨테이너로 사용하여 만들어진 래퍼.

멤버 함수

empty(), size(), top(), push(), pop(), emplace() 등

 

컨테이너 지정하기

std::stack<int, std::list<int>> st;

 

스택의 모든 연산은 시간 복잡도가 O(1)이다.

[참고] 스택에서 기본 컨테이너로 함수 호출을 전달하는 과정은 모두 인라인(inline)형식으로 호출될 수 있어서 여기서 발생하는 오버헤드는 없다.

 

 

std::queue

FIFO(First in First Out) 선입선출 구조.

std::deque를 기본 컨테이너로 사용하여 만들어진 래퍼.

모든 함수의 시간 복잡도 O(1)

 

std::priorty_queue

우선순위 큐(priorty queue)는 힙(heap) 자료구조를 제공한다. 

힙

최대or최소 원소 접근 O(1) 

원소 삽입은 O(log n) 시간복잡도로 동작

원소 제거는 최대or최소 원소만 가능

std::vector를 기본 컨테이너로 사용하여 만들어진 래퍼.

 

비교자 default는 std::less를 사용한다. 그러므로 기본적으로 최대 힙(max heap)으로 생성

 

새로운 원소를 삽입할 때마다 다시 정렬을 하기 때문에 히피파이(heapify)알고리즘으로 구현해야 한다. 이 연산은 O(log n) 시간복잡도가 걸린다. 

우선순위 큐를 초기화할 때는 O(n) 시간 복잡도로 빠르게 동작하는 힙 생성 알고리즘을 사용한다.

 

어댑터 반복자

STL은 컨테이너 어댑터에 대해서 반복자를 지우너하지 않는다.