<본 카테고리는 "코딩 테스트를 위한 자료 구조와 알고리즘 with C++을 기반으로 작성하였습니다>
컨테이너 어댑터(Container Adapter)
개요
앞서 살펴본 컨테이너들은 완전 바닥부터 직접 만들었다. 하지만 이미 존재하는 컨테이너를 기반으로 새로운 컨테이너를 만드는 작업, 즉, 래핑(wrapping)하여 새로운 인터페이스를 만드는 것이 더욱 효율적일 때가 있다. 이것이 바로 컨테이너 어댑터다. C++ 표준 라이브러리에서 제공하는 대표적인 컨테이너 어댑터를 간략하게 설명하고 구현하는 시간을 가져보자.
std::stack
스택(stack)은 데이터의 처리와 저장을 위해 LIFO(Last In First Out, 후입선출) 구조를 사용하는 컨테이너다. 기능적인 측면에서 스택은 한쪽 끝에서만 데이터를 삽입하거나 삭제하는데, 이를 활용해 괄호를 검사하거나, 뒤로 가기 버튼, 컴파일러를 구현할 때 사용된다. 즉, 데이터를 임시적으로 저장하고 필요한 순간에 쉽게 접근해야 할 때 유용하게 사용된다.
이러한 스택은 std::deque를 기본 컨테이너로 사용한다. std::vector를 이용하여 구현할 수도 있지만, 효율적인 측면에서 vector보단 deque가 다음과 같은 이유로 인해 더 뛰어나기 때문이다.
- std::deque가 std::vector보다 중간 삽입과 삭제가 더 빠름
- std::vector는 벡터의 크기가 변할 때마다 모든 원소를 복사하거나 이동시켜야하는 반면, deque는 그렇게 할 필요가 없음
스택의 모든 연산은 시간 복잡도가 O(1)이다. 스택에서 기본 컨테이너로 함수 호출을 전달하는 과정에서 오버헤드가 발생하지 않기 때문이다. 여기서 오버헤드란, 어떤 작업을 수행하기 위해 필요하지만, 실제 작업과는 직접적인 관련이 없는 추가적인 작업을 의미한다. 예를 들어 함수 호출에서 오버헤드는 함수 호출의 인자 전달, 함수의 스택 프레임 생성, 함수의 반환 주소 저장 등과 같은 추가 작업을 의미한다. 이러한 추가 작업은 함수 호출 자체보다 시간과 메모리를 더 많이 사용하게 된다.
이제 std::deque를 이용해 push, pop, empty, size를 갖고 있는 간단한 stack()을 구현해보자.
#include <iostream>
#include <deque>
template <class T>
class Stack
{
std::deque<T> dq;
public:
void push(const T& value)
{
dq.push_back(value);
}
void pop()
{
dq.pop_back();
}
const T& top() const
{
return dq.back();
}
bool empty() const
{
return dq.empty();
}
int size() const
{
return dq.size();
}
};확실히 기존의 컨테이너를 이용하다 보니, 쉽게 구현할 수 있었다. 이를 테스트하기 위해 main()에서 Stack을 생성해 접근해 보자.
int main()
{
Stack<int> myStack;
myStack.push(1);
myStack.push(2);
myStack.push(3);
while (myStack.empty() == false)
{
int data = myStack.top();
std::cout << data << ' ';
myStack.pop();
}
int size = myStack.size();
std::cout << std::endl << size << std::endl;
}std::queue
큐(queue)는 FIFO(First In First Out, 선입선출) 데이터 구조를 구현하는 컨테이너다. 스택과 마찬가지로 기능적인 측면에서 한쪽 끝에서만 데이터를 삽입하거나 삭제하는데, 이를 활용해 대기열이 있는 작업들을 처리할 때 사용되거나, 캐시를 관리할 때 사용된다.
이러한 큐는 std::deque 컨테이너를 기본적으로 사용한다. 하지만 원소의 개수가 100개 미만 정도로 적을 경우엔 std::list 컨테이너를 이용하는 것이 효율적일 때가 있다. 리스트는 원소들이 메모리상 불연속적으로 위치하기 때문에, deque와 달리 메모리 재할당이 일어나지 않기 때문이다. 따라서, 원소의 개수가 적거나 중간에 원소를 자주 삽입/삭제하는 경우 리스트를 사용하는 것이 나은 선택지가 될 수 있다. 물론, deque가 list에 비해 빠른 속도와 메모리 사용 면에서 우위를 보이는 경우가 많기 때문에, 일반적으로 큐를 구현할 때는 덱을 사용하는 것이 좋다.
이제 queue를 deque를 이용해서 한 번 구현해 보고, list를 이용해서 구현해 보겠다.
#include <iostream>
#include <deque>
template <class T>
class Queue
{
std::deque<T> dq;
public:
void push(const T& value)
{
dq.push_back(value);
}
void pop()
{
dq.pop_front();
}
const T& front() const
{
return dq.front();
}
bool empty() const
{
return dq.empty();
}
int size() const
{
return dq.size();
}
};
int main()
{
Queue<int> q;
for (int i = 1; i <= 3; i++)
q.push(i);
while (!q.empty())
{
int value = q.front();
std::cout << value << std::endl;
q.pop();
}
std::cout << q.size() << std::endl;
}
#include <iostream>
#include <list>
template <class T>
class Queue
{
std::list<T> li;
public:
void push(const T& value)
{
li.push_back(value);
}
void pop()
{
li.pop_front();
}
const T& front() const
{
return li.front();
}
bool empty() const
{
return li.empty();
}
int size() const
{
return li.size();
}
};
int main()
{
Queue<int> q;
for (int i = 1; i <= 3; i++)
q.push(i);
while (!q.empty())
{
int value = q.front();
std::cout << value << std::endl;
q.pop();
}
std::cout << q.size() << std::endl;
}std::priority_queue
우선순위 큐(priority queue) 혹은 힙(heap)은 가장 작은, 혹은 가장 큰 원소에 빠르게 접근할 수 있는 구조를 구현한 컨테이너다. 즉, 데이터를 삽입할 때마다 자동으로 우선순위에 따라 정렬되어 최상위 우선순위를 가지는 원소가 항상 맨 앞에 위치하게 된다. 이때 최소/최대 원소에 접근하는 동작은 O(1)의 시간 복잡도를 가지고, 원소 삽입은 O(logn) 시간 복잡도를 가진다.
이러한 우선순위큐는 std::vector컨테이너 혹은 heap을 기본적으로 사용한다. 특히, 매 동작마다 원소가 최상위에 위치하도록 하기 위해 히피파이 알고리즘을 구현해야 한다. 이때 히피파이(heapify) 알고리즘이란 비교자를 사용하여 원소들을 정렬하며, 힙의 구조를 유지하는 알고리즘이다.
이제 우선순위 큐를 vector를 이용하여 구현해 보겠다.
#include <iostream>
#include <vector>
template <class T>
class Priority_queue
{
std::vector<T> _heap = {};
public:
void push(const T& data)
{
_heap.push_back(data);
int now = static_cast<int>(_heap.size()) - 1;
// 현재 위치
while (now > 0)
{
int next = (now - 1) / 2;
// 현재 위치에서 부모 노드의 위치
if (_heap[now] < _heap[next])
break;
// 자식 값 < 부모 값
else
{
swap(_heap[now], _heap[next]);
now = next;
}
// 자식 값 > 부모 값일 때, 데이터와 위치 모두 바꿔줌
}
}
// 최상위에 단말 노드 -> 자식 노드와 비교
void pop()
{
_heap[0] = _heap.back();
// 최상위 값은 heap의 back
_heap.pop_back();
int now = 0; // 현재 위치
while (true)
{
int left = 2 * now + 1;
int right = 2 * now + 2;
// 배열에서 현재 위치를 기준으로 좌우 위치
if (left >= _heap.size())
break;
// 끝 위치에 도달했을 경우
else
{
int next = now;
if (_heap[next] < _heap[left])
next = left;
// 왼쪽과 비교
if (right < _heap.size() && _heap[next] < _heap[right])
next = right;
// 둘 쭉 승자를 오른쪽과 비교 ?
if (next == now)
break;
// 이동할 필요가 없을 경우
swap(_heap[now], _heap[next]);
now = next;
}
}
}
const T& top() const
{
return _heap[0];
}
bool empty() const
{
return _heap.empty();
}
};
int main()
{
Priority_queue<int> pq1;
pq1.push(100);
pq1.push(500);
pq1.push(600);
pq1.push(200);
pq1.push(400);
while (!pq1.empty())
{
int value = pq1.top();
pq1.pop();
std::cout << value << ' ';
}
std::cout << std::endl;
}요약
컨테이너 어댑터
1. 정의: 이미 존재하는 컨테이너를 기반으로 새로운 컨테이너를 만드는 작업
2. 종류
a. std::stack
- 데이터 처리와 보관을 위해 LIFO 구조를 갖는 컨테이너
b. std::queue
- 데이터 처리와 보관을 위해 FIFO 구조를 갖는 컨테이너
c. std::priority_queue
- 히피파이 알고리즘을 통해, 최대/최소 원소를 찾는 컨테이너
'CS > 자료구조' 카테고리의 다른 글
| [자료구조] 트리 순회(Tree traversal) (0) | 2023.04.17 |
|---|---|
| [자료구조] 트리(Tree) (0) | 2023.04.17 |
| [자료구조] std::deque (0) | 2023.04.01 |
| [자료구조] std::list (0) | 2023.03.31 |
| [자료구조] 메모리 청크 (0) | 2023.03.18 |