标准模板库自修教程与参考手册 STL进行C++编程 第2版
作者 :(美)David.R.Musser等编著 贺民,王朝阳译
出版时间: 2003年版
丛编项: Addison-Wesley计算机专业教材
内容简介
本书译自STL经典教程《STL Tutorial and Reference Guide》最新版,本书作者最早提出了STL的基本理论,并对STL的应用和发展作出了卓越贡献。本书内容分为3部分:第1部分是STL的入门知识,介绍了STL组件,STL与其他软件库的区别,迭代器的概念,STL类属算法,序列容器,有序关联容器,函数对象及容器、迭代器和函数适配器;第2部分是综合运用篇,其中给出了大量STL的应用实例;第3部分是STL参考指南,提供了迭代器、容器、类属算法、函数对象和函数适配器的参考信息,如文件、类的产明、示例、描述、构造函数和时间复杂度等。本书内容全面、示例丰富,适合于用C++语言编程的所有开发人员。
目录
第1部分 STL基础入门
第1章 概述
1.1 本书读者
1.2 类属编程的概念及重要性
1.3 C++模板与类属编程
1.3.1 类模板
1.3.2 函数模板
1.3.3 成员函数模板
1.3.4 模板参数的明确说明
1.3.5 默认模板参数
1.3.6 部分说明
1.4 模板的代码膨胀问题
1.5 理解STL性能保证
1.5.1 大O表示法及相关定义
1.5.2 分摊的时间复杂度
1.5.3 大O表示法的局限性
第2章 STL组件概述
2.1 容器
2.1.1 序列容器
2.1.2 有序关联容器
2.2 类属算法
2.2.1 类属查找算法
2.2.2 类属合并算法
2.3 迭代器
2.4 函数对象
2.5 适配器
2.6 分配器
第3章 STL与其他软件库的区别
3.1 可扩展性
3.2 组件的互换性
3.3 算法/容器兼容性
第4章 迭代器
4.1 输入迭代器
4.2 输出迭代器
4.3 前向迭代器
4.4 双向迭代器
4.5 随机访问迭代器
4.6 STL迭代器层次结构:算法与容器之间的高效结合
4.7 插入选代器
4.8 再论输入与输出:流迭代器
4.9 STL算法对迭代器类型要求的定义
4.10 类属算法设计
4.11 算法对迭代器的更高要求
4.12 正确选择算法
4.13 常量迭代器和可变迭代器
4.14 STL容器的迭代器分类
第5章 类属算法
5.1 STL基本算法组织
5.1.1 原地形式和复制形式
5.1.2 具有函数参数的算法
5.2 非可变序列算法
5.2.1 find
5.2.2 adjacent_find
5.2.3 count
5.2.4 for_each
5.2.5 mismatch和equal
5.2.6 search
5.3 可变序列算法
5.3.1 copy和copy_backward
5.3.2 fill
5.3.3 generate
5.3.4 partition
5.3.5 random_shuffle
5.3.6 remove
5.3.7 replace
5.3.8 reverse
5.3.9 rotate
5.3.10 swap
5.3.11 swap_ranges
5.3.12 transform
5.3.13 unique
5.4 排序相关的算法
5.4.1 比较关系
5.4.2 非降序(升序)与非升序(降序)
5.4.3 sort,stable_sort和partial_sort
5.4.4 nth_element
5.4.5 binary_search,lower_bound,upper_bound和equal_range
5.4.6 merge
5.4.7 集合操作和有序结构
5.4.8 堆操作
5.4.9 最小值和最大值
5.4.10 词典序比较
5.4.11 排列生成器
5.5 通用数值算法
5.5.1 accumulate
5.5.2 partial_sum
5.5.3 adjacent_difference
5.5.4 inner_product
第6章 序列容器
6.1 向量
6.1.1 类型
6.1.2 构造序列
6.1.3 插入
6.1.4 删除
6.1.5 访问器
6.1.6 相等和小于关系
6.1.7 赋值
6.2 双端队列
6.2.1 类型
6.2.2 构造函数
6.2.3 插入
6.2.4 删除
6.2.5 访问器
6.2.6 相等和小于关系
6.2.7 赋值
6.3 链表
6.3.1 类型
6.3.2 构造函数
6.3.3 插入
6.3.4 删除
6.3.5 拼接
6.3.6 排序相关的成员函数
6.3.7 清除
6.3.8 访问器
6.3.9 相等和小于关系
6.3.10 赋值
第7章 有序关联容器
7.1 集合和多集
7.1.1 类型
7.1.2 构造函数
7.1.3 插入
7.1.4 删除
7.1.5 访问器
7.1.6 相等和小于关系
7.1.7 赋值
7.2 映射和多映射
7.2.1 类型
7.2.2 构造函数
7.2.3 插入
7.2.4 删除
7.2.5 访问器
7.2.6 相等和小于关系
7.2.7 赋值
第8章 函数对象
8.1 通过函数指针传递函数参数
8.2 通过模板参数定义函数对象的优越性
8.3 STL所提供的函数对象
第9章 容器适配器
9.1 栈容器适配器
9.2 队列容器适配器
9.3 优先级队列容器适配器
第10章 迭代器适配器
第11章 函数适配器
11.1 绑定器
11.2 取反器
11.3 函数指针适配器
第2部分 综合运用:示例程序
第12章 为字典检索编程
12.1 查找给定单词的变位词
12.2 使用标准流和I/O流类交互
12.3 产生全排列并检索词典
12.4 完整程序
12.5 程序运行速度
第13章 编程查找所有变位词组
13.1 查找变位词组
13.2 定义STL使用的数据结构
13.3 创建用于比较的函数对象
13.4 完成变位词组检索程序
13.5 将字典读入PS对象的向量
13.6 使用比较对象排序单词对
13.7 使用等同判定对象搜索临近的相同元素
13.8 使用函数适配器包含判定对象
13.9 将变位词组对复制到输出流
13.10 变位词程序的输出
第14章 更好的变位词程序:使用表和映射容器
14.1 包含迭代器对的数据结构
14.2 在表映射中存储信息
14.3 按大小顺序输出变位词组
14.4 更好的变位词程序
14.5 程序的输出
14.6 使用映射容器的原因
第15章 更快的变位词程序:使用多映射
15.1 搜索变位词组,版本3
15.2 多映射的声明
15.3 将词典读入多映射
15.4 在多映射中查找变位词组
15.5 按照个数多少输出变位词组
15.6 程序的输出
15.7 程序的速度
第16章 定义迭代器类
16.1 迭代器新类型:计数迭代器
16.2 计数迭代器类
第17章 组合STL和面向对象编程
17.1 使用继承和虚函数
17.2 避免容器实例的“代码膨胀”
第18章 显示理论计算机科学族谱的程序
18.1 按日期对学生排序
18.2 关联学生和导师
18.3 查找树根
18.4 读取文件
18.5 打印结果
18.6 完整的“族谱”程序
第19章 用于记时的类属算法的类
19.1 精确测定算法时间的障碍
19.2 排除障碍
19.3 进一步优化
19.4 使用Timer类自动分析
19.4.1 报告最后结果
19.5 STL Sort算法计时
第3部分 STL参考指南
第20章 迭代器参考指南
20.1 输入迭代器的要求
20.2 输出迭代器的要求
20.3 前向迭代器的要求
20.4 双向选代器的要求
20.5 随机访问迭代器的要求
20.6 迭代器特性
20.6.1 迭代器基类
20.6.2 标准迭代器标记
20.7 迭代器运算
20.8 流迭代器
20.8.1 文件
20.8.2 类声明
20.8.3 示例
20.8.4 描述
20.8.5 类型定义
20.8.6 构造函数
20.8.7 公共成员函数
20.8.8 比较运算
20.9 输出流迭代器
20.9.1 文件
20.9.2 类声明
20.9.3 示例
20.9.4 描述
20.9.5 类型定义
20.9.6 构造函数
20.9.7 公共成员函数
20.10 反向迭代器
20.10.1 文件
20.10.2 类声明
20.10.3 示例
20.10.4 描述
20.10.5 构造函数
20.10.6 公共成员函数
20.10.7 全局算法
20.10.8 相等性和顺序判定
20.11 后向插入迭代器
20.11.1 文件
20.11.2 类声明
20.11.3 示例
20.11.4 描述
20.11.5 构造函数
20.11.6 公共成员函数
20.11.7 相应的模板函数
20.12 前向插入迭代器
20.12.1 文件
20.12.2 类声明
20.12.3 构造函数
20.12.4 公共成员函数
20.12.5 相应的模板函数
20.13 插入迭代器
20.13.1 文件
20.13.2 类声明
20.13.3 示例
20.13.4 构造函数
20.13.5 公共成员函数
20.13.6 相应的模板函数
第21章 容器参考指南
21.1 预备知识
21.1.1 STL容器的基本设计和组织
21.1.2 容器的公共成员
21.1.3 可逆容器的要求
21.1.4 序列容器的要求
21.1.5 关联容器的要求
21.2 容器类描述的组织
21.2.1 头文件
21.2.2 类的声明
21.2.3 示例
21.2.4 描述
21.2.5 类型定义
21.2.6 构造函数、析构函数及相关函数
21.2.7 比较操作
21.2.8 访问数据的成员函数
21.2.9 插入数据的成员函数
21.2.10 删除数据的成员函数
21.2.11 附注部分
21.3 向量
21.3.1 头文件
21.3.2 类的声明
21.3.3 示例
21.3.4 描述
21.3.5 类型定义
21.3.6 构造函数、析构函数及相关函数
21.3.7 比较操作
21.3.8 向量元素访问成员函数
21.3.9 向量插入成员函数
21.3.10 向量删除成员函数
21.3.11 关于向量插入成员函数和删除成员函数的附注
21.4 双端队列
21.4.1 头文件
21.4.2 类的声明
21.4.3 示例
21.4.4 描述
21.4.5 类型定义
21.4.6 双端队列构造函数、析构函数及相关函数
21.4.7 比较操作
21.4.8 双端队列元素访问成员函数
21.4.9 双端队列插入成员函数
21.4.10 双端队列删除成员函数
21.4.11 双端队列插入操作的复杂度
21.4.12 关于双端队列删除成员函数的附注
21.5 表
21.5.1 头文件
21.5.2 类的声明
21.5.3 示例
21.5.4 描述
21.5.5 类型定义
21.5.6 表的构造函数、析构函数及相关函数
21.5.7 比较操作
21.5.8 表元素访问成员函数
21.5.9 list类插入数据的成员函数
21.5.10 表的删除成员函数
21.5.11 特殊表操作:Splice,Remve,Remove If,Unique,Merge,Reverse和Sort
21.5.12 关于表插入成员函数的附注
21.5.13 关于表删除成员函数的附注
21.6 集合
21.6.1 头文件
21.6.2 类的声明
21.6.3 示例
21.6.4 描述
21.6.5 类型定义
21.6.6 集合构造函数、析构函数及相关函数
21.6.7 比较操作
21.6.8 集合元素访问成员函数
21.6.9 set类的插入数据的成员函数
21.6.10 集合删除成员函数
21.6.11 特殊集合操作
21.7 多集
21.7.1 头文件
21.7.2 类的声明
21.7.3 示例
21.7.4 描述
21.7.5 类型定义
21.7.6 多集的构造函数、析构函数及相关函数
21.7.7 比较操作
21.7.8 多集访问数据成员函数
21.7.9 多集插入数据成员函数
21.7.10 多集的删除数据成员函数
21.7.11 特殊多集操作
21.8 映射
21.8.1 头文件
21.8.2 类的声明
21.8.3 示例
21.8.4 描述
21.8.5 类型定义
21.8.6 映射的构造函数、析构函数及相关函数
21.8.7 map类的比较操作
21.8.8 map类访问数据的成员函数
21.8.9 映射插入成员函数
21.8.10 映射删除成员函数
21.8.11 特殊映射操作
21.9 多映射
21.9.1 头文件
21.9.2 类的声明
21.9.3 示例
21.9.4 描述
21.9.5 类型定义
21.9.6 多映射的构造函数、析构函数及相关函数
21.9.7 multiamp类的比较操作
21.9.8 多映射元素访问成员函数
21.9.9 多映射插入成员函数
21.9.10 多映射删除成员函数
21.9.11 特殊多映射操作
21.10 栈容器适配器
21.10.1 头文件
21.10.2 类的声明
21.10.3 示例
21.10.4 描述
21.10.5 类型定义
21.10.6 栈的构造函数
21.10.7 栈的公共成员函数
21.10.8 比较操作
21.11 队列容器适配器
21.11.1 头文件
21.11.2 类的声明
21.11.3 示例
21.11.4 描述
21.11.5 类型定义
21.11.6 队列的构造函数
21.11.7 公共成员函数
21.11.8 比较函数
21.12 优先级队列容器适配器
21.12.1 头文件
21.12.2 类的声明
21.12.3 示例
21.12.4 描述
21.12.5 类型定义
21.12.6 优先级队列的构造函数
21.12.7 公共成员函数
21.12.8 优先级队列的比较函数
第22章 类属算法参考指南
22.1 算法描述的组织
22.1.1 原型
22.1.2 示例
22.1.3 详细描述
22.1.4 时间复杂度
22.2 非可变序列算法概述
22.3 for_each
22.3.1 原型
22.3.2 示例
22.3.3 详细描述
22.3.4 时间复杂度
22.4 find
22.4.1 原型
22.4.2 示例
22.4.3 详细描述
22.4.4 时间复杂度
22.5 find_first_of
22.5.1 原型
22.5.2 详细描述
22.5.3 时间复杂度
22.6 adjacent_find
22.6.1 原型
22.6.2 示例
22.6.3 详细描述
22.6.4 时间复杂度
22.7 count
22.7.1 原型
22.7.2 示例
22.7.3 详细描述
22.7.4 时间复杂度
22.8 mismatch
22.8.1 原型
22.8.2 示例
22.8.3 详细描述
22.8.4 时间复杂度
22.9 equal
22.9.1 原型
22.9.2 示例
22.9.3 详细描述
22.9.4 时间复杂度
22.10 search
22.10.1 原型
22.10.2 示例
22.10.3 详细描述
22.10.4 时间复杂度
22.11 search_n
22.11.1 原型
22.11.2 详细描述
22.11.3 时间复杂度
22.12 find_end
22.12.1 原型
22.12.2 详细描述
22.12.3 时间复杂度
22.13 可变序列算法概述
22.14 copy
22.14.1 原型
22.14.2 示例
22.14.3 详细描述
22.14.4 时间复杂度
22.15 swap
22.15.1 原型
22.15.2 示例
22.15.3 详细描述
22.15.4 时间复杂度
22.16 transform
22.16.1 原型
22.16.2 示例
22.16.3 详细描述
22.16.4 时间复杂度
22.17 replace
22.17.1 原型
22.17.2 示例
22.17.3 详细描述
22.17.4 时间复杂度
22.18 fill
22.18.1 原型
22.18.2 示例
22.18.3 详细描述
22.18.4 时间复杂度
22.19 generate
22.19.1 原型
22.19.2 示例
22.19.3 详细描述
22.19.4 时间复杂度
22.20 remove
22.20.1 原型
22.20.2 示例
22.20.3 详细描述
22.20.4 时间复杂度
22.21 unique
22.21.1 原型
22.21.2 示例
22.21.3 详细描述
22.21.4 时间复杂度
22.22 reverse
22.22.1 原型
22.22.2 示例
22.22.3 详细描述
22.22.4 时间复杂度
22.23 rotate
22.23.1 原型
22.23.2 示例
22.23.3 详细描述
22.23.4 时间复杂度
22.24 random_shuffle
22.24.1 原型
22.24.2 示例
22.24.3 详细描述
22.24.4 时间复杂度
22.25 partition
22.25.1 原型
22.25.2 示例
22.25.3 详细描述
22.25.4 时间复杂度
22.26 有序队列算法概述
22.27 sort
22.27.1 原型
22.27.2 示例
22.27.3 详细描述
22.27.4 时间复杂度
22.28 nth_element
22.28.1 原型
22.28.2 示例
22.28.3 详细描述
22.28.4 时间复杂度
22.29 binary_search
22.29.1 原型
22.29.2 示例
22.29.3 详细描述
22.29.4 时间复杂度
22.30 merge
22.30.1 原型
22.30.2 示例
22.30.3 详细描述
22.30.4 时间复杂度
22.31 有序结构的集合运算
22.31.1 原型
22.31.2 示例
22.31.3 详细描述
22.31.4 时间复杂度
22.32 堆操作
22.32.1 原型
22.32.2 示例
22.32.3 详细描述
22.32.4 时间复杂度
22.33 min和max
22.33.1 原型
22.33.2 示例
22.33.3 详细描述
22.33.4 时间复杂度
22.34 lexicographical_compare
22.34.1 原型
22.34.2 示例
22.34.3 详细描述
22.34.4 时间复杂度
22.35 排列生成器
22.35.1 原型
22.35.2 示例
22.35.3 详细描述
22.35.4 时间复杂度
22.36 通用数字算法概述
22.37 accumulate
22.37.1 原型
22.37.2 示例
22.37.3 详细描述
22.37.4 时间复杂度
22.38 inner_product
22.38.1 原型
22.38.2 示例
22.38.3 详细描述
22.38.4 时间复杂度
22.39 partial_sum
22.39.1 原型
22.39.2 示例
22.39.3 详细描述
22.39.4 时间复杂度
22.40 adjacent_difference
22.40.1 原型
22.40.2 示例
22.40.3 详细描述
22.40.4 时间复杂度
第23章 函数对象和函数适配器参考指南
23.1 要求
23.1.1 函数对象
23.1.2 函数适配器
23.2 基类
23.3 算术运算
23.4 比较运算
23.5 逻辑运算
23.6 否定适配器
23.7 绑定适配器
23.8 函数指针适配器
23.9 成员函数指针适配器
第24章 分配器参考指南
24.1 概述
24.1.1 将分配器传递给STL容器
24.2 分配器要求
24.3 默认分配器
24.3.1 文件
24.3.2 类的声明
24.3.3 详细描述
24.3.4 类型定义
24.3.5 构造函数、析构函数和相关函数
24.3.6 其他成员函数
24.3.7 比较运算
24.3.8 关于void的附注
24.4 定制分配器
第25章 实用程序参考指南
25.1 概述
25.2 比较函数
25.3 pair
25.3.1 文件
25.3.2 类声明
25.3.3 例子
25.3.4 描述
25.3.5 类型定义
25.3.6 成员变量
25.3.7 构造函数
25.3.8 比较函数
附录A STL头文件
附录B 字符串参考指南
B.1 字符串类
B.1.1 文件
B.1.2 类声明
B.1.3 描述
B.1.4 类型定义
B.1.5 构造函数、析构函数及相关函数
B.1.6 比较操作
B.1.7 元素访问成员函数
B.1.8 插入成员函数
B.1.9 删除成员函数
B.1.10 附注
B.2 字符特性
B.2.1 文件
B.2.2 描述
B.2.3 类型定义
B.2.4 字符处理函数
附录C 示例程序使用的STL包含文件
C.1 示例17.1中使用的文件
附录D STL资源
D.1 STL的SGI参考实现的Internet地址
D.2 本书示例源代码的万维网地址
D.3 STL兼容的编译程序
D.4 其他相关的STL和C++文档
D.5 类属编程和STL讨论列表
参考文献