# 型別特性上進行多載
---
## 多載與 **Type Trait**
---
```cpp
template<typename T> void f(T*);
template<typename T> void f(Array<T>);
```
```cpp
// only for numbers
template<typename Number> void f(Number);
// only for container
template<typename Container> void f(Container);
```
---
## 我們如何基於型別特性來模擬出 function template 的多載呢？
---
# Overview
* Algorithm Specialization
* Tag Dispatching
* Enabling/Disabling Function Templates
* Class Specialization
* Instantiation-Safe Templates
---
## Algorithm Specialization
### 使用演算法中更 specialized 的版本
---
```cpp
template<typename T> void swap(T& x, T& y)
{
T tmp(x);
x = y;
y = tmp;
}
```
---
```cpp
template<typename T>
void swap(Array<T>& x, Array<T>& y)
{
swap(x.ptr, y.ptr);
swap(x.len, y.len);
}// note: a better option for swap() is move()
```
---
根據 C++ 的 **partial ordering rule**, 當兩者皆符合時, compiler 會選擇更特例化的那組
---
```cpp
template<typename InputIterator, typename Distance>
void advance(InputIterator& x, Distance n)
{
while (n-- > 0) ++x; // linear time
}
template<typename RandomAccessIterator, typename Distance>
void advance(RandomAccessIterator& x, Distance n)
{
x += n; // constant time
}
```
---
### /usr/include/c++/5/bits/stl_iterator_base_funcs.h
---
```cpp
template<typename _InputIterator, typename _Distance>
inline void __advance(_InputIterator& __i,
_Distance __n,
input_iterator_tag)
{
__glibcxx_function_requires(
_InputIteratorConcept<_InputIterator>
)
while (__n--) ++__i;
}
```
---
```cpp
template<typename _RandomAccessIterator, typename _Distance>
inline void __advance(_RandomAccessIterator& __i,
_Distance __n,
random_access_iterator_tag)
{
__glibcxx_function_requires(
_RandomAccessIteratorConcept<_RandomAccessIterator>
)
__i += __n;
}
```
---
### Yes! ***tag***
---
## Tag Dispatching
<style>
code.orange {
color: #F7A004 !important;
}
</style>
### 使用一個<code class="orange">獨特的型別</code>來辨識不同的實作版本
---
```cpp
template<typename InputIterator, typename Distance>
void advanceImpl(InputIterator& x, Distance n,
std::input_iterator_tag) // this is it!!
{
while (n-- > 0) ++x; // linear time
}
```
```cpp
template<typename RandomAccessIterator, typename Distance>
void advanceImpl(RandomAccessIterator& x, Distance n,
std::random_access_iterator_tag) // this is it!!
{
x += n; // constant time
}
```
---
```cpp
template<typename Iterator, typename Distance>
void advance(Iterator& x, Distance n) // no aware of tag
{
advanceImpl(x, n,
typename std::iterator_traits<Iterator>
::iterator_category());
}
```
---
### Trait Class
* /usr/include/c++/5/bits/stl_iterator_base_types.h
* /usr/include/c++/5/bits/stl_iterator.h
* /usr/include/c++/5/bits/stream_iterator.h
---
```cpp
class istream_iterator
: public iterator<input_iterator_tag, _Tp, _Dist, const _Tp*, const _Tp&>
{
//...略
}
```
```cpp
template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
typename _Pointer = _Tp*, typename _Reference = _Tp&>
struct iterator
{
/// One of the @link iterator_tags tag types@endlink.
typedef _Category iterator_category;
//...略
}
```
```cpp
template<typename _Iterator>
struct iterator_traits
{
typedef typename _Iterator::iterator_category iterator_category;
//...略
}
```
---
### Tag Dispatching 為何有效?
#### >>在於 tag 彼此的關係<<
因為有繼承關係, compiler 選擇更加特例化的那個
---
<style>
code.orange {
color: #F7A004 !important;
}
</style>
### 所以當 tag 彼此間有特殊關係, Tag Dispatching 是一個很好的選擇
### 但是如果你需要的是<code class="orange">更特別</code>的屬性呢?
E.g. T 是不是有 trivial copy assignment operator?
---
## Enabling/Disabling Function Templates
---
### 透過 EnableIf alias template 來達到在某些特定條件下啟用或停用特定的 function
---
```cpp
template<typename Iterator>
constexpr bool IsRandomAccessIterator =
IsConvertible<
typename std::iterator_traits<Iterator>::iterator_category,
std::random_access_iterator_tag
>;
template<typename Iterator, typename Distance>
EnableIf<IsRandomAccessIterator<Iterator>> // 產生 return type: void
advanceIter(Iterator& x, Distance n) {
x += n; // constant time
}
```
---
EnableIf 的兩個參數
1. 布林條件式: 指出何時 template 應啟用
2. EnableIf 在 true 時，回傳的型別
Example: [EnableIf](https://github.com/romanticamaj/tmplbook/blob/master/typeoverload/enableif.hpp)
---
* 當條件 true:
* 取出 `EnableIfT::Type` 作為 type
* 當條件 false:
* `EnableIfT::Type` 不存在...
### SFINAE!
---
### 還少一件事, 需要 `de-activate` less specialized 的 template
(因為 compiler 無從得知他們的 order)
---
### How?
### ***Negate*** 布林條件式
---
```cpp
template<typename Iterator, typename Distance>
EnableIf<!IsRandomAccessIterator<Iterator>> // 產生 return type: void
advanceIter(Iterator& x, Distance n)
{
while (n-- > 0) ++x; // linear time
}
```
---
### 提供多種特例實作
Example: [advance2](https://github.com/romanticamaj/tmplbook/blob/master/typeoverload/advance2.hpp)
---
### 比較 Tag Dispatching 與 EnableIf
Tag Dispatching 依賴繼承關係, 實作簡單 (open-closed)
EnableIf 需要維持所有條件 mutual exclusive, 但是可針對特定條件開選擇
---
### 討論: EnableIf 該放哪？
Example: [container1](https://github.com/romanticamaj/tmplbook/blob/master/typeoverload/container1.hpp)
`作為一個 defaulted template argument`
---
### 考慮再加上一個 overload ctor...
---
```cpp
// construct from an input iterator sequence
template<typename Iterator,
typename = EnableIf<IsInputIterator<Iterator> &&
!IsRandomAccessIterator<Iterator>>
>
Container(Iterator first, Iterator last);
// Error: redeclaration of constructor template
template<typename Iterator,
typename = EnableIf<IsRandomAccessIterator<Iterator>>
>
Container(Iterator first, Iterator last);
```
---
兩個 template 完全一樣,
因為 default 值不會列入考慮
solution:
```cpp
// construct from an input iterator sequence
template<typename Iterator,
typename = EnableIf<IsInputIterator<Iterator> &&
!IsRandomAccessIterator<Iterator>>
>
Container(Iterator first, Iterator last);
template<typename Iterator,
typename = EnableIf<IsRandomAccessIterator<Iterator>>
typename = int> // extra dummy template parameter
Container(Iterator first, Iterator last);
```
---
### 看點新東西: C++17 Compile-Time if
---
#### C++17 的 `constexpr if`
Example: [advance3](https://github.com/romanticamaj/tmplbook/blob/master/typeoverload/advance3.hpp)
* 好處: 省下多次使用 EnableIf, 可讀性更高
* 缺點: 只有差異在 function body 才可行
---
### 再來點新東西: C++20 Concepts
---
* Example: [container4](https://github.com/romanticamaj/tmplbook/blob/master/typeoverload/container4.hpp)
* [Constraints and concepts](https://en.cppreference.com/w/cpp/language/constraints) from cppreference.com
---
## Class Specialization
---
```cpp
template<typename Key, typename Value>
class Dictionary {
private:
vector<pair<Key const, Value>> data;
public:
Value& operator[](Key const& key) {
for (auto& element: data)
if (element.first == key)
return element.second;
data.push_back(pair<Key const, Value>(key, Value()));
return data.back().second;
}
// others
}
```
---
### Enabling/Disabling style
Example: [Enable/Disable Class Template](https://gist.github.com/romanticamaj/9c7aca0296e17b9c197f1a1188f59fa1)
---
### Tag Dispatching style
Example: [Tag Dispatching class Template](
https://gist.github.com/romanticamaj/8d060ee0cda6bb7058330aefd893a335)
---
## Instantiation-Safe Templates
---
### 想法: 直接把對型別參數的操作帶入到 EnableIf 的布林條件式中
考慮:
```cpp
template<typename T>
T const& min(T const& x, T const& y)
{
if (y < x) return y;
return x;
}
```
---
Step 1: [lessresult](
https://github.com/romanticamaj/tmplbook/blob/master/typeoverload/lessresult.hpp)
Step 2: [min2](https://github.com/romanticamaj/tmplbook/blob/master/typeoverload/min2.hpp
)
Step 3: [min usage](https://github.com/romanticamaj/tmplbook/blob/master/typeoverload/min.cpp)
---
### 唔...overconstrained...
Step 4: [iscontextualbool](https://github.com/romanticamaj/tmplbook/blob/master/typeoverload/iscontextualbool.hpp)
Step 5: [min3](https://github.com/romanticamaj/tmplbook/blob/master/typeoverload/min3.hpp)
---
## In the Standard Library
* `std::iterator_traits`
* `std::enable_if`
* `std::advance` 與 `std::distance` 使用 tag dispatch 或 enable_if 達到 algorithm specialization
* `std::copy`, `std::fill`, 當型別具有 trivial copy-assignment operator 呼叫 std::memset
* 多個演算法避免呼叫 dtor, 當型別具有 trivial destructor
Note:
1. /usr/include/c++/5/bits/stl_algobase.h:384
1. /usr/include/c++/5/bits/stl_algobase.h:723
---
### 總歸一句, 規格書沒規定不行, 而函式庫實作者想讓這些特別的 case 更有效率
---
### Tag Dispatching 已經出現在 C++ 上一段時間, enable_if 相對較新, 而未來 concept 會取代 enable_if
---
# 型別特性上進行多載
{"metaMigratedAt":"2023-06-15T00:43:33.574Z","metaMigratedFrom":"YAML","title":"型別特性上進行多載","breaks":true,"description":"如何使用多種技巧透過型別達到多載 (已搬到 Notion)","contributors":"[{\"id\":\"7d1bb91f-3f52-445b-909e-af378dea87e7\",\"add\":13857,\"del\":4927}]"}