23.泛型编程下-尧图网络科技

复杂度（complexity）

复杂度描述了执行操作所需的时间，有三种可能性，从快到慢依次为：

编译时间（compile time）：操作在编译时执行，执行时间为 0；
固定时间（constant time）：操作发生在运行阶段，但独立于对象中的元素数目；
线性时间（linear time）：时间与元素数目成正比。

C++11 新增的容器要求

C++11 新增了通用容器要求：移动构造（X u(rv);，其中 rv 表示类型为 X 的非常量右值）与移动赋值（a = rv;），以及返回 const_iterator 的 cbegin()、cend() 等；并提高要求，X::iterator 须满足正向迭代器的要求（以前只要求它不是输出迭代器）。

序列（sequence）

只要是序列，就必须满足：数据排成一条直线，有头有尾，且顺序固定。

序列是对基本容器概念的一种重要改进，7 种 STL 容器类型（deque、C++11 新增的forward_list、list、queue、priority_queue、stack和vector）都是序列（array也被归类到序列容器，虽然它并不满足序列的所有要求）。

序列概念增加了迭代器至少是正向迭代器这样的要求，这样才能保证元素将按特定顺序排列，不会在两次迭代之间发生变化。

序列要求提供 a.insert(p, t)、a.erase(p) 等操作，其复杂度为固定时间的可选操作（如 push_front/push_back）仅在实现为固定时间时才提供。

“容器如果有 push_front 函数，那就说明它插头部非常快；如果它没有，强行插就会很慢，所以它干脆不提供这个函数。”

序列容器类型

7 种序列容器类型侧重：

vector：数组的类表示，提供自动内存管理、随机访问；尾部添加/删除元素固定时间，头部或中间插入/删除线性时间；是可反转容器概念模型（提供 rbegin()/rend()）；是最简单的序列类型，除非其他类型的特殊优点能更好满足需求，否则应默认使用它。
deque：双端队列，实现类似 vector、支持随机访问，主要区别是从开始位置插入/删除元素的时间固定；对象设计比 vector 复杂，中部操作时 vector 更快；多数操作发生在序列起始和结尾处时考虑使用。
list：双向链表，在链表中任一位置插入/删除的时间都是固定的，强调元素的快速插入和删除；与 vector 不同，不支持数组表示法和随机访问；插入/删除元素后链表迭代器指向的元素不变（vector 中会因移动元素而改变数据）；包含 merge()、remove()、sort()、splice()、unique() 等链表专用成员函数。
forward_list（C++11）：单链表，每个节点只链接到下一个节点；只需正向迭代器，是不可反转的容器；比 list 更简单、更紧凑，但功能更少。
queue：适配器类，让底层类（默认为 deque）展示典型的队列接口；限制比 deque 更多，不允许随机访问甚至遍历；只允许队尾添加、队首删除、查看队首队尾值、检查数目与是否为空。
priority_queue：适配器类，操作与 queue 相同，最大元素被移到队首；默认底层类是 vector；可通过可选构造函数参数修改比较方式。
stack：适配器类，给底层类（默认为 vector）提供典型栈接口；只允许压入/弹出栈顶、查看栈顶值、检查数目与是否为空。
array（C++11）：长度固定，并非 STL 容器；没有调整容器大小的操作（如 push_back()、insert()），但定义了 operator[] 和 at()；可将很多标准 STL 算法用于 array 对象。

关联容器（associative container）

关联容器是对容器概念的另一个改进，它将值与键（key）关联在一起，并使用键来查找值。

对关联容器而言，表达式 X::key_type 指出键的类型。关联容器的优点在于提供了对元素的快速访问。与序列相似，关联容器也允许插入新元素，但不能指定元素的插入位置。关联容器通常是使用某种树（tree）实现的——树是一种分支结构，像链表一样节点使添加或删除数据项比较简单，但相对于链表，树的查找速度更快。

