泛型编程

泛型编程（generic programming）与面向对象编程的差异

泛型编程是一种与面向对象编程（object-oriented programming）截然不同的编程模式。面向对象编程关注的是编程的数据方面，而泛型编程关注的是算法

STL 通过通用算法（generic algorithm）不仅独立于容器中存储的数据类型，而且独立于容器本身的数据结构。

// 泛型编程：用模板使算法独立于数据类型 template <typename T> // T 为任意满足要求的类型 T add(const T& a, const T& b) { // 算法只依赖类型 T 的行为 return a + b; // 要求 T 支持 operator+ }

为何使用迭代器（iterator）

模板使得算法独立于存储的数据类型，而迭代器使算法独立于使用的容器类型——两者都是 STL 通用方法的重要组成部分。为数组和链表分别实现查找函数时，从实现细节上看两个算法不同（一个用数组下标遍历，一个把指针重置为 start->p_next）；但从广义上说，两个算法是相同的：将值依次与容器中的每个值进行比较，直到找到匹配为止。

泛型编程旨在使用同一个 find 函数处理数组、链表或任何其他容器类型，即函数不仅独立于存储的数据类型，而且独立于容器本身的数据结构。模板提供了数据类型的通用表示，因此还需要遍历容器中值的通用表示——迭代器正是这样的通用表示。

迭代器应具备的特征

要实现通用的 find 函数，迭代器应具备以下特征：应能对迭代器执行解除引用（dereference）操作，即若 p 是迭代器，应对 *p 进行定义；应能将一个迭代器赋给另一个，即若 p 和 q 都是迭代器，应对表达式 p = q 进行定义；应能将一个迭代器与另一个进行比较看是否相等，即应对 p == q 和 p != q 进行定义；应能使用迭代器遍历容器中的所有元素，这可通过为迭代器 p 定义 ++p 和 p++ 来实现。

注：常规指针就能满足迭代器的要求，因此可以把指针用作迭代器；STL 按功能的强弱定义了多种级别的迭代器。

// 用指针作为迭代器：常规指针满足全部迭代器要求 typedef double* iterator; // 指针即迭代器 ​ // 用两个区间指针重写查找：begin 指向起始，end 指向超尾 iterator find_arr(iterator begin, iterator end, const double& val) { for (iterator ar = begin; ar != end; ++ar) { // 遍历区间 [begin, end) if (*ar == val) // 解除引用比较值 return ar; // 找到：返回迭代器 } return end; // 未找到：返回超尾迭代器 }

为链表定义迭代器类

struct Node { // 链表节点 double item; // 节点数据 Node* p_next; // 指向下一节点 }; ​ class iterator { // 链表迭代器类 Node* pt; // 当前节点指针 public: iterator(Node* pn = nullptr) : pt(pn) {} // 构造函数 double& operator*() { return pt->item; } // 解除引用：返回节点数据 iterator& operator++() { // 前缀 ++ pt = pt->p_next; // 移到下一节点 return *this; // 返回自身 } iterator operator++(int) { // 后缀 ++（参数 int 不使用） iterator tmp = *this; // 保存旧值 pt = pt->p_next; // 移到下一节点 return tmp; // 返回旧值副本 } };

超尾元素：把要求从迭代器转移到容器类

数组版 find_arr 使用超尾迭代器（past-the-end iterator）检测结尾，链表版 find_ll 使用存储在最后一个节点中的空值检测结尾；除了这种差别外两个函数完全相同。可以让数组和链表都有超尾元素，并在迭代器到达超尾位置时结束搜索——这样两个 find 检测数据尾的方式将相同，从而成为相同的算法。

STL 遵循这一方法：每个容器类（vector、list、deque 等）定义相应的迭代器类型（可能是指针，也可能是对象），每个容器类都有超尾标记、begin() 和 end() 方法；begin() 返回指向第一个元素的迭代器、end() 返回指向超尾位置的迭代器。

// 各容器提供统一的 begin()/end() 接口与迭代器类型 // std::vector<double> scores; std::vector<double>::iterator pr; // vector 类作用域内的迭代器 typedef // for (pr = scores.begin(); pr != scores.end(); ++pr) // // 从第一个元素遍历到超尾位置 // 改用 std::list<double> 时唯一不同是 pr 的类型（list 的迭代器） // C++11 可用 auto pr = scores.begin(); 自动推断

六大组件概述

STL（Standard Template Library）提供六大组件：容器（containers）、算法（algorithms）、迭代器（iterators）、仿函数（functors）、配接器（adapters）、配置器（allocators），彼此可以组合套用。它不是面向对象的，主要依赖模板而非封装、继承和虚函数。

STL 的通用方法总结

STL 的通用方法分两步：

1. 处理容器的算法应尽可能用通用的术语来表达，使之独立于数据类型和容器类型； 如：同一份 sort 代码，不需要修改就能对 vector（连续内存）生效，也能对 list（链表）生效。

2. 即基于算法的要求，设计基本迭代器的特征和容器特征。不同的算法对“移动能力”的要求不同。 如：

