등딱지빌런

등딱지빌런

안녕하세요. 정인호입니다.

Template

Date:     Updated:

카테고리:

태그:

모두의 코드 씹어먹는 C++ 자료를 보고 정리한 내용입니다.


C++ Class Template

Template : 형판, 틀

: 프로그래머가 원하는 타입을 넣어주면 딱딱 알아서 코드를 찍어내는 틀. 단, 템플릿의 타입은 컴파일 타임에 결정되어야 함

template <typename T>
class Vector {
	T* data;
	int capacity;
	// ...
}

Vector<int> int_vec;

template <typename T> : 클래스(함수)에 대해 템플릿을 정의하고, 템플릿 인자로 타입의 이름 T를 받음

위와 같이 클래스 템플릿에 인자를 전달해서 실제 코드를 생성하는 것을 클래스 템플릿 인스턴스화(Class Template Instantiation) 라고 한다. 템플릿이 인스턴스화 되지 않고 덩그러니 있다면 컴파일 시에 아무런 코드로 변환되지 않는다. 템플릿은 반드시 인스턴스화 되어야지만 비로소 컴파일러가 실제 코드를 생성하게 되고, 이때 타입이 조금이라도 다르면 완전히 다른 종류의 클래스로 인식하게 된다.

참고로, 간혹 template <class T> 라고 쓰는 경우도 있는데 이는 typename T 와 동일하며 T 자리에 꼭 클래스가 와야 하는 것도 아니다. 되도록이면 typename 키워드를 사용하는 것을 권장하며 class 키워드의 존재 이유는 c++의 역사와 관련이 있다.

c++을 처음 만들 때 template의 인자로 class키워드를 사용했는데, 굳이 새로운 키워드를 만들고 싶지 않아서 였기 때문이다. 하지만 시간이 흐르고 c++ 위원회는 이로 인한 혼동을 막기 위해(왜냐하면 class T 라 하면 T 자리에 꼭 클래스만 와야 하는 것 처럼 느껴지니까) typename이라는 이름을 사용하기로 했다. 물론, 이전 코드와의 호환을 위해 class 도 그대로 남겨 놓았다.

Template Specialization

template <typename A, typename B, typename C>
class test {};

위와 같은 클래스 템플릿이 정의되어 있을 때 A가 int고, C가 double 인 경우를 따로 처리하고 싶다면 아래와 같은 템플릿 클래스를 추가해주면 된다.

template <typename B>
class test<int, B, double> {};

만약 B 조차도 특수화 하고 싶다면,

template <>
class test<int, int, double> {};

한 가지 중효한 점은, 템플릿 특수화의 경우 전달하는 템플릿 인자가 없더라도 template<> 을 명시해줘야 한다.

템플릿을 사용 시 상황에 따라 특정 타입에 대해서는 다른 방식으로 처리해야 하는 경우가 있다. 예를 들어 bool 데이터를 보관하는 벡터의 경우 문제가 하나 있는데, c++에서 기본적으로 데이터를 처리하는 단위가 1 byte 라는 점이다. 사실 bool 데이터 형은 1개 비트 만으로도 데이터를 저장할 수 있기 때문에 8 비트를 사용해서 1개의 bool 데이터를 저장하면 엄청난 메모리 낭비가 아닐 수 없다. 따라서 Vector<bool> 에 대해서는 특별히 따로 처리해줘야 한다.

template <>
class Vector<bool> {
	// ...
}

Vector<bool> 을 구현하기 위해 unsigned int 배열을 이용할 것이다 (int의 경우 비트 연산 시 귀찮은 예외 처리가 필요함). 1개의 unsigned int는 4바이트 이므로, 32개의 bool 데이터를 묶어서 저장할 수 있다. 이러한 방식으로 데이터를 저장하면 메모리 관리 측면에서는 매우 효율적이지만 구현이 조금 복잡해진다. 예를 들어 N번 째 bool 데이터는 N / 32 번 째 unsigned int에 들어가 있고, 그 안에서 정확히 N % 32 번 째 비트에 저장되어 있다.

tem1

template <>
class Vector<bool> {
  unsigned int* data;
  int capacity;
  int length;

 public:
  typedef bool value_type;

