STL 的全称是 standard template library,标准模板库。课件开头把它拼成了 libaray,正确拼写是 library。它是 C++ 标准库的一部分,定位是“可复用的组件库 + 包罗数据结构与算法的软件框架”——这两个说法合起来才准确:单独拿出 vector 是容器,单独拿出 sort 是算法,把它们粘在一起的才是框架。
六个组件各管一段
课件那张关系图把六个组件围在 STL 四周,每个组件下面还列了代表:
| 组件 | 管什么 | 图里列出的成员 |
|---|---|---|
| 容器 | 数据存在哪、怎么组织 | vector、list、deque、map、set、multimap、multiset、string |
| 迭代器 | 容器与算法之间的位置接口 | iterator、const_iterator、reverse_iterator、const_reverse_iterator |
| 算法 | 对区间做计算 | find、swap、reverse、sort、merge |
| 仿函数 | 给算法传规则 | greater、less |
| 适配器 | 改容器或迭代器的接口 | stack、queue、priority_queue |
| 空间配置器 | 容器从哪拿内存 | allocator |

几条配合关系:
- 算法不认识容器,只认一对迭代器。
std::sort(v.begin(), v.end())里的sort不知道参数来自vector,它只需要迭代器支持随机访问。 - 仿函数是给算法传“怎么比”的。
std::greater<int>()就是一个重载了operator()的对象,塞给sort就变成降序。 - 适配器不存数据,它包住一个底层容器,只暴露一部分操作。
stack默认套在deque上,只留push/pop/top这一组接口,vector那样的迭代器和operator[]都不给。 - 空间配置器负责申请与释放内存。容器不直接
new,而是通过allocator拿内存、构造元素,让“数据结构和内存管理”这两件事分开。
容器按访问方式分三类
图里列了八个容器,按底层组织可以归成三类:
- 连续存储:
vector、deque、string。元素地址连续或分段连续,支持operator[]和指针式随机访问,按位置读写快,适合尾部追加。 - 节点式:
list是双向链表,已定位时中间插入删除是常数时间,但查找要逐个走,不支持随机访问。 - 有序关联容器:
set、map、multimap、multiset。底层是平衡树,查找、插入、删除都是 O(log n),还能按区间遍历,比如“分数在 80 到 90 之间的记录”。
stack、queue、priority_queue 不算第四类数据结构,它们是对上面容器的再包装:stack 和 queue 默认用 deque,priority_queue 默认用 vector 加堆算法。选容器时先问三件事:主要按位置访问还是按值查找、增删集中在哪里、数据量多大。答案基本就把容器定下来了。
string 的归类需要说明一句。严格按标准的分节,它属于 strings library,不在 containers 那一节;但它的迭代器、find、sort 用法和容器一致,课件因此把它列进容器一栏。口语里按容器对待没有问题,读标准文档时要知道这是两个分节。
迭代器会失效,这是契约层面的问题
迭代器是“指向容器内部某个位置”的对象。容器一旦重新分配内存、或者把元素搬到别的位置,原来那个迭代器指向的空间可能已经被释放,或者已经不再对应它记录的元素。继续解引用、继续 ++,都是未定义行为。
最典型的是 vector 和 string:扩容、resize、insert、erase 之后旧迭代器都可能作废。规则可以提前记一句——凡是可能“搬家”或改变元素位置的操作,做完之后重新取迭代器。具体到哪几种操作、为什么 erase 一定让位置失效,留到 vector 那篇展开。
四支实现决定了你读到的源码长什么样
课件花了一页讲版本家谱,这段和考古无关,调试时打开的 stl_vector.h 是哪一版,直接取决于发行版用了哪支实现。
- HP 原始版:Alexander Stepanov 和 Meng Lee 在惠普实验室完成,允许任何人拷贝、修改、传播、商用,条件是自己也保持开源。四支都是它的后代。
- P.J. 版:P. J. Plauger 开发,被 Visual C++ 采用,不能公开也不能修改,可读性较低,命名风格比较怪。这里列的两条里,“不能公开修改”是授权限制,不是技术缺陷,课件把它们并排写成“缺陷”容易误导。
- RW 版:课件写作
Rouge Wage,公司名实际是 Rogue Wave Software,被 C++ Builder 采用,不能公开或修改,可读性一般。 - SGI 版:Silicon Graphics 开发,被 GCC 采用,可移植性好,可以公开、修改甚至再分发,命名和代码风格最易读。课件后面要读的那部分 STL 源码,参考的就是这一支。
有一处时间差要补上:今天的 libstdc++ 源自 SGI,但不等于当年那份源码。GCC 5.1 引入了新的库 ABI(二进制接口),std::string 和 std::list 被重新实现,符号进了 std::__cxx11 内联命名空间。拿二十年前的源码剖析文章逐行对照,对不上很正常;链接错误里出现 std::__cxx11::basic_string,说明两边编译时用的 ABI 不一致。
笔试、面试、工作里的位置
课件列了笔试常考的几道题:二叉树层序打印、重建二叉树、两个栈实现一个队列。这些题和 STL 的关系是“用它的零件拼出来”:层序打印用 queue,两个栈实现队列用的就是 stack 的 push / pop / top。
面试里问得更直接。下面的面经记录里,空间配置器、auto_ptr、vector 与 list 的区别、capacity 的增长都是原题:

工作里它解决的是“不重复造轮子”。课件引了一句话:“不懂 STL,不要说你会 C++”。这句话有点绝对,但它说的现象是真的——排序、查找、去重、区间划分这些常用操作,标准库里已经有经过验证的实现,自己再写一遍,收益通常为负。
能用、明理、能扩展
课件收尾给了三个境界:能用、明理、能扩展。

落到日常,三层对应三种具体动作:
- 能用:查文档选对容器,会用
push_back、find、sort这些接口,知道size与capacity不是一回事。 - 明理:读得懂
push_back触发扩容时做了什么,知道迭代器为什么分级、sort为什么拒绝list的迭代器。 - 能扩展:能给算法写比较器,能给容器写分配器,能写一个满足迭代器契约的自定义容器塞进标准算法。
顺序不能颠倒。接口还没用熟就去读源码,看到的只是一堆下划线开头的内部名字;源码没读明白就想扩展,写出来的东西通常和标准库的约定对不上。
还没有评论 — 第一条由你来留。