   1. vector（数组）：内存连续，天生支持“随机跳跃”，所以它提供的迭代器是随机访问迭代器，满足 sort 的要求。

   2. list（链表）：内存不连续，只能一个一个节点找，不能跳跃。所以它提供的迭代器是双向迭代器。 C++ 标准库专门为 list 提供了一个专属的 list::sort（利用链表特性归并排序）

// 避免直接写迭代器循环，优先使用 STL 算法或范围 for // std::for_each(scores.begin(), scores.end(), Print); // 算法处理细节 // for (auto x : scores) // C++11 范围 for // // 依次访问每个元素

配接器（adapter）

配接器是一种用来修饰容器、仿函数或迭代器接口的组件，把一种接口转换成 STL 使用的另一种接口。

配接器不改变被包装组件的内部实现，只改变对外暴露的接口；配接器容器（stack/queue/priority_queue）因此不提供迭代器。

#include <stack> std::stack<int> stk; // 容器适配器：把底层 deque 包装成栈接口 // stk.push(x); stk.pop(); // 只提供栈操作，不支持随机访问与遍历

配置器（allocator）

定义（是什么）：配置器是负责空间配置与管理的类模板，实现动态空间配置、空间管理和空间释放，是 STL 的六大组件之一。

把内存分配策略从容器中分离出来，使容器代码不直接依赖 new/delete，可替换为内存池等更高效的分配策略。

容器模板的最后一个模板参数是分配器，默认 allocator<T>（内部使用 new 和 delete）；一般无需显式指定。

#include <vector> std::vector<int> v; // 省略分配器参数：默认 allocator<int> // template<class T, class Allocator = allocator<T>> class vector; // 分配器负责容器的动态内存申请与释放

迭代器的五种类型

STL 定义了 5 种迭代器：输入迭代器（input iterator）、输出迭代器（output iterator）、正向迭代器（forward iterator）、双向迭代器（bidirectional iterator）和随机访问迭代器（random access iterator）

因为不同的算法对迭代器的要求不同——查找算法需要定义 ++ 以便遍历整个容器，要求能读取数据但不要求能写数据；排序算法要求能随机访问以便交换两个不相邻的元素，且要求能读写数据。

// 算法原型用迭代器类型标注需求 template <class InputIterator, class T> InputIterator find(InputIterator first, InputIterator last, const T& value); // 需要输入迭代器：++ 遍历、可读、无需随机访问 ​ template <class RandomAccessIterator> void sort(RandomAccessIterator first, RandomAccessIterator last); // 需要随机访问迭代器：可读写、可交换不相邻元素

输入迭代器（input iterator）

输入迭代器的算法不会修改容器中的值。且必须能够访问容器中所有的值，这通过支持 ++ 运算符（前缀和后缀格式）实现。

对于单通行（single-pass）、只读算法，可以使用输入迭代器。

输入迭代器是单向迭代器，可以递增，但不能倒退。

输出迭代器（output iterator）

输出迭代器与输入迭代器相似，只是解除引用让程序能修改容器值，而不能读取。

可以修改发送到显示器的字符流，却不能读取屏幕上的内容；

对于单通行、只写算法，可以使用输出迭代器。输出迭代器也不能倒退。

正向迭代器（forward iterator）

与输入迭代器和输出迭代器相似，正向迭代器只使用 ++ 运算符来遍历容器，每次沿容器向前移动一个元素；但与输入、输出迭代器不同的是，它总是按相同的顺序遍历一系列值。将正向迭代器递增后，仍然可以对前面的迭代器值解除引用（如果保存了它），并可以得到相同的值。正向迭代器既可以使得能够读取和修改数据，也可以使得只能读取数据（如用 int* 表示读写迭代器、用 const int* 表示只读迭代器）

正向迭代器是单向前进的；读写能力由所指类型是否为 const 决定。

注：正向迭代器虽然是单向前进的，但会保存副本。所以仍然可以对前面的迭代器值解除引用。

双向迭代器（bidirectional iterator）

双向迭代器在正向迭代器的全部功能之上增加--p与p--。

随机访问迭代器（random access iterator）

随机访问迭代器具有双向迭代器的所有特性，同时添加了支持随机访问的操作（如指针加法运算）和用于对元素进行排序的关系运算符：a + n（指向 a 之后第 n 个元素）、a - n（指向 a 之前第 n 个元素）、r += n、r -= n、a[n]（等价于 *(a + n)）、b - a（结果为这样的 n 值：b == a + n）、以及 a < b、a > b、a <= b、a >= b 关系比较。

a + n这样的表达式仅当a和a+n都位于容器区间（包括超尾）内时才合法。

迭代器层次结构与算法选用

算法选用的“向下兼容”原则。“正向迭代器”具备“输入和输出迭代器的全部功能（方法）”；“双向”具备“正向的全部功能”；“随机访问”具备“双向的全部功能”。

注：“可以使用方法”≠ “可以自动类型转换”。