知识库

Effective STL - 50条有效使用STL的经验

30分钟阅读

Effective STL

Scott Meyers 经典「Effective 系列」第三弹，专门针对 C++ 标准模板库（STL）的 50 条实用经验。全书 200 页，分 7 大章节，覆盖容器、迭代器、算法、函数对象及 STL 编程实践。每条条款都像一条「专家建议」——不解释理论，直接告诉你什么该做、什么不该做、为什么。

与其他 Meyer 著作的关系：

全书结构

章节主题条款数
1Containers（容器）Item 1–12
2vector and stringItem 13–18
3Associative Containers（关联容器）Item 19–25
4Iterators（迭代器）Item 26–29
5Algorithms（算法）Item 30–37
6Functors（函数对象）Item 38–42
7Programming with the STL（STL 编程实践）Item 43–50

第一章：Containers（容器）— Item 1–12

Item 1: 慎重选择容器类型

STL 容器种类远超想象：

  • 标准序列容器：vector、string、deque、list
  • 标准关联容器：set、multiset、map、multimap
  • 非标准序列容器：slist（单链表）、rope（重型 string）
  • 非标准哈希容器：hash_set、hash_map 等（见 Item 25）
  • 非 STL 容器：数组、bitset、valarray、stack、queue、priority_queue

选择容器要考虑的因素远不止「插入删除频率」：内存布局、迭代器失效、异常安全、排序约束、内存分配策略等。vector 是默认首选，但不是万能的。

Item 2: 当心「容器无关代码」的幻觉

STL 提倡泛型，但试图写出「对所有容器都适用」的代码往往是徒劳的。不同容器的能力差异巨大：

  • 序列容器支持 push_front/push_back，关联容器不支持
  • 关联容器有 count/find/lower_bound 等成员函数
  • vector/deque/string 是连续内存，list 不是
  • 迭代器类别也不同（随机访问 vs 双向 vs 前向）

最佳实践：用 typedef 封装容器类型，方便日后切换，而不是写模板代码强行兼容所有容器。

Item 3: 确保容器中对象的拷贝操作廉价且正确

容器里存的是对象的副本，不是原对象。插入时拷贝、取出时也拷贝。如果拷贝代价大，会严重影响性能。

  • 大对象考虑存指针（但要管理内存，见 Item 7）
  • 考虑用智能指针（见 Item 8 的警告）
  • 拷贝构造函数必须正确（深拷贝 vs 浅拷贝）

Item 4: 用 empty() 而非 size() == 0 判断是否为空

两者逻辑等价，但 empty() 是常数时间 O(1)，而某些容器（如 list）的 size() 可能是线性时间 O(n)（取决于实现是否缓存了大小）。empty() 永远是高效的。

Item 5: 优先使用区间成员函数，而非单元素操作

能用区间版本就不用循环+单元素插入：

  • assign(begin, end) 优于 循环赋值
  • insert(pos, begin, end) 优于 循环 insert
  • 区间构造函数优于默认构造后逐个插入

原因：

  1. 更简洁、更易读
  2. 更高效（单次内存分配 vs 多次）
  3. 避免多次元素移动

Item 6: 警惕 C++ 最令人头疼的语法解析（most vexing parse）

经典陷阱：

ifstream dataFile("ints.dat");
list<int> data(istream_iterator<int>(dataFile), istream_iterator<int>());

这不会创建 list，而是声明了一个返回 list 的函数！第二组参数被解析为函数指针类型。

解决方法：给迭代器参数加上额外的括号，或者用命名的迭代器变量。

这是 C++ 的经典语法歧义：凡是能被解析为函数声明的，就会被解析为函数声明。

Item 7: 容器存 new 出来的指针时，记得在容器销毁前 delete 指针

容器销毁时只会销毁指针本身，不会 delete 指针指向的对象 → 内存泄漏。

解决方案：

  1. 手动循环 delete（易错，异常不安全）
  2. 改用智能指针容器（如 shared_ptr，见 Item 8 对 auto_ptr 的警告）
  3. 改用 Handle 类或引用计数对象

Item 8: 永远不要创建 auto_ptr 容器

auto_ptr 的拷贝语义是所有权转移（拷贝后原指针变为 null），这与 STL 容器对元素的要求（必须能正常拷贝）根本冲突。