  // 생성자
  Vector(int n = 1)
      : data(new unsigned int[n / 32 + 1]), capacity(n / 32 + 1), length(0) {
    for (int i = 0; i < capacity; i++) {
      data[i] = 0;
    }
  }

  // 맨 뒤에 새로운 원소를 추가한다.
  void push_back(bool s) {
    if (capacity * 32 <= length) {
      unsigned int* temp = new unsigned int[capacity * 2];
      for (int i = 0; i < capacity; i++) {
        temp[i] = data[i];
      }
      for (int i = capacity; i < 2 * capacity; i++) {
        temp[i] = 0;
      }

      delete[] data;
      data = temp;
      capacity *= 2;
    }

    if (s) {
      data[length / 32] |= (1 << (length % 32));
    }

    length++;
  }

  // 임의의 위치의 원소에 접근한다.
  bool operator[](int i) { return (data[i / 32] & (1 << (i % 32))) != 0; }

  // x 번째 위치한 원소를 제거한다.
  void remove(int x) {
    for (int i = x + 1; i < length; i++) {
      int prev = i - 1;
      int curr = i;

      // 만일 curr 위치에 있는 비트가 1 이라면
      // prev 위치에 있는 비트를 1 로 만든다.
      if (data[curr / 32] & (1 << (curr % 32))) {
        data[prev / 32] |= (1 << (prev % 32));
      }
      // 아니면 prev 위치에 있는 비트를 0 으로 지운다.
      else {
        unsigned int all_ones_except_prev = 0xFFFFFFFF;
        all_ones_except_prev ^= (1 << (prev % 32));
        data[prev / 32] &= all_ones_except_prev;
      }
    }
    length--;
  }

  // 현재 벡터의 크기를 구한다.
  int size() { return length; }
  ~Vector() {
    if (data) {
      delete[] data;
    }
  }
};

void push_back(bool s) {
	// ...
	
	if (s) {
	  data[length / 32] |= (1 << (length % 32));
	}
	length++;
}

tem2

  • 만약 ture가 추가되었을 때 해당 비트를 true로 변환
  • shift 연산으로 해당 위치를 true로 만든 후
  • OR 연산을 통해 해당 비트 true로 변환
// 임의의 위치의 원소에 접근한다.
bool operator[](int i) { return (data[i / 32] & (1 << (i % 32))) != 0; }

tem3

  • 거꾸로 AND 연산을 통해 해당 위치의 비트를 가져올 수 있음
// x 번째 위치한 원소를 제거한다.
void remove(int x) {
  for (int i = x + 1; i < length; i++) {
    int prev = i - 1;
    int curr = i;

    // 만일 curr 위치에 있는 비트가 1 이라면(0이 아니라면)
    // prev 위치에 있는 비트를 1 로 만든다.
    if (data[curr / 32] & (1 << (curr % 32))) {
      data[prev / 32] |= (1 << (prev % 32));
    }
    // 아니면 prev 위치에 있는 비트를 0 으로 지운다.
    else {
      unsigned int all_ones_except_prev = 0xFFFFFFFF;
      all_ones_except_prev ^= (1 << (prev % 32));
      data[prev / 32] &= all_ones_except_prev;
    }
  }
  length--;
}

참고 : (1 « cur) 이 (1 « prev) 보다 왼쪽에 존재함!

  • 특정 비트를 1로 만드는 것은 OR 연산을 이용해 간단하게 구현
  • 문제는 0으로 바꾸는 작업
    • 특정 위치만 0으로 끄고 (ex. 11110111)
    • AND 연산 하면 OK
  • 특정 위치를 0으로 끄는 방법 → 11111111 과 00001000 의 XOR 연산!

Function Template

template <typename T>
T max(T& a, T& b) {
  return a > b ? a : b;
}

int main() {
  int a = 1, b = 2;
  std::cout << "Max (" << a << "," << b << ") ? : " << max(a, b) << std::endl;

  std::string s = "hello", t = "world";
  std::cout << "Max (" << s << "," << t << ") ? : " << max(s, t) << std::endl;
}

템플릿 함수 역시 클래스 템플릿과 마찬가지로, 인스턴스화 되기 전 까지는 컴파일 시에 아무런 코드로 변횐되지 않는다. 신기하게도 클래스를 인스턴스화 했을 때와는 다르게 <> 부분이 없고, c++ 컴파일러가 알아서 인스턴스화 해준다.