STL 提供了 4 种关联容器：

set：的值类型与键相同且键唯一，即集合中不会有多个相同的键；
multiset ：类似但可能有多个值的键相同；
map ：中值与键的类型不同、键唯一，每个键只对应一个值；
multimap：与 map 相似，只是一个键可以与多个值相关联。

前两种在头文件 <set> 中定义，后两种在头文件 <map> 中定义。

map 的三种插入方式

map 支持三种插入方式：insert(pair<Key,Value>(...))、insert(map::value_type(...))、数组下标方式 m[key] = value

#include <map> std::map<int, std::string> m; m.insert(std::pair<int, std::string>(1, "one")); // 方式1：pair m.insert(std::map<int, std::string>::value_type(2, "two")); // 方式2 m[3] = "three"; // 方式3：数组下标

map 的 [] 运算符与 at()

map 重载了 [] 运算符用于按键取值/赋值：m[key] 在键不存在时插入默认值并返回其引用；at(key) 只取值，键不存在时抛出异常。

[] 语法直观方便，但"读不存在的键会静默插入"容易隐藏 bug；at() 提供严格检查的读取方式。

对不存在的键调用 at() 会抛出 out_of_range；[] 可用于修改和插入；multimap 因一键多值不支持 []。

std::map<int, std::string> m; m[1] = "one"; // 键不存在：插入 std::string s = m.at(1); // 读取：键不存在时抛出异常 // m.at(99); // 错误：键 99 不存在 → out_of_range

map 的查找与删除

map 提供 find(key)（返回迭代器，找不到返回 end()）、count(key)（返回键出现次数，map 中为 0 或 1）、erase(key/迭代器/区间)、lower_bound(key)（第一个键不小于 key 的位置）、upper_bound(key)（第一个键大于 key 的位置）、equal_range(key)（返回匹配区间的迭代器对）等操作。

关联容器按键自动排序，内部由二叉树实现，这些查找操作基于树结构，复杂度为对数时间，便于快速查找。

set 示例

set 底层通常是红黑树（平衡二叉搜索树）。

set 是关联集合，可反转、可排序，且键是唯一的，所以不能存储多个相同的值。与 vector 和 list 相似，set 使用模板参数指定要存储的值类型（如std::set<std::string> A;）；

template < class Key, // 第1个：元素类型（你填的 string） class Compare = std::less<Key>, // 第2个：比较函数（决定怎么排序） class Alloc = std::allocator<Key> // 第3个：内存分配器（几乎不用管） > class set;

set 有将迭代器区间作为参数的构造函数，可把集合初始化为数组内容。数学为集合定义了标准操作：并集、交集、差，STL 提供通用算法 set_union()、set_intersection()、set_difference() 支持，它们不是方法，但所有 set 对象都自动满足使用前提（容器经过排序）。

set有将迭代器区间作为参数的构造函数，可把集合初始化为数组内容。数学为集合定义了标准操作：并集、交集、差，

STL 提供通用算法 set_union()、set_intersection()、set_difference() 支持，它们不是方法，但所有 set 对象都自动满足使用前提（容器经过排序）。

规则（限制）：键唯一（重复值在集合中只出现一次）且集合被排序。set_union() 接受 5 个迭代器参数（两个区间 + 输出迭代器）。关联集合将键看作常量，所以 c.begin() 返回常量迭代器，不能用作输出迭代器；且 set_union() 会覆盖已有数据并要求容器足够大，空集合不满足——须用 insert_iterator 解决这两个问题。lower_bound(key) 返回指向第一个不小于键参数的成员的迭代器；upper_bound(key) 返回指向第一个大于键参数的成员的迭代器。