标准明确禁止 auto_ptr 容器，编译器应该报错。但某些实现可能不报错，结果是运行时灾难。

替代方案：shared_ptr、引用计数智能指针。

Item 9: 仔细选择删除元素的方式

删除操作因容器类型而异，没有统一写法：

  • 连续内存容器（vector/deque/string）：erase-remove 惯用法 
    c.erase(remove(c.begin(), c.end(), 1963), c.end());
  • list：直接用 c.remove(value) 更高效
  • 关联容器（set/map 等）：用 c.erase(value) 成员函数

按条件删除时同理：

  • 连续容器：erase + remove_if
  • list：remove_if 成员
  • 关联容器：手动循环 erase，但要注意迭代器失效！

Item 10: 了解分配器的约定和限制

allocator 是 STL 中最容易被误解的组件之一。关键点：

  • 分配器是按值传递的，所以不能有状态（或状态必须被正确拷贝）
  • 同类型的分配器必须相等（a1 == a2 必须成立），否则无法互换内存
  • 自定义分配器的指针/引用/大小类型等都有严格的 typedef 要求
  • C++98 的分配器模型限制很多，不支持多态分配器等高级用法

大多数时候你不需要自定义分配器。如果需要，先确保你理解这些约束。

Item 11: 理解自定义分配器的合理用途

什么时候值得写自定义分配器？

  • 内存池/共享内存：特殊内存来源（如共享内存段、内存映射文件）
  • 对齐要求：某些硬件需要特定对齐的内存
  • 性能优化：默认分配器有锁开销，单线程环境可用无锁分配器
  • 内存调试：追踪分配/释放、检测泄漏

但大多数性能瓶颈不在分配器上。先 profiling，再决定是否优化。

Item 12: 对 STL 容器的线程安全性有现实的预期

标准 C++ 对线程只字不提，STL 容器的线程安全性完全取决于实现。

现实情况：

  • 多读安全（多个线程同时读同一个容器通常 OK）
  • 多写不安全（必须自己加锁）
  • 不同容器的多线程安全程度不同

最佳实践：自己加锁，不要依赖实现细节。用 RAII 锁（如 lock_guard）确保异常安全。

第二章：vector 和 string — Item 13–18

Item 13: 优先用 vector 和 string 替代动态分配的数组

用 new[] 分配数组意味着你要承担：

  1. 记得 delete[]（泄漏风险）
  2. 用对 delete 形式（new 对应 delete，new[] 对应 delete[]）
  3. 无法自动扩容

vector 和 string 自动管理内存，支持动态增长，还有完整的 STL 接口。几乎没有理由再用 new[]。

Item 14: 使用 reserve 避免不必要的重新分配

vector/string 扩容时会：

  1. 分配更大的内存（通常 1.5x 或 2x）
  2. 拷贝所有元素到新位置
  3. 销毁旧元素，释放旧内存
  4. 所有迭代器/指针/引用失效

如果你知道大致容量，提前 reserve可以避免多次重新分配，同时避免迭代器失效。

注意：reserve 只改 capacity（容量），不改 size（大小）。resize 改 size。

Item 15: 留意 string 实现的多样性

string 的实现方式比你想象的多得多：

  • COW（Copy-On-Write）：写时复制，共享底层数据。多线程下有性能问题
  • SSO（Small String Optimization）：小字符串存在栈上，不用堆分配
  • 引用计数 + 长度 + 容量
  • 不同的内存布局

这些差异会影响：性能、线程安全、迭代器失效时机等。不要假设所有实现行为一致。

Item 16: 知道如何将 vector 和 string 数据传给 legacy C API

很多 C API 接受数组指针。vector 和 string 可以无缝衔接：

  • vector：&v[0] 或 v.data()（C++11起），等价于 T* 指针
  • string：s.c_str() 返回 const char*，适用于只读 C 字符串

对于 vector，不要用 &v.front() 以外的方式（如 v.begin() 返回迭代器，不是指针）。 对于 string，不要试图通过 &s[0] 修改字符串（C++98 不保证连续存储，C++11 之后可以）。

Item 17: 用「swap 技巧」释放多余容量

vector/string 只会增长，不会自动缩小。即使你 erase 了很多元素，capacity 也不会变。

