[STL] [3] 컨테이너 어댑터 정리 (Container Adapter, std::stack, std::queue, std::priority_queue

이전 글

[STL] [1] 순차 컨테이너 정리 (Sequence Container, std::array, std::vector, std::list, std::deque)

[STL] [2] 연관 컨테이너 정리 (Associative Container, std::set, std::map) 
이전 글에서 STL container 개념과 Sequence container, Associative container에 대해서 정리하였다. 오늘은 앞서 소개한 STL container들을 이용하여 개발된 Container adapter에 대해서 정리하고자 한다.
 
 
 

Container Adapter

Container adapter는 기존 컨테이너를 변경(modify, adapt)하여 특정 인터페이스(기능)만을 제공하도록 만든 컨테이너를 의미한다[1]. 이전에서 다뤘던 Sequence container, Associative container와는 이름이 조금 다른데, 그 이유가 바로 Sequence container와 Associative container를 조작하여 만든 파생적인 컨테이너 클래스를 의미하기 때문이다. C++ STL 컨테이너 어댑터에는 std::stack, std::queue, std::priority_queue가 있다.
 
컨테이너 어댑터는 vector, list, deque 등 기존 컨테이너(underlying container)의 인터페이스를 제한하여 특정 기능만을 수행하게끔 만들어진 컨테이너 구현체이다. 이러한 인터페이스 제한을 통해 데이터를 특정한 방식으로만 조작하도록 강제된다. 예를 들어, Stack(Last in, First out, LIFO)과 Queue(First in, First out, FIFO)의 경우 데이터를 조작하는 방식이 강제적으로 고정되어야 한다. std::stack과 std::queue와 같은 Container adapter는 기존 container 구현들의 인터페이스를 제한함으로서 구현된다.

 

C++ STL 컨테이너 어댑터의 대표적인 예로는 std::stack[2], std::queue[3], std::priority_queue[4]가 있다. 세 개의 자료구조는 모두 특정 목적을 위해 데이터를 효율적으로 저장되도록 설계된 자료구조이며, 따라서 데이터를 저장, 획득하는 과정에 모두 제한사항이 있다. 예를 들어 Stack은 LIFO를 구현한 자료구조로 컨테이너에 저장된 순서 역순으로 데이터 획득이 가능하다. 반대로 Queue는 FIFO를 구현한 자료구조로 컨테이너에 저장된 순서대로 데이터 획득이 가능하다. Priority_queue는 데이터가 저장된 순서가 아닌 다른 기준(우선순위)을 두고, 그 기준에 따라서(우선순위가 높은 데이터부터) 데이터 획득이 가능하도록 설계되었다.

 

C++ STL 컨테이너 어댑터의 핵심은 기존 C++ STL 컨테이너를 기반으로 구현되었다는 점이다. 이때 기반이 되는 C++ STL 컨테이너를 underlying container라고 한다. 주로 사용되는 underlying container는 순차 컨테이너들이다. 위에서 언급한 std::stack, std::queue 모두 순서가 있기에 순차 컨테이너를 기반이 더 효율적으로 구현 될 수 있을 것이다. std::priority_queue 또한 순차 컨테이너를 이용해 구현되는데, 우선순위라는 새로운 기준이 있지만 heap[5] 개념을 이용하면 순차컨테이너를 통해서도 효율적으로 구현된다.

 

추가적으로 컨테이너 어댑터는 반복자(iterator)가 지원되지 않아[6], STL algorithm을 사용할 수 없다. 데이터 접근에 제한이 있는 자료구조이기에 모든 데이터에 접근할 수 있도록 열어주는 반복자가 지원되지 않는 게 당연한 것 같다.

 

컨테이너 어댑터들의 특징을 간단히 정리하면 다음과 같다.

 

• std::stack: LIFO 자료구조. 순차 컨테이너를 기반으로 구현되며, default 기반 컨테이너는 std::deque임. push(), pop(), top() 함수를 통해서 데이터를 저장, 삭제, 접근하며 순차 컨테이너의 한 끝에서만 모든 operation이 적용됨
• std::queue: FIFO 자료구조. 순차 컨테이너를 기반으로 구현되며, default 기반 컨테이너는 std::deque임. push(), pop(), top() 함수를 통해서 데이터를 저장, 삭제, 접근하며 순차 컨테이너의 한 끝에서만 데이터 저장이 가능, 반대쪽 끝에서는 데이터 삭제만 가능
• std::priority_queue: FIFO 자료구조. 순차 컨테이너를 기반으로 구현되며, default 기반 컨테이너는 std::vector임. push(), pop(), top() 함수를 통해서 데이터를 저장, 삭제, 접근하며, 항상 우선순위가 큰 순서대로 데이터에 접근할 수 있음

 
 
 

Stack (std::stack)

std::stack은 LIFO 제한이 있는 자료구조이다. 즉 가장 늦게 std::stack에 저장된 데이터에만 접근 및 삭제할 수 있다. std::stack은 내부적으로 순차 컨테이너를 통해 구현되는데, default로 std::deque를 사용한다. 왜 std::vector를 이용하지 않고, std::deque를 이용하는 지는 [7]에 정리되어있다. (정리하자면 std::stack을 사용하는 상황에 따라서 성능이 달라지기에, 구현하는 사람 마음으로 선택하였다. std::deque의 경우 동적 메모리 할당 과정에서 std::vector 보다 효율적이기에 사용한다.)

 

std::stack은 데이터의 저장 순서가 기억되어야 하며, std::stack의 정해진 한 끝단(the top of the stack)에서만 데이터를 저장, 획득, 삭제 하는 기능이 지원되어야 한다. 추가적으로 동적으로 크기가 커질 수 있어야 한다. 이를 만족하는 순차컨테이너에는 std::vector, std::list, std::deque가 있다. 사실 3가지 모두 underlying container로 사용가능하나, std::deque가 Stack을 구현하는데 가장 효율적이라고 생각되어[7] std::deque가 사용된다.

 

 

 

Queue (std::queue)

std::queue는 FIFO 제한이 있는 자료구조이다. 즉 가장 먼저 std::queue에 저장된 데이터에만 접근 및 삭제할 수 있다. std::queue는 내부적으로 순차 컨테이너를 통해 구현되는데, default로 std::deque를 사용한다.

 

std::queue는 데이터의 저장 순서가 기억되어야 하며, std::queue의 정해진 한 끝단(the back of the queue)에만 데이터가 저장되고, 반대편 끝단(the front of the queue)에서는 데이터를 획득, 삭제하는 기능만 지원되어야 한다. 추가적으로 동적으로 크기가 커질 수 있어야 한다. 이를 만족하는 순차컨테이너에는 std::vector, std::list, std::deque가 있다. 사실 3가지 모두 underlying container로 사용가능하나, std::deque가 Queue를 구현하는데 가장 효율적이라고 생각되어 std::deque가 사용된다.

 

 

Priority Queue (std::priority_queue)

std::priority_queue는 Heap 자료구조를 구현한 구현체이다. std::priority_queue는 데이터의 저장 순서에 따라 데이터 접근에 제한이 있는 std::stack, std::queue와는 다르게, 우선순위(priority)라는 새로운 기준을 이용하여 데이터 접근을 제한한다. std::priority_queue는 우선순위라는 기준을 이용해 데이터의 입력순서와는 상관없이 우선순위가 가장 높은 데이터부터 접근할 수 있다. 이때 우선순위는 사용자가 설정해줄 수 있다. (default로 std::less를 이용한다)

 

std::priority_queue는 Heap 자료구조를 이용하여 구현되었다. Heap을 간략히 소개하자면 이진트리 구조이며, 부모 노드의 값의 우선순위가 자식 노드보다 항상 높도록 유지한다. 따라서 Heap의 root 노드는 항상 모든 노드보다 우선순위가 높게 유지된다. 이러한 제한 사항(부모는 자식보다 항상 높은 우선순위를 가짐)을 항시 유지하기 위해 데이터 저장 및 과정에 약간은 추가적인 오버헤드가 발생한다. 데이터 저장 과정을 예로 들면, 새로 저장된 데이터에 대해서 자신의 부모 노드와 우선순위를 비교하고 만약 크다면 부모와 순서를 바꾼다. 이 과정을 더 이상 부모노드보다 크지 않을 때까지 반복된다.

 

Heap 자료구조는 개념적으로는 이진트리 구조로 설명되지만, vector와 같은 순차 컨테이너를 이용해서도 구현될 수 있다. (좀 더 생각해본다면 이진트리 구조를 사용하는 게 매우 비효율적으로 느껴질 것이다. 실제로도 그럴 것이다.) std::vector에서 i번째 데이터의 부모를 i/2라고 지정한다면 std::vector와 같은 순차 컨테이너로 쉽게 이진트리 구조를 표현할 수 있다.

 

std::priority_queue는 앞서 설명된 다른 컨테이너 어댑터와는 다르게 std::deque가 아닌 std::vector를 기본 컨테이너로 사용한다. 이에 대해서 개인적으로 생각하기에는 다음과 같은 이유이지 않을까 싶다. std::deque를 기본 컨테이너로 사용하는 std::stack은 랜덤 데이터 접근이 없고 오로지 top에서만 데이터 접근이 일어난다. 그렇기에 랜덤 데이터 접근에 강점인 std::vector를 사용할 필요도 없고, 오히려 항상 연속된 동적메모리영역이 필요한 std::vector의 특징이 약점이 될 것이다. 그에 비해 std::priority_queue는 우선순위에 따라 위치를 재조정하는 과정에서 내부적으로 끊임없이 랜덤 데이터 접근이 발생하기에 랜덤 데이터 접근이 빠른 std::vector가 좋은 도구가 될 것이다. 이런 이유로 선택하지 않았나 싶다.

 

 

Reference

[1] https://www.codeguru.com/cplusplus/an-introduction-to-container-adapters-in-c/

[2] https://en.cppreference.com/w/cpp/container/stack

[3] https://en.cppreference.com/w/cpp/container/queue

[4] https://en.cppreference.com/w/cpp/container/priority_queue

[5] https://en.wikipedia.org/wiki/Heap_(data_structure) 

[6] https://stackoverflow.com/questions/6569412/container-adapters-do-not-support-iterators

[7] https://stackoverflow.com/questions/102459/why-does-stdstack-use-stddeque-by-default