[C++] Typelists

Reference

• Ch 24, C++ Templates The Complete Guide

Contents

• Typelists
• Typelist Algorithms
• Nontype Typelists
• Optimizing Algorithms with Pack Expansions
• Cons-style Typelist

---

효과적인 프로그래밍을 위해서는 다양한 데이터 구조가 필요하다. 메타프로그래밍에서도 동일한데, 메타프로그래밍에서 핵심이 되는 데이터 구조는 타입리스트(typelists)이다. 말 그대로 타입을 포함하고 있는 리스트를 의미한다. 템플릿 메타프로그램은 이러한 타입리스트들을 가지고 조작하면서 실행 프로그램 일부를 만들어낼 수 있다. 이번 포스팅에서는 타입리스트를 다루는 기법에 대해서 살펴볼 예정이다. 타입리스트에 대한 대부분의 연산은 템플릿 메타프로그래밍을 기반으로 한다.

 

---

Typelists

타입리스트란 타입들을 리스트로 나타낸 타입이며, 템플릿 메타프로그램에 의해서 조작될 수 있다. 일반적으로 리스트와 관련된 연산들을 제공한다. 즉, 리스트 내 요소(타입)을 반복하며 방문하거나 요소를 더하거나 제거할 수 있다. 하지만 std::list와 같은 런타임 데이터 구조와는 다르며 변경할 수 없다. 예를 들어, std::list에 요소를 추가하면 리스트 자체를 바꾸고 해당 프로그램 내부에서 해당 리스트에 접근한다면 변경점을 확인할 수 있다. 반면, 타입리스트에 요소를 추가해도 원래 타입리스트는 변경되지 않으며 원래의 타입리스트에서 새로운 요소가 추가된 새로운 타입리스트가 생성된다.

 

타입리스트는 일반적으로 타입리스트의 내용을 템플릿 인자로 표현한 클래스 템플릿 특수화로 구현된다. 즉, 파라미터 팩에서 요소를 표현하도록 타입리스트를 구현한다.

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

Typelist의 요소는 템플릿 인자로 직접 작성된다. 빈 타입리스트는 Typelist<>로 작성되며, int만 가지고 있는 타입리스트는 Typelist<int>로 작성된다. 아래 타입은 모든 signed integer를 포함하는 타입리스트이다.

using SignedIntegralTypes = Typelist<signed char, short, int, long, long long>;

 

이러한 타입리스트를 조작하려면 타입리스트를 나눌 수 있어야 한다. 예를 들어, Front 메타함수는 타입리스트로부터 첫 번째 타입을 추출한다.

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;

따라서, FrontT<SignedIntegralTypes>::Type은 signed char를 생성한다.

 

비슷하게 PopFront는 타입리스트에서 첫 번째 요소를 제거한다. 이 구현은 타입리스트 요소를 head와 tail로 나눈 뒤, tail에 있는 요소들로부터 새로운 Typelist 특수화를 생성한다.

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;

 

아래 메타함수로 타입리스트 앞에 요소를 삽입할 수도 있다. 가지고 있는 요소들을 템플릿 파라미터 팩에 넣고, 새로 추가된 요소를 포함한 모든 요소를 나타내는 새로운 Typelist 특수화를 만든다.

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;

따라서, 아래의 코드는

PushFront<SignedIntegralTypes, bool>

다음과 같다.

Typelist<bool, signed char, short, int, long, long long>

 

---

Typelist Algorithms

위에서 구현한 Front, PopFront, PushFront를 조합하면 새로운 타입리스트 조작을 만들 수 있다. 예를 들어, PopFront 결과에 PUshFront를 사용하면 타입리스트 내 첫 번째 요소를 다른 것으로 치환할 수 있다.

using Type = PushFront<PopFront<SignedIntegratlTypes>, bool>;
       // equivalent to Typelist<bool, short, int, long, long long>

또한, search, transformation, reversal과 같은 알고리즘도 메타함수로 구현할 수 있다.

Indexing

타입리스트에서 가장 근본이 되는 연산은 리스트 내 특정 요소를 추출하는 것이다. 위에서는 첫 번째 요소를 추출하는 방법에 대해서 살펴봤는데, 이를 확장하여 N 번째 요소를 추출하는 방법(NthElement)에 대해서 살펴보자. 구현은 다음과 같다.