swap 技巧：

vector<Contestant>(contestants).swap(contestants);
// 创建一个临时 vector（拷贝了当前元素，但 capacity 刚好够用）
// 然后 swap，原 vector 的多余容量被临时对象带走并销毁

string 同理：

string(s).swap(s);

Item 18: 避免使用 vector

vector 有两个问题：

  1. 它不是真正的 STL 容器（不满足容器的所有要求）
  2. 它不真正存储 bool（用位压缩存储，1 位一个元素）

返回的「引用」实际上是一个代理对象（proxy），行为不像真正的 bool&。这会导致各种诡异的 bug。

替代方案：

  • deque<bool>（真正的 bool 容器）
  • bitset（固定大小的位集合）
  • 用 char 代替 bool

第三章：Associative Containers（关联容器）— Item 19–25

Item 19: 理解相等（equality）和等价（equivalence）的区别

这是 STL 中最容易混淆的概念之一：

  • 相等（equality）：基于 operator==，a == b 为 true
  • 等价（equivalence）：基于比较函数（通常 less<T>），!comp(a,b) && !comp(b,a) 为 true

关联容器用等价判断元素是否相同，不是相等。这意味着两个元素可能等价但不相等（当比较函数不基于 == 时）。

Item 20: 为指针的关联容器指定比较类型

如果你直接创建 set<string*>，默认比较器 less<string*> 比较的是指针地址，不是字符串内容！这导致元素按内存地址排序，而不是按字典序。

解决方法：自定义比较器（函数对象），比较指针指向的内容：

struct StringPtrLess {
    bool operator()(const string* a, const string* b) const {
        return *a < *b;
    }
};
set<string*, StringPtrLess> ssp;

Item 21: 永远让比较函数对相等的值返回 false

如果比较函数在两个元素相等时返回 true，会破坏关联容器的不变式。

经典例子：set<int, less_equal<int>> s; s.insert(10); s.insert(10); — 两个 10 都可能被插入，因为 !(10<=10) && !(10<=10) 是 false，容器认为它们不等价。

比较函数必须定义严格弱序（strict weak ordering）。对相等元素返回 true 会导致未定义行为。

Item 22: 避免就地修改 set/multiset 的键

set/multiset 的元素是有序的，如果你修改了一个元素的键值，可能破坏排序顺序 → 后续操作行为未定义。

map/multimap 的 key 是 const 的，编译器会阻止你修改。但 set 的元素不是 const 的（因为元素本身就是键），所以要靠程序员自律。

安全做法：要修改就先 erase 再 insert（虽然有性能代价）。

Item 23: 考虑用排序后的 vector 替代关联容器

对于「查找多、插入删除少」的场景，排序后的 vector + binary_search 可能比 set/map 更快：

  • vector 内存连续，缓存友好（locality of reference）
  • set 是树结构，每个节点都是独立分配，缓存不友好
  • 二分查找的时间复杂度相同（O(log n)），但常数因子更小

插入时先 push_back 再 sort，或者用 lower_bound 找到插入位置。

Item 24: 在效率重要时，仔细选择 map::operator[] 和 map::insert

两者行为不同：

  • operator[]：如果键不存在，先默认构造一个 value，再赋值给它。可能创建你不想要的默认对象。
  • insert：只在键不存在时插入。更高效，也更安全。

经验法则：

  • 更新操作（键一定存在）：用 operator[]，语法简洁
  • 插入操作（键可能不存在，且关心效率）：用 insert

Item 25: 熟悉非标准的哈希容器

标准 C++98 没有哈希表，但几乎每个 STL 实现都提供了非标准版本：

  • SGI 风格：hash_set、hash_map、hash_multiset、hash_multimap
  • 基于哈希表，平均 O(1) 查找，比树结构的关联容器快

C++11 已引入 unordered_set/unordered_map 等标准哈希容器。 如果你需要哈希表且可移植性要求不高，这些非标准容器是很好的选择。

第四章：Iterators（迭代器）— Item 26–29

Item 26: 优先用 iterator 而非 const_iterator / reverse_iterator

虽然四种迭代器都存在，但很多成员函数只接受 iterator：

  • insert(pos, value) 的 pos 必须是 iterator
  • erase(pos) 的 pos 在某些容器中也必须是 iterator

