企业官网建设流程全解析

1. 从C到C++：竞赛选手的第一次思维转换

很多刚开始刷算法题的朋友都有个困惑：学校的课明明在教C语言，怎么一到竞赛圈，所有人都在用C++？打开题解一看，满屏的vector、map、sort，突然觉得自己学的C语言像个没发育完的小孩。这种感受我太熟悉了，因为我也是从C语言硬生生转过来的。坦白说，如果你只是应付期末考试，C语言完全够用；但如果你要刷算法题、打竞赛，别犹豫，直接上C++。这本书第五章的标题叫“C++与STL入门”，就是这个意思——它不是让你精通C++面向对象那一整套复杂机制，而是让你掌握一套在竞赛中能救命的语言工具和容器库。

这一章的核心价值在于：它帮你建立一套“不用自己造轮子”的思维方式。在纯C语言里，你要实现一个动态数组得先malloc，然后自己写扩容逻辑，再小心翼翼处理越界问题。而在C++里，一个vector搞定一切。也许有老选手会争论说“手写数组比vector快”，这话不假，但那是优化阶段的事。在起步阶段，先学会用STL写出能AC的代码，远比亲手造一个会RE（运行错误）的轮子重要。而且STL封装的容器和算法经过了无数人的使用验证，正确性和效率都有保障，你完全可以把精力集中在“如何解决问题”本身，而不是“如何实现数据结构”上。

这本书第五章作为全书的起点章节之一，设计得很有层次。它不是一上来就甩给你一堆容器让你背，而是先讲C++相对C新增的基础语法——引用、string、bool、const限定符，然后再进入STL的三大板块：容器、迭代器和算法。很多初学者看这章会觉得很散，仿佛什么都在讲又什么都没讲透。但你要是真把这章啃透了，之后去看任何算法专题都会轻松很多。因为后面讲的排序、二分、图论、动态规划，全都建立在这一章的数据结构和语法基础之上。所以这章值得你反复翻阅，不是一次读完就算完，而是每学一个新算法，再回头看看这章，每次都还会有新的收获。

2. 代码笔记开场：书里没明说的C++基础语法细节

2.1 初识cin和cout：方便是方便，坑也不少

第五章开篇就直接进入C++的输入输出核心。书里给出了最简单的用法示例，比如cin >> a >> b;和cout << a << b << endl;。但光看示例，很多初学者会漏掉几个关键知识点，我在这里补全一下。

首先是cin和cout的性能问题。默认情况下，cin和C标准库的stdio是同步的，这导致它每次输入都要进行同步检查，性能比scanf差不少。对于一道题有大量输入数据（比如十万、百万级）的情况，用cin很可能会超时。解决办法是在main()开头加一行：

ios::sync_with_stdio(false); cin.tie(nullptr);

第一行关闭与stdio的同步，第二行解除cin与cout的绑定。加了这两行之后，cin和cout的速度基本上能和scanf/printf打平。不过我还是要多说一句：如果你用cin的同时又混用scanf，那这两行就千万不要加，否则可能出现读入顺序错乱的问题。竞赛圈里很多人对这个问题有执念，有人坚持永远用scanf，有人觉得关流之后的cin完全够用。我的态度是：你习惯用哪个就用哪个，但别混用。对于输入规模特别夸张的大数据题，我会倾向于直接用scanf或者自定义快读，因为心理上更安稳。

其次是endl的使用。书里示例大量使用了endl，看起来很美，但endl会在换行的同时强制刷新输出缓冲区（flush），如果输出量比较大，频繁的缓冲刷新会拖慢速度。竞赛中实际更推荐用'\n'换行，比如cout << ans << '\n';。你是不是觉得这差别微小？实测在多次输出的情况下，用'\n'代替endl能省出不少时间。这就是那种“书里写了，但书里不会特意告诉你为什么要这样选”的细节。

再补一个知识点——格式化输出。printf可以用%.3lf控制小数点位数，而cout怎么控制？需要引入<iomanip>头文件，然后使用fixed和setprecision(n)。比如保留3位小数：

#include <iostream> #include <iomanip> using namespace std; int main() { double pi = 3.1415926535; cout << fixed << setprecision(3) << pi << '\n'; // 输出 3.142 return 0; }

