[C++] Overloading on Type Properties

References

• Ch 20, C++ Templates The Complete Guide

Contents

• Algorithm Specialization
• Tag Dispatching
• Enabling/Disabling Function Templates

---

 

함수 오버로딩(function overloading)은 같은 함수 이름을 여러 함수에서 사용할 수 있도록 하는 것이다. 단, 이러한 함수들은 이 함수들의 파라미터로 구별된다.

void f(int);
void f(char const*);

함수 템플릿(function templates)에서는 타입 패턴에 오버로드된다.

template<typename T> void f(T*);
template<typename T> void f(Array<T>);

Type traits를 생각해 보면 템플릿 인자의 속성을 기반으로 함수 템플릿을 아래와 같이 오버로딩하는 것은 자연스럽다.

template<typename Number> void f(Number);       // only for numbers
template<typename Container> void f(Container); // only for containers

하지만 C++에서 위와 같이 타입 속성으로 오버로딩을 표현하는 방법은 제공되지 않는다. 실제로 위의 두 함수 템플릿은 같은 함수 템플릿 선언에 해당하는데, 함수 파라미터의 이름은 두 함수 템플릿을 비교할 때 무시되기 때문이다.

다행히 타입 속성으로 함수 템플릿의 오버로드를 구별하는 여러 기법들이 많이 있는데, 이번 포스팅에서는 이에 대해서 살펴본다.

 

---

Algorithm Specialization

함수 템플릿 오버로드가 필요한 이유 중 한 가지는 관련된 타입에 대한 지식을 기반으로 보다 전문화된 알고리즘 버전을 제공하기 위함이다. 두 값을 교환하는 간단한 swap() 연산을 살펴보자.

template<typename T>
void swap(T& x, T& y) {
    T tmp(x);
    x = y;
    y = tmp;
}

위 구현에는 3번의 copy 연산이 포함된다. 그러나 Array<T>와 같은 타입에서는 swap() 연산을 보다 효율적으로 제공할 수 있다. 만약 Array<T>에서 배열의 길이와 데이터(배열의 포인터)를 저장하고 있다면,

template<typename T>
void swap(Array<T>& x, Array<T>& y) {
    swap(x.ptr, y.ptr);
    swap(x.len, y.len);
}

위와 같이 보다 효율적으로 구현할 수 있다.

위의 두 swap() 구현은 모두 두 Array<T> 객체의 내용을 교환할 것이다. 그러나 후자의 경우에는 다른 임의의 타입에서는 사용할 수 없는 Array<T>의 부가적인 속성(ptr 및 len)을 사용하기 때문에 더 효율적이다. 따라서 두 번째 swap() 구현은 개념적으로 첫 번째 swap() 함수 템플릿에서 허용하는 타입의 하위 집합에 대해 동일한 작업을 수행하므로 더 전문화된다. 다행히 두 번째 함수 템플릿은 함수 템플릿의 partial ordering rules을 기반으로 specialization 되어 있으므로 컴파일러는 두 번째 함수 템플릿을 선택한다. 만약 적용 가능하지 않다면 더 일반적인 첫 번째 함수 템플릿을 선택하게 된다.

 

일반 알고리즘보다 더 전문화된 변형을 도입하는 설계 및 최적화 접근 방식을 algorithm specialization 이라고 한다. 이는 일반 알고리즘에 대해서 유효한 입력의 하위 집합에 대해 적용되어 특정 타입이나 타입의 속성을 기반으로 이를 식별하고, 일반적으로 이에 대한 일반 알고리즘 구현보다 더 효율적이다.

 

여기서 가장 중요한 점은 caller는 해당 알고리즘의 변형이 존재한다는 사실을 알고 있을 필요가 없이 적용 가능한 경우에 보다 전문화된 알고리즘이 자동으로 선택된다는 점이다. 위의 swap() 예제에서는 더 특화된 함수 템플릿(두 번째 swap())을 가장 일반적인 함수 템플릿(첫 번째 swap())으로 오버로딩하며, C++ partial ordering rule에 의해서 두 번째 swap() 함수 템플릿이 더 specialization 된다.

 

그러나 개념적으로 모든 알고리즘 변형이 모두 올바른 partial ordering 동작을 제공하는 함수 템플릿으로 직접 변환될 수 있는 것은 아니다. 예를 들어, iterator x를 n step만큼 이동시키는 advanceIter() 함수를 살펴보자. 이는 모든 입력 interator에서 동작할 수 있다.