如果你有 const_iterator 但需要 iterator，转换起来很麻烦（见 Item 27）。所以除非确实需要 const，否则用 iterator 更方便。

Item 27: 用 distance 和 advance 将 const_iterator 转为 iterator

C++98 没有直接的转换方式。技巧：

typedef deque<int> IntDeque;
typedef IntDeque::iterator Iter;
typedef IntDeque::const_iterator ConstIter;
 
ConstIter ci;
Iter i(c.begin());
advance(i, distance<ConstIter>(i, ci));

注意：distance 对随机访问迭代器是 O(1)，对其他是 O(n)，可能很慢。

C++11 提供了更直接的转换方式。

Item 28: 了解 reverse_iterator 的 base() 迭代器

reverse_iterator 的 base() 返回对应的「普通迭代器」，但指向的位置不同：

  • reverse_iterator 指向的元素，其 base() 指向下一个元素
  • 类似指针和数组的关系（rbegin 对应 end，rend 对应 begin 前一个位置）

在插入/删除操作时要特别注意这个偏移量，搞清楚你实际操作的是哪个位置。

Item 29: 考虑用 istreambuf_iterator 做逐字符输入

istream_iterator 逐字符读文件时有两个问题：

  1. 它会跳过空白字符（默认情况下）
  2. 它调用 operator>>，有额外开销

istreambuf_iterator 直接从流缓冲区读字符：

  • 不跳过空白
  • 更快（直接操作缓冲区）
  • 适合逐字符处理文本文件

第五章：Algorithms（算法）— Item 30–37

Item 30: 确保目标区间足够大

STL 算法不会自动扩大目标容器的容量。如果你写：

vector<int> results;
transform(v.begin(), v.end(), results.begin(), f);

这是未定义行为 — results 是空的，往 begin() 位置写会越界。

解决方法：

  • 提前 resize 或 reserve + back_inserter
  • 用插入迭代器：back_inserter(results)、front_inserter、inserter

Item 31: 了解你的排序选项

STL 不止 sort 一个排序算法：

  • sort：完全排序，O(n log n)，随机访问迭代器
  • stable_sort：稳定排序（保持相等元素的相对顺序）
  • partial_sort：只排前 N 个元素，其余不管
  • nth_element：只找到第 N 个元素的位置，比 partial_sort 更快
  • partition：按条件分成两组，不排序
  • stable_partition：稳定版本的 partition
  • list::sort：list 专用，用归并排序

选对算法可以节省大量时间。你不需要全排序时，就别用 sort。

Item 32: 真正想删除元素时，在 remove 类算法后调用 erase

remove 不会真正删除元素！ 它只是把要「删除」的元素移到区间末尾，返回新的逻辑末尾迭代器。容器的大小不变。

erase-remove 惯用法：

v.erase(remove(v.begin(), v.end(), val), v.end());

这是 STL 最经典的惯用法之一，必须掌握。

Item 33: 对指针容器使用 remove 类算法要小心

如果容器里存的是指针，remove 只是重新排列指针，被「移除」的指针仍然指向原来的对象 → 内存泄漏（如果你以为它们被删了）。

在 erase 之前，要么先 delete 那些要移除的对象，要么用智能指针容器。

Item 34: 注意哪些算法要求有序区间

有些算法只在有序区间上工作正确：

  • binary_search / lower_bound / upper_bound / equal_range — 二分查找系列
  • set_union / set_intersection / set_difference / set_symmetric_difference — 集合运算
  • merge — 合并两个有序区间
  • inplace_merge — 原地合并

如果你传给它们无序区间，结果是未定义的。这些算法的优势是 O(log n) 或 O(n)，但前提是输入有序。

Item 35: 用 mismatch 或 lexicographical_compare 实现简单的大小写不敏感字符串比较

大小写不敏感字符串比较是常见需求。STL 方式：

  • mismatch：逐字符比较，找到第一个不同的位置
  • lexicographical_compare：字典序比较，返回 bool

两者都可以传自定义比较函数（如大小写无关的比较）。

更复杂的场景（如 Unicode、locale 敏感）需要专门的库。

Item 36: 理解 copy_if 的正确实现

有趣的事实：STL 有 11 个名字带「copy」的算法，但没有 copy_if（C++98 时代）。你需要自己实现：

