泛型编程技术
这是一个关于 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++ 表达式，为了使参与表达式的对象被认为是概念的模型，这些表达式必须成功编译。
- 关联类型 是与建模类型相关的类型，因为它们参与一个或多个有效表达式。通常，可以通过建模类型的类定义中嵌套的类型定义来访问关联类型，或者通过 Traits 类 来访问它们。
- 不变式是对象必须始终为真的运行时特性，也就是说，涉及对象的函数必须保留这些特性。不变式通常采取先决条件和后决条件的形式。
- 复杂性保证是对有效表达式的执行时间或其计算将使用多少资源的最大限制。
C++ 标准库中使用的概念记录在 C++ 参考网站 上。
Traits
Traits 类提供了一种将信息与编译时实体（类型、整型常量或地址）关联起来的方法。例如，类模板 std::iterator_traits<T> 看起来像这样
template <class Iterator>
struct iterator_traits {
typedef ... iterator_category;
typedef ... value_type;
typedef ... difference_type;
typedef ... pointer;
typedef ... reference;
};
Traits 的 `value_type` 为泛型代码提供了迭代器“指向”的类型，而 `iterator_category` 可用于根据迭代器的功能选择更有效的算法。
Traits 模板的一个关键特性是它们是非侵入式的：它们允许我们将信息与任意类型关联起来，包括内置类型和第三方库中定义的类型。通常，通过（部分）专门化 Traits 模板来为特定类型指定 Traits。
有关 `std::iterator_traits` 的深入描述，请参阅 此页面。标准中 Traits 习语的另一种非常不同的表达是 `std::numeric_limits<T>`，它提供描述数值类型范围和功能的常量。
标签分发
标签分发是一种使用函数重载根据类型的属性进行分发的方法，它通常与 Traits 类一起使用。这种协同作用的一个很好的例子是 C++ 标准库中 std::advance() 函数的实现，该函数将迭代器递增 `n` 次。根据迭代器的类型，可以在实现中应用不同的优化。如果迭代器是 随机访问 的（可以向前和向后跳转任意距离），那么 `advance()` 函数可以简单地用 `i += n` 实现，并且非常高效：常数时间。其他迭代器必须逐步 `advance`，使操作在 n 上呈线性关系。如果迭代器是 双向 的，那么 `n` 为负是有意义的，所以我们必须决定是递增还是递减迭代器。
标签分发和 Traits 类之间的关系是用于分发的属性（在本例中为 `iterator_category`）通常通过 Traits 类访问。主要的 `advance()` 函数使用 iterator_traits 类来获取 `iterator_category`。然后，它调用重载的 `advance_dispatch()` 函数。合适的 `advance_dispatch()` 由编译器根据 `iterator_category` 解析到的任何类型选择，无论是 input_iterator_tag、bidirectional_iterator_tag 还是 random_access_iterator_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);
}
}
适配器
适配器是一个类模板，它基于另一种类型或多种类型来提供新的接口或行为变体。标准适配器的示例包括 std::reverse_iterator，它通过反转其在递增/递减时的运动来适配迭代器类型，以及 std::stack，它适配容器以提供简单的堆栈接口。
可以在 此处 找到对标准中适配器的更全面的回顾。
类型生成器
注意：类型生成器的概念在很大程度上已被更精细的 元函数 概念所取代。有关元函数的深入讨论，请参阅C++ 模板元编程。
类型生成器是一个模板，其唯一目的是根据其模板参数[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
对象生成器
对象生成器是一个函数模板，其唯一目的是根据其参数构造一个新对象。可以将其视为一种泛型构造函数。当难以或不可能表达要生成的精确类型时，对象生成器可能比普通构造函数更有用，并且生成器的结果可以直接传递给函数，而不是存储在变量中。大多数 Boost 对象生成器都以 "make_" 为前缀命名，类似于 `std::make_pair(const T&, const U&)`。
例如，给定
struct widget {
void tweak(int);
};
std::vector<widget *> widget_ptrs;
通过链接两个标准对象生成器 `std::bind2nd()` 和 `std::mem_fun()`，我们可以轻松地调整所有小部件
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));
}
随着表达式的变得越来越复杂，减少类型规范冗余的需要也变得越来越迫切。
策略类
策略类是一个模板参数，用于传递行为。标准库中的一个示例是 `std::allocator`，它为标准 容器 提供内存管理行为。
Andrei Alexandrescu 在其著作《现代 C++ 设计》的 这一章 中详细探讨了策略类。他写道
简而言之，基于策略的类设计促进了使用许多小型类（称为策略）来组装具有复杂行为的类，每个类只处理一个行为或结构方面。顾名思义，策略建立了与特定问题相关的接口。只要尊重策略接口，就可以通过各种方式实现策略。
因为可以混合和匹配策略，所以可以通过使用少量基本组件来实现组合行为集。
Andrei 对策略类（policy classes）的描述表明，它们的强大之处源于粒度和正交性。但是，实践证明，粒度较低的策略接口也能很好地工作。 这篇论文描述了一个旧版本的iterator_adaptor，它使用了非正交策略。标准库中也有先例：std::char_traits，尽管它的名字如此，但它充当策略类，决定了std::basic_string的行为。
注释
[1] 类型生成器有时被视为C++中缺乏“模板化typedef”的一种变通方法。
