컨테이너 어댑터

컨테이너 어댑터는 STL에서 제공하는 컨테이너의 인터페이스를 래핑하여 인터페이스를 변경한 컨테이너다.

외부적으로 보일 때는 새로운 컨테이너같이 보이지만 내부 동작으로는 단순히 기존 컨테이너를 래핑할 뿐이다.

컨테이너 어댑터에는 stack, queue, priority_queue가 있다.

stack

stack은 LIFO: Last-In-First-Out 방식의 컨테이너를 구현한 템플릿이다.

stack의 내부 컨테이너로 쓰이기 위해서는 다음의 인터페이스를 지원해야 한다.

• push_back()
• pop_back()
• back()
• empty()
• size()

위의 인터페이스를 지원하는 컨테이너는 시퀀스 컨테이너다.
즉, vector, deque, list가 사용될 수 있으며 기본 컨테이너는 deque이다.

컨테이너 형식 지정

#include <iostream>
#include <stack>
#include <vector>
#include <deque>
#include <list>

using namespace std;

int main(void)
{
    stack<int, vector<int>> st1;
    stack<int, deque<int>> st2;
    stack<int, list<int>> st3;
}

컨테이너 사용

stack의 인터페이스는 다음과 같은 래핑 구조를 가진다.

• push_back() → push()
• pop_back() → pop()
• back() → top()
• size() → size()
• empty() → empty()

#include <iostream>
#include <stack>

using namespace std;

int main(void)
{
    stack<int> st;

    st.push(10);
    st.push(20);
    st.push(30);
    st.push(40);
    st.push(50);

    cout << "stack size: " << st.size() << endl;

    while(!st.empty())
    {
        cout << st.top() << ' ';
        st.pop();
    }
}

queue

queue는 FIFO: First-In-First-Out 방식의 컨테이너를 구현한 템플릿이다.

queue의 내부 컨테이너로 쓰이기 위해서는 다음의 인터페이스를 지원해야 한다.

• push_back()
• pop_back()
• front()
• back()
• size()
• empty()

위의 인터페이스를 지원하는 컨테이너는 deque과 list다.
queue는 기본 컨테이너로 deque를 채용한다.

컨테이너 형식 지정

#include <iostream>
#include <queue>
#include <deque>
#include <list>

using namespace std;

int main(void)
{
    queue<int, deque<int>> que1;
    queue<int, list<int>> que2;
}

컨테이너 사용

queue의 인터페이스는 다음과 같은 래핑 구조를 가진다.

• push_back() → push()
• pop_back() → pop()
• front() → front()
• back() → back()
• size() → size()
• empty() → empty()

#include <iostream>
#include <queue>

using namespace std;

int main(void)
{
    queue<int> que;

    que.push(10);
    que.push(20);
    que.push(30);
    que.push(40);
    que.push(50);

    cout << "queue size: " << que.size() << endl;

    while(!que.empty())
    {
        cout << que.front() << ' ';
        que.pop();
    }
}

priority_queue

priority_queue는 우선순위 큐를 구현한 템플릿이다.

priority_queue는 내부적으로 make_heap(), push_heap(), pop_heap() 등의 힙 알고리즘을 사용한다.

따라서 임의 접근 반복자를 지원하는 컨테이너인 vector, deque을 사용할 수 있다.
priority_queue는 기본 컨테이너로 vector를 채용한다.

컨테이너 형식 지정

#include <iostream>
#include <queue>
#include <vector>
#include <deque>

using namespace std;

int main(void)
{
    priority_queue<int, vector<int>> pq1;
    priority_queue<int, deque<int>> pq2;
}

조건자 지정

커스텀 정렬 조건자를 지정함으로 특정 조건에 의해 정렬되도록 지정할 수 있다.
이를 이용하면 최소 힙 또는 최대 힙을 구현할 수 있다.

기본적으로 priority_queue는 less<>를 채용하며 최대 힙이다.

#include <iostream>
#include <queue>

using namespace std;

int main(void)
{
    priority_queue<int, vector<int>, less<int>> pq1;     // 최대 힙
    priority_queue<int, vector<int>, greater<int>> pq2;  // 최소 힙
}

컨테이너의 사용

queue의 인터페이스는 다음과 같은 래핑 구조를 가진다.

• push_back() → push()
• pop_back() → pop()
• back() → top()
• size() → size()
• empty() → empty()

#include <iostream>
#include <queue>

using namespace std;

int main(void)
{
    priority_queue<int> pq;

    pq.push(30);
    pq.push(50);
    pq.push(10);
    pq.push(40);
    pq.push(20);

    cout << "priority queue size: " << pq.size() << endl;

    while(!pq.empty())
    {
        cout << pq.top() << ' ';
        pq.pop();
    }
}

정리

• 컨테이너 어댑터에는 stack, queue, priority_queue가 있다.
• stack은 LIFO 방식의 컨테이너를 구현하는 템플릿 클래스다.
• queue는 FIFO 방식의 컨테이너를 구현하는 템플릿 클래스다.
• priority_queue는 우선순위 큐 컨테이너를 구현하는 템플릿 클래스다.