[C++] template value type extraction

各位如果翻開 STL container 的 document，應該會看到有一部分是寫 member type 的 document。其中應該會看到這樣的描述：

value_type : The first template parameter (T)

定義這種 type 其實用途不是為了 container 本身，而是為了使用這個 container 的 user，特別是使用這個 container 的地方是在 template class / function 時，定義這個 type 尤為重要，細節可以參考我之前寫的這篇。然而 C++ template 雖然可以讓程式撰寫上有更好的泛用性，但是因為需要做型態推導上，在使用上只要推導過程中會有疑義都會導致編譯失敗，也因此需要多做些手腳以便能夠順利編譯。這次要講的就是上次那篇 type function 的延伸

在進入主題前先來看個例子：假設今天要寫一個 function 是傳入一串數字，回傳值是這串數字的總合，我相信就算剛學寫程式沒多久的人都寫得出來這個版本 (這邊先假設傳進來的 type 都會是整數)

int computeSum(const int* val, const int count)
{
    int sum = 0;
    for(int i=0; i < count; ++i) { sum += val[i]; }
    return sum;
}

當然，只能是整數的話這重用性太低了，所以我們使用 template 來重寫一次：

template <typename T>
T computeSum(const T* val, const int count)
{
    T sum = T();
    for(int i=0; i < count; ++i) { sum += val[i]; }
    return sum;
}

好的，這樣就能針對各種不同的 type 了，但是這樣其實還有缺陷：如果傳進來的不是一般的 array 呢? 我想傳 vector 進來行不行? 只是計算總合的話，傳 linked list 進來應該也可以吧?

針對這些問題，我想只要參考 STL 的 document 就會知道答案了：參數不要傳 pointer 跟 array size，改成傳指向起點跟終點的 iterator，所以程式可以改寫成這樣：

template <typename Iterator, typename T>
T computeSum(Iterator first, Iterator last)
{
    T sum = T();
    for(Iterator iter=first; iter!=last; ++iter) { sum += *iter; }
    return sum;
}

這樣就可以傳任何種類的 container 進來了，不過還是有缺陷：這邊多用了一個 template parameter 把 container 中 element 的 type 傳進 function，但其實傳 iterator 進 function 時我們就該知道 element 的 type 了。針對這問題，STL 有 iterator_traits 可以讓我們做到這件事，所以這小程式可以進一步改寫成這樣：

template <typename Iterator>
typename std::iterator_traits<Iterator>::value_type computeSum(Iterator first, Iterator last)
{
    typedef typename std::iterator_traits<Iterator>::value_type value_type;
    value_type sum = value_type();
    for(Iterator iter=first; iter!=last; ++iter) { sum += *iter; }
    return sum;
}

前面提到的 value_type 就是用在類似這種地方上。這種做法其實也就跟之前我寫的這篇 type erasure 是相關的。

好的，雖然前言有點冗長，不過我們接下來要進入正題了。這次來考慮一個更複雜點的功能：如果 container 裡的 element 不是 primitive type 而是其他 user defined 的 structure 或 class 呢? 比方說是個像下面這樣的 structure：

template <typename T>
struct Coor
{
    T x, y;
    typedef T value_type;

    Coor(T val = T()) : x(val), y(val) {}
};

當然，為了方便說明與略過無謂的細節，我們先假設已經有 overload operator+= 了，絕對不是我想偷懶。這時後用 std::iterator_traits<Iterator>::value_type 獲得的會是 Coor<T>，但是我們要的是 T，在 function 中的寫法要改成 std::iterator_traits<Iterator>::value_type::value_type 才會是我們要的 T，所以程式上要做進一步的修改：

template <typename Iterator>
typename std::iterator_traits<Iterator>::value_type::value_type computeSum(Iterator first, Iterator last)
{
    typedef typename std::iterator_traits<Iterator>::value_type::value_type value_type;
    value_type sum = value_type();
    for(Iterator iter=first; iter!=last; ++iter) { sum += *iter; }
    return sum;
}

