复杂度complexity复杂度描述了执行操作所需的时间有三种可能性从快到慢依次为编译时间compile time操作在编译时执行执行时间为 0固定时间constant time操作发生在运行阶段但独立于对象中的元素数目线性时间linear time时间与元素数目成正比。C11 新增的容器要求C11 新增了通用容器要求移动构造X u(rv);其中 rv 表示类型为 X 的非常量右值与移动赋值a rv;以及返回 const_iterator 的 cbegin()、cend() 等并提高要求X::iterator 须满足正向迭代器的要求以前只要求它不是输出迭代器。序列sequence只要是序列就必须满足数据排成一条直线有头有尾且顺序固定。序列是对基本容器概念的一种重要改进7 种 STL 容器类型deque、C11 新增的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_listC11单链表每个节点只链接到下一个节点只需正向迭代器是不可反转的容器比 list 更简单、更紧凑但功能更少。queue适配器类让底层类默认为 deque展示典型的队列接口限制比 deque 更多不允许随机访问甚至遍历只允许队尾添加、队首删除、查看队首队尾值、检查数目与是否为空。priority_queue适配器类操作与 queue 相同最大元素被移到队首默认底层类是 vector可通过可选构造函数参数修改比较方式。stack适配器类给底层类默认为 vector提供典型栈接口只允许压入/弹出栈顶、查看栈顶值、检查数目与是否为空。arrayC11长度固定并非 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(pairKey,Value(...))、insert(map::value_type(...))、数组下标方式 m[key] value#include map std::mapint, std::string m; m.insert(std::pairint, std::string(1, one)); // 方式1pair m.insert(std::mapint, std::string::value_type(2, two)); // 方式2 m[3] three; // 方式3数组下标map 的 [] 运算符与 at()map 重载了 [] 运算符用于按键取值/赋值m[key] 在键不存在时插入默认值并返回其引用at(key) 只取值键不存在时抛出异常。[] 语法直观方便但读不存在的键会静默插入容易隐藏 bugat() 提供严格检查的读取方式。对不存在的键调用 at() 会抛出 out_of_range[] 可用于修改和插入multimap 因一键多值不支持 []。std::mapint, std::string m; m[1] one; // 键不存在插入 std::string s m.at(1); // 读取键不存在时抛出异常 // m.at(99); // 错误键 99 不存在 → out_of_rangemap 的查找与删除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::setstd::string A;template class Key, // 第1个元素类型你填的 string class Compare std::lessKey, // 第2个比较函数决定怎么排序 class Alloc std::allocatorKey // 第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::setstd::string A; // 键唯一、可排序的字符串集合 // 第二个模板参数可选指定排序比较函数/对象默认 less // 可用区间构造函数从数组初始化setstring A(s1, s1 N); // A.insert(s); // 只指定要插入的信息不指定位置 // A.lower_bound(key); // 第一个不小于 key 的成员 // A.upper_bound(key); // 第一个大于 key 的成员 // 并/交/差用通用算法set_union/set_intersection/set_differencemultimap 示例与 set 相似multimap 也是可反转的、经过排序的关联容器但键和值的类型不同且同一个键可能与多个值相关联。基本声明用模板参数指定键的类型和存储的值类型如 std::multimapint, std::string codes;template class Key, // 第1个键的类型如 int class T, // 第2个值的类型如 string class Compare std::lessKey // 第3个比较规则默认升序 class multimap;实际的存储节点的值类型将键类型和数据类型结合为一对STL 用模板类 pairT, U 将这两种值存储到一个对象中——若 keytype 是键类型、datatype 是数据类型则值类型为 pairconst keytype, datatype。规则限制pair 对象用 first 和 second 成员访问两个部分。成员函数 count(key) 返回具有该键的元素数目lower_bound()/upper_bound() 工作原理与 set 相同equal_range(key) 返回两个迭代器封装在 pair 对象中表示与该键匹配的区间。因为数据项按键排序所以不需要指出插入位置。#include map // multimap 所在头文件 std::multimapint, std::string codes; // 键类型 int值类型 string std::pairconst int, std::string item(213, Los Angeles); // 键值对 // item.first / item.second // 访问键与值 // codes.insert(item); // 插入无须指定位置 // codes.count(key); // 返回该键的元素数目 // codes.equal_range(key); // 返回匹配区间的两个迭代器pair 模板pairT1, 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。双向迭代器正向迭代器全部功能 前缀/后缀--支持反向遍历、首尾交换等算法。随机访问迭代器双向迭代器全部功能 an/a-n/a[n]/b-a/关系比较仅当a与an位于容器区间含超尾内合法用于排序、二分检索。迭代器层次结构与算法选用输入/输出→正向→双向→随机访问逐级增强算法用要求最低的迭代器以适用最大区间高级别迭代器可用于低级别算法iterator是类级 typedef容器文档标注级别。概念、改进和模型概念concept是系列要求改进refinement是概念上的继承双向是对正向的改进模型model是概念的具体实现int*是随机访问迭代器模型。将指针用作迭代器指针满足所有迭代器要求C 保证Receiptsn定义支持数组超尾概念STL 算法可用于常规数组自定义数组提供迭代器与超尾即可。copy() 算法从输入迭代器区间复制到输出迭代器位置可跨容器、跨数组复制覆盖目标已有数据目标须足够大不能放入空矢量除非用插入迭代器。ostream_iterator输出迭代器概念的模型、适配器把输出流包装成迭代器接口模板参数为数据类型与字符类型构造参数为输出流与分隔符*it 15即输出。istream_iterator输入迭代器概念的模型使输入流可用作迭代器接口省略构造参数表示输入失败从输入流读取直到文件尾/类型不匹配/输入故障。其他预定义迭代器reverse_iterator递增即递减配合 rbegin/rend 反向遍历back_insert_iterator尾插、front_insert_iterator前插限固定时间前插容器、insert_iterator指定位置前插入三者把复制转换为插入并自动分配内存。容器概念与容器类型概念是通用类别容器、序列容器、关联容器类型是可创建对象的模板基本容器概念规定所有容器类须满足的要求数据为容器所有类型须可复制构造、可赋值。复杂度编译时间编译期执行时间为 0→固定时间运行期、独立于元素数→线性时间与元素数成正比复杂度要求是 STL 特征性能规格公开便于评估成本。C11 新增容器要求移动构造/移动赋值源可为临时对象可转让所有权不做复制效率更高X::iterator须满足正向迭代器要求此前只要求非输出迭代器。序列sequence对容器概念的改进迭代器至少正向元素按特定顺序排列且两次迭代间不变严格线性顺序有首尾、除首尾外各有一前驱一后继数组和链表是序列分支结构不是。序列容器类型vector随机访问、尾部固定/中部线性、默认选择、deque两端固定时间插入删除、list任意位置固定时间插入删除、双向链表、迭代器插入后指向元素不变、forward_listC11 单链表、仅正向迭代器、不可反转、queue/priority_queue/stack适配器类底层默认 deque/vector、arrayC11长度固定非 STL 容器有at()边界检查。关联容器用键查找值、快速访问通常用树实现set键唯一、值即键、multiset可重复键、map键唯一、键值类型不同、multimap一键多值允许插入但不能指定位置。set 示例关联集合可反转、可排序、键唯一重复值只出现一次第二模板参数可选默认less并/交/差由通用算法set_union等提供须已排序c.begin()是常量迭代器、空集合不满足覆盖要求须用insert_iteratorlower_bound/upper_bound求区间。multimap 示例键与值类型不同、一键可多值实际值类型为pairconst keytype, datatype用first/second访问count()返回某键元素数equal_range()返回匹配区间的两个迭代器封装在 pair 中插入无须指定位置。