Certi Pro 취득을 위해 꼭 알아야 할 STL Container : Adaptors

지난 포스팅에서는 STL에 정의된 자료구조 중 Unordered Associative Container에 대해 알아보았다.

Unordered Associative Container : Certi Pro 취득을 위해 꼭 알아야 할 STL Container : Unordered Associative

 

이번 포스팅에서는 마지막으로 Adaptors Container에 대해 알아보자.

 

① Adaptors란?

C++ STL Container 중 Adaptors란, 다른 컨테이너를 기반으로 새로운 인터페이스를 제공하는 Container이다. Adaptors는 Sequence container 활용하여 stack, queue, priority_queue 등의 interface를 제공한다.

stack은 기본적으로 deque, queue와 priority_queue는 deque나 vector container를 사용한다.

Adators는 Iterator 및 중간 원소 접근 기능을 제공하지 않으며, 프로 시험에서 stack은 체감상 거의 쓸 일이 없고 queue는 BFS에서 주로 사용하며 priority_queue는 아주 자주 사용된다.

priority_queue는 빈번한 삽입, 삭제 속에서 우선순위를 구하는 경우에 사용되지만, set / map에 비해 활용성이 떨어진다. 위에서 언급했듯이 Iterator 및 중간 원소 접근 기능을 제공하지 않기 때문이다. 추후에 다루겠지만, priority_queue를 사용하면서 특정 원소를 O(1)에 수정하고 싶을 때는, indexed heap을 사용하면 된다.

 

② stack

stack은 Last Input, First out(LIFO) 구조를 따르며, 항상 top만 접근 가능하다.

[stack 주요 문법]

stack<T> st
st = {} // clear

void st.push(T)
void st.pop()
T st.top()
int st.size()
bool st.empty()

 

 

③ queue

queue는 First Input, First out(FIFO)를 따르며, front / back만 접근 가능하다.

[queue 주요 문법]

queue<T> q
q = {} // clear

void q.push(x)
void q.pop()
T q.front()
T q.back()
int q.size()
bool q.empty()

 

 

④ priority_queue

priority_queue는 heap으로 구성 가능하며 항상 top만 접근 가능하다. 완전 이진트리로 구현되어 있기 때문에 모든 부모 노드가 자식 노드보다 우선순위가 높다. compare 기준으로 정렬했을 때 가장 오른쪽 element를 top으로 반환한다.

max heap

[주요 문법]

priority_queue<T> pq
priority_queue<T, vector<T>, Compare> pq
pq = {} // clear

void pq.push(x)
void pq.pop()
T pq.top()
int pq.size()
bool pq.empty()

priority queue는 set과 더불어 우선수위 문제에서 자주 사용되기 때문에 별도로 사용 예제를 정리해 볼 것이다.

더불어 indexed heap을 구현할 줄 알면 Pro 시험 합격 가능성이 매우 크게 올라갈 것이다.