template<typename InputIterator, typename Distance>
void advanceIter(InputIterator& x, Distance n) {
    while (n > 0) { // linear time
        ++x;
        --n;
    }
}

특정 클래스의 iterators에서는 random access 연산을 지원할 수 있는데, 그렇다면 아래의 구현이 더 효율적일 것이다.

template<typename InputIterator, typename Distance>
void advanceIter(InputIterator& x, Distance n) {
    x += n; // constant time
}

아쉽게도 이 두 함수 템플릿을 모두 정의하면 컴파일 에러가 발생한다. 포스팅 처음에 언급했듯이 템플릿 파라미터의 이름만 다른 함수 템플릿은 오버로드할 수 없기 때문이다. 아래에서 이런 함수 템플릿을 오버로드하는 방법에 대해서 살펴보자.

---

Tag Dispatching

Algorithm Specialization의 한 가지 접근 방법은 알고리즘 변형을 식별하는 고유한 타입으로 알고리즘의 다양한 변형된 구현을 "태그(tag)"하는 것이다. 예를 들어, 위에서 예시로 사용한 advanceIter() 문제를 해결하기 위해서 표준 라이브러리의 iterator category tag 타입을 사용하여 advanceIter() 알고리즘의 두 가지 변형 구현을 식별할 수 있다.

template<typename Iterator, typename Distance>
void advanceIter(Iterator& x, Distance n, std::input_iterator_tag) {
    while (n > 0) { // linear time
        ++x;
        --n;
    }
}

template<typename Iterator, typename Distance>
void advanceIter(Iterator& x, Distance n, std::random_access_iterator_tag) {
    x += n; // constant time
}

그러면 이제 advanceIter() 함수는 적절한 태그를 포함하여 인자들을 포워딩하도록 하여 위 두 함수 중 하나를 자동으로 선택하도록 할 수 있다.

template<typename Iterator, typename Distance>
void advanceIter(Iterator& x, Distance n) {
    advanceIter(x, n,
                typename std::iterator_traits<Iterator>::iterator_category());
}

Trait 클래스인 std::iterator_traits는 iterator의 카테고리를 멤버 타입인 iterator_category로 제공한다. Iterator 카테고리는 아래 tag 중 하나가 되는데, 아래 태그들을 C++ 표준 라이브러리에서 제공하는 것들이다.

namespace std {
  struct input_iterator_tag {};
  struct output_iterator_tag {};
  struct forward_iterator_tag : public input_iterator_tag {};
  struct bidirectional_iterator_tag : public forward_iterator_tag {};
  struct random_access_iterator_tag : public bidirectional_iterator_tag {};
}

C++에서 제공하는 태그는 위와 같이 정의되며, 한 태그가 다른 태그에서 파생된 카테고리라는 것을 가리키기 위해서 상속을 사용하고 있다.

 

Tag dispatching을 효과적으로 활용하는 핵심은 각 태그 간의 관계에 있다. advanceIter() 구현의 두 가지 변형에서는 std::input_iterator_tag 및 std::random_access_iterator_tag가 지정되어 있으며, std::random_access_iterator_tag는 std::input_iterator_tag를 상속받으므로 random access iterator로 advanceIter()가 호출될 때 std::random_access_iterator_tag를 사용하는 알고리즘 변형 버전이 더 선호될 것이다.

 

Tag dispatching은 알고리즘에서 사용하는 속성과 해당 태그 값을 제공하는 기존 traits 집합에 대한 계층 구조가 자연스러울 때 가장 잘 동작한다. T라는 타입이 trivial copy assignment operator를 가지고 있는지 여부와 같은 hoc type properties에 따라 달라지는 알고리즘에서는 편리하지 않다. 이와 같은 경우에는 보다 강력한 기법이 필요하다.

---

Enabling/Disabling Function Templates

Algorithm specialization에는 템플릿 인자의 속성을 기반으로 선택되는 다양한 함수 템플릿을 제공하는 것이 포함된다. 하지만 함수 템플릿의 partial ordering이나 overload resolution으로는 algorithm specialization을 표현하기에 충분하지 않다.

 

이를 위해 C++ 표준 라이브러리에서 제공하는 helper 중 하나는 std::enable_if 이다. 이번 섹션에서는 이를 활용하여 구현하는 방법에 대해서 살펴본다. 우선 std::enable_if에 해당하는 EnableIf는 아래와 같이 간단하게 구현할 수 있다.

template<bool, typename T = void>
struct EnableIfT {};
template<typename T>
struct EnableIfT<true, T> {
    using Type = T;
};

