C++ 언어 기초 (14) - 템플릿 template (Feat. 버블정렬)

▣ Container class & template

 ●  Container Class 컨테이너 클래스

  ▷ 객체를 저장하는 클래스로 아래와 같이 다양한 형태의 데이터를 저장한다.

• array 배열
• queue 큐
• stack 스택
• list 리스트

 ●  Container Class의 예시 (템플릿의 필요성)

  ▷int형 데이터를 저장하는 stack 클래스 - Stack.h

typedef int STACK_ITEM;
class Stack {
    enum { MAXSTACK = 20 };
    int top;
    STACK_ITEM item[MAXSTACK];
public:
    Stack();
    bool empty();
    void initialize();
    void push(STACK_ITEM s);
    STACK_ITEM pop();
};

• typedef int STACK_ITEM; 을 통해 STACK_ITEM 자료형을 int로 설정하여, 후에 stack의 자료형을 다른 걸로 바꿀 때 이 구문만 바꿔주면 되기 때문에 수정에 용이하다.

 

• 예를 들어서, stack의 자료형을 float으로 바꾸면 아래와 같이 바꿀 수 있다.

  ▷float형 데이터를 저장하는 stack 클래스

typedef float STACK_ITEM;
class Stack {
    enum { MAXSTACK = 20 };
    int top;
    STACK_ITEM item[MAXSTACK];
public:
    Stack();
    bool empty();
    void initialize();
    void push(STACK_ITEM s);
    STACK_ITEM pop();
};

 

  ▷ int형 stack과 float형 stack을 모두 만들고 싶을 때

• 두 가지 자료형에 대해 클래스를 각각 선언해줘야 한다. 멤버함수도 자료형에 따라 각각 다르게 선언해줘야 한다.

typedef int INT_ITEM;
class StackInt {
    enum { MAXSTACK = 20 };
    int top;
    INT_ITEM item[MAXSTACK];
public:
    Stack();
    bool empty();
    void initialize();
    void push(INT_ITEM s);
    INT_ITEM pop();
    ...
};

typedef float FLOAT_ITEM;
class StackFloat {
    enum { MAXSTACK = 20 };
    int top;
    FLOAT_ITEM item[MAXSTACK];
public:
    Stack();
    bool empty();
    void initialize();
    void push(FLOAT_ITEM s);
    FLOAT_ITEM pop();
};

• 하지만 이런 경우에 불필요하게 동일한 코드가 반복되기 때문에 효율성이 떨어진다.
• 정해진 틀을 만들어놓는 generic programming 일반화 프로그래밍이 필요하다.

 

 ●  Template 템플릿

  ▷ Template의 정의

• 클래스/함수 등을 선언하기 위한 기본이 되는 형식
• 특정 자료형이 아니라 일반 자료형을 대상으로 선언한다. (generic programming 일반화 프로그래밍)
  
• 자료형, 상수 등을 매개변수로 하여 템플릿에 전달하면 이것을 따라서 클래스/함수가 자동 선언된다.
• 여러 대상을 위한 클래스/함수를 템플릿으로 선언해서, 동일한 코드 반복을 예방한다.

  ▷ Template 종류

• Class Template
• Function Template

 

▣ Class Template

 ●  Class Template 클래스 템플릿

  ▷ 클래스 템플릿 선언 형식

template <templateParameters>
class ClassTemplateName {
  ...
};

// templateParameters: 템플릿 매개변수 목록 (예시) class A, typename A
// ClassTemplateName: 클래스 템플릿 이름

 

  ▷ 예시 - Stack 클래스 템플릿 선언- Stack.h

template <typename T>
class Stack {
    T *buf;    //data를 저장하는 저장공간인 buffer를 가리키는 포인터  
    int top;    // stack top
    int size;   // stack size
public:
    Stack(int s);    // constructor
    virtual ~Stack();   //destructor
    bool full() const;
    bool empty() const;
    void push(const T& a);  //값이 l-value일 때 stack에 저장하게 해줌
    void push(T&& a);   //값이 r-value일때 저장하게 해줌
    T&& pop();    //pop으로 꺼낸 값을 가져갈 수 있도록 설정
};

 

  ▷ 템플릿 선언문 외부에서 멤버함수 선언할 때 형식

template <templateParameters>
ReturnType ClassTemplateName<args>::funcName(fParameterList)
{
	...
}

//ReturnType: 멤버함수의 반환 자료형
//funcName: 멤버함수 이름
//args: templateParameters의 매개변수
//fParameterList: 멤버함수의 형식 매개변수 목록

 

  ▷  예시 - Stack 클래스 템플릿 선언- Stack.h

 

template <typename T> Stack<T>::Stack(int s) : size(s), top(s)
{
    buf = new T[s];
}

