z 24. 형식 목록 :: C++, 그래픽 기술 블로그

형식 메타프로그래밍일 경우 핵심이 되는 데이터 구조는 형식 목록으로, 이름에서 알 수 있듯이 형식을 포함하는 목록입니다. 템플릿 메타프로그램은 이런 형식의 목록을 가지고 동작하면서 실행할 수 있는 프로그램의 일부를 만들어내도록 조작할 수 있습니다.

24.1 형식 목록 해부

형식 목록이란 형식들의 목록을 나타내는 형식으로, 템플릿 메타프로그램에 따라 조작할 수 있습니다. 형식 목록은 대개 목록에 관련돼 있는 연산을 제공합니다. 형식 목록은 일반적으로 형식 목록의 내용을 템플릿 인자로 표현한 클래스 템플릿 특수화로 구현됩니다.

template<typename... Elements>
class Typelist
{};

template<typename List>
class FrontT;

template<typename Head, typename... Tail>
class FrontT<Typelist<Head, Tail...>>
{
 public:
  using Type = Head;
};

template<typename List>
using Front = typename FrontT<List>::Type;

template<typename List>
class PopFrontT;

template<typename Head, typename... Tail>
class PopFrontT<Typelist<Head, Tail...>> {
 public:
  using Type = Typelist<Tail...>;
};

template<typename List>
using PopFront = typename PopFrontT<List>::Type;

template<typename List, typename NewElement>
class PushFrontT;

template<typename... Elements, typename NewElement>
class PushFrontT<Typelist<Elements...>, NewElement> {
 public:
  using Type = Typelist<NewElement, Elements...>;
};

template<typename List, typename NewElement>
using PushFront = typename PushFrontT<List, NewElement>::Type;

24.2 형식 목록 알고리즘

기본적인 형식 목록 연산을 조합하면 형식 목록을 조금 더 재밌게 조작할 수 있습니다. 더 나아가 검색, 변형, 역전 등과 같은 알고리즘도 구현 가능합니다. 위에서 PopFront를 통해 첫 번째 요소를 추출하였는데, 이 연산을 일반화시켜 N번째 요소를 추출하는 것도 가능합니다.

// recursive case:
template<typename List, unsigned N> 
class NthElementT : public NthElementT<PopFront<List>, N-1>
{};

// basis case:
template<typename List>
class NthElementT<List, 0> : public FrontT<List>
{};

template<typename List, unsigned N>
using NthElement = typename NthElementT<List, N>::Type;

가장 큰 형식을 찾는 것도 가능합니다.

template<typename List>
class IsEmpty
{
 public:
  static constexpr bool value = false;
};

template<>
class IsEmpty<Typelist<>> {
 public:
  static constexpr bool value = true;
};

template<typename List, bool Empty = IsEmpty<List>::value>
class LargestTypeT;

// recursive case:
template<typename List>
class LargestTypeT<List, false>
{
 private:
  using Contender = Front<List>;
  using Best = typename LargestTypeT<PopFront<List>>::Type;
 public:
  using Type = IfThenElse<(sizeof(Contender) >= sizeof(Best)),
                          Contender, Best>;
};

// basis case:
template<typename List>
class LargestTypeT<List, true>
{
 public:
  using Type = char;
};

template<typename List>
using LargestType = typename LargestTypeT<List>::Type;

다른 목록에 새로운 형식을 붙이는 것도 가능합니다.

template<typename List, typename NewElement, bool = IsEmpty<List>::value>
class PushBackRecT;

// recursive case:
template<typename List, typename NewElement>
class PushBackRecT<List, NewElement, false>
{
  using Head = Front<List>;
  using Tail = PopFront<List>;
  using NewTail = typename PushBackRecT<Tail, NewElement>::Type;

 public:
  using Type = PushFront<Head, NewTail>;
};

// basis case:
template<typename List, typename NewElement>
class PushBackRecT<List, NewElement, true>
{
 public:
  using Type = PushFront<List, NewElement>;
};

// generic push-back operation:
template<typename List, typename NewElement>
class PushBackT : public PushBackRecT<List, NewElement> { };

template<typename List, typename NewElement>
using PushBack = typename PushBackT<List, NewElement>::Type;

이를 통해 삽입 정렬도 가능합니다.

template<typename List, 
         template<typename T, typename U> class Compare,
         bool = IsEmpty<List>::value>
class InsertionSortT;

template<typename List, 
         template<typename T, typename U> class Compare>
using InsertionSort = typename InsertionSortT<List, Compare>::Type;

// recursive case (insert first element into sorted list):
template<typename List,
         template<typename T, typename U> class Compare>
class InsertionSortT<List, Compare, false>
 : public InsertSortedT<InsertionSort<PopFront<List>, Compare>,
                        Front<List>, Compare>
{
};

// basis case (an empty list is sorted):
template<typename List,
         template<typename T, typename U> class Compare>
