知识库

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

Properties1
tagscpp, stl, containers, iterators, algorithms

11分钟阅读

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

作者：Scott Meyers | 分类：C++编程进阶 | 核心：STL最佳实践50条

核心观点

STL是C++最强大的标准库组件，但多数人只使用了其皮毛。本书通过50条独立指南，揭示STL使用中常见的陷阱和最佳实践。

关键概念与指南

一、容器选择（Item 1-12）

Item 1. 慎重选择容器类型

  • 区分连续内存容器（vector、string、deque）与节点容器（list、set、map）
  • 连续内存容器插入/删除时会移动元素；节点容器只修改指针
  • 选择标准：是否需要随机访问、是否需要稳定迭代器、空间利用率要求等

Item 2. 警惕”容器无关代码”的幻觉

  • 试图写出适用于多种容器的通用代码往往适得其反
  • 不同容器有不同的迭代器类别、内存布局、失效规则
  • 正确做法：用typedef封装容器类型，需要时通过类封装隐藏实现

Item 3. 容器中对象的拷贝必须廉价且正确

  • 容器存储的是对象的拷贝，不是原对象
  • 拷贝构造函数和赋值运算符决定容器操作的成本
  • 继承体系中的对象存入容器会导致”切片”问题

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

  • empty()对所有标准容器都是O(1)
  • 某些list实现的size()是O(n)

Item 5. 优先使用范围成员函数

  • assign(begin, end)比循环push_back高效
  • insert(pos, begin, end)比循环insert高效
  • 范围操作减少内存重分配和元素移动次数

Item 6. 警惕C++最烦人的解析

  • Widget w();声明函数而非对象
  • MyClass x(ClassName());可能被解析为函数声明
  • 解决方案：用括号包裹参数或使用初始化列表

Item 7. 指针容器需手动delete

  • STL容器不会delete它存储的指针
  • 使用智能指针（如shared_ptr）或手动遍历删除
  • 避免用auto_ptr存入容器（Item 8）

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

  • auto_ptr的拷贝会转移所有权，破坏容器语义
  • 排序等操作可能导致auto_ptr变为NULL
  • 使用shared_ptr替代

Item 9. 谨慎选择删除方式

  • vector/string/deque：erase-remove惯用法
  • list：使用list::remove/remove_if成员函数
  • 关联容器：使用erase成员函数，或遍历+后置递增迭代器

Item 10. 了解分配器的约定与限制

  • 分配器的pointer/reference typedef可被忽略
  • 同类型分配器必须等价（不可有状态）
  • 节点容器（list、关联容器）不使用T的分配器，而是用rebind

Item 11. 自定义分配器的合法用途

  • 控制内存布局、共享内存、特殊堆管理等
  • 分配器不能有per-object状态

Item 12. 对STL容器线程安全要有现实期望

  • 多读者安全、不同容器多写者安全是常见保证
  • 无法自动保证复合操作的线程安全
  • 需手动加锁或使用Lock类管理

二、vector与string（Item 13-18）

Item 13. 优先使用vector/string而非动态数组

  • 自动管理内存，避免忘记delete
  • 完整的STL算法支持
  • 唯一例外：需要与C API兼容且必须用原始数组时

Item 14. 用reserve避免不必要的重分配

  • vector默认容量翻倍增长
  • 预估大小后调用reserve可消除重分配
  • resize改变size，reserve只改变capacity

Item 15. 了解string实现的差异

  • 是否使用引用计数（影响多线程性能）
  • 对象大小从1倍指针到7倍指针不等
  • 小字符串优化（SSO）：短字符串不分配堆内存

Item 16. 知道如何将vector/string数据传递给遗留API

  • vector：使用&v[0]获取指针（空向量时用begin()判空）
  • string：使用s.c_str()获取C字符串
  • 其他容器：先复制到vector再传递

Item 17. 用”swap技巧”缩小多余容量

vector<T>(v).swap(v);  // shrink to fit
vector<T>().swap(v);   // clear and minimize capacity

Item 18. 避免使用vector

  • 不是真正的STL容器（不满足容器要求）
  • 存储为压缩位集，不支持普通指针操作
  • 替代品：deque或bitset

三、关联容器（Item 19-25）

Item 19. 理解相等与等价的区别

  • 相等：operator==
  • 等价：基于排序关系的!(a<b) && !(b<a)
  • 关联容器使用等价，find算法使用相等
  • 自定义比较器时可能产生不同结果