// 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;

이를 사용하면 아래와 같이 주어진 타입리스트에서 2번째 인덱스 타입을 추출할 수 있다.

using TL = NthElement<Typelist<short, int, long>, 2>;

Finding the Best Match

많은 타입리스트 알고리즘은 타입리스트 내에서 데이터를 탐색한다. 예를 들어, 리스트 내 타입 중 충분히 큰 공간을 할당하기 위해서 타입리스트 내에서 가장 큰 타입을 찾을 수 있다. 이 또한 재귀 템플릿 메타프로그램으로 구현할 수 있다.

template<typename List>
class LargestTypeT;
// recursive case
template<typename List>
class LargestTypeT
{
private:
    using First = Front<List>;
    using Rest = typename LargestTypeT<PopFront<List>>::Type;
public:
    using Type = std::conditional_t<(sizeof(First) >= sizeof(Rest)), First, Rest>;
};
// basis case
template<>
class LargestTypeT<Typelist<>>
{
public:
    using Type = char;
};
template<typename List>
using LargestType = typename LargestTypeT<List>::Type;

LargestType 알고리즘은 타입리스트 내에서 가장 큰 타입 중 가장 먼저 발견된 타입을 반환한다. 예를 들어, Typelist<bool, int, long, short>가 주어졌을 때 이 알고리즘은 long과 크기가 같은 첫 번째 타입을 반환하는데, 플랫폼마다 다르겠지만 int 또는 long이 반환될 것이다. 재귀 구현을 뜯어보면 쉽게 이해할 수 있기 때문에 자세한 설명은 생략한다. 여기서 크기가 같을 경우, 타입리스트 내에서 먼저 발견된 것을 선호하도록 >=을 사용했다.

위 구현은 빈 타입리스트일 때 재귀가 끝난다. 알고리즘 초기화를 위해 기본값으로 char를 사용했는데, 모든 타입의 크기는 char의 크기 이상이기 때문이다.

 

기본 케이스는 빈 타입리스트 Typelist<>에 대해 명시적으로 정의했다. 이는 다소 불행한 것으로 볼 수 있는데, 다른 형태의 타입리스트 사용을 방해하기 때문이다. 이에 대해서는 아래에서 조금 더 살펴본다. 이 문제를 해결하기 위해서 주어진 타입리스트에 요소가 하나도 없는지 확인하는 IsEmpty 메타함수를 구현해보자.

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

