泛型编程与STL

目 录
译序（侯捷） 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