Item 20. 指针关联容器必须指定比较类型

  • 默认按指针值排序，非指针指向的内容
  • 需要自定义比较函数对象

Item 21. 比较函数对相等值必须返回false

  • 严格弱序要求：comp(x,x)必须为false
  • 使用less_equal等会导致容器损坏

Item 22. 避免在set/multiset中就地修改键

  • 修改可能破坏排序
  • 安全做法：删除-修改-重新插入
  • map的键是const，无法直接修改

Item 23. 考虑用排序vector替代关联容器

  • 适合三阶段使用模式：构建→查询→重组
  • 内存占用更小，缓存局部性更好
  • 查询用binary_search/lower_bound等

Item 24. map[]与insert的效率选择

  • 新增元素：insert更高效（避免默认构造+赋值）
  • 更新已有元素：operator[]更高效

Item 25. 熟悉非标准哈希容器

  • hash_set/hash_map等虽非标但广泛可用
  • SGI和Dinkumware是两种主要实现
  • 查找速度O(1)，但无序

四、迭代器（Item 26-29）

Item 26. 优先使用iterator而非const_iterator等

  • 需要时再降级到const版本

Item 27. 用distance和advance转换迭代器

  • 将const_iterator转为iterator

Item 28. 理解reverse_iterator的base()

  • base()返回的是”当前元素之后”的迭代器
  • 用于erase等操作时需特别注意

Item 29. 考虑用istreambuf_iterator进行逐字符输入

  • 比istream_iterator效率更高

五、算法（Item 30-37）

Item 30. 确保目标范围足够大

  • 使用back_inserter等插入迭代器避免越界

Item 31. 了解排序选项

  • sort：不稳定，O(n log n)
  • stable_sort：稳定，可能较慢
  • partial_sort：部分排序
  • nth_element：第n个元素定位

Item 32. remove-like算法后跟erase

  • erase-remove惯用法
  • remove不真正删除元素，只移动

Item 33. 谨慎在指针容器上使用remove-like算法

  • 只移动指针，不删除对象
  • 需配合DeleteObject等functor

Item 34. 注意哪些算法要求排序范围

  • binary_search、lower_bound、upper_bound、equal_range
  • 未排序范围使用这些算法行为未定义

Item 35. 实现大小写不敏感的字符串比较

  • 使用mismatch或lexicographical_compare

Item 36. 正确实现copy_if

  • C++98没有copy_if，需自行实现或用remove_copy_if替代

Item 37. 用accumulate或for_each汇总范围

  • accumulate用于数值计算
  • for_each用于副作用操作

六、函数对象（Item 38-42）

Item 38. functor类按值传递设计

  • 小对象按值传递效率高

Item 39. 谓词必须是纯函数

  • 无副作用，相同输入产生相同输出

Item 40. functor类要可适配

  • 继承binary_function等基类
  • 定义argument_type、result_type等typedef

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

  • 将函数指针/成员函数转为functor

Item 42. 确保less对应operator<

  • 保持一致性

七、STL编程（Item 43-50）

Item 43. 优先使用算法而非手写循环

  • 更高效、更可读、更少bug

Item 44. 优先使用成员函数而非同名算法

  • 关联容器的find比算法find更高效
  • 因为成员函数使用等价而非相等

Item 45. 区分count、find、二分搜索、lower_bound、upper_bound、equal_range

  • 未排序范围：count、find
  • 排序范围：binary_search、lower_bound、upper_bound、equal_range
  • equal_range返回pair，最灵活

Item 46. 考虑用函数对象替代函数作为算法参数

  • 函数对象可被内联，效率更高
  • 函数指针调用有间接开销

Item 47. 避免产出”不可读代码”

  • 过度使用高级STL技巧
  • 适度原则

Item 48. 始终包含正确的头文件

  • 不同编译器头文件可能不同
  • 用typename提示依赖类型

Item 49. 学会解读STL相关编译器诊断

  • 用typedef简化类型名
  • 替换基本字符串gobbledegook为string
  • 忽略实现细节如_Tree

Item 50. 熟悉STL相关网站

  • SGI STL：文档最全，含哈希容器
  • STLport：跨平台移植版，有debug模式
  • Boost：shared_ptr等实用库

可行动点

  1. 代码审查清单：检查是否混用相等和等价判断
  2. 性能优化：vector使用前先reserve
  3. 安全习惯：指针容器使用shared_ptr
  4. 代码风格：优先算法和成员函数，避免手写循环
  5. 调试技巧：学会简化编译器错误信息

与其他知识的关联

关系图谱