IsEmpty를 사용하여 LargestType을 구현하면 어떠한 타입리스트에도 잘 동작할 수 있다.

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 = std::conditional_t<(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;

LargestTypeT의 두 번째 템플릿 파라미터 Empty는 리스트가 비었는지 검사하는 값이다. 비어있지 않다면 재귀를 계속하고 비어있다면 basis case로 재귀를 멈추고 초기값 char를 제공한다.

Appending to a Typelist

위에서 구현한 PushFront 연산을 사용하면 타입리스트 앞부분에 새로운 요소를 추가하여 새로운 타입리스트를 만들 수 있다. 이번에는 std::list나 std::vector와 같이 리스트 끝부분에 새로운 요소를 추가하는 PushBack 연산을 구현해보자. 위에서 구현한 PushFront를 약간 수정만 해주면 PushBack 연산을 간단하게 구현할 수 있다.

template<typename List, typename NewElement>
class PushBackT;

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

또는, LargestType 알고리즘에서와 같이 PushBack 연산을 이미 구현해둔 Front, PushFront, PopFront, IsEmpty를 사용하여 구현할 수도 있다.

template<typename List, typename NewElement, bool = IsEmpty<List>::value>
class PushBackT;
// recursive case
template<typename List, typename NewElement>
class PushBackT<List, NewElement, false>
{
    using Head = Front<List>;
    using Tail = PopFront<List>;
    using NewTail = typename PushBackT<Tail, NewElement>::Type;
public:
    using Type = PushFront<NewTail, Head>;
};
// basis case
template<typename List, typename NewElement>
class PushBackT<List, NewElement, true>
{
public:
    using Type = PushFront<List, NewElement>;
};
template<typename List, typename NewElement>
using PushBack = typename PushBackT<List, NewElement>::Type;

 

여러 가지 방법으로 구현할 수 있는데, 템플릿 인스턴스화 자체가 시간이 꽤 걸리는 컴파일 과정이므로 템플릿 인스턴스의 수가 적게 생성되도록 하는 것이 합리적이다. 사실 첫 번째 PushBackT 구현은 구정된 수의 템플릿 인스턴스화만 시도하므로 두 번째 구현한 generic 버전보다 훨씬 더 효율적이다 (컴파일 과정 측면에서).

Reversing a Typelist

이번에는 타입리스트의 순서를 뒤집는 연산을 살펴보자. 예를 들어, 정수의 타입 크기가 증가하는 순으로 정렬되어 있는 SignedIntegralTypes 타입리스트의 순서를 뒤집어서 크기가 줄어드는 순서로 정렬되어 있는 타입리스트가 필요할 수 있다.

template<typename List, bool = IsEmpty<List>::value>
class ReverseT;
template<typename List>
using Reverse = typename ReverseT<List>::Type;
// recursive case
template<typename List>
class ReverseT<List, false> : public PushBackT<Reverse<PopFront<List>>, Front<List>> {};
// basis case
template<typename List>
class ReverseT<List, true>
{
public:
    using Type = List;
};

자세히 보면 알겠지만, 재귀적으로 앞부분의 요소를 추출하여 다시 끝부분으로 추가해주면서 순서를 뒤집고 있다.

 

이 알고리즘을 활용하면 타입리스트에서 마지막 요소를 제거하는 PopBack 연산도 구현할 수 있다.

template<typename List>
class PopBackT
{
public:
    using Type = Reverse<PopFront<Reverse<List>>>;
};
template<typename List>
using PopBack = typename PopBackT<List>::Type;

위 알고리즘은 우선 리스트를 뒤집은 다음, 뒤집은 리스트에서 첫 번째 요소를 추출하고 다시 뒤집는다.

Transforming a Typelist

지금까지 구현한 연산들도 유용하지만 타입리스트 내의 요소들을 가지고 어떠한 연산이든 할 수 있는 것은 아니다. 예를 들어, 타입리스트 내 모든 타입을 어떤 방식으로 변형(transform)하고 싶다면, 예를 들어, 아래의 AddConst와 같은 메타 함수를 통해 const로 한정된 타입으로 바꾸고 싶다면 어떻게 구현해야 하는지 살펴보자.

template<typename T>
struct AddConstT {
    using Type = T const;
};
template<typename T>
using AddConst = typename AddConstT<T>::Type;

 

모든 타입에 대해서 특정 메타 함수를 적용하여 변형하려면 std::transform() 함수와 유사하게 타입리스트와 메타함수를 전달받아서 각 타입에 메타함수를 적용한 결과를 포함하는 새로운 타입리스트를 생성하는 Transform 알고리즘이 필요하다. 예를 들어, 아래 코드는

Transform<SignedIntegralTypes, AddConstT>

부호가 있는 정수형 타입에 const 한정자가 붙은 타입리스트이다.

 

메타함수는 템플릿 템플릿 파라미터로 전달된다. 입력 타입을 출력 타입으로 바꾸는 역할을 하며, 예상할 수 있다시피 재귀로 구현된다.

template<typename List, template<typename T> class MetaFun, bool = IsEmpty<List>::value>
class TransformT;
// recursive case
template<typename List, template<typename T> class MetaFun>
class TransformT<List, MetaFun, false>
: public PushFrontT<typename TransformT<PopFront<List>, MetaFun>::Type,
                    typename MetaFun<Front<List>>::Type> {};
// basis case
template<typename List, template<typename T> class MetaFun>
class TransformT<List, MetaFun, true>
{
public:
    using Type = List;
};
template<typename List, template<typename T> class MetaFun>
using Transform = typename TransformT<List, MetaFun>::Type;

구현은 직관적이다. 타입리스트의 첫 번째 요소를 변형한 결과를 타입리스트의 나머지 요소를 재귀적으로 변형하여 얻은 리스트의 처음에 추가해준 것이 최종 결과이다. 조금 더 효율적으로 구현하는 방법은 Pack Expansions을 활용해야 하며, 아래에서 다룰 예정이다.

Accumulating Typelists

Transform은 리스트 내 각 요소를 변경할 때 유용하다. Accumulate 알고리즘과 결합하여 사용하는 경우가 많은데, Accumulate는 시퀀스 내 요소를 전부 결합하여 하나의 결과로 바꾸는 걸 의미한다. Accumulate 알고리즘에서는 타입리스트 T와 초기 타입 I, 그리고 두 타입을 받아서 하나의 타입을 변환하는 메타함수 F를 받는다.

 

타입리스트, 메타함수, 초기 타입에 따라서 Accumulate는 다양한 결과를 만들어낼 수 있다. 예를 들어, F가 두 타입 중 큰 타입을 선택한다면 Accumulate는 LargestType 알고리즘처럼 동작한다. 반면, F가 타입리스트와 타입을 전달받아서 타입리스트 뒤에 추가한다면 Reverse 알고리즘처럼 동작하게 된다.

 

구현은 다음과 같다.

template<typename List,
         template<typename X, typename Y> class F,
         typename I,
         bool = IsEmpty<List>::value>
class AccumulateT;
// recursive case
template<typename List,
         template<typename X, typename Y> class F,
         typename I>
class AccumulateT<List, F, I, false>
: public AccumulateT<PopFront<List>, F, typename F<I, Front<List>>::Type> {};
// basis case
template<typename List,
         template<typename X, typename Y> class F,
         typename I>
class AccumulateT<List, F, I, true>
{
public:
    using Type = I;
};
template<typename List,
         template<typename X, typename Y> class F,
         typename I>
using Accumulate = typename AccumulateT<List, F, I>::Type;

여기서 I는 accumulator로써 현재의 결과를 가지고 있는다. 따라서, basis case에서는 타입리스트의 끝에 도달했을 때 이를 반환한다. Recursive case에서는 이전 결과(I)와 리스트 첫 요소에 F를 적용하고 그 결과를 나머지 부분의 accumulate를 위한 초기 타입으로 전달한다.

 

PushFrontT를 메타함수 F로 사용하고 빈 타입리스트를 초기 타입 I로 전달하면 주어진 타입리스트를 역전시킬 수 있다.

using Result = Accumulate<SignedIntegralTypes, PushFrontT, Typelist<>>;

 

LargestType을 Accumulate 기반으로 구현하려면 두 타입 중 더 큰 타입을 반환하는 메타함수를 만들어야 한다.

template<typename T, typename U>
class LargerTypeT
{
public:
    using Type = std::conditional_t<sizeof(T) >= sizeof(U), T, U>;
};
template<typename Typelist, bool = IsEmpty<Typelist>::value>
class LargestTypeAccT;
template<typename Typelist>
class LargestTypeAccT<Typelist, false>
: public AccumulateT<PopFront<Typelist>, LargerTypeT, Front<Typelist>> {};
template<typename Typelist>
class LargestTypeAccT<Typelist, true> {};
template<typename Typelist>
using LargestTypeAcc = typename LargestTypeAccT<Typelist>::Type;

Accumulate 알고리즘은 다양한 연산을 표현할 수 있다는 점에서 강력한 타입리스트 알고리즘이며, 타입리스트 조작을 위한 근본적인 알고리즘 중 하나로 생각할 수 있다.

Insertion Sort

마지막으로 삽입 정렬을 구현한다. 이 알고리즘 또한 다른 알고리즘과 마찬가지로 리스트의 첫 번째 요소와 나머지 요소들로 분리하는 재귀적 단계를 거친다. 그런 다음 나머지 요소를 다시 정렬하고 첫 번째 요소를 정렬된 리스트 내 적절한 위치에 삽입한다.

template<typename T>
struct IdentityT {
    using Type = T;
};

template<typename List, typename Element,
         template<typename T, typename U> class Compare,
         bool = IsEmpty<List>::value>
class InsertSortedT;
// recursive case
template<typename List, typename Element,
         template<typename T, typename U> class Compare>
class InsertSortedT<List, Element, Compare, false>
{
    // compute the tail of the resulting list:
    using NewTail = typename std::conditional_t<Compare<Element, Front<List>>::value,
                                       IdentityT<List>,
                                       InsertSortedT<PopFront<List>, Element, Compare>>::Type;
    // compute the head of the resulting list:
    using NewHead = std::conditional_t<Compare<Element, Front<List>>::value,
                                       Element,
                                       Front<List>>;
public:
    using Type = PushFront<NewTail, NewHead>;
};
// basis case
template<typename List, typename Element,
         template<typename T, typename U> class Compare>
class InsertSortedT<List, Element, Compare, true> : public PushFrontT<List, Element> {};
template<typename List, typename Element, template<typename T, typename U> class Compare>
using InsertSorted = typename InsertSortedT<List, Element, Compare>::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;
// recurssive 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;
};

