컨테이너 어댑터
이번 게시글에서는 이미 존재하는 컨테이너를 기반으로 만들어진 컨테이너를 알아볼 것이다.
기존 컨테이너를 감싸는 래퍼를 제공하는 데에는 몇 가지 이유가 있다.
코드에 좀 더 의미를 부여하고 싶거나, 또는 특별한 인터페이스를 새롭게 제공하고 싶은 경우가 대표적이다.
이러한 자료 구조 중의 하나가 스택이다.
스택은 데이터 처리와 보관을 위해 LIFO(Last In First Out, 후입선출) 구조를 사용한다.
기능적인 측면에서 스택은 컨테이너의 한족 끝에서만 데이터를 삽입하거나 삭제할 수 있으며,
한쪽 끝이 아닌 위치에 있는 데이터는 접근하거나 변경할 수 없다.
벡터나 덱은 이러한 기능을 기본적으로 지원하기 때문에 스택을 구현하기 위한 용도로 사용할 수 있다.
그러나 벡터나 덱을 직접 스택처럼 사용하기에는 약간의 문제가 있다.
다음 예제 코드는 두 가지의 스택 구현 방법을 보여준다.
std::deque<int> stk1;
stk1.push_back(1); // 스택에 1 추가 : {1}
stk1.push_back(2); // 스택에 2 추가 : {1, 2}
stk1.pop_back(); // 스택에서 맨 위 원소 제거 : {1}
stk1.push_front(0); // 원래 스택에서는 지원하지 않는 동작이다. : {0, 1}
std::stack<int> stk2;
stk2.push(1); // 스택에 1 추가 : {1}
stk2.push(2); // 스택에 2 추가 : {1, 2}
stk2.pop(); // 스택에서 맨 위 원소 제거 : {1}
stk2.push_front(0) // 지원되지 않아서 컴파일 에러!
이 예제의 앞부분에서는 std::deque을 사용하여 스택 객체 stk1을 만들어 사용했다.
이 경우 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(), pop(), emplace() 등의 함수로 제공한다.
push() 함수는 기본 컨테이너의 push_back() 함수를 사용하여 구현되고,
pop() 함수는 pop_back() 함수를 사용하여 구현한다.
top() 함수는 기본 컨테이너의 back() 함수를 사용하는데, 이는 스택에서 맨 위에 있는 데이터가
덱 구조에서는 맨 끝에 있는 원소이기 때문이다.
이처럼 기본 컨테이너의 한족 끝에서만 원소의 추가 및 삭제를 수행함으로써 LIFO 특징을 제공한다.
스택의 구현을 위해 벡터가 아니라 덱을 기본 컨테이너로 사용한다는 점을 기억하자.
이는 덱을 사용하면 원소 저장 공간을 재할당할 때 벡터처럼 전체 원소를 이동할 필요가 없기 때문이다.
그러므로 벡터보다 덱을 사용하는 것이 더 효율적이다.
그러나 몇몇 경우에는 특정 컨테이너가 더 좋은 효율을 보여줄 수 있으며,
이러한 경우에는 std::stack 객체 생성 시 템플릿 매개변수로 사용할 컨테이너를 지정할 수 있다.
예를 들어 std::vector 또는 std::list를 기본 컨테이너로 사용하는 스택을 만들고 싶다면
다음과 같이 코드를 작성한다.
std::stack<int, std::vector<int>> stk;
std::stack<int, std::list<int>> stk;
스택의 모든 연산은 시간 복잡도가 O(1)이다.
스택에서 기본 컨테이너로 함수 호출을 전달하는 과정은 컴파일러의 최적화에 의해
모두 인라인(inline) 형식으로 호출될 수 있어서 여기서 발생하는 오버헤드는 없다.
std::queue
LIFO 구조를 사용하는 std::stack과 달리 FIFO(First In First Out, 선입선출) 구조가 필요한 경우도 많이 있으며,
이러한 경우에는 std::queue 어댑터를 사용할 수 있다.
std::queue는 스택과 비슷한 형태의 함수를 지원하며,
다만 LIFO 대신 FIFO를 지원하기 위해 그 의미와 동작이 조금 다르게 정의되어 있다.
예를 들어 std::queue에서 push()는 std::stack에서의 push_back()을 의미하지만, pop() 명령은 pop_front()를 의미한다.
원소를 제거하는 pop() 함수와 달리,
단순히 양 끝단에 있는 원소에 접근하고 싶을 때에는 front() 또는 back() 함수를 사용한다.
다음은 std::queue를 사용하는 예제 코드이다.
std::queue<int>q;
q.push(1); // 맨 뒤에 1을 추가 : {1}
q.push(2); // 맨 뒤에 2를 추가 : {1, 2}
q.push(3); // 맨 뒤에 3을 추가 : {1, 2, 3}
q.pop(); // 맨 앞 원소를 제거 : {2, 3}
q.push(4); // 맨 뒤에 4를 추가 : {2, 3, 4}
앞 에제 코드에서는 큐(queue)에 원소 1, 2, 3을 차례대로 삽입한다.
그 다음에 큐에서 원소 하나를 제거한다.
제일 먼저 추가된 원소가 1이므로 원소를 제거할 때에도 1이 먼저 제거가 된다.
그런 다음 4를 추가하면 큐의 맨 뒤에 들어가게 된다.
std::queue는 std::stack과 같은 이유로 std::deque를 기본 컨테이너로 사용하며,
앞서 사용한 모든 함수는 시간 복잡도 O(1)로 동작한다.
std::priority_queue
우선순위 큐 (priority queue)는 힙(heap)이라고 부르는 매우 유용한 구조를 제공한다.
힙은 컨테이너에서 가장 작은 (또는 가장 큰) 원소에 빠르게 접근할 수 있는 자료구조이다.
최소/최대 원소에 접근하는 동작은 O(1)의 시간 복잡도를 가진다.
원소 삽입은 O(log n) 시간 복잡도로 동작하며, 원소 제거는 최소/최대 원소에 대해서만 가능하다.
여기서 유의해야 할 점은 최대 또는 최소 둘 중 하나에 대해서만 적용할 수 있으며,
최대와 최소에 한꺼번에 빠르게 접근할 수는 없다.
최대와 최소 중 어느 것에 빠르게 접근할 것인지는 컨테이너 비교자에 의해 결정된다.
std::stack이나 std::queue와 달리 std::priority_queue는 기본적으로
std::vector를 기본 컨테이너로 하며, 필요한 경우 변경이 가능하다.
비교자는 기본적으로 std::less를 사용한다.
그러므로 기본적으로는 최대 힙 (max heap)으로 생성되며, 이는 최대 원소가 맨 위에 나타나게 됨을 의미한다.
새로운 원소를 삽입할 때마다 최대 또는 최소 원소가 최상위에 위치하도록 설정해야 하기 때문에
단순하게 기본 컨테이너 함수를 호출하는 형태로 동작할 수 없다.
대신 비교자를 사용하여 최대 또는 최소 데이터를 맨 위까지 끌어올리는 히피파이(healify) 알고리즘을 구현해야 한다.
이러한 연산은 컨테이너 크기에 대한 로그 형태의 시간을 소요하며,
O(log n) 시간 복잡도로 표한한다.
여러 개의 원소를 이용하여 우선순위 큐를 초기화하 때에도 이러한 작업이 수행된다.
그러나 std::priority_queue 생성자는 단순히 초기화 원소에 대해 각각 삽입 함수를 호출하지 않는다.
대신 O(n) 시간 복잡도로 빠르게 동작하는 다른 힙 생성 알고리즘을 사용한다.
어댑터 반복자
지금까지 살펴본 모든 어댑터는 각가의 자료 구조에서 꼭 필요한 기능만 지원했다.
생각해보면 스택, 큐, 우선순위 큐에서 모든 원소를 순회하는 작업을 할 필요는 없다.
언제든 특정 위치에 있는 원소 하나만을 참조할 수 있으면 된다.
그러므로 STL은 이들 어댑터에 대해서는 반복자를 지원하지 않는다.
실습 문제
사무실 공유 프린터의 인쇄 대기 목록 시뮬레이션
보통의 회사 사무실에서는 한 대의 프린터를 공유하여 사용한다.
보통 여러 대의 컴퓨터가 하나의 프린터에 연결되어 있다.
프린터는 한 번에 하나의 인쇄 요청을 수행할 수 있으며,
하나의 인쇄 작업을 완료하기 전까지는 얼마간의 시간이 필요하다.
그러는 동안에는 다른 사용자가 인쇄 요청을 보낼 수 있다.
이 경우 프린터는 지연된 인쇄 요청 내역을 어딘가에 저장해 두어야 하며,
현재 인쇄 작업이 완료된 후 저장된 인쇄 요청을 처리해야한다.
#include <iostream>
#include <queue>
class Job
{
int id;
std::string user;
int pages;
static int count;
public:
Job(const std::string& u, int p) : user(u), pages(p), id(++count) {}
friend std::ostream& operator<<(std::ostream& os, const Job& j)
{
os << "id : " << j.id << ", 사용자 : " << j.user << ", 페이지 수 : " << j.pages << "장";
return os;
}
};
int Job::count = 0;
template <size_t N>
class Printer
{
std::queue<Job> jobs;
public:
bool addNewJob(const Job& job)
{
if (jobs.size() == N)
{
std::cout << "인쇄 대기열에 추가 실패 : " << job << std::endl;
return false;
}
std::cout << "인쇄 대기열에 추가 : " << job << std::endl;
jobs.push(job);
return true;
}
void startPrinting()
{
while (not jobs.empty())
{
std::cout << "인쇄 중 : " << jobs.front() << std::endl;
jobs.pop();
}
}
};
int main(void)
{
Printer<5> printer;
Job j1("광희", 10);
Job j2("정다", 4);
Job j3("현수", 5);
Job j4("유미", 7);
Job j5("채원", 8);
Job j6("시원", 10);
printer.addNewJob(j1);
printer.addNewJob(j2);
printer.addNewJob(j3);
printer.addNewJob(j4);
printer.addNewJob(j5);
printer.addNewJob(j6);
printer.startPrinting();
return 0;
}
해당 게시글은 코딩 테스트를 위한 자료구조와 알고리즘 with c++ 서적을 기반하여 작성되었습니다.
'컴퓨터 프로그래밍 공부 > 자료구조와 알고리즘' 카테고리의 다른 글
| 해시 테이블과 블룸 필터 (1) - 해시 테이블이란 (2) | 2024.01.05 |
|---|---|
| 트리 - 상하 반전된 형태 (0) | 2023.12.29 |
| 그리디 알고리즘 (2) - 분할 가능 배낭 문제 (2) | 2023.12.03 |
| 그리디 알고리즘 - 최단 작업 우선 스케줄링 (0) | 2023.12.01 |
| std::deque (0) | 2023.10.27 |