template<bool Cond, typename T = void>
using EnableIf = typename EnableIfT<Cond, T>::Type;

그러면 advanceIter()의 random-acess version은 다음과 같이 구현할 수 있다.

template<typename Iterator>
constexpr bool IsRandomAccessIterator =
    std::is_convertible<
        typename std::iterator_traits<Iterator>::iterator_category,
        std::random_access_iterator_tag
    >::value;

template<typename Iterator, typename Distance>
EnableIf<IsRandomAccessIterator<Iterator>>
advanceIter(Iterator& x, Distance n) {
    x += n; // constant time
}

EnableIfT specialization은 오직 iterator가 random access iterator일 때에만 사용된다.

 

EnableIfT에서 조건이 true라면, 단순히 두 번째 인수인 T로 평가된다. 조건이 false라면 EnableIfT는 유효한 타입을 생성하지 않으며 EnableIfT의 템플릿에는 Type이라는 멤버가 없다. 일반적으로 이는 에러이지만, SFINAE 문맥 (함수 템플릿의 리턴 타입)에서는 함수 인자 추론 실패 유발하는 효과를 가지며 결과적으로 템플릿 고려 대상에서 이 함수 템플릿을 제거하는 효과를 갖는다. 즉, 여기서 EnableIf를 사용한다는 것은 Iterator가 random access iterator일 때 이 함수 템플릿을 사용할 수 있고, 그렇지 않을 때에는 고려 대상에서 제거된다는 것을 의미한다.

EnableIf를 템플릿 구현 요구 사항을 충족하지 않는 템플릿 인수를 사용하여 인스턴스화로부터 템플릿을 보호하는 방법으로 생각할 수도 있다. 왜냐면, 이 advanceIter()는 random access iterator에서만 사용할 수 있는 연산이므로 random access iterator로만 인스턴스화할 수 있기 때문이다. 이러한 방식으로 EnableIf를 사용하는 것은 완벽하지는 않지만 의도치 않은 실수를 조기에 검출하는데 도움이 될 수 있다.

 

위의 방법으로 우리는 적용하고자 하는 타입에 보다 specialization 된 템플릿을 명시적으로 활성화하는 방법을 확립했다. 하지만 이것만으로 충분하지는 않으며, 덜 spcialization 된 템플릿도 비활성화해야 한다. 왜냐하면 컴파일러는 두 버전 중 하나를 선택할 수 없고 두 버전이 모두 적용되는 경우에는 ambiguity 에러를 발생시키기 때문이다. 다행히 이를 해결하는 것은 어렵지 않다. 조건식을 무효화한다는 점을 제외하면 덜 specialization 된 템플릿에 동일한 EnableIf 패턴을 사용하면 된다. 이렇게 하면 구체적인 Iterator 타입에 대해서 두 템플릿 중 하나만 활성화된다. 즉, random access iterator가 아닌 iterator에 대한 advanceIter() 버전은 아래와 같다.

template<typename Iterator, typename Distance>
EnableIf<!IsRandomAccessIterator<Iterator>>
advanceIter(Iterator& x, Distance n) {
    while (n > 0) { // linear time
        ++x;
        --n;
    }
}

 

Providing Multiple Specialization

이번에는 advanceIter() 알고리즘의 3번째 변형을 추가해보자. 이 세 번째 구현은 음수의 distance 값을 주었을 때 뒤로 이동할 수 있도록 한다. 이와 같은 동작은 input iterator에서는 불가능하지만 random access iterator에서는 가능하다. 표준 라이브러리에는 bidirectional iterator, 즉, random access는 불가능하지만 뒤로 이동하는 것이 가능한 iterator가 있다. 이 경우를 구현하려면 조금 더 정교한 구조가 필요하다. 각 함수 템플릿은 알고리즘의 서로 다른 변형을 나타내는 다른 함수 템플릿의 모든 조건이 상호 배재 원칙을 따르게 EnableIf를 사용해야 한다. 여기에는 아래와 같은 조건들이 사용된다.

• Random Access Iterator: random access case (constant time, forward or backward)
• Bidirectional Iterator and Not Random Access: bidirectional case (linear time, forward or backward)
• Input Iterator and Not Bidirectional: general case (linear time, forward)

이들의 구현은 다음과 같다.

// implementation for random access iterators
template<typename Iterator, typename Distance>
EnableIf<IsRandomAccessIterator<Iterator>>
advanceIter(Iterator& x, Distance n) {
    x += n; // constant time
}

template<typename Iterator>
constexpr bool IsBidirectionalIterator =
    std::is_convertible<
        typename std::iterator_traits<Iterator>::iterator_category,
        std::bidirectional_iterator_tag
    >::value;