template <typename InputIterator, typename OutputIterator, typename Predicate>
OutputIterator copy_if(InputIterator begin, InputIterator end,
                       OutputIterator destBegin, Predicate p) {
    while (begin != end) {
        if (p(*begin)) *destBegin++ = *begin;
        ++begin;
    }
    return destBegin;
}

C++11 已加入 std::copy_if。

Item 37: 用 accumulate 或 for_each 做区间汇总

有时候你需要把整个区间「压缩」成一个值：

  • accumulate：求和、求积、拼接字符串等简单汇总
    • 默认是加法，也可传自定义二元操作
  • for_each：更通用的区间遍历，可以做任何事
    • for_each 返回函数对象，可以携带结果

两者的区别：accumulate 用于计算汇总值，for_each 用于产生副作用。

第六章：Functors（函数对象）— Item 38–42

Item 38: 按值传递设计函数对象类

STL 算法总是按值传递函数对象（就像 C 按值传递函数指针一样）。这意味着：

  • 你的函数对象应该拷贝代价低
  • 不应该有太多状态（或状态必须能正确拷贝）
  • 如果状态很大，用 pimpl 手法（把状态放到堆上，用引用计数共享）

经典陷阱：函数对象的状态在拷贝后不同步 → 用 ref/cref 包装（C++11）或者用指针实现。

Item 39: 让谓词成为纯函数

纯函数 = 返回值只依赖参数，没有副作用，也不修改任何状态。

为什么谓词必须是纯函数？因为 STL 算法可能会多次拷贝和调用谓词对象，如果谓词有内部状态且会变化，不同拷贝的状态不一致 → 行为不可预测。

如果你真的需要有状态的谓词，用 Item 38 的 pimpl 技巧，但要非常小心。

Item 40: 让函数对象类可适配

STL 函数适配器（bind1st、bind2nd、not1、not2 等）要求函数对象提供特定的 typedef：

  • argument_type、result_type（一元函数）
  • first_argument_type、second_argument_type、result_type（二元函数）

最简单的方式：继承自 unary_function 或 binary_function 基类，它们提供了这些 typedef。

C++11 用 std::function 和 lambda 替代了这些适配器。

Item 41: 理解 ptr_fun、mem_fun、mem_fun_ref 的用途

这三个函数把普通函数/成员函数包装成可适配的函数对象：

  • ptr_fun：包装普通函数指针
  • mem_fun：包装成员函数指针，通过指针调用
  • mem_fun_ref：包装成员函数指针，通过引用调用

它们的存在是为了让函数指针也能用 bind1st/bind2nd 等适配器。

C++11 的 std::bind 和 lambda 让这些变得过时。

Item 42: 确保 less 等价于 operator<

默认情况下，set<T> 用 less<T> 作为比较器，而 less<T> 默认调用 operator<。

如果你为某个类型特化了 less<T> 但不改 operator<（或反过来），就会造成混乱：有些容器用 less，有些代码用 operator<，行为不一致。

经验：要么都用默认（operator<），要么两者一起改，保持一致。

第七章：Programming with the STL（STL 编程实践）— Item 43–50

Item 43: 优先用算法调用，而非手写循环

三个理由：

  1. 效率：算法作者比你更了解底层实现，优化更好
  2. 正确性：手写循环容易出边界错误、迭代器失效等 bug
  3. 可维护性：算法名表达意图（find、for_each、transform），循环没有语义

但也不要为了用算法而用算法。如果循环写起来更简单清晰，就用循环。见 Item 47。

Item 44: 同名时，优先用成员函数而非算法

有些容器有和算法同名的成员函数：

  • 关联容器：count、find、lower_bound、upper_bound、equal_range
  • list：remove、remove_if、unique、sort、merge、reverse

优先用成员函数，两个原因：

  1. 更快：成员函数知道容器的内部结构（如树结构直接遍历）
  2. 更正确：成员函数用等价关系（基于比较器），算法用相等（基于 ==），关联容器中两者可能不一致

Item 45: 区分 count、find、binary_search、lower_bound、upper_bound、equal_range

查找算法选择指南：

你想知道什么无序区间有序区间
值是否存在？findbinary_search
第一个等于 x 的元素？findlower_bound
有多少个等于 x 的元素？count / count_ifequal_range + distance
第一个大于 x 的元素？—upper_bound
所有等于 x 的范围？find + 遍历equal_range