Compare 파라미터는 타입리스트 내의 요소를 정렬할 때 필요한 비교 함수를 나타낸다. 두 개의 타입을 받아서 bool 값을 계산하고 value 멤버에 저장한다.

삽입 정렬 연산의 핵심은 InsertSortedT 메타함수이다. 이 함수는 이미 정렬된 리스트 내에서 새로운 값이 들어가도 리스트가 정렬된 상태를 유지할 수 있는 첫 번째 위치에 값을 삽입한다. 요소가 하나인 상황은 항상 정렬된 상태이기 때문에 그냥 삽입하면 된다. 재귀 상황에서는 삽입할 요소가 리스트 내 첫 번째 요소 앞에 삽입되어야 한다면 PushFront를 사용하여 가장 앞쪽에 삽입한다. 그렇지 않다면 Head와 Tail로 나누어서 재귀적으로 새로운 요소를 Tail에 삽입하고 그 결과를 Head에 덧붙인다.

 

11~25 lines의 구현에서는 사용하지 않는 타입에 대해서는 인스턴스화하지 않도록 최적화되어 있다.

 

이렇게 구현한 삽입 정렬은 다음과 같이 사용할 수 있다.

int main()
{
    using Types = Typelist<int, char, short, double>;
    using ST = InsertionSort<Types, SmallerThanT>;
    std::cout << std::is_same_v<ST, Typelist<char, short, int ,double>> << std::endl; // print 1
}