// implementation for bidirectional iterators
template<typename Iterator, typename Distance>
EnableIf<IsBidirectionalIterator<Iterator> &&
         !IsRandomAccessIterator<Iterator>>
advanceIter(Iterator& x, Distance n) {
    if (n > 0) {
        for (; n > 0; ++x, --n) {}
    }
    else {
        for (; n < 0; --x, ++n) {}
    }
}

// implementation for all other iterators
template<typename Iterator, typename Distance>
EnableIf<!IsBidirectionalIterator<Iterator>>
advanceIter(Iterator& x, Distance n) {
    if (n < 0) {
        throw "advanceIter(): invalid iterator category for negative n";
    }
    while (n > 0) {
        ++x;
        --n;
    }
}

각 함수 템플릿의 EnableIf 조건을 다른 함수 템플릿의 조건들과 상호 배제가 되도록 한다면 인자가 주어졌을 때 템플릿 인자 추론에 성공하는 함수 템플릿은 그중 하나라는 것을 보장할 수 있다.

 

위 예제에서는 algorithm specialization을 위해 EnableIf를 사용할 때의 단점을 잘 보여준다. 매번 알고리즘의 새로운 변형이 추가될 때마다 모든 알고리즘 변형이 상호 배제가 되도록 조건을 수정해주어야 한다는 것이다. 이와 달리 tag dispatching은 새로운 태그를 사용하여 오버로딩만 추가해주기만 하면 된다.

 

Tag dispatching과 EnableIf, 두 가지 기법은 서로 다른 문맥에서 유용하게 쓰일 수 있다. 일반적으로 tag dispatching은 계층 구조가 있는 태그에 기반을 두어 간단히 디스패치하는 기능을 제공하는 반면, EnableIf는 type traits로 알 수 있는 속성이라면 어떤 것이라도 사용하여 디스패치할 수 있다는 장점이 있다.

Where Does the EnableIf Go?

EnableIf는 보통 함수 템플릿의 반환 타입에 사용된다. 하지만 이와 같은 방식은 생성자 템플릿(constructor templates)이나 변환 함수 템플릿에서는 소용이 없다 (둘 다 명시된 반환 타입이 있기 때문). 뿐만 아니라 EnableIf를 리턴 타입 자리에 위치시키면 코드를 읽기 불편하다. 이런 경우에는 EnableIf를 기본 템플릿 인자에 내장시킬 수도 있다.

template<typename Iterator>
constexpr bool IsInputIterator =
    std::is_convertible<
        typename std::iterator_traits<Iterator>::iterator_category,
        std::input_iterator_tag
    >::value;

template<typename T>
class Container {
public:
    // construct from an input iterator sequence
    template<typename Iterator,
            typename = EnableIf<IsInputIterator<Iterator>>>
    Container(Iterator first, Iterator last);
    // convert to a container so long as the value types are convertible
    template<typename U, typename = EnableIf<std::is_convertible<T, U>::value>>
    operator Container<U>() const;
};

하지만 여기에도 문제는 있는데, 또 다른 오버로딩을 추가하려고 한다면 에러가 발생한다는 점이다.

// construct from an input iterator sequence
typename<typename Iterator,
        typename = EnableIf<IsInputIterator<Iterator> && !IsRandomAccessIterator<Iterator>>>
Container(Iterator first, Iterator last);

typename<typename Iterator,
        typename = EnableIf<IsRandomAccessIterator<Iterator>>>
Container(Iterator first, Iterator last);   // ERROR: redeclaration of constructor template

위 코드의 문제는 두 생성자 템플릿이 기본 템플릿 인자만 빼고 완전히 똑같은데, 두 템플릿이 동등한지 결정할 때 기본 템플릿 인자는 고려되지 않는다는 점이다. 이 문제는 아래와 같이 두 생성자 템플릿이 갖는 파라미터의 수가 다르도록 하여 해결할 수 있다.

// construct from an input iterator sequence
typename<typename Iterator,
        typename = EnableIf<IsInputIterator<Iterator> && !IsRandomAccessIterator<Iterator>>>
Container(Iterator first, Iterator last);

typename<typename Iterator,
        typename = EnableIf<IsRandomAccessIterator<Iterator>>,
        typename = int> // extra dummy parameter to enable both constructors
Container(Iterator first, Iterator last);   // OK now

 

Compile-Time If