template <typename Cont>
void bubble_sort(Cont& cont) {
  for (int i = 0; i < cont.size(); i++) {
    for (int j = i + 1; j < cont.size(); j++) {
      if (cont[i] > cont[j]) {
        cont.swap(i, j);
      }
    }
  }
}

위 함수는 임의의 컨테이너를 받아서 이를 정렬해 주는 함수이다. 물론 이 함수가 정상적으로 작동하려면 size(), swap() 함수, [] 연산자가 정의되어 있어야 한다. 만약 그렇지 않다면 컴파일 에러가 발생한다. 그런데 위 bubble_sort 함수에서 정렬 순서를 반대로 하고 싶다면 어떤 방법이 있을까?

  • 1) bubble_sort2 를 만들어 부등호 방향을 반대로 바꾼다 → C 언어 스타일
  • 2) operator > 를 오버로딩한다 → int, string 처럼 표준 헤더 파일 내부에 정의되어 있어서 힘듬
  • 3) cont[i]와 cont[j]의 비교를 >로 하지 말고 특정 함수에 넣어서 전달한다 → good idea

Function-Pointer

typedef bool(*ITEM_SELECTOR)(Item* item);

Item* FindItem(Item items[], int itemCount, ITEM_SELECTOR* selector)
{
    for (int i = 0; i < itemCount; i++)
    {
        Item* item = &items[i];
        if (selector(item))
            return item;
    }

    return nullptr;
}

bool IsRareItem(Item* item)
{
    return item->_rarity >= 2;
}

int main()
{
    Item items[10] = {};
    Item* rareItem = FindItem(items, 10, &IsRareItem);

    return 0;
}
  • 함수의 이름은 함수의 시작 주소 (like 배열)
  • C와의 호환성 떄문에 &는 생략 가능 (함수 포인터임을 나타내기 위해 맥락상 쓰는 것이 좋음)
  • 함수 포인터는 *(접근 연산자) 붙어도 여전히 함수 주소
  • 함수 포인터는 [전역 함수 / 정적 함수] 만 담을 수 있음
    • 호출 규약이 동일한 변수(함수)들만 사용 가능
  • 멤버 함수를 사용하고 싶다면? 
    typedef int(Knight :: *PMEMFUNC)(int, int)

함수 포인터의 단점 )

  • 상태를 가질 수 없음
  • 함수 시그니처가 안맞으면 사용 못함

Functor

함수처럼 동작하는 객체 → operator () 오버로딩

class Functor
{
public:
    void operator()()
    {
        cout << _value << endl;
    }

    bool operator()(int num)
    {
        _value += num;
        cout << _value << endl;
    }

private:
    int _value = 0;
};
  • 필요한 상태를 멤버 변수로 들고다닐 수 있음
  • 함수 오버로딩을 통해 시그니처가 달라도 유연하게 대응 가능
  • 컴파일러가 operator() 자체를 인라인화 시켜 매우 강력한 최적화가 가능
  • 아무튼 Functor가 여러모로 좋은 점이 많음

[MMO에서 함수 객체를 사용하는 예시]

  • 클라 ↔ 서버
  • 서버 : 클라가 보내준 네트워크 패킷을 받아서 처리
  • 클라 : 수 많은 유저들이 request 요청
  • 클라의 요청들을 객체(Functor)로 생성해 놓고 스택에 쌓아둔 뒤
  • 하나하나 처리

다시 bubble_sort 함수로 넘어가보면 아래와 같이 Functor를 이용해 구현할 수 있다.

template <typename Cont, typename Comp>
void bubble_sort(Cont& cont, Comp& comp) {
  for (int i = 0; i < cont.size(); i++) {
    for (int j = i + 1; j < cont.size(); j++) {
      if (!comp(cont[i], cont[j])) {
        cont.swap(i, j);
      }
    }
  }
}

struct Comp1 {
  bool operator()(int a, int b) { return a > b; }
};

struct Comp2 {
  bool operator()(int a, int b) { return a < b; }
};

Comp2 comp2;
bubble_sort(int_vec, comp2);

실제로, c++ 표준 라이브러리의 sort 함수는 비교 클래스를 받지 않는

template <class RandomIt>
void sort(RandomIt first, RandomIt last);

버전과, 비교 클래스를 받는

