《C++ STL 精解》学习笔记

一、常见预处理命令

1. 定义变量和取消定义变量
2. 条件预处理
3. 包含头文件
4. #line预处理命令
5. 特殊预处理命令（error、 pragam 、NULL）
6. 宏（基本预定义宏：__cpluspluc, __FILE__, __LINE__,__TIME__）

命名空间 ：

1. 可以嵌套
2. 匿名命名空间 的使用， IBM

STL组件：容器、迭代器、算法和仿函数

1. 容器：序列式（vector、list、deque）；关联式（set、map、multiset、multimap）
2. 迭代器：输入、输出、前向、双向、随机接入
3. 仿函数：可以理解为函数的一般形式
4. 内存配置器：负责底层的内存分配和释放
5. 适配器：stack、queue、priority_queue

字符串通用操作（string）

1. 构造器和析构器
2. 大小和容量
3. 元素存取：[]不检查索引的有效性，无效时未定义；at()会检查下标是否有效，无效时抛出out_of_range异常
4. 字符串比较
5. 字符串拼接
6. IO操作
7. 字符串修改
8. 查找和替换

explicit ：指定构造函数或转换函数 (C++11 起)不允许隐式转换或复制初始化

二、容器

容器成员必须满足三个条件：可复制、可赋值、可释放

STL容器的数据结构：string、bitset、valarray

for_each find 尤其要注意其中条件表达式的使用

顺序型容器

1. Vector
   Vector <bool> 类：空间高效
2. List
   通过双向链表实现，不提供对元素的随机访问
   插入删除不会使其它迭代器、指针、引用等失效
   特殊成员函数：merge、remove、remove_if、sort、splice、unique
3. Deque
   通过动态数组管理内存，支持随机存取

关联式容器：通常通过二叉树数据结构实现

1. Set
2. Multiset
3. Map
4. Multimap

特殊容器

1. Bitset
   不能改变既定bitset型容器的大小；对bitset型对象进行比较和组合时，对象位的个数必须相同
2. Stack
   可以使用任何序列式容器支持stack，默认使用deque实现
3. Queue
   可以使用任何序列式容器支持queue，只需要该容器包括front(),back(),push_back(),pop_front()即可；默认使用deque实现
4. priority_queue
   可以使用任何序列式容器支持priority_queue，默认使用vector实现

三、算法

非修改性算法、修改性算法、 排序 和相关操作算法、以及删除算法

非修改性算法

1. For_each
2. 元素计数算法： count (), count_if ()
3. 最大最小值算法： min_element (), max_element (),返回迭代器

4. 搜索算法：

   find ()、find_if()：搜索第一个匹配元素，返回迭代器

   search _n ()：搜索前n个连续匹配的值，返回迭代器

   search ()：搜索第一个子区间

   find_end ()：和上面对应，搜索最后一个子区间

   find_first_of ()：搜索某些元素第一次出现的位置

   adjacent_find ()：搜索两个连续相等的元素

5. 比较算法：

   Equal ()：两个对象是否相等

   Mismatch ()：查找两个容器之间首次不同的地方

   Lexicographical_compare ()：字典式比较两个容器

修改性算法

1. 复制（应确保目标区间容量足够大，否则应该使用插入型迭代器）

   copy ()

   copy_backward ()

   remove_copy ()

   remove copy if ()

   replace_copy ()

2. 转换

   transform ()

3. 互换

   swap ()

4. 赋值

   Fill ()

   Fill_n()

   Generate()

   Generate_n()

5. 替换

   replace ()

   Replace_if()

6. 逆转

   Reverse ()

   reverse_copy ()

7. 旋转

   Rotate ()

   Rotate_copy()

8. 排列

   next_permutation () :下一个字典升序

   Prev_permutation() ：前一个字典升序

   Random_shuffle()

   Partition ()

   Stable_partition()

排序及相关操作算法

1. 全部元素排序

   Sort ()：不稳定

   Stable_sort ()：稳定

2. 局部排序

   Partial_sort() ：不稳定

   Partial_sort_copy() ：不改变原始序列的顺序

3. 根据某个元素排序

   nth_element()