C++17에서 도입된 constexpr을 사용하면 EnableIf를 사용하지 않고 구현할 수 있다. 예를 들어, C++17에서는 advanceIter()를 아래와 같이 구현할 수 있다.

template<typename Iterator, typename Distance>
void advanceIter(Iterator& x, Distance n) {
    if constexpr (IsRandomAccessIterator<Iterator>) {
        // implementation for random access iterators
        x += n;
    }
    else if constexpr (IsBidirectionalIterator<Iterator>) {
        // implementation for bidirectional iterators
        if (n > 0) {
            for (; n > 0; ++x, --n) {}
        }
        else {
            for (; n < 0; --x, ++n) {}
        }
    }
    else {
        // implementation for all other iterators that are at least input iterators
        if (n < 0) {
            throw "advanceIter(): invalid iterator category for negative n";
        }
        while (n > 0) {
            ++x;
            --n;
        }
    }
}

구현이 명백하다. 더 특수화된 코드 경로는 이를 지원하는 타입에 대해서만 인스턴스화된다. 따라서 모든 iterator에서 제공되는 연산을 포함하는 코드는 if constexpr 내에서 보호받는 것이 안전하다.

 

하지만 단점이 존재한다. 이는 오직 generic component 내에서의 차이점이 함수 템플릿 body에서 표현될 수 있을 때에만 사용할 수 있다. 따라서, 여전히 다음과 같은 경우에는 EnableIf가 필요하다.

• Different "interfaces" are involved
• Different class defintions are needed
• No valid instantiation should exist for certain template argument lists

Concepts

지금까지 살펴본 기법들은 잘 동작하지만 너무 장황하며, 코드를 읽기 힘들게 만든다. C++20에서는 이러한 기법들을 조금 더 간결하게 쓰기 위해서 concepts이라는 것을 도입했다. 이를 사용하면 Container의 생성자들을 다음과 같이 간단하게 작성할 수 있다.

template<typename T>
class Container {
public:
    // construct from an input iterator sequence
    template<typename Iterator>
    requires IsInputIterator<Iterator>
    Container(Iterator first, Iterator last);
    // construct from an random access iterator sequence
    template<typename Iterator>
    requires IsRandomAccessIterator<Iterator>
    Container(Iterator first, Iterator last);
    // convert to a container so long as the value types are convertible
    template<typename U>
    requires std::is_convertible_v<T, U>
    operator Container<U>() const;
};

requires는 템플릿의 요구 사항을 나타낸다. 요구 사항 중 하나라도 만족하지 못한다면 해당 템플릿은 후보군에서 제외된다. 따라서 EnableIf를 언어 자체에서 제공하는 기능으로 직접적으로 표현할 수 있다.

 

여기에는 또 다른 장점이 있는데, Constraint subsumption을 사용하여 요구 사항만 다른 템플릿들을 ordering 할 수 있어서 태그 디스패치가 필요 없게 된다. 또한 이는 템플릿이 아닌 다른 곳에서도 사용될 수 있는데, 예를 들어, 타입 T를 '<'로 비교할 수 있을 때에만 sort() 멤버 함수를 제공하도록 구현할 수 있다.

template<typename T>
class Container {
public:
    ...
    requires HasLess<T>
    void sort() {
        ...
    }
};

 

---

Class Specialization

클래스 템플릿의 partial specialization은 함수 템플릿 오버로딩과 마찬가지로 특정 템플릿 인자에 대한 클레스 템플릿의 대안을 제공하는 데 사용될 수 있다. 오버로드된 함수 템플릿과 마찬가지로 템플릿 인자의 속성을 기반으로 partial specialization을 구분하는 것이 합리적일 수 있다. key와 value type으로 사용하는 generic Dictionary 클래스 템플릿을 예시로 살펴보자. 간단하지만 비효율적인 Dictionary 구현은 key 타입이 equality operator만 제공한다면 구현할 수는 있다.

template<typename Key, typename Value>
class Dictionary {
private:
    std::vector<std::pair<Key const, Value>> data;
public:
    // subscripted access to the data
    Value& operator[](Key const& key) {
        // search for the element with this key
        for (auto& element : data) {
            if (element.first == key) {
                return element.second;
            }
        }
        // there is no element with this key; add one
        data.push_back(std::pair<Key const, Value>(key, Value()));
        return data.back().second;
    }
    ...
};

만약 Key 타입이 '<' 연산자를 지원한다면, 표준 라이브러리의 map 컨테이너를 기반으로 더 효율적인 구현을 제공할 수 있다. 비슷하게, 만약 Key 타입이 hashing 연산을 지원한다면 unordered_map을 기반으로 더 효율적인 구현을 제공할 수 있다.

 

