컨테이너 어댑터: std::stack, std::queue, std::priority_queue
reference: "전문가를 위한 C++" / 마크 그레고리
앞서의 컨테이너(array, vector, forward_list, deque..)는 완전히 바닥부터 만들어졌다. 컨테이너 어댑터는 이미 존재하는 컨테이너를 기반으로 만들어진 컨테이너이다.
기존 컨테이너를 감싸는 래퍼를 제공하는 데에는 몇 가지 이유가 있다.
- 코드에 좀 더 의미 부여
- 의도하지 않는 함수를 실수로 사용하지 못하도록 제한
- 특별한 인터페이스를 새롭게 제공
이러한 자료 구조 중 하나가 스택(stack)이다.
벡터나 덱의 기본적인 기능을 통해 스택을 구현할 수 있지만 약간의 문제가 있다.
std::deque<int> stk1;
stk1.push_back(1);
stk1.push_back(1);
stk1.pop_back();
stk1.push_front(0); // 스택에서 지원하지 않는 동작deque를 사용하여 스택 객체를 만들어 사용하였다. 이 경우 push_front() 함수처럼 기본 스택에서 사용하면 안되는 명령 코드를 작성하는 것을 막을 수 없다.
이와 달리 std::stack을 사용하면 작성된 소스 코드는 어떤 작업을 하고 있는지 좀 더 직관적으로 알 수 있다. 또한 의도하지 않은 동작을 지시하거나 실수로 코드를 잘못 작성하는 경우가 발생하지 않게 된다.
정리하자면, std::stack은 std::deque으로 만든 간단한 래퍼로서 스택 자료 구조에서 꼭 필요한 인터페이스만을 제공한다. 이러한 방식으로 만들어진 것을 컨테이너 어댑터(container adapter)라고 하며, stack, queue, priority_queue가 있다.
std::stack
스택의 구현을 위해 벡터가 아닌 덱을 기본 컨테이너로 사용한다. 이는 덱을 사용하면 원소 저장 공간을 재할당할 때 벡터처럼 전체 원소를 이동할 필요가 없기 때문이다. 그러므로 덱을 사용하는 것이 더 효율적이다.
그러나 몇몇 경우에는 특정 컨테이너가 더 좋은 효율을 보여줄 수 있으며, 이러한 경우 std::stack 객체 생성 시 템플릿 매개변수로 사용할 컨테이너를 지정할 수 있다.
std::stack<int, std::vector<int>> stk; std::stack<int, std::list<int>> stk;위 코드와 같이 기본 컨테이너를 변경할 수 있다.
스택의 모든 연산은 시간 복잡도가 O(1)이다.
std::queue
std::queue도 std::stack과 같은 이유로 std::deque을 기본 컨테이너로 사용하며, 마찬가지로 모든 함수의 시간 복잡도는 O(1)이다.
어댑터의 반복자?
스택, 큐, 우선순위 큐에서 모든 원소를 순회하는 작업을 할 필요는 없다. 특정 위치에 있는 원소 하나만을 참조하고자 하는 목적으로 만들어졌다. 그러므로 STL은 어댑터에 대해선 반복자를 지원하지 않는다.
