算法算法设计的两个通用部分对于算法函数设计有两个主要的通用部分它们都使用模板来提供泛型它们都使用迭代器来提供访问容器中数据的通用表示。模板解决了“存储什么类型”的问题。迭代器解决了“数据怎么存放”的问题。因为指针是一种特殊的迭代器所以 copy() 等 STL 函数可用于常规数组统一的容器设计使得不同类型的容器之间具有明显关系——可用 copy() 把数组值复制到 vector、把 vector 值复制到 list、把 list 值复制到 set可用 比较不同类型的容器如 deque 和 vector因为容器重载的 运算符使用迭代器比较内容只要内容与排列顺序相同即相等。// 算法设计的两个通用部分模板提供泛型、迭代器提供通用访问 template class InputIterator, class OutputIterator OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result); // 同一 copy 算法可用于double 数组、string 链表、set 树结构算法组的四种分类STL 将算法库分成 4 组非修改式序列操作non-modifying sequence operations遍历区间但不修改容器元素的值也不改动元素的顺序。find、count、for_each注、equal修改式序列操作mutating sequence operations会修改元素的值或者改变元素的位置/顺序。copy、remove、reverse、transform、fill排序和相关操作sorting and related operations专门针对顺序做文章排序、归并、集合运算、二分查找。sort、merge、set_union、lower_bound通用数字运算generalized numeric operations专治各种数学计算累加、内积、差分。accumulate、inner_product、adjacent_difference前 3 组在头文件 algorithm以前为 algo.h中描述第 4 组专用于数值数据有自己的头文件 numeric以前它们也位于 algo.h 中。算法原型的迭代器假设常写template class T这里的T没有任何含义随便换成U都行。但在 STL 中模板参数名是有特殊意义的。例如templateclass InputIterator, class OutputIteratorInputIterator输入迭代器OutputIterator输出迭代器编译器不会像检查 int 或 class 那样去验证“你是不是一个输入迭代器”它没有专门的内置类型叫 InputIterator。如果sort内部写了一句it 5;随机访问才支持的操作。此时编译器检查listint::iterator是否有operator。结果没有。编译器报错。就地算法与复制算法copy 后缀约定就地算法In-place直接在原始数据上动手。原件被销毁/覆盖节省内存。复制算法Copying algorithm从头到尾不动原件把修改后的结果放到另一个地方。原件完好无损。命名规则STL 的约定是如果某个算法通常就地修改数据但你想保留原件就调用它的_copy版本。_copy版本总是多一个参数用来指定“结果放哪”输出迭代器。transform() 可以以两种方式完成工作——与 copy() 相似用输出迭代器指示结果存储位置但允许输出迭代器指向输入区间因此可用计算结果覆盖原来的值。有些算法有两个版本就地版本和复制版本STL 的约定是复制版本的名称以 copy 结尾并接受一个额外的输出迭代器参数指定结果的放置位置。特例transform 可以“以两种方式完成工作”。因为 transform 本身就要求你传一个输出迭代器copy 版的特性。但它允许你把输出迭代器设为输入区间的起点即 dst src这样它就变成了“就地”算法。复制算法统一的约定是返回一个迭代器该迭代器指向复制的最后一个值后面的一个位置如 replace_copy() 的返回类型为 OutputIterator。if 后缀与谓词变体无 _if如 replace只认准一个具体的值。比如“把所有等于 2 的换成 99”。带 _if如 replace_if不管具体值是多少只问是或不是。比如“把所有大于 10 的换成 99”、“把所有偶数换成 99”。STL 与 string 类string 类虽然不是 STL 的组成部分但设计它时考虑到了 STL——它包含 begin()、end()、rbegin() 和 rend() 等成员因此可以使用 STL 接口。next_permutation按“字典序字母表顺序”生成下一个排列。成功该算法返回 true如果区间已经处于最后的序列中则该算法返回 false。要得到区间内容的所有排列组合应从最初的顺序开始先排序。#include string // string 提供 begin/end 等成员 #include algorithm // next_permutation 所在头文件 std::string letters(awl); // 先用 sort(letters.begin(), letters.end()); 得到最初顺序 // while (next_permutation(letters.begin(), letters.end())) // 每次调用转换为下一种字母递增排列已是最后序列时返回 false函数方法与容器方法的取舍使用 STL 方法或 STL 函数通常方法是更好的选择首先它更适合于特定的容器其次作为成员函数它可以使用模板类的内存管理工具从而在需要时调整容器的长度。尽管方法通常更适合但非方法函数更通用使用 STL组件协同工作典型综合用法用 vectorstring 按输入顺序保存单词用 setstring 自动排序并去重配合 transform() 与插入迭代器、转换函数把单词转为小写用 mapstring, int 把单词与其出现次数关联用 count() 统计每个词在 vector 中出现的次数。// 组件协同vector 保序、set 排序去重、map 计数 std::vectorstd::string words; // 按输入顺序保存 std::setstd::string wordset; // 自动排序、键唯一 std::mapstd::string, int wordmap; // 键单词→ 值次数 // 把 vector 内容经转换函数复制进 set排序 去重 转小写 // transform(words.begin(), words.end(), // insert_iteratorsetstring (wordset, wordset.begin()), ToLower); // 对每个单词统计在 vector 中出现的次数 // wordmap[*si] count(words.begin(), words.end(), *si); // 数组表示法wordmap[key] 返回与键关联的值键无效时为 0常见的STL算法查找算法find、count、count_if、binary_search算法核心功能是否需要排序返回结果复杂度find找“第一个” 等于某值的位置❌ 不需要迭代器指向第一个匹配项找不到返回end()O(n) 线性count数 等于某值的元素个数❌ 不需要整数difference_type匹配的数量O(n) 线性count_if数 满足条件谓词 的元素个数❌ 不需要整数匹配的数量O(n) 线性binary_search判断 某值是否存在只回答有/没有✅ 必须排序booltrue/falseO(log n) 对数