template <typename T> Stack<T>:: ~Stack()
{
    delete[] buf;
}

template <typename T> bool Stack<T>::full() const
{
    return !top;
}

template <typename T> bool Stack<T>::empty() const
{
    return top == size;
}

template <typename T> void Stack<T>::push(const T& a) 
{
    buf[--top] = a;      // 대입연산자 필요
}

template <typename T> void Stack<T>::push(T&& a)
{
    buf[--top] = move(a);   //이동대입연산자, move로 r-value값을 받고 buf로 값 이동
}

template <typename T> T&& Stack<T>::pop()   //r-value 참조 return! --> 필요하면 값을 가져갈 수 있게 설정
{
    return move(buf[top++]);
}

 

 ●  클래스 템플릿 객체 정의

  ▷ 클래스 템플릿 객체 정의 형식

ClassTemplateName<ClassName> objName(constrArgs);

// ClassName: 템플릿 매개변수에 전달할 클래스/자료형 이름 등 템플릿 인수
// objName: 정의할 객체 이름
// constrArgs: 생성자에 전달할 인수

 

  ▷ 예시1 - char을 저장하는 stack 활용 - Main.cpp

• 아까 template <typename T> class Stack에서 모든 T 자리에 char가 들어간다.

#include "Stack.h"
using namespace std;

int main()
{
    Stack<char> sc(100);   //char stack 생성
    sc.push('Y');
    sc.push('M');
    sc.push('R');
    sc.push('A');
    cout << "문자 STACK : ";
    while (!sc.empty())
        cout << sc.pop();
    cout << endl;
    return 0;
}

출력결과

 

  ▷ 예시2 - int를 저장하는 stack 활용 - Main.cpp

• template <typename T> class Stack에서 모든 T 자리에 char가 들어간다.

#include "Stack.h"
using namespace std;

int main()
{
    Stack<int> si(50);
    si.push(13);
    si.push(6);
    cout << "정수형 STACK : ";
    while (!si.empty())
        cout << si.pop();
    cout << endl;
    return 0;
}

출력결과

 

  ▷ 예제3 - MyString을 저장하는 stack 활용 - Main.cpp

• MyString 객체를 10개 저장할 수 있도록 했다. MyString 클래스 코드는 아래 글에서 얻을 수 있다.

2020/09/03 - [Programming/C++] - C++ 언어 기초 (10) - 연산자 다중정의 II

• template <typename T>에서 T에 MyString이 들어간다.

#include "Stack.h"
#include "MyString.h"
using namespace std;

int main()
{
    Stack<MyString> msStack(10);
    MyString s1("BTS");
    MyString s2("from");
    MyString s3("Bighit");
    msStack.push(s1);
    msStack.push(s2+s3);    //연결 연산자, r-value -> void push(T&& a); 동작
    cout << "MyString STACK : ";
    while (!msStack.empty())
        cout << msStack.pop() << " ";
    cout << endl;
    return 0;
}

• 위의 여러 자료형 stack을 한 코드에서 여러 개 정의해도 무방하다.

출력결과

 

 

 ●  클래스 템플릿 객체 관련한 주의점

  ▷ 사용자가 선언한 클래스의 객체를 저장하는 컨테이너

• 기본 자료형 외에 사용자 정의 클래스 객체를 저장하기 위해 컨테이너 클래스 템플릿을 사용할 수 있다.
• ㄴ-> 예시: MyString 객체를 저장하기 위한 스택
• 이 경우 클래스 템플릿에서 필요로 하는 멤버함수가 대상 클래스에 포함되어 있어야 한다.
• ㄴ-> 클래스 템플릿 Stack에 저장할 객체에는 default 생성자, 대입 연산자, 이동 대입 연산자 등이 필요하다.
• 아래 예로 다시 확인해보자.

class Person {
    string name
public:
    Person(const string& n) : name(n) {}
    void print() const {
        cout << name;
    }
};

int main() {
    Stack<Person> pStack(10); // 오류발생!!!!
    ...
}

위의 코드를 실행시키면 오류가 발생한다. 왜냐하면 템플릿 클래스로부터 아래 명령을 실행하여 버퍼에 새로운 메모리를 할당해줘야 하고 이를 위해서는 default 생성자가 필요한데, Person 클래스에서는 다른 형식의 생성자가 이미 존재해서 default 생성자가 정의되지 않았기 때문이다. 

template <typename T>
Stack<T>::Stack(int s) : size(s), top(s)
{
    buf = new T[s];
}

 

 ●  비자료형 템플릿 매개변수

  ▷ 템플릿 매개변수를 통해 전달할 수 있는 인수