4. 堆操作算法

   make_heap ()

   Push_heap() :将最后一个元素加入堆

   Pop_heap() ：将堆顶放到最后并重新构造堆

   Sort_heap()

5. 容器并交差算法

   Merge ()：两个有序集合的总和

   set_union ()：两个已排序集合的并集

   set_intersection ()：两个有序集合的交集

   set_difference () ：两个有序集合的差集

   Inplace _merge() ：连续有序区间的合并

6. 搜索算法

   binary_search () ：在有序区间中搜寻指定元素

   Includes ()：在指定区间中检查若干值是否存在

   lower_bound () ：返回第一个大于等于value的元素位置

   Upper _bound() ：返回第一个大于value的元素位置

   equal_range ()：返回等于value的元素位置的范围

7. 删除算法

   Remove ()

   Remove_if()

   Remove_copy()

   Remove_copy_if()

   Unique ()：移除重复元素（重复元素只保留一份）

   unique_copy () ：复制过程中移除重复元素；要求源区间有序（重复元素只保留一份）

四、迭代器

分类：输入型、输出型、前向型、双向型、随机访问型

输入型：只能从一个序列中读取数据，可以被修改、引用、比较

输出型：只能向一个序列中写入数据，可以被修改和引用（不提供比较操作，不能和尾端迭代器相比较）

前向型：

双向型：所有STL容器都提供了双向型迭代器功能

随机型：可以通过跳跃的方式访问任意数据，具有双向迭代器的所有功能

只有随机访问型迭代器可以通过加减整数取得相对地址，除了输出型迭代器之外其余类型都可以通过distance()函数获取两个迭代器之间的位置。

迭代器配接器

1. 逆向型迭代器

   通常迭代器若具备双向移动的功能，就可以转化成一个逆向迭代器；逆向迭代器类模板提供了一个 base ()成员函数用于将逆向迭代器转化为正常迭代器

2. 插入型迭代器

   插入型迭代器都属于输出型迭代器；分为后插入、前插入和产生型迭代器，区别在于插入位置的不同

   back_inserter (), front_inserter (), inserter ()

3. 流型迭代器

   ostream_iterator ， istream_iterator

迭代器辅助函数

1. Advance ()
2. Distance ()
3. Iter_swap ()

交换两个迭代器所指向元素的值

五、数值计算类模板

复数运算

成员函数：构造函数、实部函数、虚部函数、运算符函数

复数类运算：

1. 算术运算：加减乘除

2. 其它运算：

   Abs()：绝对值

   Norm()：绝对值平方

   Arg()：复数相位

   Conj():共轭

   Polar():复数极坐标形式

3. 复数的超越函数运算：

   三角函数：sin, cos, tan, sinh, cosh, tanh

   指数函数：pow、exp、sqrt、log、log10

数组（向量）运算

通俗来讲， valarray 是经过优化的向量，由描述valarray中各个部分的4个辅助类支持： slice_array 、 gslice_array 、 mask_array 、和 indirect_array

构造函数

下标、赋值以及数学运算

成员函数

1. Size()
2. Sum()
3. Max()
4. Min()
5. Resize()
6. Shift()
7. Cshift()
8. Apply()
9. Free()

超越函数：返回一个新的valarray型数组

abs、pow、exp、sqrt、log、log10、sin、cos、tan、sinh、cosh、tanh、asin、acos、atan、atan2

通用数值运算

求和 accumulate ()、内积 inner_product ()，部分和 partial_sum ()、相邻差 adjacement_difference ()

全局性数学函数

指数、对数、三角、反三角、，等

输入输出类模板

basic_istream 、 basic_ostream 、 basic_iostream

basic_ifstream 、 basic_ofstream 、 basic_fstream

basic_istringstream 、 basic_ostringstream 、 basic_stringstream

标准IO操作符：setprecision()、dec()、hex()、oct()、resetiosflags()、setfill()，等<iomanip>

stream状态：goodbit、eofbit、failbit、badbit

状态函数：good()、fail()、bad()、rdstate()、clear()、setstate()等

输入函数：get、getline、read、readsome、gcount、ignore、peek、unget、putback、tellg、seekg、tellp、seekp

输出函数：put、write