Enabling/Disabling Class Templates

클래스 템플릿의 다른 구현은 활성화/비활성화하는 방법은 클래스 템플릿의 enabled/disabled partial specialization을 사용하는 것이다. 클래스 템플릿의 부분 특수화는 위에서 구현한 EnableIf와 HasLess, HasHash와 같은 type traits를 구현하여 작성할 수 있다.

template<typename Key, typename Value, typename = void>
class Dictionary
{
    ... // vector implementation as above
};

template<typename Key, typename Value>
class Dictionary<Key, Value,
                 EnableIf<HasLess<Key> && !HasHash<Key>>>
{
private:
    std::map<Key, Value> data;
public:
    Value& operator[](Key const& key) {
        return data[key];
    }
    ...
};

template<typename Key, typename Value>
class Dictionary<Key, Value,
                 EnableIf<HasHass<Key>>>
{
private:
    std::unordered_map<Key, Value> data;
public:
    Value& operator[](Key const& key) {
        return data[key];
    }
    ...
};

 

함수 템플릿과 달리 모든 partial specialization이 기본 템플릿보다 우선시 되기 때문에 기본 템플릿에서 어떤 조건도 비활성화할 필요가 없다. 다만, hashing 연산이 포함된 Key에 대한 또 다른 구현을 추가할 때는 partial specialization에 대한 조건이 상호 배타적인지 확인해야 한다.

Tag Dispatching for Class Templates

Tag dispatching 역시 클래스 템플릿의 partial specialization을 선택하는데 사용될 수 있다. 위에서 살펴본 advanceIter() 알고리즘과 유사한 함수 객체 타입을 이 방법으로 구현하면 다음과 같다. 여기에서는 iterator의 category_tag에 가장 적합한 것을 선택하기 위한 BestMatchInSet (구현은 아래에서 확인)을 사용하고 있다.

// primary template (intentionally undefined)
template<typename Iterator,
         typename Tag = BestMatchInSet<
                            typename std::iterator_traits<Iterator>::iterator_category,
                            std::input_iterator_tag,
                            std::bidirectional_iterator_tag,
                            std::random_access_iterator_tag>>
class Advance;

// general, linear-time implementation for input iterator
template<typename Iterator>
class Advance<Iterator, std::input_iterator_tag>
{
public:
    using DifferenceType = typename std::iterator_traits<Iterator>::difference_type;

    void operator()(Iterator& x, DifferenceType n) const {
        while (n > 0) {
            ++x;
            --n;
        }
    }
};
// bidirectional, linear-time algorithm for bidirectional iterator
template<typename Iterator>
class Advance<Iterator, std::bidirectional_iterator_tag>
{
public:
    using DifferenceType = typename std::iterator_traits<Iterator>::difference_type;

    void operator()(Iterator& x, DifferenceType n) const {
        if (n > 0) {
            while (n > 0) {
                ++x;
                --n;
            }
        }
        else {
            while (n < 0) {
                --x;
                ++n;
            }
        }
    }
};
// bidirectional, constant-time algorithm for random access iterator
template<typename Iterator>
class Advance<Iterator, std::random_access_iterator_tag>
{
public:
    using DifferenceType = typename std::iterator_traits<Iterator>::difference_type;

    void operator()(Iterator& x, DifferenceType n) const {
        x += n;
    }
};

위와 같은 구현은 함수 템플릿에서 사용한 tag dispatching과 매우 유사하지만, 문제는 주어진 iterator에 대해 일치하는 태그가 무엇인지 결정하는 BestMatchInSet trait를 작성하는 것이다. 본질적으로 이 trait는 iterator의 category_tag 값에 따라 어떤 오버로드가 선택되는지 알려주기 위한 것이다.

// construct a set of match() overloads for the types in Types...
template<typename... Types>
struct MatchOverloads;
// basis case: nothing matched
template<>
struct MatchOverloads<> {
    static void match(...);
};
// recursive case: introduce a new match() overload
template<typename T1, typename... Rest>
struct MatchOverloads<T1, Rest...> : public MatchOverloads<Rest...> {
    static T1 match(T1);    // introduce overload for T1
    using MatchOverloads<Rest...>::match;   // collect overloads from bases
};
// find the best match for T in Types...
template<typename T, typename... Types>
struct BestMatchInSetT {
    using Type = decltype(MatchOverloads<Types...>::match(declval<T>()));
};

template<typename T, typename... Types>
using BestMatchInSet = typename BestMatchInSetT<T, Types...>::Type;

 

