11장. 컨테이너 어댑터

1. stack 컨테이너

deque 컨테이너를 기반으로 함수를 이용해 stack처럼 구현한 것

스택의 기본 컨테이너는 deque 컨테이너다.

• 템플릿 형식

template<typename T, typename Container = deque<T>> // T: 원소형식, Container: 스택에 사용할 컨테이너 형식
class stack

 

• 스택 형식

멤버 형식	설명
value_type	Container::value_type으로 T 형식이다.
size_type	Container::size_type으로 인덱스나 원소 개수 등의 형식
container_type	Conatiner 형식이며, 기본은 deque<T>

생성자	설명
explicit stack(const Container& = Container())	기본 생성자를 호출해 stack을 생성, 인자로 받아 stack 생성

공통 멤버 함수	설명
bool empty() const	원소가 없는가?
size_type size() const	원소의 개수
void Push(const value_type& x)	원소 추가
void pop()	원소 제거

특수 멤버 함수	설명
value_type& top()	Top 원소를 참조한다.
const value_type& top() const	const 객체 Top 원소를 참조한다.

※ 스택은 vector, deque, list 다 가능하다.

 

2. queue 컨테이너

마찬가지로 deque가 기본 컨테이너다.

• 템플릿 형식

template<typename T, typename Container = deque<T>>
class queue

 

• 스택 형식 (멤버 형식과 공통 멤버 함수는 스택과 동일)

생성자	설명
explicit queue(const Container& = Container())	기본 생성자를 호출해 queue을 생성, 인자로 받아 queue 생성

특수 멤버 함수	설명
value_type& front()	첫 원소 참조
const value_type& front()	const 객체 첫 원소 참조
value_type& back()	마지막 원소 참조
const value_type& back() const	const 객체 마지막 원소 참조

※ front()와 back()으로 deque, list 컨테이너만 사용 가능하다.

queue<int, list<int>> q; // list 컨테이너 사용

 

3. priority_queue 컨테이너

특정 최상/하단의 오브젝트를 수시로 넣고 뺄 때 좋다.

• 템플릿 형식

template<typename T, typename Container=vector<T>, // T: 원소형식, Container: 사용할 컨테이나(기본 vector)
typename Comp = less<typename Container::value_type>> // Comp은 우선순위를 결정할 정렬 기준(기본 less<T>)
class priority_queue

• 스택 형식 (멤버 형식과 공통 멤버 함수는 스택과 동일)

생성자	설명
explicit priority_queue(const Comp& = Comp(), const Container& = Container())	기본 생성자를 호출해 priority_queue을 생성, 인자로 받아  priority_queue 생성

특수 멤버 함수	설명
value_type& top()	Top 원소를 참조한다.
const value_type& top() const	const 객체 Top 원소를 참조한다.

힙 알고리즘인 make_heap(), push_heap(), pop_heap()을 사용 및 구현되어 있으므로 임의 접근 반복자를 사용.

※ vector, deque 컨테이너 사용 가능

priority_queue<int> pq; // vector, less<int>
priority_queue<int, deque<int>, greater<int>> pq2; // deque, greater<int>