算法竞赛必备：C++ STL容器与常用函数从入门到实战

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循环C11起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; vectorint v; // 空vector vectorint a(10); // 大小为10初值为0 vectorint b(10, 5); // 大小为10初值全是5 vectorint 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(), greaterint())当然可以但在C14前你需要确保正确引入functional头文件。反向迭代器的写法更省心。3.2 set与multiset自带排序与去重的集合set是基于红黑树一种自平衡二叉搜索树实现的有序集合主要特点有三元素不重复、元素自动升序排列、几乎所有核心操作复杂度为O(log n)。它非常适合处理需要“去重并排序”的问题。书里介绍了set的基本操作insert、erase、find、count、size。我来补充实际做题时高频使用的细节#include set setint 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 mapstring, 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是自定义类型默认构造会带来一次开销在循环中频繁这样做可能莫名增加时间和内存。那怎么安全查询呢用findauto 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而言在C20之前count常用于判断“是否存在”。虽然它不像find那样能拿到对应的值但很多场景下我们只关心“在不在”用count写起来更简洁。配合map不得不提pair。pair就是STL封装好的结构体包含两个成员first和second。算法竞赛中经常用它来存储二维坐标、边信息起点终点、合并一次操作产生的结果等等。我们不需要为它专门定义结构体直接使用即可pairint, int p1(2, 3); pairint, 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 stackint st; st.push(1); st.push(2); int topVal st.top(); // 取栈顶元素不删除 st.pop(); // 删除栈顶元素无返回值 queueint 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_queueint maxQ; // 最大堆 priority_queueint, vectorint, greaterint minQ; // 最小堆这里有一个长期让新手困惑的问题为什么最小堆的模板参数写这么长因为priority_queue底层默认用vector存储第二个参数指定底层容器第三个参数指定比较规则。greater表示“父节点大于子节点时交换”表现成堆顶是最小元素。你用不着彻底弄懂仿函数机制先把写法背下来用起来以后再深究原理也来得及。对于自定义结构体放进priority_queue事情会变得有点微妙。如果你定义了operator 默认情况下它有“最大堆”的语义——即堆顶是最大的元素。但这里的“最大”取决于你写的比较规则。书里给过一个很经典的例子这里我补一个更详细的图论中“最短路”维护最小代价的写法struct Node { int cost, id; bool operator (const Node rhs) const { return cost rhs.cost; // 注意这里反过来了 } }; priority_queueNode pq;在优先队列中operator 为真表示前者优先级更低。上述写法让代价小的Node优先级更高因此堆顶是最小代价节点。如果你在普通排序里写return cost rhs.cost是升序但在优先队列里这么写就是最大堆效果很容易直觉错位。为了避开这个混乱我建议你在自定义类型时用operator 的方式配合greaterNode来明确语义或者干脆在结构体里倒着写。怎么舒服怎么来但一定要测试验证堆顶是否符合预期别在赛场上意气用事。3.5 迭代器能否遍历理解STL的关键STL容器之间的操作主要靠迭代器串联。你可以把迭代器想象成“带类型的指针”——它能够前移、后移、取值甚至配合算法函数完成区间操作。书里在vector部分已经用到begin()和end()它们返回迭代器表示容器的头部和尾部下一个位置。迭代器的基本操作包括vectorint 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); vectorint 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的默认比较 pairint, int —— 已排序先按first升序再按second升序。方法二只能处理两个关键字且方向相同的情况但很简洁。方法一更通用你甚至可以设计非常复杂的规则比如性别优先、年龄其次、编号兜底。只要严格弱序sort就给你稳稳的幸福。4.2 lower_bound与upper_bound二分查找的正确姿势在有序数组或容器中查找某个位置是算法竞赛的高频场景。手写二分很容易写错边界STL提供了两个现成的函数——lower_bound和upper_bound。vectorint 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里也有同名成员函数比如setint::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。实际应用中常见的组合拳vectorint 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里就是去重且升序的唯一元素集。某些题目还需要做“离散化”这也是sortlower_bound的组合拳vectorint 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用来生成下一个字典序排列。它可以直接替换手写的递归全排列生成器解决很多需要枚举排列组合的搜索题。用法vectorint 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 vectorint 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; setint 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 单词出现次数统计问题描述给一段文本统计每个单词出现的次数按字典序输出。这个用mapstring, int是标准解法。核心流程就是读入单词如果存在则自增否则插入初值1。这里注意我上面提到的[]自动插入问题。用[]确实更简洁但你遍历时会多出一堆初始化的默认元素。稳妥写法如下#include iostream #include map #include string using namespace std; int main() { string word; mapstring, 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”数组和询问规模都比较大。这个场景就需要sortlower_bound配合了。思路先对数组排序然后每一次询问都用lower_bound找到第一个不小于x的位置用end减去位置即得数量。#include iostream #include vector #include algorithm using namespace std; int main() { int n, q; cin n q; vectorint 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)返回truecmp(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比vectorsortunique更省事需要在前端插入时deque显然更优。容器选型也是需要经验积累的不是“一个vector走天下”。多接触不同题目看看别人的题解里如何选用容器是短时间提升这一块能力的好办法。平时我也会在刷完一道题后立刻打开同题的其他解法看看有没有我的STL没配合好的地方。有些题目在大数据规模下用默认的map会超时有人改成unordered_map就通过了这就是容器选择的差距。类似的案例积累多了你对STL的敏感度会越来越高写出的代码也会越来越“聪明”。最后再说一点学STL别急着把每个容器都摸透。重点是掌握常用容器的基础操作和时间复杂度特征然后放到题目里去反复验证。算法竞赛的准备过程很漫长但第五章节绝对能帮你少走很多弯路。把这里的基本功打牢后面的图论、动态规划、贪心和搜索你都会学得更轻松——因为那时候你只需要思考算法本身而不会被无聊的代码细节绊住脚。