這段 code 如果直接拿去編譯是編不過的，因為 compiler 看到這行
typename std::iterator_traits<Iterator>::value_type::value_type 時不會認為這是一種型態，所以型態推導過程就出錯啦。解決方法其實也很簡單，多一層包裝就可以了。首先我們先定義一個 template struct：

template <typename T>
struct value_type
{
    typedef typename T::value_type type;
};

用途很簡單看傳進來的 type 是什麼，把他裡面定義好的 value_type 重新定義一次，如此一來我們可以把剛剛那個 function 重新改寫這樣：

template <typename Iterator>
typename value_type<typename std::iterator_traits<Iterator>::value_type>::type computeSum(Iterator first, Iterator last)
{
    typedef typename value_type<typename std::iterator_traits<Iterator>::value_type>::type value_type;
    value_type sum = value_type();
    for(Iterator iter=first; iter!=last; ++iter) { sum += *iter; }
    return sum;
}

好的，現在又浮出了另一個問題：primitive type 可不會定義 value_type 這種東西，這是 user-defined 的 structure / class 才會有的，所以這樣寫會變成無法運用到儲存 primitive type 的 container。

不過這也是有辦法可以解決的，只要改寫 value_type 這個 structure，讓他的 type 會隨著 T 是 structure / class 還是 primitive type 做出不同的定義即可。所以修改如下：

// 當 T 是 container 時，value 會是 true
// 反之，T 是 primitive type 時，value 是 false
template <typename T>
struct has_value_type
{
 typedef char true_type;
 typedef char false_type[2];

 //template not available if there's no nested value_type in U's scope
 template <class U>
 static true_type test(typename U::value_type*);

 //fallback
 template <class U>
 static false_type& test(...);

 //tests which overload of test is chosen for T
 static const bool value = sizeof(test<T>(0)) == sizeof(true_type);
};

// predeclaration for partial specialization
template <typename T, bool b>
struct value_type_impl;

// 這邊定義當 T 是 primitive type 時，type 就是 T 本身
template <typename T>
struct value_type_impl<T, false> //if T doesn't define value_type
{
 typedef T type;
};

// 如果 T 是個 structure / class，那麼 type 就該定義成 T::value_type
template <typename T>
struct value_type_impl<T, true> //if T defines value_type
{
 typedef typename T::value_type type;
};

// 接下來這個 structure 就會先將 T 丟給 has_value_type 去判斷是不是 primitive type
// 再根據 has_value_type 裡 value 的值去決定要繼承 value_type_impl<T, false> 還是 value_type_impl<T, true>
// 如此一來 value_type<T>::type 就會根據 T 是不是 primitive type 而有所變化
template <typename T>
struct value_type : value_type_impl<T, has_value_type<T>::value> {};

所以現在我們可以這樣寫了：

int main()
{
    // primitive type array
    int v1[] = {1, 2, 3, 4, 5};
    int sum1 = computeSum(v1, v1+5); 
 
    // vector
    std::vector<int> v2;
    for(int i=1; i < 5; ++i) { v2.push_back(i); }
    int sum2 = computeSum(v2.begin(), v2.end()); 
 
    // list
    std::list<double> v3;
    for(int i=1; i < 5; ++i) { v3.push_back(i); }
    int sum3 = computeSum(v3.begin(), v3.end()); 
 
    // Coor，當然，假設有 operload operator+=
    std::vector< Coor<unsigned> > v4;
    for(int i=1; i < 5; ++i) { v4.emplace(i); }
    int sum2 = computeSum(v4.begin(), v4.end()); 
 
    return 0;
}

本篇作法參考自這篇文章：
Can C++'s value_type be extended from iterator_traits to all types?

至於之前說的 overloading resolution 跟 name mangling 就讓我繼續拖稿吧XDD