컨테이너 어뎁터(container adaptor)
- 이미 존재하는 컨테이너를 기반으로 만들어진 컨테이너에 대해 알아본다
- 각 자료구조에 대한 기본적인 내용은 이미 알고있다고 가정하고 글을 작성합니다!
- 래퍼를 제공하는 이유
- 코드에 의미를 부여
- 의도하지 않는 함수를 실수로 사용하지 못하도록 제한
- 특별한 인터페이스를 새롭게 제공
std::stack
- LIFO 구조를 사용하기 때문에 스택은 컨테이너의 한쪽 끝에서만 데이터를 삽입/삭제한다
- 벡터나 덱은 이러한 기능을 기본적으로 지원하기 때문에 스택을 구현하기 위한 용도로 사용할 수 있다
- push_front()로 맨 앞 원소에 접근할 수 있기 때문에 벡터나 덱을 직접 사용하기에는 문제가 있다
- 이와 달리 std::stack을 사용하여 작성된 소스 코드는 어떤 작업을 하고 있는지 직관적으로 알 수 있다.
- 또한 의도하지 않은 동작을 지시하거나 실수로 코드를 잘못 작성하는 경우가 발생하지 않게 된다
- 간단한 래퍼로서 만들어진 것을 컨테이너 어댑터(container adaptor)라고 한다
- std::stack은 std::deque를 기본 컨테이너로 사용한다
- 덱을 사용함으로써 원소 저장 공간을 재할당 할 때 벡터처럼 전체 원소를 이동할 필요가 없어 효율적이다
- std::stack 객체 생성시 템플릿 매개변수로 사용할 컨테이너를 지정할 수 있다.
- std::vector 또는 std::list를 기본 컨테이너로 사용하는 스택으로 만들 수 있다
std::stack<int, std::vector<int>> stk;
std::stack<int, std::list<int>> stk;
- empty(), size(), top(), push(), pop(), emplace()등의 함수를 제공한다
- push()는 덱의 push_back()을, pop()은 덱의 pop_back()을, top()은 덱의 back()을 사용하여 구현된다
- 스택의 모든 연산은 시간 복잡도가 O(1)이다
- 스택에서 기본 컨테이너로 함수 호출을 전달하는 과정은 컴파일러 최적화에 의해 모두 인라인 형식으로 호출되기 때문에 오버헤드가 없다
- 멍청하게 조금이라도 스택의 성능을 끌어올리려고 덱을 가져다가 스택처럼 사용할 필요는 없다는 것
std:queue
- FIFO 구조가 필요한 경우 std::queue 어댑터를 사용할 수 있다
- push(), pop()을 사용할 수 있으며, 단순히 양 끝단 원소에 접근하고 싶을 때는 front(), back() 함수를 사용한다
- example
std::queue<int> q;
q.push(1); // {1}
q.push(2); // {1, 2}
q.push(3); // {1, 2, 3}
q.pop(); // {2, 3}
q.push(4); // {2, 3, 4}
- std::deque를 기본 컨테이너로 사용하며, 앞서 사용한 모든 함수는 시간 복잡도 O(1)으로 동작한다
std::priority_queue
- 우선순위 큐(priority queue)는 힙(heap)이라고 부르는 매우 유용한 구조를 제공한다
- 힙은 컨테이너에서 가장 작은 원소에 빠르게 접근할 수 있는 자료 구조이다
- 최소/최대 원소에 접근하는 동작은 O(1) 시간 복잡도를 가진다
- 원소 삽입은 O(log n) 시간 복잡도로 동작하며, 원소 제거는 최소/최대 원소에 대해서만 가능하다
- 유의할 점
- 최대 / 최소 둘 중 하나에 대해서만 적용할 수 있으며, 최대/최소에 한꺼번에 빠르게 접근할 수 없다
- 어느 것에 빠르게 접근할 것인지는 컨테이너 비교자에 의해 결정된다
- std::priority_queue는 기본적으로 std::vector를 기본 컨테이너로 사용하고, 필요한 경우 변경할 수 있다
- 비교자는 std::less를 기본적으로 사용한다
- 새로운 원소를 삽입할 때 마다 최대/최소 원소가 최상위에 위치하도록 설정해야 함
- 기본 컨테이너 함수를 호출하는 형태로 동작할 수 없다
- 비교자를 사용하여 최소/최대 데이터를 끌어올리는 히피파이 알고리즘을 구현해야 한다
- 여러 개의 원소를 이용하여 우선순위 큐를 초기화할 때에도 이러한 작업이 수행된다
- std::priority_queue 생성자는 초기화 원소에 대해 각각 삽입 함수를 호출하지 않는다
- O(n) 시간복잡도로 빠르게 동작하는 다른 힙 생성 알고리즘을 사용한다
어댑터 반복자
- 어댑터는 각각의 자료구조에서 꼭 필요한 기능만 지원한다.
- 어댑터에서 모든 원소를 순회하는 작업을 할 필요는 없다
- 따라서 STL은 어댑터에 대해서 반복자를 지원하지 않는다