template <class RandomIt, class Compare>
void sort(RandomIt first, RandomIt last, Compare comp);

버전으로 구성되어 있다.

Non-Type Template Arguments

template <typename T, int num>
T add_num(T t) {
  return t + num;
}

한 가지 재미있는 점은 템플릿 인자로 꼭 타입만 받는 것은 아니다. 위 코드의 경우 template의 인자로 T를 받고, 추가적으로 마치 함수의 인자처럼 int num을 또 받고 있다.

add_num<int, 5>(x)

위와 같이 T에 int를, num에 5를 전달하게 되면 컴파일 타임에 생성되는 add_num 코드는 아래와 같다.

int add_num(int t) { return t + 5; }

이때 중요한 점은 템플릿 인자로 전달할 수 있는 타입들이 제한적이라는 것이다.

c++ 20 부터 이 제한들이 좀 더 완화되었다고 한다.

  • 정수 타입들 (bool, char, int, long 등등) . float과 double은 제외.
  • 포인터 타입
  • enum 타입
  • std::nullptr_t (널 포인터)

타입이 아닌 템플릿 인자를 가장 많이 활용하는 예시는 컴파일 타임에 값들이 정해져야 하는 것들 이다. 대표적인 예시로 C에서의 배열은 함수의 인자로 넘어갈 때 크기에 대한 정보를 잃어버린다는 것이다. 하지만 템플릿 인자로 배열의 크기를 명시한다면(어차피 배열의 크기는 컴파일 타임에 정해지는 것이니까), 크기를 포함한 타입을 주고 받을 수 있다. 실제로 c++ 11 부터 제공되는 std::array도 이와 같이 구성되어 있다.

std::array<int, 5> arr = { 1, 2, 3, 4, 5 };

중요한 점은 std::array<int, 5> 자체가 하나의 타입이라는 것이다. 따라서 템플릿을 활용해 생성한 arr은 런타임에 동적으로 메모리가 할당되는 것이 아니라 컴파일 시에 스택에 할당된다. (int arr[5]와 다른 점은 여러 편의 기능들을 포함하고 있다는 것)

Default Template Argument

template <typename T>
struct Compare {
  bool operator()(const T& a, const T& b) const { return a < b; }
};

template <typename T, typename Comp = Compare<T>>
T Min(T a, T b) {
  Comp comp;
  if (comp(a, b)) {
    return a;
  }
  return b;
}

함수에 디폴트 인자를 지정할 수 있는 것처럼 템플릿도 디폴트 인자를 지정할 수 있다.

Variadic Template (가변 길이 템플릿)

template <typename T>
void print(T arg) {
  std::cout << arg << std::endl;
}

template <typename T, typename... Types>
void print(T arg, Types... args) {
  std::cout << arg << ", ";
  print(args...);
}

Python에서의 print 함수는 타입과 갯수에 상관없이 인자로 전달된 모든 내용들을 출력할 수 있다. c++ 역시 템플릿을 활용하여 같은 기능을 구현할 수 있다. 이제 위 코드가 어떻게 작동하는지 살펴보자.

template <typename T, typename... Types>

먼저 위와 같이 typename 뒤에 ...으로 오는 것을 템플릿 파라미터 팩(Parameter pack) 이라고 부른다. 이는 0개 이상의 템플릿 인자들을 나타낸다.

void print(T arg, Types... args)

마찬가지로 함수 인자로 ...로 오는 것을 함수 파라미터 팩 이라고 부르며 0개 이상의 함수 인자를 나타낸다. 템플릿 파라미터의 경우 타입 앞에 ...이 오고, 함수 파라미터의 경우 타입 뒤에 ...이 온다.

함수의 작동은 재귀함수로 돌다가 마지막에는 템플릿 하나, 변수 하나짜리 print 함수를 호출하게 된다. 만약 아래와 같이 두 함수의 순서를 바꾼다면 컴파일 오류가 발생한다.

template <typename T, typename... Types>
void print(T arg, Types... args) {
  std::cout << arg << ", ";
  print(args...);
}

template <typename T>
void print(T arg) {
  std::cout << arg << std::endl;
}

c++ 컴파일러는 함수를 컴파일 할 경우, 자신의 앞에 정의되어 있는 함수들 밖에 보지 못하기 때문이다. 번거롭지만 템플릿 함수를 작성할 때에는 항상 순서에 유의해야 한다.