---

Instantiation-Safe Templates

앞서 설명한 EnableIf 기법은 오직 템플릿 인자가 특정 조건을 만족할 때 특정 템플릿이나 partial specialization을 활성화시킨다. 예를 들어, advanceIter() 알고리즘의 가장 효율적인 형태는 iterator 인자의 카테고리가 std::random_access_iterator_tag로 변환될 수 있는지 체크하며, 이는 다양한 random-access iterator 연산들은 이 알고리즘을 이용할 수 있다는 것을 의미한다.

이러한 개념을 극단적으로 적용하여 템플릿이 템플릿 인자에 대해 수행하는 모든 연산을 EnableIf 조건의 일부로 넣어주면 어떻게 될까? 이런 템플릿의 인스턴스화는 결코 실패할 수 없다. 이는 필요한 연산을 제공하지 않는 템플릿 인자가 들어왔을 때 추론 시 실패하는 것일 뿐 인스턴스화가 이루어지진 않기 때문이다. 이러한 템플릿을 instantiation-safe template이라고 부른다.

 

이를 구현하기 위해서 먼저 두 값의 최솟값을 계산하는 min() 함수로 시작해보자. 템플릿으로 구현하면 일반적으로 아래와 같이 작성될 것이다.

template<typename T>
T const& min(T const& x, T const& y)
{
    if (y < x) {
        return y;
    }
    return x;
}

T 타입인 두 값을 비교하기 위해서 타입 T는 '<' 연산자를 가지고 있어야 한다. 그리고 그 비교 결과를 if문에서 사용할 수 있도록 암묵적으로 bool로 변환할 수 있어야 한다. 따라서 이를 체크하기 위해 아래의 LessResultT trait가 필요하다.

template<typename T1, typename T2>
class HasLess {
    template<typename T> struct Identity;
    template<typename U1, typename U2>
    static std::true_type test(Identity<decltype(std::declval<U1>() < std::declval<U2>())>*);
    template<typename U1, typename U2>
    static std::false_type test(...);
public:
    static constexpr bool value = decltype(test<T1, T2>(nullptr))::value;
};

template<typename T1, typename T2, bool HasLess>
class LessResultImpl {
public:
    using Type = decltype(std::declval<T1>() < std::declval<T2>());
};

template<typename T1, typename T2>
class LessResultImpl<T1, T2, false> {};

template<typename T1, typename T2>
class LessResultT : public LessResultImpl<T1, T2, HasLess<T1, T2>::value> {};

template<typename T1, typename T2>
using LessResult = typename LessResultT<T1, T2>::Type;

이를 std::is_convertible trait와 결합하면 min()을 instantiation-safe하도록 만들 수 있다.

template<typename T>
std::enable_if_t<std::is_convertible_v<LessResult<T const&, T const&>, bool>,
                 T const&>
min(T const& x, T const& y)
{
    if (y < x) {
        return y;
    }
    return x;
}

여러가지 '<' 연산자를 갖거나 아예 없는 다양한 타입에 대해서 테스트를 해보면 다음과 같다.

struct X1 {};
bool operator<(X1 const&, X1 const&) { return true; }

struct X2 {};
bool operator<(X2, X2) { return true; }

struct X3 {};
bool operator<(X3&, X3&) { return true; }

struct X4 {};

struct BoolConvertible {
    operator bool() const { return true; }
};

struct X5 {};
BoolConvertible operator<(X5 const&, X5 const&) {
    return BoolConvertible();
}

struct NotBoolConvertible {};

struct X6 {};
NotBoolConvertible operator<(X6 const&, X6 const&) {
    return NotBoolConvertible();
}

struct BoolLike {
    explicit operator bool() const { return true; }
};

struct X7 {};
BoolLike operator<(X7 const&, X7 const&) {
    return BoolLike();
}

int main()
{
    min(X1(), X1());    // X1 can be passed to min()
    min(X2(), X2());    // X2 can be passed to min()
    min(X3(), X3());    // ERROR: X3 cannot be passed to min()
    min(X4(), X4());    // ERROR: X4 cannot be passed to min()
    min(X5(), X5());    // X5 can be passed to min()
    min(X6(), X6());    // ERROR: X6 cannot be passed to min()
    min(X7(), X7());    // UNEXPECTED ERROR: X7 cannot be passsed to min()
}

