컨테이너 어댑터

스택

스택은 데이터 처리와 보관을 위해 LIFO(Last In First Out, 후입 선출) 구조를 사용

컨테이너의 한쪽 끝에서만 데이터를 삽입하거나 삭제할 수 있으며,

한쪽 끝이 아닌 위치에 있는 데이터는 접근하거나 변경할 수 없다.

벡터나 덱은 이러한 기능을 기본적으로 지원하기 때문에 스택을 구현하기 위한 용도로 사용할 수 있다.

하지만 벡터나 덱을 직접 스택처럼 사용하기에는 문제가 있다.

push_front() 함수처럼 스택에서 사용하면 안 되는 명령 코드를 작성하는 것을 막을 수 없다.

또한 push_back()과 pop_back() 같은 함수 이름은 자료 구조 맨 뒤에 데이터를 추가하거나 삭제한다는 의미인데,

스택으로 사용할 때에는 어느 위치에 데이터가 저장되는지는 알 필요가 없다.

이와는 달리 std::stack을 사용하여 작성된 소스 코든느 어떤 작업을 하고 있는지 좀 더 직관적으로 알 수 있다.

또한 의도하지 않은 동작을 지시하거나 실수로 코드를 잘못 작성하는 경우가 발생하지 않게 된다.

std::stack은 std::deque으로 만든 간단한 래퍼로서 스택 자료 구조에서 꼭 필요한 인터페이스만을 제공

이러한 방식으로 만들어진 것을 컨테이너 어댑터

C++에서 제공하는 컨테이너 어댑터는 std::stack, std::queue, stD::priority_queue가 있다.

 

std::stack

어댑터는 std::deque, std::vector 같은 다른 컨테이너를 사용하여 구성

std::stack은 보통 std::deque을 기본 컨테이너로 사용, std::stack은 스택이 기본적으로 제공해야 할 기능을

empty(), size(), top(), push(), emplace() 등의 함수로 제공, push() 함수는 기본 컨테이너의 push_back() 함수를 사용하여 구현되고, pop() 함수는 pop_back() 함수를 사용하여 구현, top() 함수는 기본 컨테이너의 back() 함수를 사용하는데, 스택에서 맨 위에 있는 데이터가 덱 구조에서는 맨 끝에 있는 원소, 기본 컨테이너의 한쪽 끝에서만 원소의 추가 및 삭제를 수행함으로써 LIFO 특징을 제공

스택의 구현을 위해 벡터가 아니라 덱을 기본 컨테이너로 사용

덱을 사용하면 원소 저장 공간을 재할당할 때 벡터처럼 전체 원소를 이동할 필요가 없기 때문

벡터보다 덱을 사용하는 것이 더 효율적, 몇몇 경우에는 특정 컨테이너가 더 좋은 효율을 보여줄 수 있으며, 

std::stack 객체 생성 시 템플릿 매개변수로 사용할 컨테이너를 지정할 수 있습니다.

std::vector 또는 std::list를 기본 컨테이너로 사용하는 스택을 만들고 싶다면

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

 

스택의 모든 연산은 시간 복잡도가 O(1), 스택에서 기본 컨테이너로 함수 호출을 전달하는 과정은 컴파일러의 최적화에 의해 모두 인라인 형식으로 호출될 수 있어서 여기서 발생하는 오버헤드는 없다.

 

std::queue

FIFO(First In First Out) 구조가 필요한 경우도 많이 있기에 이러한 경우에는 std::queue 어댑터를 사용할 수 있다.

스택과 비슷한 형태의 함수를 지원, 다만 LIFO 대신 FIFO를 지원하기 위해 그 의미와 동작이 조금 다르게 정의

std::queue에서 push()는 std::stack에서의 push_back(), pop명령은 pop_front()를 의미

원소를 제거하는 pop()함수와 달리, 단순히 양 끝단에 있는 원소에 접근하고 싶을 때에는 front() 또는 back() 함수 사용

 

std::queue는 std::stack과 같은 이유로 std::deque을 기본 컨테이너로 사용, 앞서 사용한 모든 함수는 시간 복잡도 O(1)로 동작

 

std::priority_queue

우선순위 큐는 힙이라고 부르는 매우 유용한 구조를 제공

힙은 컨테이너에서 가장 작거나 큰 원소에 빠르게 접근할 수 있는 자료 구조, 최소/최대 원소에 접근하는 동작은 O(1)의 시간 복잡도를 가진다. 원소 삽입은 O(log n) 시간 복잡도로 동작, 원소 제거는 최소/최대 원소에 대해서만 가능

유의해야 할 점은 최대 또는 최소 둘 중 하나에 대해서만 적용할 수 있으며, 최대와 최소에 한꺼번에 빠르게 접근할 수는 없다. 최대와 최소 중 어느 것에 빠르게 접근할 것인지는 컨테이너 비교자에 의해 결정

std::stack이나 std::queue와는 달리 std::priority_queue는 기본적으로 std::vector를 기본 컨테이너로 사용하며, 필요한 경우 변경할 수 있다. 비교자는 기본적으로 std::less를 사용, 기본적으로는 최대 힙으로 생성, 이는 최대 원소가 맨 위에 나타나게 됨

 

새로운 원소를 삽입할 때마다 최대 또는 최소 원소가 최상위에 위치하도록 설정해야 하기 때문에 단순하게 기본 컨테이너 함수를 호출하는 형태로 동작 X, 대신 비교자를 사용하여 최대 또는 최소 데이터를 맨 위로 끌어올리는 히피파이 알고리즘을 구현해야 함, 컨테이너 크기에 대한 로그 형태의 시간을 소요, O(lon n) 시간 복잡도로 표현, 여러 개의 원소를 이용하여 우선순위 큐를 초기화할 때에도 이러한 작업 수행

그러나 std::priority_pueue 생성자는 단순히 초기화 원소에 대해 각각 삽입 함수를 호출 X

대신 O(n) 시간 복잡도로 빠르게 동작하는 다른 힙 생성 알고리즘을 사용

 

이 구조들은 어댑터 반복자를 지원하지 않음

 

벤치마킹

벤치마킹은 통계 데이터 기반으로 더 나은 접근 방식을 결정하는 방법

연속적인 메모리에 데이터를 저장, 다양한 함수를 이용하여 저장된 데이터에 접근하여 처리하는 시나리오라면

std::vector 나 std::deque를 사용할 수 있지만 어느 것이 적합할지는 확신할 수 없을 때, 두 가지 모두 주어진 상황에서 좋은 성능을 낼 것 같을 때, 실제 모델과 비슷한 작은 프로토타입을 만들고, 각각의 성능을 측정, 테스트 결과에 따라 전반적으로 더 나은 결과를 나타내는 구현 방법 선택

성능 측정을 위해 각각의 방법으로 구현한 프로토타입에 대해서 여러 작업을 실행해보고, 각각의 수행 시간을 비교

운영체제의 스케줄링, 캐시, 인터럽트 등의 영향으로 인해 같은 작업을 수행한다 하더라도 매번 실행할 때마다 수행 시간이 조금씩 달라질 수 있다. 이런 영향으로 인해 한 번 작업을 수행할 때 수백 나노초만큼의 수행 시간 차이가 발생할 수 있으므로 부정확한 결과를 얻을 수 있다. 이러한 문제를 극복하기 위해 두 측정 시간에서 상당한 시간 차이가 발생할 대까지 작업을 여러 번(많게는 수백만 번) 반복하여 수행 시간을 측정하는 것이 좋다.