동적 할당이 필요한 데이터들을 연결할 때에도 가변 길이 템플릿이 유용하게 사용된다. 아래와 같이 std::string 문자열을 합치는 경우를 생각해보자.

concat = s1 + s2 + s3;

위 코드는 실제로 아래와 같이 실행된다.

concat = s1.operator+(s2).operator+(s3);

여기서 문제는 s2를 더할 때 메모리 할당이 발생하고, s3를 더할 때 메모리 할당이 또 한 번 발생한다는 것이다. 합쳐진 문자열의 크기는 미리 알 수 있으니 필요한 메모리를 한 번에 할당해버리는 것이 훨씬 좋다.

size_t GetStringSize(const char* s) { return strlen(s); }

size_t GetStringSize(const std::string& s) { return s.size(); }

template <typename String, typename... Strings>
size_t GetStringSize(const String& s, Strings... strs) {
  return GetStringSize(s) + GetStringSize(strs...);
}

void AppendToString(std::string* concat_str) { return; }

template <typename String, typename... Strings>
void AppendToString(std::string* concat_str, const String& s, Strings... strs) {
  concat_str->append(s);
  AppendToString(concat_str, strs...);
}

template <typename String, typename... Strings>
std::string StrCat(const String& s, Strings... strs) {
  // 먼저 합쳐질 문자열의 총 길이를 구한다.
  size_t total_size = GetStringSize(s, strs...);

  // reserve 를 통해 미리 공간을 할당해 놓는다.
  std::string concat_str;
  concat_str.reserve(total_size);

  concat_str = s;
  AppendToString(&concat_str, strs...);

  return concat_str;
}

sizeof…

가변 길이 템플릿을 사용한 경우 필요에 따라 인자의 갯수가 필요할 수 있다. 예를 들어 인자들의 평균을 구하는 함수가 있다. 일반적으로 사용하는 sizeof 연산자는 인자의 크기를 리턴하지만, 파라미터 팩에 sizeof...을 사용할 경우 전체 인자의 갯수를 리턴한다.

// 재귀 호출 종료를 위한 베이스 케이스
int sum_all() { return 0; }

template <typename... Ints>
int sum_all(int num, Ints... nums) {
  return num + sum_all(nums...);
}

template <typename... Ints>
double average(Ints... nums) {
  return static_cast<double>(sum_all(nums...)) / sizeof...(nums);
}

Fold Expression

c++ 11에서 도입된 가변 길이 템플릿은 매우 편리하지만 한 가지 단점이 존재한다. 함수를 재귀 형태로 구성해야 하기 때문에, 반드시 재귀 호출 종료를 위한 함수(베이스 케이스)를 따로 만들어 주저야 한다는 것이다. 하지만 c++ 17에 새로 도입된 Fold Expression을 사용하면 훨씬 간단하게 표현할 수 있다.

template <typename... Ints>
int sum_all(Ints... nums) {
  return (... + nums);
}

sum_all(1, 4, 2, 3, 10)

return (... + nums);

위 코드는 아래와 같이 컴파일러에서 해석된다.

return ((((1 + 4) + 2) + 3) + 10);

이와 같은 형태를 단항 좌측 Fold (Unary left fold) 라고 부르며 c++ 17에서 지원하는 Fold 방식의 종류는 아래 표와 같이 총 4 가지이다.

ten7

  • I 는 초기값을 의미하며 파라미터 팩이 아니다 
    template <typename Int, typename... Ints>
Int diff_from(Int start, Ints... nums) {
return (start - ... - nums);
}
  • op 자리에는 대부분의 이항 연산자들이 포함될 수 있다
    • +, -, <, <<, , , 등등
  • 중요한 점은 Fold식을 쓸 때 꼭 ()로 감싸줘야 한다는 것
  • return (... + nums);

한 가지 더 재미있는 점은 , 연산자를 사용하면 각각의 인자들에 대해 원하는 식을 실행할 수 있다.

class A {
 public:
  void do_something(int x) const {
    std::cout << "Do something with " << x << std::endl;
  }
};