fixed表示用定点表示法（不用科学计数法），setprecision(3)表示保留三位小数。注意这个设置在设置一次后对后续输出持续生效，直到你手动修改，所以不用每次都写。这些都是书里代码示例没有直接写全、但你在做题时必然会用到的东西。

2.2 引用&：不只在函数参数里有用

第五章花了不少篇幅讲C++的引用，这是从C到C++最核心的语法差异之一。书里最典型的场景是写自定义函数时用引用参数实现“传址修值”，避免拷贝。但我想从三个层面拆解引用，帮你彻底搞懂它。

第一个层面：作为函数参数的引用，比指针更安全直观。纯C时代的写法是void swap(int *a, int *b)，调用时得写swap(&x, &y)，而C++的引用写法是void swap(int &a, int &b)，调用时直接swap(x, y)。对于初学者，引用省去了取地址符和指针运算的心智负担。而且引用的语义更强——看到&就明白这个参数会被修改，可读性更好。

第二个层面：引用能避免不必要的对象拷贝。在竞赛中经常遇到自定义的结构体或string作为函数参数。如果直接传值，每次调用都要做一次深拷贝，数据量大时会白白浪费大量时间。用引用传递就不会。但要注意，如果只是读取而不修改我们应该用const string &s这种写法，既能避免拷贝，又能防止意外修改。书里在讲string时也应用了这样的技巧，但它没有停下来特别解释为什么，我建议你把这个写成习惯。

第三个层面：引用是某些STL容器的必要配合。比如后面会讲范围for循环（C++11起）：

for (int &x : v) x *= 2;

这里的&x表示遍历容器中的每个元素，并且允许修改。如果没有引用符&，x只是每个元素的拷贝，你对x的修改不会影响v里的数据。这个细节藏得很深，很多初学者在范围for循环里改了半天，最后发现原容器纹丝不动，就是这个原因。

2.3string用法补全：不只是字符数组的替代品

书里第五章介绍了string是C++的字符串类型，但篇幅有限。我这里把它在竞赛中的高频用法一次性梳理清楚，方便你在做题时随时查阅。

string区别于C风格字符数组的核心优势是自动管理长度和内存，你可以直接拼接str1 + str2，可以用+=追加，也可以用==直接比较两个字符串是否相等。此外它支持随机访问，s[i]取字符，和数组一样。竞赛中我最常用的几个操作：

#include <string> #include <algorithm> string s = "hello world"; int len = s.size(); // 长度 string sub = s.substr(0, 5); // 截取子串，从0开始取5个字符：hello size_t pos = s.find("world"); // 查找子串，返回下标；未找到返回string::npos s.insert(5, ","); // 在下标5处插入"," s.erase(5, 1); // 从下标5开始删除1个字符 sort(s.begin(), s.end()); // 字符串也能排序

这里尤其要注意find的返回值。判断找不到时要用if (pos == string::npos)，而不是if (pos == -1)。虽然很多环境下npos的值就是-1的无符号表示，但为了严谨和可移植性，规范写法是拿它和string::npos比较。

另外一个细节：string的size()和length()功能完全一样，都返回字符个数。用哪个都行，没有性能差异，纯属个人习惯。但需要注意的是，这个返回值是无符号整数类型size_t。如果你拿它和一个负数比较，或者直接用它减一个较大的正整数，可能会溢出变成很大的数，导致意外。比如：

for (int i = s.size() - 2; i >= 0; i--) { ... } // 当s.size()小于2时，灾难现场

这个坑看起来不起眼，实际调试时让人抓狂。我的习惯是涉及下标运算时，直接先转成int n = s.size();再往下走。

2.4 结构体：从“数据的聚合”到“自定义类型”

C语言里你已经用过结构体了，C++对它做了两件重要的事。第一件事是不需要写struct关键字也能直接声明变量。C语言里声明结构体变量要写struct Student stu;，C++里直接Student stu;就行。第二件事是结构体可以定义成员函数（简称方法），甚至能重载运算符，这直接为STL自定义类型铺平了道路。

书里第五章在讲“集合”相关内容时，反复用到结构体作为元素类型。我先给一个竞赛中非常典型的“二维坐标点”结构体写法：