#include <set> // set 所在头文件 std::set<std::string> A; // 键唯一、可排序的字符串集合 // 第二个模板参数可选：指定排序比较函数/对象，默认 less<> // 可用区间构造函数从数组初始化：set<string> A(s1, s1 + N); // A.insert(s); // 只指定要插入的信息，不指定位置 // A.lower_bound(key); // 第一个不小于 key 的成员 // A.upper_bound(key); // 第一个大于 key 的成员 // 并/交/差用通用算法：set_union/set_intersection/set_difference

multimap 示例

与 set 相似，multimap 也是可反转的、经过排序的关联容器，但键和值的类型不同，且同一个键可能与多个值相关联。基本声明用模板参数指定键的类型和存储的值类型（如 std::multimap<int, std::string> codes;），

template < class Key, // 第1个：键的类型（如 int） class T, // 第2个：值的类型（如 string） class Compare = std::less<Key> // 第3个：比较规则（默认升序） > class multimap;

实际的存储节点的值类型将键类型和数据类型结合为一对，STL 用模板类 pair<T, U> 将这两种值存储到一个对象中——若 keytype 是键类型、datatype 是数据类型，则值类型为 pair<const keytype, datatype>。

规则（限制）：pair 对象用 first 和 second 成员访问两个部分。成员函数 count(key) 返回具有该键的元素数目；lower_bound()/upper_bound() 工作原理与 set 相同；equal_range(key) 返回两个迭代器（封装在 pair 对象中），表示与该键匹配的区间。因为数据项按键排序，所以不需要指出插入位置。

#include <map> // multimap 所在头文件 std::multimap<int, std::string> codes; // 键类型 int，值类型 string std::pair<const int, std::string> item(213, "Los Angeles"); // 键值对 // item.first / item.second // 访问键与值 // codes.insert(item); // 插入，无须指定位置 // codes.count(key); // 返回该键的元素数目 // codes.equal_range(key); // 返回匹配区间的两个迭代器

pair 模板

pair<T1, T2> 是定义在头文件 <utility> 中的结构体模板，把两个值（可以是不同类型）组合成一个对象，用公有成员 first 和 second 访问。