有序区间的查找都是 O(log n)，无序的是 O(n)。差别巨大。

Item 46: 考虑用函数对象而非函数作为算法参数

反直觉但正确：函数对象通常比函数指针更快。

原因：函数对象是模板参数，编译器可以内联；函数指针是运行时参数，无法内联。

Stepanov 的基准测试显示：sort 用 less<int>()（函数对象）比用 strcmp（函数指针）快得多，因为前者被完全内联了。

这也解释了为什么 C++ 的 sort 通常比 C 的 qsort 快。

Item 47: 避免写出「只写不读」的代码

一行代码塞入 5 个适配器 + 绑定器 + 反向迭代器，虽然很酷，但别人（包括三个月后的你）根本看不懂。

例子：

v.erase(
  remove_if(
    find_if(v.rbegin(), v.rend(), bind2nd(greater_equal<int>(), y)).base(),
    v.end(),
    bind2nd(less<int>(), x)
  ),
  v.end()
);

这行代码在做什么？（答案：删除最后一个 >= y 的元素之前所有 < x 的元素）

经验法则：如果你需要思考超过 10 秒才能理解一行代码，就把它拆成多行，加注释，或者用命名的变量/函数。

Item 48: 永远 include 正确的头文件

不同 STL 实现的头文件依赖不同。在一个平台上编译通过，换个平台可能缺头文件。

基本规则：

  • vector → <vector>
  • string → <string>
  • map → <map>
  • set → <set>
  • 算法 → <algorithm>
  • 迭代器 → <iterator>
  • 函数对象/适配器 → <functional>

不要依赖间接包含，显式 include 你用到的每个组件。

Item 49: 学会解读 STL 相关的编译器错误

STL 的编译器错误信息又长又吓人，动辄几百行。技巧：

  1. 找关键信息：跳过模板实例化堆栈，找真正的错误描述
  2. 替换复杂类型名：用 typedef 简化代码，错误信息也会更清晰
  3. 用静态检查工具：如 STL 特定的 lint 工具
  4. 从小例子开始：逐步增加复杂度，定位哪一步出错

常见错误：传给算法的迭代器类型不匹配、函数对象缺少必要的 typedef、operator[] 用在 const map 上等。

Item 50: 熟悉 STL 相关的网站

推荐资源（2001 年视角）：

  • SGI STL 文档：最完整的 STL 参考
  • STLport：可移植的 STL 实现
  • Boost：高质量 C++ 库集合，很多被收入 C++11/14/17 标准
  • C++ FAQ：通用 C++ 问答

2025 年的更新：cppreference.com 是最权威的在线参考。Boost 仍然重要。

核心洞见总结

1. STL 的设计哲学

STL 不是一个库，而是一个约定。只要你遵循迭代器/容器/算法的约定，你自己写的代码也能无缝融入 STL 生态。

2. 最重要的几条经验

如果只能记住 10 条：

  1. 慎重选容器（Item 1）— vector 不是万能的
  2. empty() 优于 size() == 0（Item 4）
  3. erase-remove 惯用法（Item 9, 32）— 删除元素的标准写法
  4. reserve 提前分配（Item 14）— 避免多次扩容
  5. swap 技巧释放内存（Item 17）
  6. vector 是坑（Item 18）— 别用
  7. 关联容器用等价，不是相等（Item 19）
  8. 目标区间要够大，用 back_inserter（Item 30）
  9. 优先算法，其次手写循环（Item 43）
  10. 同名时成员函数优于算法（Item 44）

3. C++ 版本演进视角

书中很多内容是针对 C++98 的。在现代 C++（C++11 及以后）中，以下已改变或有更好的替代：

  • auto_ptr → unique_ptr / shared_ptr
  • 哈希容器 → unordered_set / unordered_map（标准）
  • bind1st/bind2nd/ptr_fun/mem_fun → std::bind / lambda
  • iterator/const_iterator 转换 → 更灵活
  • vector → 仍然是坑 😅

但这本书的核心思想（选择合适的容器、理解算法的前提条件、注意迭代器失效、避免常见陷阱）完全适用。

关联笔记

关系图谱

反向链接