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

六个组件围在中心的 STL 四周,每个方框外侧列出各自的代表类型:算法那栏是 find、swap、reverse、sort、merge,容器那栏是一串容器名。图里容器一栏最后的 mutliset 拼错了,正确名字是 multiset

几条配合关系:

  • 算法不认识容器,只认一对迭代器。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 的增长都是原题:

面试记录里连着问了空间配置器和智能指针的关系、auto_ptr 的缺陷、vector 与 list 的差别,第 8 条单独问 vector 的 capacity 怎么增长。这张图说明的是面试的落点,不是要背的题库

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

能用、明理、能扩展

课件收尾给了三个境界:能用、明理、能扩展。

侯捷在书序里把 STL 的学习分成三层:熟用 STL、了解泛型技术的内涵与 STL 的学理乃至实作、扩充 STL。这张图用的是他 1998 年的原话,三层顺序本身就是学习顺序

落到日常,三层对应三种具体动作:

  • 能用:查文档选对容器,会用 push_back、find、sort 这些接口,知道 size 与 capacity 不是一回事。
  • 明理:读得懂 push_back 触发扩容时做了什么,知道迭代器为什么分级、sort 为什么拒绝 list 的迭代器。
  • 能扩展:能给算法写比较器,能给容器写分配器,能写一个满足迭代器契约的自定义容器塞进标准算法。

顺序不能颠倒。接口还没用熟就去读源码,看到的只是一堆下划线开头的内部名字;源码没读明白就想扩展,写出来的东西通常和标准库的约定对不上。