泛型程式設計技巧
這是一份關於 Boost 函式庫中使用的一些泛型程式設計技巧的不完整調查。
目錄
簡介
泛型程式設計的重點在於將軟體組件泛化，以便在各種情況下輕鬆重複使用。在 C++ 中，類別和函式模板是泛型程式設計的有效機制，因為它們在不犧牲效率的情況下實現了泛化。
作為泛型程式設計的一個簡單範例，我們將探討如何泛化 C 標準函式庫中的 memcpy() 函式。 memcpy() 的一個實作可能如下所示
void* memcpy(void* region1, const void* region2, size_t n)
{
const char* first = (const char*)region2;
const char* last = ((const char*)region2) + n;
char* result = (char*)region1;
while (first != last)
*result++ = *first++;
return result;
}
memcpy() 函式已經透過使用 void* 進行了一定程度的泛化，因此該函式可以用於複製不同種類資料的陣列。但是，如果我們要複製的資料不在陣列中呢？也許它在一個連結串列中。我們可以將複製的概念泛化到任何元素序列嗎？觀察 memcpy() 的主體，該函式的最低要求是它需要使用某種指標來遍歷序列、存取指向的元素、將元素寫入目的地，以及比較指標以了解何時停止。C++ 標準函式庫將這些要求歸納為概念，在本例中是輸入迭代器概念（針對 region2）和輸出迭代器概念（針對 region1）。
如果我們將 memcpy() 重寫為函式模板，並使用輸入迭代器和輸出迭代器概念來描述模板參數的要求，我們可以透過以下方式實作一個高度可重複使用的 copy() 函式
template <typename InputIterator, typename OutputIterator>
OutputIterator
copy(InputIterator first, InputIterator last, OutputIterator result)
{
while (first != last)
*result++ = *first++;
return result;
}
使用泛型 copy() 函式，我們現在可以從任何類型的序列中複製元素，包括匯出迭代器的連結串列，例如 std::list。
#include <list>
#include <vector>
#include <iostream>
int main()
{
const int N = 3;
std::vector<int> region1(N);
std::list<int> region2;
region2.push_back(1);
region2.push_back(0);
region2.push_back(3);
std::copy(region2.begin(), region2.end(), region1.begin());
for (int i = 0; i < N; ++i)
std::cout << region1[i] << " ";
std::cout << std::endl;
}
概念剖析
一個概念是一組需求，包含有效的表達式、關聯型別、不變量和複雜度保證。滿足這些需求的型別被稱為模型化該概念。一個概念可以擴展另一個概念的需求，這稱為精煉。
- 有效的表達式是指 C++ 表達式，這些表達式必須針對表達式中涉及的物件成功編譯，才能被視為概念的模型。
- 關聯型別是指與模型化型別相關的型別，它們參與一個或多個有效表達式。通常，關聯型別可以透過模型化型別的類別定義中巢狀的 typedef 進行存取，或者透過特性類別進行存取。
- 不變量是物件的執行時期特性，這些特性必須始終為真，也就是說，涉及物件的函式必須保留這些特性。不變量通常採用前置條件和後置條件的形式。
- 複雜度保證（Complexity Guarantees）指的是對於一個有效表達式執行時間或其計算所使用各種資源量的最大限制。
C++ 標準函式庫中使用的概念可以在 C++ 參考網站 找到說明。
特性
特性類別（Traits Class）提供一種將資訊與編譯時期實體（類型、整數常數或地址）關聯起來的方法。例如，類別模板 std::iterator_traits<T> 看起來像這樣：
template <class Iterator>
struct iterator_traits {
typedef ... iterator_category;
typedef ... value_type;
typedef ... difference_type;
typedef ... pointer;
typedef ... reference;
};
特性類別的 value_type 為泛型程式碼提供迭代器「指向」的類型，而 iterator_category 可用於根據迭代器的功能選擇更有效的演算法。
特性模板的一個關鍵特性是它們是*非侵入式*的：它們允許我們將資訊與任意類型關聯，包括內建類型和第三方程式庫中定義的類型。通常，特性是通過（部分）特化特性模板來為特定類型指定的。
關於 std::iterator_traits 的詳細說明，請參閱此頁面。標準中另一個非常不同的特性慣用法表達是 std::numeric_limits<T>，它提供描述數值類型範圍和功能的常數。
標籤分派
標籤分派（Tag Dispatching）是一種使用函式多載根據類型的屬性進行分派的方法，並且經常與特性類別一起使用。這種協同作用的一個很好的例子是 C++ 標準函式庫中 std::advance() 函式的實現，該函式將迭代器遞增 n 次。根據迭代器的類型，可以在實現中應用不同的最佳化。如果迭代器是隨機存取（可以向前和向後跳躍任意距離），則 advance() 函式可以簡單地用 i += n 實現，並且非常有效率：常數時間。其他迭代器必須以步進方式遞增，使操作時間與 n 成線性關係。如果迭代器是雙向的，那麼 n 為負數是有意義的，因此我們必須決定是遞增還是遞減迭代器。
標籤分派和特性類別之間的關係是，用於分派的屬性（在這種情況下是 iterator_category）通常是通過特性類別存取的。主要的 advance() 函式使用 iterator_traits 類別來獲取 iterator_category。然後它呼叫多載的 advance_dispatch() 函式。編譯器根據 iterator_category 解析的類型（input_iterator_tag、bidirectional_iterator_tag 或 random_access_iterator_tag）來選擇適當的 advance_dispatch()。標籤（Tag）只是一個類別，其唯一目的是傳達一些屬性，用於標籤分派和類似技術。有關迭代器標籤的更詳細說明，請參閱此頁面。
namespace std {
struct input_iterator_tag { };
struct bidirectional_iterator_tag { };
struct random_access_iterator_tag { };
namespace detail {
template <class InputIterator, class Distance>
void advance_dispatch(InputIterator& i, Distance n, input_iterator_tag) {
while (n--) ++i;
}
template <class BidirectionalIterator, class Distance>
void advance_dispatch(BidirectionalIterator& i, Distance n,
bidirectional_iterator_tag) {
if (n >= 0)
while (n--) ++i;
else
while (n++) --i;
}
template <class RandomAccessIterator, class Distance>
void advance_dispatch(RandomAccessIterator& i, Distance n,
random_access_iterator_tag) {
i += n;
}
}
template <class InputIterator, class Distance>
void advance(InputIterator& i, Distance n) {
typename iterator_traits<InputIterator>::iterator_category category;
detail::advance_dispatch(i, n, category);
}
}
配接器
一個*配接器 (adaptor)* 是一個類別樣板，它基於另一種或多種類型來提供新的介面或行為變體。標準配接器的例子有 std::reverse_iterator，它通過反轉遞增/遞減時的移動來調整迭代器類型，以及 std::stack，它調整容器以提供簡單的堆疊介面。
更全面的標準配接器回顧可以在這裡找到。
型別產生器
**注意：***類型產生器 (type generator)* 的概念很大程度上已被更精確的 元函數 (metafunction) 概念所取代。有關元函數的深入討論，請參閱 *C++ Template Metaprogramming*。
一個*類型產生器* 是一個樣板，其唯一目的是根據其樣板參數合成一個或多個新類型[1]。生成的類型通常表示為一個名為 type 的巢狀 typedef。類型產生器通常用於將複雜的類型表達式合併成一個簡單的表達式。這個例子使用了一個舊版本的 iterator_adaptor，其設計不允許派生迭代器類型。因此，每個經過調整的迭代器都必須是 iterator_adaptor 本身的特化，而產生器是產生這些類型的一種便捷方式。
template <class Predicate, class Iterator,
class Value = complicated default,
class Reference = complicated default,
class Pointer = complicated default,
class Category = complicated default,
class Distance = complicated default
>
struct filter_iterator_generator {
typedef iterator_adaptor<
Iterator,filter_iterator_policies<Predicate,Iterator>,
Value,Reference,Pointer,Category,Distance> type;
};
現在，這很複雜，但使用產生器產生一個經過調整的過濾迭代器要容易得多。通常你只需寫
boost::filter_iterator_generator<my_predicate,my_base_iterator>::type
物件產生器
一個*物件產生器 (object generator)* 是一個函數樣板，其唯一目的是根據其參數構造一個新物件。把它想像成一種泛型建構函式。當難以或不可能表達要產生的確切類型，並且產生器的結果可以直接傳遞給函數而不是儲存在變數中時，物件產生器可能比普通的建構函式更有用。大多數 Boost 物件產生器都以 "make_" 作為前綴命名，仿照 std::make_pair(const T&, const U&)。
例如，給定
struct widget {
void tweak(int);
};
std::vector<widget *> widget_ptrs;
通過鏈接兩個標準物件產生器，std::bind2nd() 和 std::mem_fun()，我們可以輕鬆地調整所有 widgets
void tweak_all_widgets1(int arg)
{
for_each(widget_ptrs.begin(), widget_ptrs.end(),
bind2nd(std::mem_fun(&widget::tweak), arg));
}
如果不使用物件產生器，上面的例子會像這樣
void tweak_all_widgets2(int arg)
{
for_each(struct_ptrs.begin(), struct_ptrs.end(),
std::binder2nd<std::mem_fun1_t<void, widget, int> >(
std::mem_fun1_t<void, widget, int>(&widget::tweak), arg));
}
隨著表達式變得越來越複雜，減少類型規範的冗長性的需求也變得越來越迫切。
策略類別
策略類別 (policy class) 是一種用於傳遞行為的樣板參數。標準程式庫中的一個例子是 std::allocator，它為標準 容器 提供記憶體管理行為。
Andrei Alexandrescu 在他的著作 *Modern C++ Design* 的這一章中詳細探討了策略類別。他寫道
簡而言之，基於策略的類別設計促進了用許多小類別（稱為策略）組裝具有複雜行為的類別，每個小類別只負責一個行為或結構方面。顧名思義，策略建立了與特定問題相關的介面。只要遵守策略介面，就可以用各種方式來實現策略。
因為您可以混合和匹配策略，所以您可以通過使用少量基本組件來實現組合行為集。
Andrei 對策略類別的描述表明，它們的能力源自於粒度和正交性。然而，實務上已證明，粒度較低的策略介面也能良好運作。這篇論文描述了舊版本的 iterator_adaptor，它使用了非正交策略。標準函式庫中也有先例：std::char_traits 儘管其名稱如此，但它實際上作為一個策略類別，決定了 std::basic_string 的行為。
註釋
[1] 類型產生器有時被視為 C++ 缺少「樣板化 typedef」的變通方案。