• 자료형 매개변수 : 기본자료형(int, char, double, ...), 클래스, 구조체(struct) 등
• 비자료형 매개변수 
  
  1) 정수형 자료형 상수식 (int형 자료형 상수식, double형 상수식은 안됨)
  2) 객체나 함수에 대한 포인터
  3) 객체나 함수에 대한 l-value 참조
  4) 멤버에 대한 포인터 등
  
• 예시

template <typename T, int size> class Buffer {  //int size로 정수형 상수식을 매개변수로 전달.->가능
    T buf[size];
    ..
};

void f()
{
    Buffer<char, 256> buf1;    //크char형 객체 128개 저장하는 버퍼 선언
    Buffer<Complex, 30> buf2;  //Complex 객체 20개 저장하는 버퍼 선언
    int n = 50;
    Buffer<char, n> buf3;    //오류! 정수형 상수식이 아니기 때문에 오류가 발생! double형인 0.4이런것도 안됨.
    ..
}

++) Buffer<char, 128>과 Buffer<char, 256>은 서로 다른 자료형이 된다.

 

▣ Function Template

 ●  Function Template 함수 템플릿 선언

  ▷ 함수 템플릿 선언 형식

template <templateParameters>
ReturnType funcName(fParameterList) {
 	..
}

//templateParameters: 템플릿 매개변수 선언
//funcName: 함수 템플릿 이름

 

 ●  함수 템플릿 활용 예시 (1) - swapFT

   값을 교환하는 함수인 swapFT를 만들어보자.

  ▷ 함수 템플릿 선언 - SwapFT.h

#ifndef SWAP_FUNCTION_TEMPLATE_H_INCLUDED
#define SWAP_FUNCTION_TEMPLATE_H_INCLUDED
#include <utility>
using namespace std;
template <typename ANY>
void swapFT(ANY &a, ANY &b)
{
    ANY temp = move(a);   //이동 대입 연산자 이용
    a = move(b);
    b = move(temp);
}
#endif

++ 참고: ((동적 메모리 할당으로 대규모 데이터를 이동할 땐 이동 대입 연산자를 이용하는 것이 좋다. 이동 대입 연산자가 정의되어 있지 않으면 default 대입 연산자가 동작할 것이다.))

 

  ▷ 함수 템플릿 이용 1 - SwapFTMain.cpp

#include <iostream>
#include "SwapFT.h"
#include "MyString.h"
using namespace std;

int main()
{
    int x = 10, y = 20;
    cout << "x = " << x << ", y = " << y << endl;
    swapFT(x,y);
    cout << " After swap --> ";
    cout << "x = " << x << ", y = " << y << endl;
    
    MyString s1("BTS"), s2("ARMY");
    cout << "s1 = " << s1 << ", s2 = " << s2 << endl;
    swapFT(s1, s2);
    cout << " After swap --> ";
    cout << "s1 = " << s1 << ", s2 = " << s2 << endl;
    return 0;
}

• swapFT(x, y);에서 x, y가 int형이므로 ANY가 int형이 된다. 
• swapFT(s1, s2);에서 s1, s2가 MyString 객체이므로 ANY가 MyString이 된다. 

출력결과

 

 ●  함수 템플릿 활용 예시 (2) - sortFT

  ▷ 버블 정렬

• 배열의 맨앞에서 시작해서 차례대로 인접한 두 값을 비교하면서 앞의 값이 크면 값을 교환하는 것을 반복하며 오름차순으로 정렬한다.
• 배열의 맨끝에 무조건 가장 큰 수가 위치하게 되므로 그 수를 고정해놓고 앞에 수들을 대상으로 다시 정렬한다.
• 이 과정을 반복해서 오름차순 정렬을 완료한다.
• doAgain 함수를 둬서 한 번이라도 교환이 일어나면 true로 설정하고, 교환이 일어나지 않으면 false로 설정한다.

 

  ▷ 함수 템플릿 선언 - SortFT.h

#include "SwapFT.h"

// bubble sort algorithm
template <typename T> void sortFT(T arr[], int size)
{
    bool doAgain = true;
    for (int i = 1; doAgain; i++) {
        doAgain = false;
        for (int j = 0; j < size - i; j++)
            if (arr[j] > arr[j + 1])
                swapFT(arr[j], arr[j + 1]), doAgain = true;
    }
}

 

  ▷ 함수 템플릿 이용 - Main.cpp

#include <iostream>
#include "SortFT.h"
#include "MyString.h"
using namespace std;

int main()
{
    int x[10] = { 4, 3, 6, 9, 7, 1, 0, 10, 5, 2};
    sortFT(x, 10);
    for (auto i : x)
        cout << i << " ";
    cout << endl;
    
    MyString s[5] = { "jkl", "mno", "def", "abc", "ghi"};
    sortFT(s, 5);
    for (auto str : s)
        cout << str << " ";
    cout << endl;
    return 0;
}

출력결과