泛型编程与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