企业官网建设流程全解析

算法

算法设计的两个通用部分

对于算法函数设计，有两个主要的通用部分：它们都使用模板来提供泛型；它们都使用迭代器来提供访问容器中数据的通用表示。

• 模板：解决了“存储什么类型”的问题。

• 迭代器：解决了“数据怎么存放”的问题。

因为指针是一种特殊的迭代器，所以 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 组：

1. 非修改式序列操作（non-modifying sequence operations）：遍历区间但不修改容器元素的值，也不改动元素的顺序。find、count、for_each（注）、equal

2. 修改式序列操作（mutating sequence operations）：会修改元素的值，或者改变元素的位置/顺序。copy、remove、reverse、transform、fill

3. 排序和相关操作（sorting and related operations）：专门针对顺序做文章（排序、归并、集合运算、二分查找）。sort、merge、set_union、lower_bound

4. 通用数字运算（generalized numeric operations）：专治各种数学计算（累加、内积、差分）。accumulate、inner_product、adjacent_difference

   前 3 组在头文件 <algorithm>（以前为 <algo.h>）中描述，第 4 组专用于数值数据，有自己的头文件 <numeric>（以前它们也位于 <algo.h> 中）。

算法原型的迭代器假设

常写template <class T>，这里的T没有任何含义，随便换成U都行。

但在 STL 中，模板参数名是有特殊意义的。例如template<class InputIterator, class OutputIterator>InputIterator（输入迭代器）OutputIterator（输出迭代器）

编译器不会像检查 int 或 class 那样去验证“你是不是一个输入迭代器”，它没有专门的内置类型叫 InputIterator。

如果sort内部写了一句it + 5;（随机访问才支持的操作）。此时编译器检查list<int>::iterator是否有operator+。结果没有。编译器报错。

就地算法与复制算法（copy 后缀约定）

1. 就地算法（In-place）：直接在原始数据上动手。原件被销毁/覆盖，节省内存。

2. 复制算法（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：组件协同工作

典型综合用法：用 vector<string> 按输入顺序保存单词；用 set<string> 自动排序并去重（配合 transform() 与插入迭代器、转换函数把单词转为小写）；用 map<string, int> 把单词与其出现次数关联（用 count() 统计每个词在 vector 中出现的次数）。

// 组件协同：vector 保序、set 排序去重、map 计数 std::vector<std::string> words; // 按输入顺序保存 std::set<std::string> wordset; // 自动排序、键唯一 std::map<std::string, int> wordmap; // 键（单词）→ 值（次数） // 把 vector 内容经转换函数复制进 set（排序 + 去重 + 转小写） // transform(words.begin(), words.end(), // insert_iterator<set<string> >(wordset, wordset.begin()), ToLower); // 对每个单词统计在 vector 中出现的次数 // wordmap[*si] = count(words.begin(), words.end(), *si); // 数组表示法：wordmap[key] 返回与键关联的值，键无效时为 0

常见的STL算法

查找算法：find、count、count_if、binary_search