template <typename T, typename... Ints>
void do_many_things(const T& t, Ints... nums) {
  // 각각의 인자들에 대해 do_something 함수들을 호출한다.
  (t.do_something(nums), ...);
}
int main() {
  A a;
  do_many_things(a, 1, 3, 2, 4);
}

tem8

다음 단원에 배울 내용인데, Template Meta Programming에서는 for문을 사용할 수 없다. 따라서 새로 추가된 fold expression 문법은 굉장히 중요하게 사용될 수 있다.

Template Meta Programming (TMP)

template <typename T, unsigned int N>
class Array {
  T data[N];

 public:
  // 배열을 받는 레퍼런스 arr
  Array(T (&arr)[N]) {
    for (int i = 0; i < N; i++) {
      data[i] = arr[i];
    }
  }

std::cout << typeid(Array<int, 3>) == typeid(Array<int, 5>); // false

앞서 이야기 했듯이 템플릿 인자로는 타입 뿐만이 아니라 특정한 조건을 만족하는 값들도 올 수 있다. 이때 중요한 것은 템플릿 타입 인자가 조금이라도 다른 경우 컴파일러는 각기 다른 코드를 생성하며 다른 클래스 객체를 생성한다는 것이다.

template <int N>
struct Int {
	static const int num = N;
}

위 Int 클래스는 템플릿 인자로 int 값을 받는데, 왜 static const에 값을 저장하는지 생각해보자. 첫 번째로 static 타입 멤버의 특성 상, 이 클래스가 생성한 객체들 사이에서 공유되는 값이기 때문에 “이 타입이면 이 값을 나타낸다” 라고 볼 수 있다. 또한 const이므로 위와 같이 초기화 할수 있고, 그 값이 변하지 않게 된다. 따라서 아래와 같이 마치 객체를 생성하듯 타입들을 생성할 수 있다.

템플릿을 사용하면 객체를 생성하지 않더라도, 타입에 값을 부여할 수 있고, 또 그 타입들을 가지고 연산을 할 수 있다. 이때 타입은 반드시 컴파일 타임에 확정되어야 하므로, 컴파일 타임에 모든 연산이 끝나게 된다. 이렇게 컴파일 타임에 생성되는 코드로 프로그래밍 하는 것을 메타 프로그래밍이라 한다. c++의 경우 템플릿을 가지고 이러한 작업을 하기 때문에 템플릿 메타 프로그래밍, 줄여서 TMP라 한다.

template <int N>
struct Factorial {
  static const int result = N * Factorial<N - 1>::result;
};

template <>
struct Factorial<1> {
  static const int result = 1;
};

int main() {
  std::cout << "6! = 1*2*3*4*5*6 = " << Factorial<6>::result << std::endl; 
}

[!success] 6! = 1x2x3x4x5x6 = 720

한 가지 재미있는 사실은 어떠한 c++코드도 템플릿 메타 프로그래밍 코드로 변환할 수 있다는 점이다(물론 코드가 엄청나게 길어지겠지만). 게다가 템플릿 메타 프로그래밍으로 작성된 코드는 모두 컴파일 타임에 모든 연산이 끝나기 대문에 프로그래밍 실행 속도를 향상시킬 수 있다는 장점이 있다.

하지만 그렇다고 해서 템플릿 메타 프로그래밍으로 프로그램 전체를 구현하는 일은 없다. 일단 템플릿 메타 프로그래밍은 위 Fractoinal 예제외는 달리 매우 복잡하다. 그 뿐만이 아니라, 템플릿 메타 프로그래밍으로 작성된 코드는 버그를 찾는 것이 매우 힘들다. 일단 기본적으로 컴파일 타임에 연산하는 것이기 때문에 디버깅이 불가능하고, c++ 컴파일러 특성 상 템플릿 오류 시에 엄창난 길이의 오류를 내뿜게 된다.

따라서 TMP를 이용하는 경우는 꽤나 제한적이지만, 많은 c++ 라이브러리들이 TMP를 이용해 구현되었고(Boost 라이브러리), TMP를 통해서 컴파일 타임에 여러 오류를 잡아낼 수 있고(Ex. 단위나 통화 일치 여부 등), 속도가 매우 중요한 프로그램의 경우 TMP를 통해 런타임 속도도 향상 시킬 수 있다.



맨 위로 이동하기

Cpp 카테고리 내 다른 글 보러가기

댓글 남기기

최근 글 10 개 :)