泛型编程泛型编程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::vectordouble scores; std::vectordouble::iterator pr; // vector 类作用域内的迭代器 typedef // for (pr scores.begin(); pr ! scores.end(); pr) // // 从第一个元素遍历到超尾位置 // 改用 std::listdouble 时唯一不同是 pr 的类型list 的迭代器 // C11 可用 auto pr scores.begin(); 自动推断六大组件概述STLStandard Template Library提供六大组件容器containers、算法algorithms、迭代器iterators、仿函数functors、配接器adapters、配置器allocators彼此可以组合套用。它不是面向对象的主要依赖模板而非封装、继承和虚函数。STL 的通用方法总结STL 的通用方法分两步处理容器的算法应尽可能用通用的术语来表达使之独立于数据类型和容器类型 如同一份 sort 代码不需要修改就能对 vector连续内存生效也能对 list链表生效。即基于算法的要求设计基本迭代器的特征和容器特征。不同的算法对“移动能力”的要求不同。 如vector数组内存连续天生支持“随机跳跃”所以它提供的迭代器是随机访问迭代器满足 sort 的要求。list链表内存不连续只能一个一个节点找不能跳跃。所以它提供的迭代器是双向迭代器。 C 标准库专门为 list 提供了一个专属的 list::sort利用链表特性归并排序// 避免直接写迭代器循环优先使用 STL 算法或范围 for // std::for_each(scores.begin(), scores.end(), Print); // 算法处理细节 // for (auto x : scores) // C11 范围 for // // 依次访问每个元素配接器adapter配接器是一种用来修饰容器、仿函数或迭代器接口的组件把一种接口转换成 STL 使用的另一种接口。配接器不改变被包装组件的内部实现只改变对外暴露的接口配接器容器stack/queue/priority_queue因此不提供迭代器。#include stack std::stackint stk; // 容器适配器把底层 deque 包装成栈接口 // stk.push(x); stk.pop(); // 只提供栈操作不支持随机访问与遍历配置器allocator定义是什么配置器是负责空间配置与管理的类模板实现动态空间配置、空间管理和空间释放是 STL 的六大组件之一。把内存分配策略从容器中分离出来使容器代码不直接依赖 new/delete可替换为内存池等更高效的分配策略。容器模板的最后一个模板参数是分配器默认 allocatorT内部使用 new 和 delete一般无需显式指定。#include vector std::vectorint v; // 省略分配器参数默认 allocatorint // templateclass T, class Allocator allocatorT 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和an都位于容器区间包括超尾内时才合法。迭代器层次结构与算法选用算法选用的“向下兼容”原则。“正向迭代器”具备“输入和输出迭代器的全部功能方法”“双向”具备“正向的全部功能”“随机访问”具备“双向的全部功能”。注“可以使用方法”≠ “可以自动类型转换”。迭代器类型拥有的“核心能力”方法/操作相比上一级新增的能力输入迭代器前移、*读取、/!比较——输出迭代器前移、*写入——正向迭代器、*读写、/!多趟通行保存旧副本依然有效 同时具备读写能力如果没有const双向迭代器正向的全部能力--后退一步随机访问迭代器双向的全部能力n/-n跳跃、[]下标访问、/比较大小