---

Nontype Typelists

타입리스트를 사용하면 위에서 구현한 여러 알고리즘을 통해 타입의 시퀀스를 설명하거나 조작할 수 있다. 타입 이외에도 다차원 배열의 크기나 다른 타입리스트의 인덱스 등과 같은 compile-time values의 시퀀스에 대해서도 동일한 작업을 수행할 수 있다.

 

타입리스트의 Compile-time values를 생성하는 방법에는 여러 가지가 있다. 그중에서 가장 간단한 방식인 타입 리스트 내 특정 타입의 값을 나타내는 CTValue 클래스 템플릿을 구현해보자.

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

이 템플릿을 사용하면 몇 가지 작은 소수를 포함한 타입을 표현할 수 있다.

using Primes = Typelist<CTValue<int, 2>, CTValue<int, 3>,
                        CTValue<int, 5>, CTValue<int, 7>, CTValue<int, 11>>;

이렇게 하면, 이 소수들의 곱과 같이 값에 대한 타입리스트를 받아서 숫자 계산도 가능하다.

 

먼저 타입이 같은 두 개의 compile-time value 값을 받아 타입은 같지만 입력값의 곱을 생성하는 MultiplyT 템플릿을 정의해보자.

template<typename T, typename U>
struct MultiplyT;

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

이를 사용하면 아래 코드를 통해 모든 소수의 곲을 계산할 수 있다.

Accumulate<Primes, MultiplyT, CTValue<int, 1>>::value; // 2310

다만, Typelist와 CTValue를 사용하는 것은 코드를 꽤나 지저분하게 만든다. 특히 모든 값의 타입이 같은 경우가 그렇다.

 

같은 타입의 값 리스트를 제공하는 CTTypelist라는 alias를 도입하면 이 경우만을 위해 최적화할 수 있다.

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

그러면 아래와 같이 Primes를 간결하게 정의할 수 있다.

using Primes = CTTypelist<int, 2, 3, 5, 7, 11>;

이 방식의 유일한 단점은 alias template은 alias일 뿐이어서 에러가 생기면 CTValueType의 Typelist를 출력하여 장황한 메세지가 나온다는 것이다. 이 문제를 해결하기 위해 값을 직접 지정하는 새로운 타입리스트 클래스인 Valuelist를 구현해보자.

// value list
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...>;
};

