C++의 템플릿 기능
C++에는 클래스와 함수의 재사용에 큰 도움을 주는 템플릿이라는 기능이 있다.
간단하게 설명하면, 우리는 보통 함수를 정의할 때 함수에 사용되는 매개변수의 자료형을 설정해준다.
정수형 값인 매개변수면 int로 선언해야하고, 실수형이면 double 이나 float으로 선언해야 한다.
그러나 템플릿 기능을 사용하면, 해당 매개변수의 타입을 '모호하게' 설정하여 아무 값이나 유연하게 작동한다.
선택정렬의 두 가지 코드를 보며 비교해보자.
void SelectionSort(int *a, const int n) {
for(int i=0; i<n; i++) {
int j = i;
for(int k=i; k<n; k++) {
if(a[k] < a[k]) j = k;
}
swap(a[i], a[j]);
}
}
위의 코드가 우리가 아는 일반적인 함수의 정의와 선언이다. 매개변수의 자료형을 미리 지정해주는 모습이다.
그러나 템플릿을 사용한 밑의 코드를 보면,
template <class T>
void SelectionSort(T *a, const int n) {
for(int i=0; i<n; i++) {
int j = i;
for(int k=i; k<n; k++) {
if(a[k] < a[k]) j = k;
}
swap(a[i], a[j]);
}
}
template <class T> 라는 줄이 추가되었고, 매개변수의 자료형 또한 T 타입으로 바뀐 모습이다.
해당 라인의 의미는, '모호한' 타입을 매개변수의 자료형으로 설정해 어떤 자료형이 오던지 작동하게 해준다는 것이다.
굳이 여러 자료형에 대해 함수를 따로 구분지어줄 필요 없이, 템플릿 기능을 사용하면 하나만 구현해도 된다.
그러나 템플릿에도 문제가 존재한다. 바로 클래스를 사용하는 경우이다.
위처럼 매개변수의 자료형은 primitive한 타입을 사용하는 경우가 많아 swap, 대소비교는 당연히 가능해 문제가 안되지만,
클래스를 선언하는 경우는 온전히 새로운 자료형을 만드는 것과 동일하다. 객체지향에 대해 조금 공부해보았다면,
연산자 오버로딩이라는 개념에 대해 알고 있을 것이다. 특정 자료형에 대한 연산을 추가 정의해주는 것으로,
만약 rectangle 이라는 클래스를 만들었다고 해보자. rectangle 객체 간의 대소비교는 어떻게 해야할까?
기본적으로 이런 연산들은 정의되어있지 않다. 사용자가 직접 정의하는 과정이 필요하고, 이를 연산자 오버로딩이라 한다.
여기서 템플릿을 사용하는데 대소비교가 정의되어있지 않은 클래스 타입이 T에 들어간다면, 오류가 발생하게 된다.
따라서 템플릿의 경우는 꼭 내부 함수에서 사용된 연산들이 어떤 자료형이든 적용할 수 있는지 고민해보아야한다.
컨테이너 클래스의 템플릿(Using Templates to Represent Container Classes)
컨테이너 클래스란 특정 데이터 객체들을 담은 자료구조를 표현하는 클래스를 말한다. 배열, 배낭, 집합 등이 해당한다.
해당 클래스를 통해 객체들은 추가되고 지워질 수 있다. 이 중에서도 우린 배낭(Bag)에 대해 알아볼 것이다.
배낭 자료구조의 특성과 연산은 다음과 같다.
- 같은 요소를 여러 개 가지고 있을 수 있다(중복허용)
- 요소의 위치는 중요하지 않다(집합, 인덱스 x)
- 삽입 : 요소를 가장 처음으로 찾는 위치에 넣는다. 꽉차면, 크기가 두 배가 된다.
- 삭제(delete) : 특정 위치의 값을 삭제한다. 해당 값의 오른쪽에 있는 값들은 한 칸씩 왼쪽으로 땡겨진다.
- pop : 같은 삭제이지만, 삭제된 값을 반환한다.
이런 자료구조는, 템플릿으로 구현하면 어떤 자료형이든 담을 수 있어 매우 편리하다.
실제로 STL로 사용할 수 있는 여러 자료구조들도 템플릿 기능을 사용했기 때문에, 여러 자료형에 대해 적용 가능한 것.
template <class T>
class Bag {
public:
Bag(int bagCapacity = 10);
~Bag();
int Size() const;
bool IsEmpty() const;
T& Element() const;
void Push(const T&);
void Pop();
private:
T *array;
int capacity;
int top;
};
이런 식으로 배낭 자료구조를 정의해줄 수 있다. 이렇게 구현해두면, 정수를 저장하는 배낭, 실수를 저장하는 배낭을
내 입맛에 맞게 자료형만 바꿔서 사용하면 된다. Bag<int> a; 나 Bag<Rectangle> r; 이런 식으로 말이다.
스택(Stack), 스택 추상 데이터 타입
이제부터 본격적으로 기초에서는 다루지 못해봤을 여러 자료구조들에 대해 배운다.
가장 먼저 접하게 되는 것이 스택 혹은 큐로, 비교적 간단한 구현과 연산들을 가지고 있어 이해하고 사용하기도 쉽다.
스택은 ordered list의 스페셜 케이스이다. 데이터의 삽입과 삭제가 오직 'top' 이라는 위치에서만 이루어지기 때문이다.
그래서 스택을 설명할때 배열을 세로로 세워서 top과 bottom을 두고 설명을 하곤 한다.
stack S = $(a_0, ... , a_{n-1})$ 라고하면, $a_0$은 bottom, $a_{n-1}$은 top이 된다.
그림을 보면, 데이터가 수직으로 쌓이는 모습을 볼 수 있다. 아무것도 없는 경우 바닥부터 하나씩 쌓이게 되고,
빼내는 경우도 가장 위의 것을 뺀다. 그러면 당연히 나중에 삽입된 데이터가 먼저 삭제됨을 알 수 있다.
이를 LIFO(Last In First Out) 라고 부르며, 스택의 가장 중요한 특징중 하나이다.
이런 방식은 우리가 프로그램을 실행할 때 함수의 호출 과정에서도 사용되는데, 시스템 스택이 그 예시이다.
함수가 호출되면, 해당 함수의 스택 프레임이 시스템 스택 가장 위에 추가된다. 이때 스택 프레임은 호출한 쪽을 가리킨다.
즉, 이전의 스택 프레임을 가리킨다는 이야기이다. 스택 프레임에는 주소, 포인터, 변수, 매개변수 등의 값들이 존재한다.
재귀함수는 자기 자신을 계속해서 호출하는데, 최악의 경우 사용가능한 메모리를 모두 써 오버플로우가 발생할 수 있다.
이제 스택 ADT를 템플릿 기능을 활용해 구현해보자. 이때, 스택에 아무것도 없는 빈 상태는 top = -1 로 정의한다.
template <class T>
class Stack {
private :
T* stack;
int capacity;
int top;
public :
Stack(int firstcap = 10000);
void push(const T& item);
void pop();
bool isEmpty();
T& Top();
};
template <class T>
Stack<T> :: Stack(int firstcap) : capacity(firstcap) {
if(capacity < 1) throw "Stack capacity must be > 0";
stack = new T[capacity];
top = -1;
}
이런 식으로 간단하게 먼저 구현해볼 수 있다. 전체적인 틀만 짠 것이고, 세부 함수들은 아직 구현하지 않았다.
isempty나 top은 매우 간단하니, 내가 직접 구현했던 push와 pop을 적어두도록 하겠다.
template <class T>
void Stack<T> ::pop() {
if(top == -1) {
cout << -1 << '\n';
}
else {
cout << stack[top] << '\n';
stack[top--].~T();
size--;
}
}
template <class T>
void Stack<T> ::push(const T& item) {
if(top+1 >= capacity) {
T* newStack = new T[2*capacity];
copy(stack, stack+capacity, newStack);
delete[] stack;
stack = newStack;
capacity *= 2;
}
stack[++top] = item;
size++;
}
중요한건 ++와 --의 위치, 그리고 예외의 경우를 잘 설정해주는 것이다. 직접 구현해보는 것을 추천한다.
스택은 매우 간단하니 이 정도만 하고 넘어가도록 하겠다.
큐(Queue), 큐 추상 데이터 타입
큐도 ordered list의 스페셜 케이스로, 큐는 삽입과 삭제가 서로 다른 위치에서 이루어진다.
큐는 스택과 달리 배열 그대로 가로로 눕힌 형태인데, front와 rear라는 용어를 사용해 앞과 뒤를 부른다.
이때 삽입은 rear에서 이루어지고, 삭제는 front에서 이루어진다. 즉, 먼저 들어온 데이터가 먼저 삭제된다.
이는 FIFO(First In First Out) 라고 부르며, 이또한 큐에서 가장 중요한 특징 중 하나이다.
이런 식으로 큐의 연산이 이루어진다. 큐를 구현하는 방법도 여러 가지가 있는데, 하나씩 살펴보도록 하자.
큐의 구현(1) : front는 항상 queue[0], 첫 인덱스로 하는 방법
가장 쉽고 간단하게 떠올릴 수 있는 구현 방법이다. 항상 큐 배열의 0번 인덱스를 front로 유지한다.
그러면 삽입의 경우는 그냥 뒤에 데이터를 추가하면 된다.
삭제는 0번 인덱스의 데이터를 지우고, 1~끝번까지의 데이터를 한 칸씩 앞으로 땡기면 된다.
이 경우 삭제는 n개의 요소를 하나씩 옮기므로 $O(n)$, 삽입은 배열 크기 변화를 제외하면 $O(1)$이 걸린다.
그러나 해당 방법은 삭제 연산에 많은 시간이 소요된다.
큐의 구현(2) : front 변수를 지정해 queue[front]로 유지하는 방법
그 다음 방법은 front 변수로 현재 맨 앞의 값이 어디에 있는지 확인하면서 진행하는 방법이다.
해당 방법에서는 삭제 연산이 일어날 경우 값을 삭제하지 않고, front의 위치를 오른쪽으로 한 칸 옮긴다.
이러면 삭제 또한 $O(1)$의 시간이 소요되지만, 삭제된 데이터에 대한 메모리는 삭제되지 않으므로 메모리가 낭비된다.
큐가 꽉차면 확장해야 되는데, 해당 과정에서 삭제 연산이 많이 이루어졌을 경우 실제 사용하는 데이터는 적은데
메모리는 다 쓴 최악의 상황이 발생한다. 이런 경우는 어떻게 해야할까?
이를 해결하기 위해 고안된 방법이 원형 큐(Circular queue)이다. 우리는 구현도 해당 방법으로 할 것이다.
큐의 구현(3) : 원형 큐(Circular queue)를 사용하는 방법
원형 큐는 말 그대로 큐 자체를 평행한 배열이 아니라, 끝과 시작을 원형으로 붙여놓은 형태이다.
원형 큐도 동일하게 front와 rear가 존재하지만, 모두 포인터 느낌으로 가리키는 위치가 변하며, 특히 front가 다르다.
원형 큐에서의 front는, 실제 맨 앞의 값보다 한 칸 반시계 방향의 위치를 가리키는 값을 가진다.
그 이유는 이후 원형 큐의 연산 구현을 보면 알 수 있을 것이다. rear는 이전과 동일하다.
그림으로 연산에 대해 대강 살펴보면 다음과 같다. 보면 초기의 front와 rear는 동일하지만,
새로운 데이터가 0번 인덱스가 아닌 1번 인덱스에 들어감으로써, 앞에서 말한 front의 규칙이 유지되고 있다.
데이터를 지울 때는 front 포인터가 한 칸 이동하면서, 해당 데이터가 빠지는 모습이다.
이제 그 구현을 살펴보자. 이때 미리 정해두어야 할 중요한 값들이 있다.
원형 큐의 크기를 capacity라고 한다면, capacity - 1의 다음 칸은 0번이고, 0번의 이전 칸은 capacity - 1번 칸이다.
이렇게 이어주면 원형 모양이라고 생각할 수 있는 것이다. 그럼 해당 논리적 연결을 어떻게 해줄 수 있을까?
바로 모듈러 연산이다. % 를 이용해 나머지를 구하며 진행하면 자연스럽게 이어줄 수 있다.
template <class T>
class Queue {
private :
T* queue; // T타입 배열
int capacity; // 큐의 사이즈
int front, rear; // 큐의 시작포인트와 끝포인트
public :
Queue(int firstcap = 10001);
bool isEmpty() const;
T& Front() const;
T& Rear() const;
void push(const T& item);
void pop();
};
template <class T>
Queue<T> ::Queue(int firstcap) : capacity(firstcap) {
queue = new T[capacity];
front = 0; // front가 0이면 첫 인덱스는 1에 들어가면 됨
rear = 0;
}
원형 큐 클래스의 대략적인 틀은 다음과 같다. 사실 가장 중요한건 push와 pop이니, 그 부분에 대해서 더 이야기해보자.
앞서 스택에 데이터를 넣을때는 ++top 과 같은 명령어를 사용해서 인덱스를 바꿔주었다. 그러나 원형 큐에서는
rear == capacity - 1인 경우 이야기가 다르다. 다음 칸이 0번 칸으로 가야하는데, 이때 모듈러 연산을 사용해야한다.
그럼 rear = (rear+1)%capacity 로 지정해 줄 경우, 자연스럽게 0번 칸으로 갈 수 있게 된다. 이 식을 잘 기억하자.
이 식을 활용해 큐의 front 값을 반환해주는 front 함수를 구현해보면 다음과 같다.
template <class T>
int Queue<T>::Front() const {
if(isEmpty()) {
return -1;
}
else return queue[(front+1)%capacity];
나머지 연산자를 쓰지 않으면, 배열의 크기가 막 늘어나게 되어 메모리가 부족해질 수도 있다.
원형 큐의 경우는 front == rear 일 때 큐가 비어있다고 생각할 수 있다. 그러나 한 가지 예외가 존재한다.
바로 큐가 꽉 찼을 경우에도 front == rear 라는 것이다. front는 처음 인덱스의 반시계 한 칸 앞, rear는 그대로 끝 위치이니
큐가 꽉 찬 경우 front와 rear 모두 맨 마지막 요소를 가리키고 있다.
따라서 원형 큐를 사용하는 경우, 최대 가질 수 있는 요소 개수를 capacity - 1 로 설정해 예외처리 해주는 것이 중요하다.
원형 큐의 구현 - Push와 Pop
이제 가장 중요한 기능인 push와 pop 함수의 구현에 대해 알아보자.
우선, push 에는 스택에서 구현한 것처럼 꽉 찰 경우 크기를 늘려주는 부분이 필요하다.
여기서는 front == (rear+1)%capacity 인 경우가 하나라도 더 들어가면 꽉차므로 늘려주는 경우가 된다.
그러나 이때 front과 rear의 위치가 딱 떨어지는 상태가 아니라, front = 5, rear = 4와 같은 경우면,
크기를 두 배로 늘렸을 경우 위치가 다시 꼬이게 되어 위치를 다시 맞추어 주어야 한다. 진행 순서는 다음과 같다.
- 먼저 기존의 큐보다 capacity가 두 배 큰 newQueue 배열을 생성한다.
- front를 기준으로 queue[front+1] ~ queue[capacity-1]의 값을 먼저 복사해 newQueue에 0번 인덱스부터 삽입한다.
- 나머지 값, queue[0] ~ queue[rear] 까지의 값을 그 뒤에 붙여넣는다.
template <class T>
void Queue<T>::push(const T& item) {
if((rear+1)%capacity == front) { // 꽉 찬 경우
T* newQueue = new T(2*capacity); // 새로운 배열 생성
if((front+1)%capacity < 2) { // 어디부터 복사해 옮길지 정하는 과정
copy(queue+(front+1)%capacity, queue+(front+1)%capacity+capacity-1, newQueue );
}
else {
copy(queue+(front+1)%capacity, queue+(front+1)%capacity+capacity-1, newQueue );
copy(queue, queue+rear, newQueue+capacity);
}
front = 2 * capacity - 1;
rear = capacity -2;
capacity *= 2;
delete[] queue;
queue = newQueue;
}
rear = (rear+1)%capacity; // 원래대로 데이터 삽입
queue[rear] = item;
count ++;
}
이런 식으로 Push 함수를 구현해줄 수 있다. 스택보다는 복잡하니 한 번 꼼꼼히 분석해보길 바란다.
다행히도 Pop 함수는 Push 보다는 훨 간단하게 구현된다. 크기를 고려할 필요가 없어서 그렇다. 시간은 $O(1)$ 이다.
template <class T>
void Queue<T>::pop() {
if(isEmpty()) {
cout << -1 << '\n';
}
else {
cout << queue[(front+1)%capacity] << '\n';
front = (front+1)%capacity; // front를 한칸 앞으로 이동
queue[front].~T(); // 그 칸의 인덱스를 파괴, 즉 자연스레 프론트 한 칸 앞에 첫 인덱스가 위치
count--;
}
}
그런데, 정말로 원형 큐의 모든 인덱스를 다 사용하는 방법은 존재하지 않는 것일까?
사실 존재하긴 한다. 새로운 변수 하나를 추가해 사용하면 되는데, 바로 직전에 수행된 연산이 무엇인지 저장하면 된다.
lastOp 라는 변수를 추가해, 직전 연산이 삽입이면 push, 삭제면 pop을 저장하게끔 한다.
그리고 front == rear가 되었을 때, 직전 연산이 삽입이었다면 꽉 찬 것이고, 삭제라면 빈 상태임을 알 수 있다.
대신 기존의 삭제와 삽입 연산이 조금씩 느려진다는 단점이 있어 잘 사용하지 않는다.
첫 번째 포스트는 여기서 마무리 하겠다. 사실 스택과 큐를 다 다루었으니 알아볼게 없는거 아니냐? 할 수 있지만,
같이 나오는 개념인 상속과, 스택과 큐를 사용한 예제( 미로 문제, 전위, 후위 표현법 등 )를 다룰 예정이다.
지금은 스택과 큐 그 자체에 대해 이해하는 시간이라고 생각하면 될 것 같다.
그럼 다음 포스트에서 뵙도록 하겠다!
'학부 CS > 자료구조' 카테고리의 다른 글
| 자료구조(6) : 연결 리스트(2, 完) - 연결 리스트의 활용, 동치류, 이중 연결 리스트 (0) | 2025.03.01 |
|---|---|
| 자료구조(5) : 연결 리스트(1) - 연결 리스트, 반복자(Iterators), 자유 공간 리스트 (0) | 2025.02.27 |
| 자료구조(4) : 스택과 큐(2, 完) - 서브타입과 상속, 미로 문제, 수식 표기법 (0) | 2025.02.25 |
| 자료구조(2) : 배열(2, 完) - 희소 행렬, 문자열 (0) | 2025.02.22 |
| 자료구조(1) : 배열(1) - ADT와 다항식, 고차원 배열 (0) | 2025.02.17 |