[1. 리스트, 스택, 큐] 컨테이너 어댑터

컨테이너 어댑터(container adaptor)

기존의 컨테이너를 변형하여 꼭 필요한 인터페이스만을 제공하여 만든 컨테이너로, C++에서 제공하는 컨테이너 어댑터는 std::stack, std::queue, std::priority_queue가 있다.

---

std::stack

---

std::stack은 std::deque을 기본 컨테이너로 사용한다.

데이터 처리와 보관을 위해 LIFO(Last In First Out, 후입선출) 구조를 사용하고 한쪽 끝에서만 데이터의 삽입과 삭제가 이루어진다.

벡터와 덱에서 이러한 기능을 기본적으로 지원하지만, 직접 스택처럼 사용하기에는 기능이 너무 많다. 

그래서 의도하지 않은 동작과 코드를 잘못 작성하는 경우를 방지하기 위해 스택에 꼭 필요한 인터페이스만을 제공한다.

아래 코드에서 stack의 기본적인 함수들을 사용하였다.

#include <iostream>
#include <stack>
using namespace std;

int main(){
    stack<int> stack1;
    // deque에서의 push_back()함수를 사용하여 구현한다.
    stack1.push(1);
    stack1.push(2);
    stack1.push(3);

    cout << "stack1 size: " << stack1.size() << "\n"; // 출력 stack1 size: 3

    // 출력: 3 2 1 (LIFO)
    while(!stack1.empty()){
        cout << stack1.top() << "\t"; // deque에서의 back() 함수를 사용한다.
        stack1.pop(); // deque에서의 pop_back() 함수를 사용한다.
    }

    cout << "\n";

    cout << "stack1 size: " << stack1.size() << "\n"; // 출력 stack1 size: 0
}

stack에서 vector가 아닌 deque을 사용하는 이유는 원소 저장 공간을 재할당할 때 vector는 전체 원소를 이동해야 하기 때문이다. 그렇기에 deque을 사용하는 것이 효율적인데, 경우에 따라 vector나 list를 사용할 때도 존재한다.

다음과 같이 코드를 작성하면 vector나 list를 기본 컨테이너로 사용할 수 있다.

stack<int, std::vector<int>> stk;
stack<int, std::list<int>> stk;

스택의 모든 연산은 시간 복잡도가 O(1)이다. 스택에서 기본 컨테이너로 함수 호출을 전달하는 과정은 인라인(inline) 형식으로 호출될 수 있다.

---

std::queue

---

stack은 LIFO 구조를 사용하지만 queue는 FIFO 구조를 사용한다.

std::stack과 같은 이유로 std::deque을 기본 컨테이너로 사용하고, stack과 같은 방식으로 모든 함수는 시간 복잡도가 O(1)이다.

각 함수들은 다음과 같이 사용할 수 있다.

#include <iostream>
#include <queue>
using namespace std;

int main(){
    queue<int> queue1;

    // deque의 push_back()을 사용한다.
    queue1.push(1);
    queue1.push(2);
    queue1.push(3);

    cout << "queue1 size: " << queue1.size() << "\n"; // 출력: queue1 size: 3

    // 출력: 1 2 3 (FIFO)
    while (!queue1.empty()){
        cout << queue1.front() << "\t";
        queue1.pop();
    }

    cout << "\nqueue1 size: " << queue1.size(); // 출력: queue1 size: 0
}

---

std::priority_queue

---

priority queue는 heap 구조를 제공한다. 

heap은 컨테이너에서 가장 작거나 큰 원소에 빠르게 접근할 수 있는 자료구조로, 최소/최대 원소에 접근하는 동작은 O(1)의 시간복잡도를 갖고 원소 삽입은 O(logN) 시간복잡도로 동작한다.

stack과 queue와 달리 priority_queue는 std::vector를 기본 컨테이너로 사용한다. (필요한 경우 변경 가능하다.)

기본적으로는 비교자 std::less를 사용하여 최대 힙으로 생성되며, 이 또한 비교자를 이용하면 변경할 수 있다.

새로운 원소를 삽입할 때마다 최대 또는 최소 원소가 최상위에 위치하도록 설정해야 하기 때문에 heapity 알고리즘을 구현해야 한다. (O(logn))

다음 코드와 같이 간단하게 priority queue를 사용할 수 있다.

#include <iostream>
#include <queue>
using namespace std;

int main(){
    priority_queue<int> priorityQueue1;

    priorityQueue1.push(1);
    priorityQueue1.push(2);
    priorityQueue1.push(3);
    priorityQueue1.push(5);
    priorityQueue1.push(7);
    priorityQueue1.push(2);
    priorityQueue1.push(20);
    priorityQueue1.push(1);

    cout << "priorityQueue1 size: " << priorityQueue1.size() << "\n"; // 출력: priorityQueue1 size: 3

    // 출력: 20      7       5       3       2       2       1       1
    while (!priorityQueue1.empty()){
        cout << priorityQueue1.top() << "\t";
        priorityQueue1.pop();
    }

    cout << "\npriorityQueue1 size: " << priorityQueue1.size(); // 출력: priorityQueue1 size: 0


    priority_queue<int, vector<int>, greater<int>> priorityQueue2;

    priorityQueue2.push(1);
    priorityQueue2.push(2);
    priorityQueue2.push(3);
    priorityQueue2.push(5);
    priorityQueue2.push(7);
    priorityQueue2.push(2);
    priorityQueue2.push(20);
    priorityQueue2.push(1);

    cout << "priorityQueue1 size: " << priorityQueue2.size() << "\n"; // 출력: priorityQueue2 size: 3

    // 출력: 1       1       2       2       3       5       7       20
    while (!priorityQueue2.empty()){
        cout << priorityQueue2.top() << "\t";
        priorityQueue2.pop();
    }

    cout << "\npriorityQueue2 size: " << priorityQueue2.size(); // 출력: priorityQueue2 size: 0

}

---

경우에 따라 다른 컨테이너를 사용해야 할 텐데, 어떤 경우에 어떤 컨테이너가 맞는지 알기 위해 작은 프로토 타입을 만들고 성능을 측정하는 과정도 필요하다.

https://quick-bench.com/

Quick C++ Benchmarks

벤치마킹을 쉽게 수행할 수 있는 벤치마킹 프로그램의 도움을 받아 결과를 비교해볼 수 있다.