Valuelist와 함께 이전에 구현한 IsEmpty, FrontT, PopFrontT, PushFrontT 알고리즘도 같이 구현하였다. 이들을 통해서 이전에 구현한 InsertionSort 알고리즘을 Valuelist에 대해서 적용할 수 있다.

int main()
{
    using Integers = Valuelist<int, 6, 2, 4, 9, 5, 2, 1, 7>;
    using SortedIntegers = InsertionSort<Integers, GreaterThanT>;
    static_assert(std::is_same_v<SortedIntegers, Valuelist<int, 9, 7, 6, 5, 4, 2, 2, 1>>, "insertion sort failed");
}

위 코드는 문제없이 컴파일된다.

Deducible Nontype Parameters

C++17에서는 CTValue에 auto를 사용하여 개선할 수 있다.

template<auto Value>
struct CTValue {
    static constexpr auto value = Value;
};

그러면 CTValue를 사용할 때마다 타입을 명시해주지 않아도 되기 때문에 편리하게 사용할 수 있다.

using Primes = Typelist<CTValue<2>, CTValue<3>,
                        CTValue<5>, CTValue<7>, CTValue<11>>;

C++17에서 Valuelist도 위와 같이 할 수 있지만, 그 결과가 더 좋다는 것은 보장할 수 없다. 이는 타입이 아닌 parameter pack에서는 추론된 타입을 사용하면 각 인자의 타입이 다를 수 있기 때문이다.

template<auto... Values>
struct Valuelist {};
int x;
using MyValueList = Valuelist<1, 'a', true, &x>;

서로 다른 타입의 값 리스트가 필요할 때도 있지만 앞서 정의한 Valuelist는 모든 요소가 동일한 타입이어야 한다. 모든 요소가 같은 타입을 갖게 할 수 있지만, 비어있는 Valuelist<>는 known element type을 가져선 안된다.

---

Optimizing Algorithms with Pack Expansions

Pack Expansion은 컴파일러가 타입리스트를 반복하는 작업을 덜어주는 유용한 메커니즘이다. 위의 Transform 알고리즘은 리스트 내 각 요소에 대해 같은 연산을 적용하므로 Pack Expansion을 적용할 수 있다.

// recursive case
template<typename... Elements, template<typename T> class MetaFun>
class TransformT<Typelist<Elements...>, MetaFun, false>
{
public:
    using Type = Typelist<typename MetaFun<Elements>::Type...>;
};

이전 구현에서는 List를 템플릿 파라미터로 받았지만, 이번에는 타입리스트의 요소를 parameter pack으로 받는다. 그런 다음 typename MetaFun<Elements>::Type을 pack expansion을 활용하여 Elements 내의 타입 각각에 메타함수를 적용하고, 그 결과로부터 타입리스트를 생성한다. 이 구현이 의심의 여지없이 더 간단하다는 것을 알 수 있다. 재귀도 필요없고 꽤나 직관적인 방식으로 언어 자체의 특성을 이용한다. 더불어 단 하나의 Transform 템플릿 인스턴스만 생성되므로 템플릿 인스턴스의 수도 더 적다. 알고리즘에 사용되는 MetaFun의 인스턴스 수는 여전히 선형적으로 증가하지만, 이는 꼭 필요한 부분이라 어쩔 수 없다.

 

다른 알고리즘에도 Pack Expansion을 사용하면 인스턴스 수에 영향을 준다. 예를 들어, Reverse 알고리즘은 PushBack의 인스턴스 수가 선형적으로 증가했다. 하지만 Typelist에 대한 PushBack을 pack expansion으로 표현하면 Reverse의 복잡도는 linear로 줄어든다. 일반 재귀 방식의 Reverse 또한 인스턴스의 수 자체는 선형적으로 증가하지만 Reverse의 복잡도는 제곱에 비례했다.

 

Pack Expansion은 인덱스의 리스트를 받아 요소를 선택해 새로운 타입리스트를 만들 때에도 유용하다. Select 메타함수는 타입리스트와 그 타입리스트에 대한 인덱스를 포함한 Valuelist를 받아서 Valuelist가 가리키는 요소를 포함한 새로운 타입리스트를 생성한다.

