泛型編程與STL

目 錄
譯序（侯捷） i
目錄   v
前言 xv
第一篇 泛型編程（Generic Programming）導入
第1 章 STL 巡禮  3
1.1 一個簡單的例子3
1.2 總結  7
第2 章  算法與區(qū)間（Algorithms and Ranges） 9
2.1 線性查找（Linear Search）  9
    2.1.1 以 C 完成線性查找 10
    2.1.2 Ranges（區(qū)間）  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 臨時緩沖區(qū)（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 拷貝某個區(qū)間（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 充填整個區(qū)間（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 對某個區(qū)間排序（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 身上執(zhí)行集合（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