class InsertionSortT<List, Compare, true>
{
 public:
  using Type = List;
};

24.3 형식이 아닌 형식 목록

형식 목록을 사용하면 풍부한 알고리즘과 연산을 사용해 형식의 순열을 설명하거나 조작할 수 있습니다. 때로는 다차원 배열의 크기나 다른 형식 목록의 인덱스 등과 같은 컴파일 과정 값의 순열에 대해서도 같은 작업을 할 수 있으면 좋을 것입니다. 컴파일 과정 값의 형식 목록을 생성하는 방법에는 여러가지가 있는데 그중에서도 가장 간단한 방법인 형식 목록 내 특정 형식의 값을 나타내는 CTValue 클래스 템플릿을 정의하고 이에 대한 곱셈도 아래와 같이 정의하겠습니다.

template<typename T, T Value>
struct CTValue
{ 
  static constexpr T value = Value;
};

template<typename T, typename U>
struct MultiplyT;

template<typename T, T Value1, T Value2>
struct MultiplyT<CTValue<T, Value1>, CTValue<T, Value2>> {
 public:
  using Type = CTValue<T, Value1 * Value2>;
};

template<typename T, typename U>
using Multiply = typename MultiplyT<T, U>::Type;

이러한 값들도 목록처럼 만들 수 있으며 앞서 수행한 것과 같이 알고리즘에 사용할 수 있는 형식 목록이 됩니다.

template<typename T, T... Values>
using CTTypelist = Typelist<CTValue<T, Values>...>;

template<typename T, T... Values>
struct Valuelist {
};

template<typename T, T... Values>
struct IsEmpty<Valuelist<T, Values...>> {
  static constexpr bool value = sizeof...(Values) == 0;
};

template<typename T, T Head, T... Tail>
struct FrontT<Valuelist<T, Head, Tail...>> {
  using Type = CTValue<T, Head>;
  static constexpr T value = Head;
};

template<typename T, T Head, T... Tail>
struct PopFrontT<Valuelist<T, Head, Tail...>> {
  using Type = Valuelist<T, Tail...>;
};

template<typename T, T... Values, T New>
struct PushFrontT<Valuelist<T, Values...>, CTValue<T, New>> {
  using Type = Valuelist<T, New, Values...>;
};

template<typename T, T... Values, T New>
struct PushBackT<Valuelist<T, Values...>, CTValue<T, New>> {
  using Type = Valuelist<T, Values..., New>;
};

이를 통해 앞서한 것과 같이 삽입 정렬 알고리즘도 구현 가능합니다. C++17에서는 연역할 수 있는 형식이 아닌 파라미터를 사용해 개선도 가능합니다.

24.4 꾸러미 확장 을 사용한 알고리즘 최적화

꾸러미 확장은 컴파일러가 형식 목록을 반복하는 짐을 덜어주게 합니다. 이를 통해 알고리즘 특수화를 적용할 수 있습니다. 꾸러미 확장은 인덱스의 목록을 받아 요소를 선택해 새로운 형식 목록을 만들 때에도 유용합니다.

24.5 cons-스타일 형식 목록

가변 템플릿이 도입되기 전에 형식 목록은 cons 셀을 따라 모델된 재귀 데이터 구조로 형식화되는 것이 일반적이었습니다.

class Nil { };

template<typename HeadT, typename TailT = Nil>
class Cons {
 public:
  using Head = HeadT;
  using Tail = TailT;
};

빈 형식 목록이 Nil로 표현되었습니다. 이는 다음과 같이 목록을 더하거나 뺼 수 있습니다.

template<typename List>
class PopFrontT {
 public:
  using Type = typename List::Tail;
};

template<typename List>
using PopFront = typename PopFrontT<List>::Type;

template<typename List, typename Element>
class PushFrontT {
 public:
  using Type = Cons<Element, List>;
};

template<typename List, typename Element>
using PushFront = typename PushFrontT<List, Element>::Type;

 이는 현재 가변 템플릿이 할 수 있는 모든 일을 할 수 있지만, 중첩된 목록 때문에 코드 뿐만 아니라 컴파일러 진단 메세지를 작성하기도 읽기도 매우 어려우며, 여러 가지 알고리즘은 훨씬 효울적인 구현을 위해 가변 형식 목록을 위해 특수화될 수 있으며, 가변 템플릿이 이종 컨테이너를 위해 가변 템플릿을 사용할 때 더 적합합니다.

'C++공부 > C++ Templates' 카테고리의 다른 글

26. 구별 공용체  (0) 2022.07.07
25. 튜플  (0) 2022.07.07
23. 메타프로그래밍  (0) 2022.07.06
22. 정적과 동적 다형성 사이 잇기  (0) 2022.07.06
21. 템플릿과 상속  (0) 2022.07.06

+ Recent posts

티스토리툴바