格式标识：std::ios::boolalpha、hex、internal、left、oct、right、scientific、showbase、showpos、skipws、dec、uppercase、fixed等

格式操控符：std::endl、ends、dec、flush、hex、oct、ws等

格式化函数：fill()、precision()、setf()、unsetf()、width()等

六、异常处理类模板

七、通用 工具 类模板

数值极限： numeric_limits

日期和时间 ：

1. 三个类型：size_t、 clock_t 、 time_t
2. 一个结构： tm
3. 十个函数：
   asctime ：将指定的时间tm以字符串形式输出
   ctime ：用于将指定时间time_t以字符串形式输出，并遵循本地时区设置
   strftime ：根据区域设置格式化本地时间/日期
   clock ：返回硬件滴答数，换算成时间需要除以CLK_TCK或者CLOCKS_PER_SEC
   difftime ：返回两个time_t型参数之间的时间差
   gmtime ：用于将传递的time_t转换为格林威治时间
   localtime ：将从1970/01/01零时零分到当前时间系统所偏移的秒数转换为日历时间
   mktime ：和上面相反，将当前日历时间转换为1970/01/01零时零分起至今的UTC时间经过的秒数
   time ：获取当前系统时间

九、语言支持类模板

类型： NULL 、 nullptr 、 offsetof 、 size_t 、 ptrdiff_t

numeric_limits

函数的启动和终止： EXIT_SUCCESS 、 EXIT_FAILURE 、 abort ()、 atexit ()、 exit ()

动态内存分配： new 、 malloc 、 delete 、 free

类型标识符： type_info 、 bad_cast 、 bad_typeid 、 typeid

特殊异常处理： bad_exception 、 unexpected _handler 、 set_unexpected 、 unexpected

异常终止： terminate_handler 、 set_terminate 、 terminate

未捕获异常： uncaught_exception 、

其它类型支持： va_arg 、 va_start 、 va_end 、 va_list 、 setjmp 、 jmp_buf 、 longjmp 、 getenv 、 system 、 signal 、 raise 、 sig atomic t

十、检测类模板

异常类

1. logic_error
2. domain_error
3. invalid_argument
4. length_error
5. out_of_range
6. runtime_error
7. range_error
8. verflow_error
9. underflow_error

断言：无论是debug还是release版本都起作用；捕捉不应该发生的非法情况，而不是捕捉错误

错误码 ：

十一、国际化库

国际化元素

字符：ASCII字符、多字节字符、宽字符

字符排序：

字符分类：字母、数字、标点、其它符号，等

数字：

货币：

时间和日期：

大小写：

语言：

多种字符编码

类 locale

十二、仿函数

概念

仿函数（函数对象）：生成器、一元函数、二元函数

使用仿函数的4中常见形式：

1. 作为排序规则（sort()的第三个参数、set等有序容器的构造函数参数）
2. 拥有内部状态
3. 算法for_each的返回值
4. 作为判断式（predicate、binary predicate）

预定义仿函数

辅助用仿函数

关系仿函数

逻辑仿函数

算术仿函数

其它类型仿函数

适配器

十三、配置器

内存配置器：代表一种特定的内存模型，并提供一种抽象的概念，便于将内存的申请转变为对内存的直接调用

十四、原子运行库模板

原子类和原子模板保证了某操作的原子性。

头文件< atomic >

C++11中的原子操作 c++11新特性之atomic

十五、 线程控制类模板

线程类 ： 构造函数、析构、 id 、get_id、joinable、join、detach、swap

互斥

1. 互斥类型： mutex （lock()、try_lock()、unlock()）、 recursive_mutex 、 timed_mutex 、 recursive_timed_mutex
2. 互斥锁类型： lock_guard （保证可锁定对象的占有权贯穿lock_guard类型对象的整个生命周期）、 unique_lock
3. call_once

条件变量

1. condition_variable 、 condition_variablee_any

十六、模板类 future

1. future_error 、 future_errc 、 future_category
2. promise
3. future
4. shared_future
5. async
6. packaged_task

十七、正则表达式

类模板 basic_regex

名称空间std::regex_constants: syntax_option_type 、 match_flag_type 、 error_type

regex_error