위 코드를 컴파일하면 X3, X4, X6, X7에 대한 min() 호출에서 컴파일 에러가 발생한다. Non-instantiation-safe 버전처럼 min()의 body에서 에러가 나는 것이 아니라 적절한 min()을 찾을 수 없다고 출력한다 (error: no matching function for call to 'min'). 이는 유일하게 사용할 수 있는 후보군이 SFINAE로 제거되었기 때문이다.

따라서, std::enable_if<>는 템플릿의 요구 사항을 만족시키는 템플릿 인자(X1, X2, X5)에 대해서만 인스턴스화를 허용하며 min()의 body 내에서 에러가 발생하지 않는다. 그 뿐만 아니라 이들 타입에 대해 동작할 수 있는 min()의 오버로딩 버전이 있다면 overloading resolution에 따라서 다른 오버로딩 버전이 선택될 수 있다.

 

마지막에 사용된 X7 타입에 대해서 조금 더 살펴보자. 만약 non-instantiation-safe 버전의 min()에 X7 타입이 전달되었다면 인스턴스화는 성공할 것이다. 하지만 위에서 구현한 버전의 min()은 암묵적으로 BoolLike가 bool로 변환되지 않기 때문에 X7에 대해서 인스턴스화되지 않는다. 이 차이점은 꽤 미묘하다. Control-flow 명령문(if, while, for, do)과 built-in !, &&, || 연산자, 그리고 삼항 연산자 ?:에 사용된 boolean 조건과 같은 특정 문맥에서는 bool로 explicit을 써서 하는 변환이 암묵적으로 사용된다. 이런 상황에서는 문맥상 값이 bool로 변환되었다고 한다.

하지만 bool로의 일반적이고 암묵적(implicit)인 변환이 이루어지고 있어서 이번 instantiation-safe 템플릿이 지나치게 제약된다. 즉, 특정 (std::enable_if 내에 있는)요구 사항이 실제 (인스턴스화된 속성에서 필요한 것)요구 사항보다 더 강력한 것이다. 한 번 bool로의 변환에 대한 요구 사항을 완전히 제거해버리면 min() 템플릿은 underconstrained되어 일부 템플릿 인자에서는 인스턴스화 실패가 일어날 수 있다 (X6과 같이).

이를 수정하려면 타입 T가 bool로 문맥적으로 변환 가능한지 여부를 판단하는 trait이 필요하다. SFINAE 문맥에서는 구문(statement)이 실행될 수 없으므로 control-flow 문은 이를 정의할 때 도움이 되지 않는다. 다행히 삼항 연산자는 표현식(expression)이고, 오버로딩될 수 없으므로 삼항 연산자를 통해 bool로 문맥적으로 변환이 되는지 검사할 수 있다.

template<typename T>
class IsContextualBoolT {
    template<typename T> struct Identity;
    template<typename U>
    static std::true_type test(Identity<decltype(declval<U>() ? 0 : 1)>*);
    template<typename U>
    static std::false_type test(...);
public:
    static constexpr bool value = decltype(test<T>(nullptr))::value;
};

template<typename T>
constexpr bool IsContextualBool = IsContextualBoolT<T>::value;

이를 std::enable_if 내의 요구 사항으로 추가하여 instantiation-safe min()을 구현할 수 있다.

template<typename T>
std::enable_if_t<IsContextualBool<LessResult<T const&, T const&>>,
                 T const&>
min(T const& x, T const& y)
{
    if (y < x) {
        return y;
    }
    return x;
}

IsContextualBoolT에서 Identity 구조체의 typename T와 IsContextualBoolT의 typename T가 중복되어 shadows template parameter에러가 발생한다. Identity 구조체의 템플릿 파라미터 이름을 바꾸면 해당 에러는 발생하지 않지만, 모든 타입에 대해서 일치하는 후보군이 없다는 에러가 발생하고 있다. 이렇게 의도된 구현은 아닌 것으로 추정되나 어떻게 수정해야 될 지 아직 파악하지는 못한 상태이다.

 

여기서 min()을 instantiation-safe 한 형태로 만들기 위해 사용한 기법은 타입의 카테고리를 표현하는 trait 내 다양한 요구 사항을 결합하고 이런 trait을 std::enable_if 내에 조합하여 평범하지 않은 템플릿의 요구 사항을 표현하는 데 사용될 수 있다. 이렇게 구현하면 오비로딩 동작이 더 나아질 뿐만 아니라 에러가 발생했을 때 장황한 에러가 아니라 명확한 에러를 표출하도록 할 수 있어서 디버깅에도 좋다. 하지만 에러 메세지에서 어떤 연산이 실패했는지 구체적으로 지적하지 못할 수는 있다.