struct Point { int x, y; Point(int x = 0, int y = 0) : x(x), y(y) {} // 构造函数，带默认参数 bool operator < (const Point &rhs) const { return x < rhs.x || (x == rhs.x && y < rhs.y); } friend ostream& operator << (ostream &out, const Point &p) { out << "(" << p.x << ", " << p.y << ")"; return out; } };

你可能觉得这又长又难懂，但这里的每一样东西都有明确用途。构造函数Point(int x = 0, int y = 0)让你能直接写出Point p1, p2(3, 4);这样方便的初始化语句，而不是先声明再逐个给成员赋值。operator <是给排序或者放进set用的，STL里的容器需要知道“谁小谁大”。operator <<是输出重载，让你可以cout << p1直接打印一个点，省得再写printf("(%d,%d)", p.x, p.y);。

很多初学者在这里会卡住，觉得语法太花哨没必要。但构建自定义结构体并配合STL使用，是算法竞赛中特别常见的事，尤其是图论、计算几何、搜索这些专题，你会经常定义边、点、状态这类结构体，里面放上一大堆字段，再配好比较方式和输出方式。你最终会发现，把结构体定义得舒服，就等于把代码写对了一半。

3. STL容器：从vector到map的全套笔记

3.1 vector：动态数组的正确打开方式

vector是STL里使用频率最高的容器。它其实就是自动管理内存的动态数组，用下标访问即可，底层是连续内存空间，所以随机访问是O(1)的。书里给出了创建、插入、遍历等基本操作，我挑重点讲。

先看最常见的基本操作清单：

#include <vector> using namespace std; vector<int> v; // 空vector vector<int> a(10); // 大小为10，初值为0 vector<int> b(10, 5); // 大小为10，初值全是5 vector<int> c = {1, 2, 3}; // 直接初始化 v.push_back(4); // 尾部插入元素 v.pop_back(); // 删除尾部元素 v.size(); // 元素个数 v.empty(); // 是否为空 v.resize(20); // 重新设置大小 v.clear(); // 清空所有元素 v[i]; // 按下标访问，不检查越界 int first = v.front(); // 首元素 int last = v.back(); // 尾元素

关于push_back的性能，很多初学者有个误区，认为它会频繁申请内存导致很慢。实际上vector的内存扩容策略是倍增的，当容量不足时会申请一个约为当前容量两倍的新内存块，然后把旧元素搬过去。均摊下来，单次push_back的时间复杂度仍然是O(1)。所以不用杯弓蛇影地预估它会太慢，放心用。

真正值得警惕的坑是迭代器失效。比如遍历vector时如果同时进行insert或erase操作，原本保存的迭代器可能就指向了无效位置。后面的章节我会专门讲这类问题，这边先记下结论：修改容器时，立刻结束之前拿到的迭代器的继续使用，重新获取。

第三个高频场景是排序。vector配合sort简直天作之合：

sort(v.begin(), v.end()); // 升序 sort(v.rbegin(), v.rend()); // 降序

rbegin()和rend()是反向迭代器，这个技巧比手动写自定义比较函数去翻转排序简单得多。也有同学问能不能用sort(v.begin(), v.end(), greater<int>())，当然可以，但在C++14前你需要确保正确引入<functional>头文件。反向迭代器的写法更省心。

3.2 set与multiset：自带排序与去重的集合

set是基于红黑树（一种自平衡二叉搜索树）实现的有序集合，主要特点有三：元素不重复、元素自动升序排列、几乎所有核心操作复杂度为O(log n)。它非常适合处理需要“去重并排序”的问题。

书里介绍了set的基本操作：insert、erase、find、count、size。我来补充实际做题时高频使用的细节：

#include <set> set<int> s; s.insert(10); s.insert(20); s.insert(10); // 重复插入无效，set里还是只有10和20 auto it = s.find(10); // 查找元素，返回迭代器；找不到返回s.end() if (it != s.end()) cout << *it << '\n'; s.lower_bound(15); // 返回第一个 >= 15 的元素迭代器 s.upper_bound(15); // 返回第一个 > 15 的元素迭代器

lower_bound和upper_bound是你刷算法题的核心武器，很多二分查找类的题目会直接用它们的语义来解题，省去手写二分的烦恼。至于set内部为什么能自动排序？因为它内部维护了一棵红黑树，插入时会根据比较规则把新元素放到合适位置，所以任何时候遍历，结果都是有序的。这也是为什么结构体放进set时必须定义好operator <——否则排序规则缺失，set无法工作。

multiset则是允许元素重复的同款容器。它和set的唯一区别就是不能去重。需要注意multiset的erase行为有两种：s.erase(value)会删除所有等于该值的元素；而如果只想删除某个，要用迭代器去删：s.erase(s.find(value))。书里提过一嘴multiset，但没有展开讲，这两个函数语义的差异，我强烈建议你自己跑一遍验证一下。

3.3 map与pair：建立键值映射的黄金搭档

map也是基于红黑树的有序容器，它存放的是键值对key-value。key唯一且自动按序排列，value可以重复。它在算法竞赛里的使用频率，仅次于vector。

书里入门示例大概是这样的：

#include <map> #include <string> map<string, int> mp; mp["apple"] = 3; mp["banana"] = 5; mp["apple"]++; // 如果key已存在，直接改value cout << mp["apple"] << '\n'; // 输出4

这里有一个初学者最容易掉进去的坑：用[]访问一个不存在的key时，map会自动插入一个默认值（比如int默认0），然后返回它的引用。也就是说，if (mp["unknown"] == 0)这样的情况不是“纯粹查询”，它其实已经修改了mp的结构，插入了一对新键值对。如果你接下来遍历这个map，会发现多出一个你从未主动插入的元素。更严重的副作用是，如果value是自定义类型，默认构造会带来一次开销，在循环中频繁这样做可能莫名增加时间和内存。

那怎么安全查询呢？用find：

auto it = mp.find("apple"); if (it != mp.end()) { cout << it->first << " " << it->second << '\n'; }

it->first是键，it->second是值。用find不会触发任何插入操作，是真正意义上的“只查询是否存在”。还有一个常用技巧：mp.count(key)返回0或1（对于map而言），在C++20之前count常用于判断“是否存在”。虽然它不像find那样能拿到对应的值，但很多场景下我们只关心“在不在”，用count写起来更简洁。

配合map不得不提pair。pair就是STL封装好的结构体，包含两个成员first和second。算法竞赛中经常用它来存储二维坐标、边信息（起点终点）、合并一次操作产生的结果等等。我们不需要为它专门定义结构体，直接使用即可：

pair<int, int> p1(2, 3); pair<int, int> p2 = {4, 5}; int x = p1.first; int y = p1.second; auto p3 = make_pair(6, 7); // 也可以这么构造

pair自带比较规则：先按first比较，如果相等再比较second。这个默认规则在很多时候正好满足需求，比如按起点排序、起点相同按终点排序。把pair配上map，可以处理很多复杂的映射和计数场景。

3.4 stack、queue与priority_queue：三大线性容器的竞赛笔记

这三个容器在算法题里随处可见。stack是后进先出，queue是先进先出，priority_queue是“最大堆”或“最小堆”。书里对它们的介绍比较简略，我这里把实战细节和常见错误全部补齐。

先看stack和queue的基本用法：

#include <stack> #include <queue> stack<int> st; st.push(1); st.push(2); int topVal = st.top(); // 取栈顶元素（不删除） st.pop(); // 删除栈顶元素（无返回值） queue<int> q; q.push(1); q.push(2); int frontVal = q.front(); // 取队首元素 q.pop(); // 删除队首元素

注意pop()不返回被删除的元素。很多初学者会误以为st.pop()能拿到栈顶值，实际不行。这也是C++设计上比较“别扭”的地方——必须先top()再pop()。类似地，queue也是必须先front()再pop()。

而priority_queue默认是最大堆，取值用top()，插入用push()，删除用pop()。如果你想实现最小堆，书里也提过可以用greater：

#include <queue> priority_queue<int> maxQ; // 最大堆 priority_queue<int, vector<int>, greater<int>> minQ; // 最小堆

这里有一个长期让新手困惑的问题：为什么最小堆的模板参数写这么长？因为priority_queue底层默认用vector存储，第二个参数指定底层容器，第三个参数指定比较规则。greater表示“父节点大于子节点时交换”，表现成堆顶是最小元素。你用不着彻底弄懂仿函数机制，先把写法背下来用起来，以后再深究原理也来得及。

对于自定义结构体放进priority_queue，事情会变得有点微妙。如果你定义了operator <，默认情况下它有“最大堆”的语义——即堆顶是最大的元素。但这里的“最大”取决于你写的比较规则。书里给过一个很经典的例子，这里我补一个更详细的图论中“最短路”维护最小代价的写法：

struct Node { int cost, id; bool operator < (const Node &rhs) const { return cost > rhs.cost; // 注意：这里反过来了 } }; priority_queue<Node> pq;

在优先队列中，operator <为真表示前者优先级更低。上述写法让代价小的Node优先级更高，因此堆顶是最小代价节点。如果你在普通排序里写return cost < rhs.cost是升序，但在优先队列里这么写就是最大堆效果，很容易直觉错位。为了避开这个混乱，我建议你在自定义类型时用operator >的方式配合greater<Node>来明确语义，或者干脆在结构体里倒着写。怎么舒服怎么来，但一定要测试验证堆顶是否符合预期，别在赛场上意气用事。

3.5 迭代器：能否遍历，理解STL的关键

STL容器之间的操作主要靠迭代器串联。你可以把迭代器想象成“带类型的指针”——它能够前移、后移、取值，甚至配合算法函数完成区间操作。书里在vector部分已经用到begin()和end()，它们返回迭代器表示容器的头部和尾部下一个位置。

迭代器的基本操作包括：

vector<int> v = {1, 2, 3, 4, 5}; for (auto it = v.begin(); it != v.end(); ++it) { cout << *it << ' '; // 解引用迭代器获取元素 }

使用auto可以自动推导迭代器类型，写起来非常省事。v.end()指向的是最后一个元素的下一个位置，不是最后一个元素本身，所以循环条件是it != v.end()，而不是it <= v.end()。这一点和很多人的直觉不一样，得专门留意。

关于迭代器，还有三个补充知识。第一，在set和map中，迭代器指向的元素本身不能通过迭代器修改键值（因为会破坏排序结构），但可以读取。第二，vector和deque在插入/删除元素时会导致之后位置的所有迭代器失效，如果你保存了早期的迭代器就会出问题。第三，set/map的插入和删除操作不会使已有迭代器失效（除了被删除的那个），这是它们作为平衡树容器的优势，在复杂代码里可以放心保存一些迭代器做标记。

4. algorithm头文件：算法竞赛的弹药库

4.1 sort排序：从入门到自定义比较函数

sort是算法竞赛中使用率最高的函数。它的底层不是简单的快排，而是结合了堆排序和插入排序的混合策略，最坏时间复杂度为O(n log n)，而且经过充分优化，实际表现非常稳定。基本用法是：

#include <algorithm> int arr[100]; sort(arr, arr + 100); vector<int> v = {5, 2, 8, 1}; sort(v.begin(), v.end());

对数组排序时，传的是首尾指针；对vector排序时，传的是首尾迭代器。两个区间都是左闭右开。如果你想自定义排序规则，就传入第三个参数——一个“比较函数”。比较函数的返回值代表“第一个参数是否应该在第二个参数前面”。

bool cmp(int a, int b) { return a > b; // 降序 } sort(v.begin(), v.end(), cmp);

这里有个非常经典的陷阱：比较函数必须满足严格弱序（strict weak ordering）。简单来说，如果a和b相等，cmp(a,b)和cmp(b,a)都必须返回false。如果你不小心写出了return a >= b;这样的比较逻辑，在某些情况下会导致sort行为未定义，出现复杂的运行时错误。我见过有人写类似return rand() % 2;这种随机比较，结果程序崩溃或排序结果错乱，这种错误排查起来极其痛苦。所以写cmp的时候，永远只使用<或>，不要用<=或>=。

补充一个在结构体排序中非常常用的技巧——用tuple或pair间接实现多关键字排序。比如按总分降序、总分相同按语文成绩升序：

// 方法一：自定义cmp bool cmp(Student a, Student b) { if (a.total != b.total) return a.total > b.total; return a.chinese < b.chinese; } // 方法二：利用pair的默认比较 pair<int, int> —— 已排序先按first升序，再按second升序。

方法二只能处理两个关键字且方向相同的情况，但很简洁。方法一更通用，你甚至可以设计非常复杂的规则，比如性别优先、年龄其次、编号兜底。只要严格弱序，sort就给你稳稳的幸福。

4.2 lower_bound与upper_bound：二分查找的正确姿势

在有序数组（或容器）中查找某个位置，是算法竞赛的高频场景。手写二分很容易写错边界，STL提供了两个现成的函数——lower_bound和upper_bound。

vector<int> v = {1, 3, 5, 5, 7, 9}; auto it1 = lower_bound(v.begin(), v.end(), 5); // 第一个 >= 5 的元素，即下标2 auto it2 = upper_bound(v.begin(), v.end(), 5); // 第一个 > 5 的元素，即下标4

返回的都是迭代器。减去v.begin()后就得到了下标。这两个函数内部就是二分查找，时间复杂度O(log n)，前提是区间已经有序。

一个特有用途：统计有序数组中某个值的出现次数。

int cnt = upper_bound(v.begin(), v.end(), 5) - lower_bound(v.begin(), v.end(), 5);

代码简洁、性能优秀，而且不容易写错。这道在很多题库里叫“数的范围”或“查找区间”的题目，用这个写法一分钟内解决。在set和map里也有同名成员函数，比如set<int>::lower_bound，它们靠红黑树内部的比较逻辑查找，同样O(log n)。要注意的是，set的lower_bound需要调用成员函数s.lower_bound(x)，而不是lower_bound(s.begin(), s.end(), x)。虽然全局函数也能用，但效率会退化，因为set的迭代器不是随机访问迭代器，全局二分无法发挥优势。这是一个值得记住的细节。

还有一个容易误解的点：lower_bound应该处理的是“有序”区间，如果区间本来无序，结果就是错的。所以我建议你养成习惯——用sort排完序后，紧跟着用lower_bound/upper_bound，这俩是“黄金搭档”。

4.3 unique去重：和sort配合才能发挥威力

unique函数的功能是“移除相邻重复元素”，但它不会真正删除元素，只是把不重复的元素移动到前面，然后返回“新逻辑末尾”的迭代器。它只对相邻的重复元素生效，所以在用unique之前，必须保证序列有序——通常先用sort。

实际应用中常见的组合拳：

vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3}; sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());

这行代码被很多人称为“STL经典三连”。sort排序后，unique把重复元素移到末尾，返回新逻辑结尾，然后erase把尾部的那段重复废弃数据真正删除。执行完后，v里就是去重且升序的唯一元素集。

某些题目还需要做“离散化”，这也是sort+lower_bound的组合拳：

vector<int> all = {5, 5, 3, 8, 3, 1}; sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); // 之后对任一原值x，其离散化下标为： int idx = lower_bound(all.begin(), all.end(), x) - all.begin() + 1;

这就是把无穷种取值压缩成“排名”的技巧，常见于树状数组、线段树、莫队这类需要处理区间统计的题目。书里第五章虽然没有细讲离散化，但数列离散化依赖的就是这一小节的三个函数，认识了它们，后面学专题就能触类旁通。

4.4 next_permutation和reverse：不起眼但能救命的小函数

再补充两个书里出现过但我认为非常实用的小函数。

第一个是next_permutation，用来生成下一个字典序排列。它可以直接替换手写的递归全排列生成器，解决很多需要枚举排列组合的搜索题。用法：

vector<int> v = {1, 2, 3}; do { for (int x : v) cout << x << ' '; cout << '\n'; } while (next_permutation(v.begin(), v.end()));

这个循环会把所有的排列都打一遍。注意next_permutation在已经不存在下一个排列时返回false，并把序列重置为最小排列，所以用do-while而不是while，才能保证第一组排列也被处理。prev_permutation是对应求上一个排列的，对称存在。

第二个是reverse，反转区间元素。用途极其广泛，比如代码里有时需要逆序遍历字符串或者数组：

string s = "abc"; reverse(s.begin(), s.end()); // s变成"cba" vector<int> v = {1, 2, 3}; reverse(v.begin(), v.end()); // v变成{3, 2, 1}

这两个函数虽然不起眼，但能帮你省下很多手写逻辑的时间，而且在一些特定题解里几乎成为“隐藏规定动作”。学习STL就是这样，你掌握的函数越多，写代码的“词汇量”就越丰富，面对新题时思路也更开阔。

5. 解题实操：用第五章知识秒掉三道经典入门题

本章的内容学完后，最好的检验方法是直接上手刷题。我选了三个经典场景，完全用STL加algorithm头文件解决，大家可以对比一下自己和这些代码的时间与内存消耗。

5.1 数据去重排序

问题描述：给定n个整数，输出去重后升序排列的结果。

这道题甚至可以只用set一行流解决：

#include <iostream> #include <set> using namespace std; int main() { int n, x; cin >> n; set<int> s; while (n--) { cin >> x; s.insert(x); } for (auto it = s.begin(); it != s.end(); ++it) { cout << *it << (next(it) == s.end() ? '\n' : ' '); } return 0; }

利用set自动排序+去重的特性，整个算法复杂度是O(n log n)，写起来十几行搞定。如果换纯C语言，你得先动态数组存下所有数，再写快排，再手写去重移动……高下立判。这就是STL解决“算法思维”之外杂事的最好示范。

5.2 单词出现次数统计

问题描述：给一段文本，统计每个单词出现的次数，按字典序输出。

这个用map<string, int>是标准解法。核心流程就是读入单词，如果存在则自增，否则插入初值1。这里注意我上面提到的[]自动插入问题。用[]确实更简洁，但你遍历时会多出一堆初始化的默认元素。稳妥写法如下：

#include <iostream> #include <map> #include <string> using namespace std; int main() { string word; map<string, int> cnt; while (cin >> word) { cnt[word]++; } for (auto &p : cnt) { cout << p.first << " " << p.second << '\n'; } return 0; }

这段代码里我用了cnt[word]++的写法，利用int默认值为0的特性完成首次计数自增。执行结果是字典序输出。如果你担心性能，可以改用find再插入，逻辑会长两三行，但更严谨。在数据规模不大的情况下，哪一种都可以。但关键要有这个意识：[]到底会不会修改map，取决于你是否真的想插入。

5.3 区间查询与排序综合

问题描述：给一个数组，多次询问“数组中有多少元素不小于x”，数组和询问规模都比较大。

这个场景就需要sort+lower_bound配合了。思路：先对数组排序，然后每一次询问都用lower_bound找到第一个不小于x的位置，用end减去位置即得数量。

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, q; cin >> n >> q; vector<int> v(n); for (int i = 0; i < n; ++i) cin >> v[i]; sort(v.begin(), v.end()); while (q--) { int x; cin >> x; auto it = lower_bound(v.begin(), v.end(), x); cout << v.end() - it << '\n'; } return 0; }

这里用到了迭代器减法计算元素个数。因为vector的迭代器是随机访问迭代器，所以v.end() - it是可以直接得到距离（也就是元素个数）的。这道题如果不使用lower_bound，每次询问都线性扫描就会超时。很多初学者对“下标”比对“迭代器”更习惯，你也可以改成：

int pos = lower_bound(v.begin(), v.end(), x) - v.begin(); cout << n - pos << '\n';

这两者本质一样，选一个自己顺手的就好。但这段代码真正教会你的不是某个容器，而是把问题转化为“在一个有序序列中做二分”的思维模式，这是STL带给你的算法思维升级。

6. 常见错误与调试心得：我踩过的那些坑

6.1 迭代器失效问题

先说最让人头疼的迭代器失效。在使用vector时，如果它在insert时触发了扩容，所有已获得的迭代器、指针、引用都会失效；erase之后，被删元素后面的迭代器也会失效。这类错误通常表现为“运行结果莫名奇妙”或者直接RE（运行时错误）。我曾经在一次调试中，明明往vector里插入了一个值，结果下次用旧的迭代器取值，取出来的是垃圾数据。后来才发现是我在push_back之前保存了v.begin()，插入后旧迭代器已经没有意义了。

避免的方法是：尽量在使用迭代器的循环中不要修改容器本身，如果必须修改，及时更新迭代器：

it = v.insert(it, 100); // 插入后获取新迭代器 it = v.erase(it); // 删除后获取新迭代器

map和set则温和很多，除了指向被删除元素本身的迭代器外，其他迭代器通常不会失效。所以需要标记一些位置长期有效时，优先考虑用set或map。

6.2 越界与下标计算问题

vector的[]运算符不检查越界，访问v[-1]或v[v.size()]会直接导致未定义行为。这是它和at()成员函数的最大区别——at()会抛出异常，但竞赛中极少用at()，因为多了一层检查会拖慢速度。所以我建议从意识上严格要求自己：凡是写下标访问，先估算边界。

另一个和下标计算有关的坑是size_t与int混用。v.size()是size_t类型（无符号），如果你在循环里这样写：

for (int i = v.size() - 1; i >= 0; i--) { ... }

当v.empty()时，v.size() - 1会变成最大的size_t值，然后赋值给int后变成-1，导致循环仍然不执行？恰恰相反，因为v.size() - 1在无符号下是一个巨大的正数，赋值给int后变成-1，循环条件i >= 0仍然为真，但i已经是负数，访问v[i]就会越界。这个坑非常隐蔽，很多新手在这里debug很久。我的写法是：

for (int i = (int)v.size() - 1; i >= 0; i--) { ... }

或者干脆用反向迭代器：

for (auto it = v.rbegin(); it != v.rend(); ++it) { ... }

6.3 cin/cout同步问题

前文已经提过ios::sync_with_stdio(false)和cin.tie(nullptr)。我再补充一个细节：如果你用cin读入大量数据，却没有关闭同步，可能比scanf慢一个数量级甚至更多。但很多人在做题时并没有“大量数据”的直观感知，等超时了才发现卡在输入上。一个简单的经验法则是：当输入规模超过10万条时，就值得关注IO性能问题；超过100万条时，基本应该用scanf或者更快的自定义输入函数，或者正确关闭同步。

如果你既想享受cin的流畅，又担心性能，可以这样做：

ios::sync_with_stdio(false); cin.tie(nullptr);

加上这两行后，不要混用scanf/printf即可。实测在常见的题目范围内基本不会成为性能瓶颈。

6.4 sort比较函数不严格弱序

前面提到过比较函数必须严格弱序，我在这里再展示一个反例。这种写法非常容易出现误判：

bool cmp(int a, int b) { return a <= b; // 错误示例 }

如果a == b，那么cmp(a, b)返回true，cmp(b, a)也返回true，两个方向都为真，严重违反严格弱序。有的编译器可能恰好没让你崩，但在排序数据比较“扭曲”的时候，会产出乱序甚至触发段错误。竞赛时遇到那种“sort结果时对时错”的玄学问题，八成是cmp写得不够“严格”。

正确的习惯：只用<，尽量少用>，在排降序时仍然写成return a > b;，但保证相等时返回false。这样你的比较函数基本不会出事。

7. 从代码笔记到解题能力：第五章之后的成长路径

很多读者学完这一章后会产生一个错觉——不就是会了几个容器和函数吗？我觉得这本书第五章的真正价值，不是让你背会这些API，而是让你完成一次“编程思维”的升维。以前你思考问题的方式是“怎么用数组模拟一个栈”“怎么自己写排序”，学完这章之后，你的思考方式会变成“这里该用stack”“这里应该用sort加lower_bound”直接构建解决方案。这是从“造轮子”到“用轮子”的关键跨越。

接下来我的建议是，花两三周时间专门刷一组“STL练习题”巩固这章知识。题目的典型特征就是可以直接用set、map、vector、priority_queue中的一两个数据结构配合STL函数完成。在练习的过程中，每当写到一个手动实现的数据结构或算法流程，反问自己一句：“STL里有没有现成的？”如果有，试试看换成现成方案后代码变短没有，调试变快没有。经过二十道题的刻意练习，你会发现自己写题的速度明显提升，代码也更不容易出低级错误了。

我个人的感觉是，第五章节最容易被忽略的是标准库提供的容器类型选择问题。很多初学者不管什么都用vector，但在需要频繁删除和插入的场合，list可能更合适；需要保证唯一排序时，set比vector+sort+unique更省事；需要在前端插入时，deque显然更优。容器选型也是需要经验积累的，不是“一个vector走天下”。多接触不同题目，看看别人的题解里如何选用容器，是短时间提升这一块能力的好办法。

平时我也会在刷完一道题后，立刻打开同题的其他解法，看看有没有我的STL没配合好的地方。有些题目在大数据规模下用默认的map会超时，有人改成unordered_map就通过了，这就是容器选择的差距。类似的案例积累多了，你对STL的敏感度会越来越高，写出的代码也会越来越“聪明”。

最后再说一点，学STL别急着把每个容器都摸透。重点是掌握常用容器的基础操作和时间复杂度特征，然后放到题目里去反复验证。算法竞赛的准备过程很漫长，但第五章节绝对能帮你少走很多弯路。把这里的基本功打牢，后面的图论、动态规划、贪心和搜索，你都会学得更轻松——因为那时候你只需要思考算法本身，而不会被无聊的代码细节绊住脚。