知识点	描述
泛型编程与面向对象编程的差异	OOP 关注数据方面，泛型编程关注算法；泛型编程旨在编写独立于数据类型的代码，工具是模板；STL 通过通用算法更进一步。
为何使用迭代器	模板使算法独立于数据类型，迭代器使算法独立于容器类型；数组/链表版`find`实现细节不同但算法相同，迭代器提供通用的遍历表示。
迭代器应具备的特征	支持`*p`解除引用、`p = q`赋值、`p == q`/`p != q`比较、`++p`/`p++`递增；常规指针满足全部要求。
为链表定义迭代器类	定义`operator`与前/后缀`operator++`；前缀返回`this`，后缀保存旧值返回副本；`int`形参区分前后缀且不使用。
超尾元素：要求转移到容器类	数组用超尾迭代器、链表用空值检测结尾；容器都提供超尾元素后两个`find`成为相同算法；对迭代器的要求变成对容器类的统一要求。
STL 的通用方法总结	算法用通用术语表达；定义满足算法需求的迭代器并把要求加到容器设计上；优先用 STL 函数与范围 for，避免直接写迭代器循环。
迭代器的五种类型	输入、输出、正向、双向、随机访问；查找需输入迭代器（`++`、可读），排序需随机访问迭代器（读写、可交换不相邻元素）；原型用迭代器类型标注需求。
输入迭代器	从程序角度“输入”：读取容器值不一定可修改；单向、单通行，不保证第二次遍历顺序不变、递增后旧值未必可解除引用；用于单通行只读算法。
输出迭代器	从程序角度“输出”：解除引用可修改容器值但不能读取；单通行只写；用于单通行只写算法。
正向迭代器	只用`++`向前遍历，总是按相同顺序；递增后保存旧值仍可解除引用得到相同值，支持多通行算法；可读写或只读（`const`）。
双向迭代器	正向迭代器全部功能 + 前缀/后缀`--`；支持反向遍历、首尾交换等算法。
随机访问迭代器	双向迭代器全部功能 +`a+n`/`a-n`/`a[n]`/`b-a`/关系比较；仅当`a`与`a+n`位于容器区间（含超尾）内合法；用于排序、二分检索。
迭代器层次结构与算法选用	输入/输出→正向→双向→随机访问逐级增强；算法用要求最低的迭代器以适用最大区间；高级别迭代器可用于低级别算法；`iterator`是类级 typedef，容器文档标注级别。
概念、改进和模型	概念（concept）是系列要求；改进（refinement）是概念上的继承（双向是对正向的改进）；模型（model）是概念的具体实现（`int*`是随机访问迭代器模型）。
将指针用作迭代器	指针满足所有迭代器要求；C++ 保证`Receipts+n`定义，支持数组超尾概念，STL 算法可用于常规数组；自定义数组提供迭代器与超尾即可。
copy() 算法	从输入迭代器区间复制到输出迭代器位置；可跨容器、跨数组复制；覆盖目标已有数据，目标须足够大，不能放入空矢量（除非用插入迭代器）。
ostream_iterator	输出迭代器概念的模型、适配器；把输出流包装成迭代器接口；模板参数为数据类型与字符类型，构造参数为输出流与分隔符；`*it++ = 15`即输出。
istream_iterator	输入迭代器概念的模型；使输入流可用作迭代器接口；省略构造参数表示输入失败；从输入流读取直到文件尾/类型不匹配/输入故障。
其他预定义迭代器	reverse_iterator（递增即递减，配合 rbegin/rend 反向遍历）；back_insert_iterator（尾插）、front_insert_iterator（前插，限固定时间前插容器）、insert_iterator（指定位置前插入）；三者把复制转换为插入并自动分配内存。
容器概念与容器类型	概念是通用类别（容器、序列容器、关联容器），类型是可创建对象的模板；基本容器概念规定所有容器类须满足的要求；数据为容器所有，类型须可复制构造、可赋值。
复杂度	编译时间（编译期执行，时间为 0）→固定时间（运行期、独立于元素数）→线性时间（与元素数成正比）；复杂度要求是 STL 特征，性能规格公开便于评估成本。
C++11 新增容器要求	移动构造/移动赋值（源可为临时对象，可转让所有权不做复制，效率更高）；`X::iterator`须满足正向迭代器要求（此前只要求非输出迭代器）。
序列（sequence）	对容器概念的改进：迭代器至少正向，元素按特定顺序排列且两次迭代间不变；严格线性顺序（有首尾、除首尾外各有一前驱一后继）；数组和链表是序列，分支结构不是。
序列容器类型	vector（随机访问、尾部固定/中部线性、默认选择）、deque（两端固定时间插入删除）、list（任意位置固定时间插入删除、双向链表、迭代器插入后指向元素不变）、forward_list（C++11 单链表、仅正向迭代器、不可反转）、queue/priority_queue/stack（适配器类，底层默认 deque/vector）、array（C++11，长度固定非 STL 容器，有`at()`边界检查）。
关联容器	用键查找值、快速访问；通常用树实现；set（键唯一、值即键）、multiset（可重复键）、map（键唯一、键值类型不同）、multimap（一键多值）；允许插入但不能指定位置。
set 示例	关联集合：可反转、可排序、键唯一（重复值只出现一次）；第二模板参数可选（默认`less<>`）；并/交/差由通用算法`set_union`等提供（须已排序）；`c.begin()`是常量迭代器、空集合不满足覆盖要求，须用`insert_iterator`；`lower_bound`/`upper_bound`求区间。
multimap 示例	键与值类型不同、一键可多值；实际值类型为`pair<const keytype, datatype>`，用`first`/`second`访问；`count()`返回某键元素数；`equal_range()`返回匹配区间的两个迭代器（封装在 pair 中）；插入无须指定位置。