template<typename Types, typename Indices>
class SelectT;
template<typename Types, unsigned... Indices>
class SelectT<Types, Valuelist<unsigned, Indices...>>
{
public:
    using Type = Typelist<NthElement<Types, Indices>...>;
};
template<typename Types, typename Indices>
using Select = typename SelectT<Type, Indices>::Type;

인덱스들은 parameter pack인 Indices에 포함되어 있고, 이 Indices는 주어진 타입리스트를 인덱스하는 NthElement 타입의 시퀀스를 생성하도록 확장된다. 그리고 그 결과를 다시 타입리스트로 저장한다. 이 메타함수는 아래와 같이 사용하여 타입리스트 순서를 역전시키는데 사용할 수 있다.

// SignedIntegralTypes = Typelist<signed char, short, int, long, long long>
using ReversedSignedIntegralTypes = Select<SignedIntegralTypes, Valuelist<unsigned, 4, 3, 2, 1, 0>>;
// produces Typelist<long long, long, int, short, signed char>

---

Cons-style Typelist

가변(variadic) 템플릿이 도입되기 전에 타입리스트는 LIPS의 cons 셀을 따라 모델된 재귀 데이터 구조로 형식화하는 것이 일반적이었다. 각 cons 셀에는 값(리스트의 head)과 중첩된 리스트가 포함되는데, 중첩된 리스트는 또 다른 cons 셀이거나 빈 목록 nil이다. 이는 C++로도 직접 표현할 수 있다.

class Nil{};

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

빈 타입리스트가 Nil이라면 int를 포함한 단일 요소 리스트는 Cons<int, Nil> 또는 Cons<int>로 표현한다. 더 길다면 중첩되어 표현된다.

using TwoShort = Cons<short, Cons<unsigned short>>;

재귀를 계속 중첩하면 어떠한 길이의 타입리스트라도 만들 수 있지만, 코드로 작성하기는 어렵다.

using SignedIntegralTypes = Cons<signed char, Cons<short, Cons<int,
                               Cons<long, Cons<long long, Nil>>>>>;

cons-style의 리스트에서 첫 번째 요소를 추출하려면 직접 리스트의 head를 가리키면 된다.

template<typename List>
class FrontT {
public:
    using Type = typename List::Head;
};
template<typename List>
using Front = typename FrontT<List>::Type;

또한, 전달받은 리스트를 또 다른 Cons로 감싸면 리스트 앞 부분에 요소를 추가할 수 있다.

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

마지막으로 중첩된 타입리스트에서 첫 번째 요소를 제거하여 리스트의 Tail을 추출할 수 있다.

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

Nil을 위한 IsEmpty 특수화를 구현하고나면 핵심 타입리스트 연산 구현이 완료된다.

template<typename List>
struct IsEmpty {
    static constexpr bool value = false;
};
template<>
struct IsEmpty<Nil> {
    static constexpr bool value = true;
};

이렇게 준비된 연산들로부터 이전에 구현한 InsertionSort 알고리즘을 아래와 같이 사용할 수 있다.

template<typename T, typename U>
struct SmallerThanT {
    static constexpr bool value = sizeof(T) < sizeof(U);
};

int main()
{
    using ConsList = Cons<int, Cons<char, Cons<short, Cons<double>>>>;
    using SortedTypes = InsertionSort<ConsList, SmallerThanT>;
    using Expected = Cons<char, Cons<short, Cons<int, Cons<double>>>>;
    std::cout << std::is_same_v<SortedTypes, Expected> << std::endl;
}

 

cons-style 타입리스트를 사용하여 이전에 설명한 타입리스트 알고리즘 및 가변 타입리스트의 알고리즘을 모두 다 표현할 수 있다. 사실 앞에서 설명한 많은 알고리즘들을 cons-style 타입리스트를 조작할 때 사용한 방식과 동일한 방식으로 작성할 수 있다. 하지만 몇 가지 단점이 있는데, 중첩된 리스트로 인하여 에러가 발생하면 컴파일 에러 메세지가 너무 장황하다는 것이다. 두 번째로는 여러 가지 알고리즘들은 가변 타입리스트로 특수화되어 훨씬 효율적으로 구현될 수 있는데, cons-style은 그렇지 못하다. 마지막으로 타입리스트에 가변 템플릿을 사용하는 것은 이종(heterogeneous) 컨테이너를 사용할 때 유용한데 이를 활요하지 못한다.