泛型编程技术
这是对 boost 库中使用的一些泛型编程技术的不完整调查。
目录
- 简介
- 概念的剖析
- 特性 (Traits)
- 标签分发 (Tag Dispatching)
- 适配器 (Adaptors)
- 类型生成器 (Type Generators)
- 对象生成器 (Object Generators)
- 策略类 (Policy Classes)
简介
泛型编程是关于通用化软件组件，以便它们可以在各种情况下轻松重用。在 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;
}
通过使用 void*， memcpy() 函数在某种程度上已经被通用化，因此该函数可以用于复制不同类型数据的数组。但是，如果我们想要复制的数据不在数组中怎么办？也许它在链表中。我们能否将复制的概念推广到任何元素序列？查看 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 访问，也可以通过 特性类 访问。
- 不变量是对象的运行时特征，必须始终为真，也就是说，涉及对象的功能必须保留这些特征。不变量通常采用前提条件和后置条件的形式。
- 复杂度保证是对执行其中一个有效表达式将花费多长时间或其计算将使用多少各种资源的最大限制。
C++ 标准库中使用的概念记录在 C++ 参考网站。
特性 (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>，它提供了描述数字类型的范围和功能的常量。
标签分发 (Tag Dispatching)
标签分发是一种使用函数重载根据类型的属性进行分发的方法，并且经常与 traits 类配合使用。这种协同作用的一个很好的例子是 C++ 标准库中 std::advance() 函数的实现，它将迭代器递增 n 次。根据迭代器的种类，可以在实现中应用不同的优化。如果迭代器是 随机访问（可以向前和向后跳转任意距离），那么 advance() 函数可以简单地使用 i += n 来实现，并且非常有效：常数时间。其他迭代器必须以步进方式 advance，使操作在线性时间内完成。如果迭代器是 双向的，那么 n 可以是负数，因此我们必须决定是递增还是递减迭代器。
标签分发和 traits 类之间的关系是，用于分发的属性（在本例中为 iterator_category）通常通过 traits 类访问。主 advance() 函数使用 iterator_traits 类来获取 iterator_category。然后它调用重载的 advance_dispatch() 函数。编译器根据 iterator_category 解析成的任何类型来选择适当的 advance_dispatch()，无论是 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);
}
}
适配器 (Adaptors)
适配器是一个类模板，它构建在另一个或多个类型之上，以提供新的接口或行为变体。标准适配器的示例包括 std::reverse_iterator，它通过反转其递增/递减时的运动来适配迭代器类型，以及 std::stack ，它适配容器以提供简单的堆栈接口。
有关标准中适配器的更全面的回顾可以在 此处 找到。
类型生成器 (Type Generators)
注意：类型生成器的概念在很大程度上已被更精细的 元函数概念所取代。有关元函数的深入讨论，请参阅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
对象生成器 (Object Generators)
对象生成器是一个函数模板，其唯一目的是从其参数构造一个新对象。可以将其视为一种通用构造函数。当要生成的准确类型难以或不可能表达，并且生成器的结果可以直接传递给函数而不是存储在变量中时，对象生成器可能比普通构造函数更有用。大多数 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));
}
随着表达式变得越来越复杂，减少类型规范的冗长性的需求变得更加迫切。
策略类 (Policy Classes)
策略类是一个模板参数，用于传输行为。标准库中的一个例子是 std::allocator，它为标准 容器提供内存管理行为。
Andrei Alexandrescu 在他的书Modern C++ Design的 这一章中详细探讨了策略类。他写道
简而言之，基于策略的类设计促进了用许多小类（称为策略）组装具有复杂行为的类，每个类只负责一个行为或结构方面。顾名思义，策略建立了与特定问题相关的接口。只要你遵守策略接口，你就可以通过各种方式实现策略。
因为你可以混合和匹配策略，所以你可以通过使用少量基本组件来实现行为的组合集。
Andrei 对策略类的描述表明，他们的力量源于粒度和正交性。尽管如此，较少粒度的策略接口已在实践中证明效果良好。 这篇论文描述了 iterator_adaptor 的旧版本，该版本使用了非正交策略。标准库中也有先例： std::char_traits，尽管它的名字，但它充当一个策略类，决定了 std::basic_string 的行为。
注释
[1] 类型生成器有时被视为解决 C++ 中缺少“模板 typedef”的变通方法。
