[자료구조] Generic 프로그래밍과 C++ Template

Function Template

• 두 값을 비교하여 -1, 0, 혹은 1을 반환하는 함수가 필요하다고 가정
• 단, 정수, 실수, string 등의 서로 다른 타입에 대해서 이런 일을 하는 함수가 필요
• 그렇다면 각 타입에 대해 별개의 함수를 만들어야 함
• 이 세 함수들은 완벽하게 동일한 로직이지만 데이터의 타입이 다르므로 별개로 구성해야 함

int compare(string &v1, string &v2) {
if (v1 < v2) return -1;
if (v2 < v1) return 1;
return 0;
}

int compare(double &v1, double &v2) {
if (v1 < v2) return -1;
if (v2 < v1) return 1;
return 0;
}

int compare(int &v1, int &v2) {
if (v1 < v2) return -1;
if (v2 < v1) return 1;
return 0;
}

 

Function Template

• 함수 탬플럿은 하나 혹은 그 이상의 타입명을 매개변수로 하여 작성된 함수를 말합니다.
• 매개변수 타입은 실제로 이 함수를 호출할 때 결정되고
• 그때 컴파일러에 의해 실제 함수가 생성됩니다.

template <typename T>
int compare(T &v1, T &v2)
{
	if (v1 < v2) return -1;
	if (v2 < v1) return 1;
	return 0;
}

 

 

Bubble Sort

#include <iostream>
using namespace std;

template <typename T>
void bubbleSort(T a[], int n) {
    for (int i=n-1; i>0; i--)
        for (int j=0; j<i; j++)
            if (a[j] > a[j+1])
                swap(a[j], a[j+1]);
}

int main() {
    string s[5] = {"how", "fun", "is", "c++", "programming"};
    int a[5] = {10, 50, 30, 40, 20};
    int n = sizeof(a)/sizeof(a[0]);

    bubbleSort<int>(a, n);
    bubbleSort<string>(s, n);

    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;

    for (int i = 0; i < n; i++)
        cout << s[i] << " ";
    cout << endl;

    return 0;
}

 

Class Template

template<typename T> 
class MyArray {
private:
    T* ptr;
    int size;

public:
    MyArray(T arr[], int s) {
        ptr = new T[s];
        size = s;
        for (int i=0; i<size; i++)
            ptr[i] = arr[i];
    }

    void print() {
        for (int i=0; i<size; i++)
            cout << " " << *(ptr+i);
        cout << endl;
    }
};

int main() {
    int arr[5] = { 1, 2, 3, 4, 5 };
    MyArray<int> a(arr, 5);
    a.print();
    return 0;
}

 

Generic Programming

• 자료형에 의존하지 않는 알고리즘과 자료구조를 작성하는 프로그래밍 패러다임
• 재사용성을 높이고 유지보수성 향상시킴
• 적절히 사용하면 다양한 데이터타입 유용하게 작성 가능
• C++ STL은 다양한 컨테이너들을 구현하는 Class template구현

스택을 클래스 템플릿으로 구현

데이터 타입을 미리 지정하지 않고 사용시에 결정하는 스택 구현

 

const int MAX_CAPACITY = 100;

template<typename T> 
class ArrayStack {

private:
    T stack[MAX_CAPACITY];
    int top_pos = -1;

public:
    bool full() {
        return top_pos == MAX_CAPACITY - 1;
    }

    bool empty() {
        return top_pos == -1;
    }

    void push(T c) {
        if (full())
            throw runtime_error("stack_full");
        stack[++top_pos] = c;
    }
    void pop() {
    if (empty())
        throw runtime_error("stack_empty");
    top_pos--;
    }

    T top() {
        if (empty())
            throw runtime_error("stack_empty");
        return stack[top_pos];
    }
};

int main() {
    ArrayStack<string> s1;
    s1.push("hello");

    ArrayStack<int> s2;
    s2.push(100);

    cout << s1.top() << ' ' << s2.top() << endl;
}

 

 

 

template<typename S> 
class Node {
    template<typename T> 
    friend class LinkedStack;

private:
    S data;
    Node *next;
    
    Node() {}
    Node(S c, Node *p): data(c), next(p) {}
};

template<typename T> 
class LinkedStack {
private:
    Node<T> *head = nullptr;

public:
    bool full() {
        return false;
    }

    bool empty() {
        return head == nullptr;
    }

    void push(T c) {
        head = new Node<T>(c, head);
    }
    void pop() {
    if (empty())
        throw runtime_error("stack_empty");
    Node<T> *tmp = head;
    head = head->next;
    delete tmp;
    }

    T top() {
        if (empty())
            throw runtime_error("stack_empty");
        return head->data;
    }
};

int main() {
    LinkedStack<string> s1;
    LinkedStack<int> s2;

    s1.push("hello");
    s2.push(100);

    cout << s1.top() << ' ' << s2.top() << endl;
}