泛型编程技巧
这是一份关于 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++ 表达式，对于表达式中涉及的对象，必须成功编译才能被认为是该概念的模型。
- 关联类型 是与建模类型相关的类型，因为它们参与一个或多个有效表达式。通常，可以通过建模类型的类定义中嵌套的类型定义来访问关联类型，或者通过 特性类 来访问它们。
- 不变量是对象在运行时的特性，必须始终为真，也就是说，涉及对象的函数必须保持这些特性。不变量通常采用先决条件和后决条件的形式。
- 复杂度保证是对有效表达式的执行时间或其计算将使用多少各种资源的最大限制。
C++ 标准库中使用的概念在 C++ 参考网站 上有记录。
特性
特性类提供了一种将信息与编译时实体（类型、整型常量或地址）关联起来的方法。例如，类模板 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>，它提供描述数值类型范围和功能的常量。
标签分派
标签分派是一种使用函数重载根据类型的属性进行分派的方法，并且经常与特性类一起使用。这种协同作用的一个很好的例子是 C++ 标准库中 std::advance() 函数的实现，该函数将迭代器递增 n 次。根据迭代器的类型，可以在实现中应用不同的优化。如果迭代器是 随机访问（可以向前和向后跳跃任意距离），那么 advance() 函数可以简单地用 i += n 实现，并且非常高效：常数时间。其他迭代器必须分步 advance，这使得操作与 n 成线性关系。如果迭代器是 双向的，那么 n 为负数是有意义的，因此我们必须决定是递增还是递减迭代器。
标签分派和特性类之间的关系是用于分派（在本例中为 iterator_category）的属性通常通过特性类访问。主要的 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。类型生成器通常用于将复杂的类型表达式合并为简单的类型表达式。此示例使用旧版本的 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 在其著作Modern C++ Design的 本章 中进行了详细探讨。他写道
简而言之，基于策略的类设计促进了使用许多小型类（称为策略）来组装具有复杂行为的类，每个类只处理一个行为或结构方面。顾名思义，策略建立了与特定问题相关的接口。只要您尊重策略接口，就可以以各种方式实现策略。
由于您可以混合和匹配策略，因此可以通过使用少量基本组件来实现组合行为集。
Andrei 对策略类的描述表明，它们的力量源于粒度和正交性。虽然在实践中，粒度较低的策略接口已被证明效果良好。本文档 描述了 iterator_adaptor 的旧版本，该版本使用了非正交策略。标准库中也有先例： std::char_traits 尽管其名称，但充当策略类，它决定了 std::basic_string 的行为。
注释
[1] 类型生成器有时被视为 C++ 中缺乏“模板类型定义”的解决方法。
