泛型编程与STL
出版时间：2003
丛编项： 深入C++系列
内容简介
　　许多程序员可能并不知道，C++不仅是一个面向对象程序语言， 它还适用于泛型编程（generic programming）。这项技术可以大大增强你的能力，协助你写出高效率并可重复运用的软件组件（software components）。本书由知名的C++专家Matthew H．Austern执笔，引导你进入泛型编程思维模型，并将你带往此一模型的最重要成品：C++ Standard Template Library（STL）。本书揭示STL的奥秘，告诉你STL不仅仅是一组方便运用的容器类（container classes）。对于泛型组件和可交互作用的组件而言，STL是一个具备扩充能力的框架（framework）、《泛型编程与STL》阐述了泛型编程的中心思想：concepts、modeling、refinement，并为你展示这些思想如何导出STL的基础概念：iterators、containers、function objects。循此路线，你可以把STL想像为一个由concepts（而非明确之functions或classes）组成的程序库：、你将学习其正式结构并因此获得其潜在威力所带来的完整优势。本书使你能够：●以你自己的“可移植组件”及“可交互作用之泛型组件”扩充STL；●产生一些算法，让它们和它们所处理之型别（types）及数据结构彻底划清界线；●撰写更精致、更高效、更有效力的代码，可跨平台重复使用。
目录
目 录
译序（侯捷） i
目录 v
前言 xv
第一篇 泛型编程（Generic Programming）导入
第1 章 STL 巡礼 3
1.1 一个简单的例子3
1.2 总结 7
第2 章 算法与区间（Algorithms and Ranges） 9
2.1 线性查找（Linear Search） 9
2.1.1 以 C 完成线性查找 10
2.1.2 Ranges（区间） 12
2.1.3 以 C++ 完成线性查找 13
2.2 Concepts 和 Modeling 16
2.3 Iterators（迭代器，泛形指针） 19
2.3.1 Input Iterators 20
2.3.2 Ouput Iterators 22
2.3.3 Forward Iterators 24
Constant（不变的）Iterators 和 Mutable（可变的）Iterators 27
2.3.4 Bidirectional Iterators 27
2.3.5 Random Access Iterators 28
2.4 Refinement（精炼、强化） 29
2.5 总结 31
第3 章 再论Iterators（迭代器or泛形指针） 33
3.1 Iterator Traits（迭代器特征）与 Associated Types（相关型别） 33
3.1.1 Value Type（数值型别） 33
3.1.2 Difference Type（差距型别） 36
3.1.3 Reference Type 和 Pointer Type 37
3.1.4 算法的处理与 Iterator Tags 38
3.1.5 把一切统合起来 41
3.1.6 没有 iterator_traits，如何制作 Iterator Traits（迭代器特征） 43
3.2 定义新组件（New Components） 44
3.2.1 Iterator Adapters 46
3.2.2 定义 Iterator 时的建议 47
3.2.3 定义算法时的建议 47
3.3 总结48
第4 章 Function Objects（函数对象） 49
4.1 将线性查找一般化 49
4.2 Function Object Concepts（函数对象概念） 52
4.2.1 一元（Unary）与二元（Binary）Function Objects 52
4.2.2 Predicates 和 Binary Predicates 53
4.2.3 相关型别（Assocated Types） 54
4.3 Function Object Adapters（函数对象配接器） 56
4.4 预定义的 Function Objects 58
4.5 总结58
第5 章 Containers（容器） 59
5.1 一个简单的 Container59
5.1.1 一个 Array Class 60
5.1.2 它是如何运作的 63
5.1.3 最后讨论 63
5.2 Container Concepts 67
5.2.1 元素的容纳（Containment of Elements） 68
5.2.2 Iterators 68
5.2.3 Containers 的阶层架构（hierarchy） 70
5.2.4 最平淡无奇的 Container 71
5.3 大小可变的 Container Concepts 72
5.3.1 Sequences（序列） 73
其它形式的 insert 与 erase 74
安插（Insertion）于开头（Front）和尾端（Back） 74
安插（Insertion）语义和覆写（Overwrite）语义 75
5.3.2 Associative Containers（关系型容器） 75
5.3.3 Allocators（配置器） 78
5.4 总结 78
5.4.1 我们应该使用什么样的 Container？ 78
5.4.2 设计你自己的 Container 79
第二篇 参考手册：STL Concepts 81
第6 章 基本概念（Basic Concepts） 83
6.1 Assignable 83
6.2 Default Constructible 84
6.3 Equality Comparable 85
6.4 可序性（Ordering） 86
6.4.1 LessThan Comparable 86
6.4.2 Strict Weakly Comparable 88
第7 章 Iterators（迭代器or泛型指针） 91
7.1 Trivial Iterator 91
7.2 Input Iterator94
7.3 Output Iterator 96
7.4 Forward Iterator 100
7.5 Bidirectional Iterator 102
7.6 Random Access Iterator 103
第8 章 Function Objects（函数对象） 109
8.1 基本的 Function Objects110
8.1.1 Generator 110
8.1.2 Unary Function111
8.1.3 Binary Function 112
8.2 Adaptable Function Objects 113
8.2.1 Adaptable Generator 113
8.2.2 Adaptable Unary Function 114
8.2.3 Adaptable Binary Function 115
8.3 Predicates 116
8.3.1 Predicate 116
8.3.2 Binary Predicate 117
8.3.3 Adaptable Predicate 118
8.3.4 Adaptable Binary Predicate 119
8.3.5 Strict Weak Ordering 119
8.4 特化的 Concept（Specialized Concepts） 122
8.4.1 Random Number Generator122
8.4.2 Hash Function 123
第9 章 Containers（容器） 125
9.1 General Container Concepts（一般容器概念） 125
9.1.1 Container 125
9.1.2 Forward Container131
9.1.3 Reversible Container 133
9.1.4 Random Access Container134
9.2 Sequence（序列；循序式容器） 136
9.2.1 Sequence136
9.2.2 Front Insertion Sequence 141
9.2.3 Back Insertion Sequence143
9.3 Associative Containers 145
9.3.1 Associative Container 145
9.3.2 Unique Associative Container 149
9.3.3 Multiple Associative Container 152
9.3.4 Simple Associative Container 153
9.3.5 Pair Associative Container 154
9.3.6 Sorted Associative Container 154
9.3.7 Hashed Associative Container 161
9.4 Allocator（空间配置器）166
第三篇 参考手册：算法与类 173
第10 章 基本组件（Basic Components） 175
10.1 pair 175
10.2 Iterator 基本要素（Iterator Primitives）177
10.2.1 iterator_traits 177
10.2.2 Iterator Tag Classes 179
10.2.3 distance 181
10.2.4 advance183
10.2.5 Iterator Base Class 185
10.3 allocator 187
10.4 内存管理基本要素（Memory Management Primitives） 189
10.4.1 construct 189
10.4.2 destroy190
10.4.3 uninitialized_copy 191
10.4.4 uninitialized_fill 194
10.4.5 uninitialized_fill_n 195
10.5 临时缓冲区（Temporary Buffers） 196
10.5.1 get_temporary_buffer 197
10.5.2 return_temporary_buffer 198
第11 章「不改变操作目标物内容」的算法（Nonmutating Algorithms） 199
11.1 线性查找（Linear Search） 199
11.1.1 find 199
11.1.2 find_if200
11.1.3 adjacent_find202
11.1.4 find_first_of204
11.2 子序列匹配（Subsequence Matching）206
11.2.1 search 206
11.2.2 find_end 209
11.2.3 search_n 211
11.3 计算元素个数（Counting Elements） 214
11.3.1 count 214
11.3.2 count_if 216
11.4 for_each 218
11.5 比较两个 Ranges 220
11.5.1 equal 220
11.5.2 mismatch 222
11.5.3 lexicographical_compare 225
11.6 最大值与最小值 227
11.6.1 min 227
11.6.2 max 228
11.6.3 min_element 229
11.6.4 max_element 231
第12 章「会改变操作目标物内容」的算法（Basic Mutating Algorithms）233
12.1 拷贝某个区间（Copying Ranges） 233
12.1.1 copy 233
12.1.2 copy_backward236
12.2 元素互换（Swapping Elements） 237
12.2.1 swap 237
12.2.2 iter_swap 238
12.2.3 swap_ranges 239
12.3 transform 240
12.4 替换元素（Replacing Elements） 243
12.4.1 replace243
12.4.2 replace_if 244
12.4.3 replace_copy 246
12.4.4 replace_copy_if 248
12.5 充填整个区间（Filling Ranges） 249
12.5.1 fill 249
12.5.2 fill_n 250
12.5.3 generate 251
12.5.4 generate_n 252
12.6 移除元素（Removing Elements） 253
12.6.1 remove 253
12.6.2 remove_if 255
12.6.3 remove_copy 256
12.6.4 remove_copy_if 258
12.6.5 unique 259
12.6.6 unique_copy 262
12.7 排列算法（Permuting Algorithms） 264
12.7.1 reverse264
12.7.2 reverse_copy 265
12.7.3 rotate 266
12.7.4 rotate_copy 268
12.7.5 next_permutation269
12.7.6 prev_permutation271
12.8 分割（Partitions） 273
12.8.1 partition 273
12.8.2 stable_partition274
12.9 随机重排与抽样（Random Shuffling and Sampling） 275
12.9.1 random_shuffle 276
12.9.2 random_sample277
12.9.3 random_sample_n 279
12.10 一般化之数值算法（Generalized Numeric Algorithms） 281
12.10.1 accumulate 281
12.10.2 inner_product 283
12.10.3 partial_sum 285
12.10.4 adjacent_difference 287
第13 章 排序和查找（Sorting and Searching） 291
13.1 对某个区间排序（Sorting Ranges） 291
13.1.1 sort 292
13.1.2 stable_sort 294
13.1.3 partial_sort 297
13.1.4 partial_sort_copy 300
13.1.5 nth_element 301
13.1.6 is_sorted 303
13.2 sorted ranges 上的操作行为 305
13.2.1 二分查找法（Binary Search） 305
13.2.1.1 binary_search 306
13.2.1.2 lower_bound 308
13.2.1.3 upper_bound 310
13.2.1.4 equal_range 313
13.2.2 合并（Merging）两个 Sorted Ranges 316
13.2.2.1 merge 316
13.2.2.2 inplace_merge 318
13.2.3 在 Sorted Ranges 身上执行集合（Set）相关操作 320
13.2.3.1 includes 321
13.2.3.2 set_union 324
13.2.3.3 set_intersection327
13.2.3.4 set_difference 330
13.2.3.5 set_symmetric_difference 333
13.3 堆的相关操作（Heap Operations） 336
13.3.1 make_heap 336
13.3.2 push_heap 338
13.3.3 pop_heap 339
13.3.4 sort_heap 342
13.3.5 is_heap343
第14 章 Iterator Classes（迭代器类） 345
14.1 Insert Iterators 345
14.1.1 front_insert_iterator 345
14.1.2 back_insert_iterator 348
14.1.3 insert_iterator 351
14.2 Stream Iterators 353
14.2.1 istream_iterator353
14.2.2 ostream_iterator357
14.2.3 istreambuf_iterator 359
14.2.4 ostreambuf_iterator 362
14.3 reverse_iterator 363
14.4 raw_storage_iterator 368
第15 章 Function Object Classes（函数对象类）371
15.1 Function Object Base Classes371
15.1.1 unary_function 371
15.1.2 binary_function 372
15.2 算术运算（Arithmetic Operations） 373
15.2.1 plus 373
15.2.2 minus 375
15.2.3 multiplies 376
15.2.4 divides378
15.2.5 modulus379
15.2.6 negate 380
15.3 大小比较（Comparisons） 382
15.3.1 equal_to 382
15.3.2 not_equal_to 383
15.3.3 less 384
15.3.4 greater386
15.3.5 less_equal 387
15.3.6 greater_equal388
15.4 逻辑运算（Logical Operations） 390
15.4.1 logical_and 390
15.4.2 logical_or 391
15.4.3 logical_not 393
15.5 证同（Identity）与投射（Projection） 394
15.5.1 identity 394
15.5.2 project1st 395
15.5.3 project2nd 397
15.5.4 select1st 398
15.5.5 select2nd 399
15.6 特殊的 Function Objects 400
15.6.1 hash 400
15.6.2 subtractive_rng 402
15.7 Member Function Adapters 403
15.7.1 mem_fun_t 404
15.7.2 mem_fun_ref_t406
15.7.3 mem_fun1_t 408
15.7.4 mem_fun1_ref_t 410
15.7.5 const_mem_fun_t 412
15.7.6 const_mem_fun_ref_t 414
15.7.7 const_mem_fun1_t416
15.7.8 const_mem_fun1_ref_t 418
15.8 其它的 Adapters 421
15.8.1 binder1st 421
15.8.2 binder2nd 422
15.8.3 pointer_to_unary_function 424
15.8.4 pointer_to_binary_function 426
15.8.5 unary_negate 428
15.8.6 binary_negate429
15.8.7 unary_compose431
15.8.8 binary_compose 433
第16 章Container Classes（容器类） 435
16.1 序列（Sequences） 435
16.1.1 vector 435
16.1.2 list 441
16.1.3 slist 448
16.1.4 deque 455
16.2 Associative Containers（关系型容器） 460
16.2.1 set 461
16.2.2 map 466
16.2.3 multiset 473
16.2.4 multimap 478
16.2.5 hash_set 484
16.2.6 hash_map 488
16.2.7 hash_multiset494
16.2.8 hash_multimap499
16.3 Container Adapters 504
16.3.1 stack 505
16.3.2 queue 507
16.3.3 priority_queue 510
附录A 可移植性与标准化（Portability and Standarization） 515
A.1 语言上的变动 516
A.1.1 Template 编译模型（Compilation Model） 516
A.1.2 带缺省值的Template参数（Default Template Parameters）517
A.1.3 Member Templates 518
A.1.4 局部特化（Partial Specialization） 519
A.1.5 新加入的关键词 521
A.2 程序库的变动 524
A.2.1 Allocator 524
A.2.2 Container Adapters 525
A.2.3 次要的程序库变动 526
A.3 命名及包装（Naming and Packaging） 527
参考书目（Bibliography） 531
索引（Index） 535