C++程序设计语言第四部分标准库

简介

C++程序设计语言第四部分标准库相关笔记

第三十章标准库概览

30.1 引言

标准库是一个组件集合，在ISO C++标准中定义，在所有实现中都以一致的形式(和性能)提供。出于可移植性和长期维护的考虑，强烈推荐在合适的地方尽量使用表混库。一般而言，不要尝试重新发明轮子。

30.1.1 标准库设施

标准库是所有C++实现都必须提供的，以便每个程序员都能依靠它来编写程序。C++标准库提供
- 语言特性的支持，例如内存管理，范围for语句和运行时类型信息
- 具体C++实现所定义的一些语言相关的信息，如最大float值
- 单纯用语言难以高效实现的基本操作，例如 is_polymorphic, is_scalar 和 is_nothrow_constructible
- 底层(无锁)并发编程设施
- 基于线程的并发编程的支持
- 基于任务的并发的基本支持，例如future和async()
- 大多数程序员难以实现最优且可移植版本的函数，例如 uninitialized_fill()和memmove()
- 无用内存回收(垃圾收集)的基本支持，例如declare_reachable()
- 程序员编写可移植代码所需的复杂基础组件，例如list,map,sort和IO流
- 用于标准库自身扩展的框架，例如允许用户为自定义类型提供与内置类型相似的I/O操作的规范和基础组件以及标准模板库STL
标准库的设计目标之一是成为其他库的公共基础。特别是，组合使用标准库特性可以起到三方面的支撑作用
- 可移植性的基础
- 一组紧凑且高效的组件，可以作为构造性能敏感的库和应用的基础
- 一组实现库内交互的组件。

30.2 头文件

标准库组件都定义在命名空间std中，以一组头文件的形式提供。头文件构成了标准库最主要的部分，因此，列出头文件可以给出标准库的一个概貌。
以字母c开头的标准库头文件对应C标准库中的头文件。每个C标准库头文件都定义了一些同时位于全局命名空间和命名空间std中的内容，且有一个定义相同内容的对应头文件。理想情况下，头文件中的名字不会污染全局命名空间，但不幸的是(归咎于管理多语言，多操作系统环境的复杂性)大多数实际情况下会发生污染。
容器
- 可变大小一维数组
- 双端队列
- 单向链表
- 双向链表
- 关联数组
- 集合
- 哈希关联数组
- 哈希集合
- 队列
- 栈
- 固定大小一维数组
- bool数组
关联容器multimap和multiset分别声明在<map>和中，priority_queue声明在中
通用工具
- 运算符和值对
- 元组
- 类型萃取
- 将type_info用作一个关键字或哈希码
- 函数对象
- 资源管理指针
- 限定作用域的分配器
- 编译时有理数算术运算
- 时间工具
- C风格日期和时间工具
- 迭代器及其支持
迭代器机制令标准库算法具有通用性
算法
- 泛型算法
- bseach(), qsort()
一个典型的泛型算法能应用于任何类型的元素构成的序列。C标准库函数bsearch()和qsort()只能用于内置数组，且元素类型不能有用户自定义的拷贝构造函数和析构函数
诊断
- 异常类
- 标准异常
- 断言宏
- C风格错误才处理
- 系统错误支持
字符串和字符
- T的字符串
- 字符分类
- 宽字符分类
- C风格字符串函数
- C风格宽字符字符串函数
- C风格分配函数
- C风格多字节字符串
- 正则表达式匹配
头文件声明了strlen(),strcpy()等一族函数。头文件声明了atof()和atoi()，可将C风格字符串转换为数值。
输入/输出
- I/O组件的前置声明
- 标准iostream对象和操作
- iostream基类
- 流缓冲
- 输入流模板
- 输出流模板
- 操纵符
- 字符串流
- 字符分类函数
- 文件流
- printf() I/O函数族
- 宽字符printf()风格I/O函数
操纵符是操作流状态的对象
本地化
- 表示文化差异
- 文化差异C风格表示
- 代码转换
locale对日期输出格式，货币表示符号和字符串校勘等在不同语言和文化中有差异的内容进行本地化
语言支持
- 数值限制
- 数值标量限制C风格宏
- 浮点数限制C风格宏
- 标准整数类型名
- 动态内存管理
- 运行时类型识别支持
- 异常处理支持
- initializer_list
- C标准库语言支持
- 可变长函数参数列表
- C风格栈展开
- 程序终止
- 系统时钟
- C风格信号处理
头文件定义了sizeof()返回的类型size_t，指针减法和数组下标返回的类型ptrdiff_t以及声名狼藉的NULL宏
C风格栈展开(使用)与析构函数和异常处理不兼容，因此最好避免使用。
数值
- 复数及其运算
- 数值向量及其运算
- 推广的数值运算
- 标准数学函数
- C风格随机数
- 随机数发生器
由于历史原因，abs()和div()不像其他数学函数那样在中，而是在中
并发
- 原子类型及其操作
- 等待动作
- 异步任务
- 互斥类
- 线程
C标准库的一些组件与C++程序员有着不同程度的关联，C++标准库提供了对这些组件的访问机制。
C兼容性
- 公共整数类型的别名
- C的bool类型
- 浮点数环境
- C的对齐机制
- C的泛型数学函数：和

30.3 语言支持

语言支持是标准库中很小但至关重要的部分，是程序正常运行所必需的，因为语言特性依赖于这些组件。
标准库支持的语言特性
- new和delete
- typeid()和type_info
- 范围for
- initializer_list

30.3.1 initializer_list 支持

一个 {} 列表会依据规则转换为一个 std::initializer_list 类型的对象。

不幸的是, initializer_list并未提供下标运算符。如果你希望用 [] 而不是 *，可对指针使用下标

void f(initializer_list<int> lst)
{
const int* p = lst.begin();
for (int i = 0; i < lst.size(); i++>)
{
  std::cerr << p[i] << "\n";
}
}

initializer_list自然也可用于范围for语句

void f2(initializer_list<int> lst)
{
for (auto x : lst)
{
  std::cerr << x << "\n";
}
}

30.3.2 范围for支持

一条范围for语句会借助迭代器映射为一条for语句。
在中，标准库提供了std::begin()和std::end()两个函数，可用于内置数组及任何提供了begin()和end()成员的类型。
所有标准库容器和字符串都支持使用范围for的迭代；容器适配器(例如stack和priority_queue)则不支持。容器的头文件(例如)会包含，因此用户很少需要自己直接包含它。

30.4 错误处理

标准库包含的组件已有将近40年的开发历程。因此，它们处理错误的风格和方法并不统一
- C风格库函数大多数通过设置errno来指示发生了错误
- 很多对元素序列进行操作的算法返回一个尾后迭代器来指示未找到或失败
- I/O流库要依赖于每个流中的一个状态来反映错误，并可能(根据用户需要)通过抛出异常来指示错误。
- 一些标准库组件，例如vector,string和bitset通过抛出异常来指示错误。
标准库的设计目标之一是所有组件都遵守基本保证：即，即使抛出了异常，也不会有资源(例如内存)泄露，且不会有标准库类的不变式被破坏的情况出现。

30.4.1 异常

一些标准库组件通过抛出异常来报告错误
标准库异常
- bitset: 抛出invalid_argument, out_of_range,overflow_error
- iostream: 如果允许异常的话，抛出ios_base::failure
- regex: 抛出regex_error
- string: 抛出length_error,out_of_range
- vector: 抛出out_of_range
- new T: 如果不能为一个T分配内存，抛出bad_alloc
- dynamic_cast(r): 如果不能将引用r转换为一个T，抛出bad_cast
- typeid(): 如果不能获得一个type_info,抛出bad_typeid
- thread: 抛出system_error
- call_once(): 抛出system_error
- mutex: 抛出system_error
- condition_variable: 抛出system_error
- async(): 抛出system_error
- packaged_task: 抛出system_error
- future和promise: 抛出system_error
任何直接或间接使用这些组件的代码都可能遇到这些异常。
除非你确认使用组件的方式不会令它们抛出异常，否则坚持在某处(例如main())捕获标准库异常类层次的某个根类(例如exception)和任何异常(…)是一个很好的编程习惯。

30.4.1.1 标准库exception类层次

不要抛出int，C风格字符串等内置类型，而应该抛出专门表示异常的类型的对象。

30.4.1.2 异常传播

中提供了一些组件，令异常传播对程序员可见
异常传播
- exception_ptr: 非特定的异常指针类型
- ep = current_exception() ep是一个exception_ptr,指向当前异常，若当前无活动异常则不指向任何异常；不抛出异常
- rethrow_exception(ep): 重新抛出ep指向的异常；ep包含的不能是空指针nullptr；无返回值
- ep = make_exception_ptr(e): ep是指向exception e的exception_ptr；不抛出异常。
一个exception_ptr可以指向任何异常，不局限于exception类层次中的异常。可将exception_ptr看作一种智能指针(类似shared_ptr)–只要一个exception_ptr还指向其异常，那么这个异常就会保持活跃。这样，我们就可以通过exception_ptr将一个异常从捕获它的函数中传递出来，并在其他地方重新抛出。即，exception_ptr可用来实现在捕获线程之外的其他线程中重抛出异常，这是promise和future所需要的。对一个exception_ptr使用rethrow_exception(在不同线程中)不会引起数据竞争。
异常不能从noexcept函数中传播出去.

30.4.1.3 terminate()

在中，标准库提供了处理意外异常的组件
terminate
- h = get_terminate(): h为当前终止处理程序；不抛出异常
- h2 = set_terminate(): 当前终止处理程序被设定为h；h2为旧终止处理程序；不抛出异常
- terminate(): 终止程序；无返回值；不抛出异常。
除了极特殊的情况下使用set_terminate()和terminate()之外，其他情况应避免使用这些函数

30.4.2 断言

标准库提供了断言机制
断言
- static_assert(e, s) 在编译时对e求职；若!e为假则将s作为编译器错误信息输出
- assert(e): 若宏NOBUG未定义，则在运行时对e进行求职，若!e为假，向cerr输出一个消息并调用abort();若定义了NOBUG，则什么也不做。
- assert()是一个宏，定义在中，assert()生成什么错误信息由C++具体实现自己决定，但应该包含源文件名(__FILE__)和assert()所在的源码行号(__LINE__)
- 断言常常用于产品级代码而非教材的小例子中(它也本应如此)
- 函数名(func)也可能包含在消息中。

30.4.3 system_error

在中，标准库提供了一个能从操作系统和底层系统组件报告错误的框架。

30.4.3.1 错误码

当一个错误以错误码的形式从程序底层浮上来时，我们必须处理这个错误或将错误码转换为一个异常。

30.4.3.2 错误类别

30.4.3.3 system_error异常

system_error报告的错误都源自标准库中处理操作系统的部分。它传递一个error_code，并可传递一个错误消息字符串。
自然的，system_error可用于标准库之外的程序。它传递一个系统相关的error_code，而不是一个可移植的error_condition

30.4.3.4 可移植的错误状态

可移植错误码(error_condition)的表现形式与系统相关的error_code几乎相同。总体思路是每个系统有一组特有的(“原生的”)错误码，可映射到潜在可移植的错误码，这样对于需要跨平台编程的程序员(通常是编写库的程序员)来说会更加方便。

30.5 建议

使用标准库组件保持可移植性
使用标准库组件尽量减少维护成本
将标准库组件作为更广泛和更专门化的库的基础
使用标准库组件作为灵活，广泛使用的软件的模型
标准库组件定义在命名空间std中，都是在标准库头文件中定义的
每个C标准库头文件X.h都有其C++标准库对应的版本
必须#include相应的头文件才能使用标准库组件
为了对内置数组使用范围for，需要 #include
优选基于异常的错误处理而非返回错误码方式的错误处理
始终要捕获 exception&(对标准库和语言支持的异常)和…(对意料之外的异常)
标准库exception层次可以(但不是必须支持)用于用户自定义异常
如果发生严重错误，调用terminate()
大量使用static_assert()和assert()
不要假定assert()总是会被求值

第三十一章 STL容器

31.1 引言

STL包含标准库中的迭代器，容器，算法和函数对象几个部分。

31.2 容器概览

一个容器保存着一个对象序列。容器可分类为
- 顺序容器提供对元素(半开)序列的访问
- 关联容器提供基于关键字的关联查询
此外，标准库还提供了一些保存元素的对象类型，它们并未提供顺序容器或关联容器的全部功能
- 容器适配器提供对底层容器的特殊访问
- 拟容器保存元素序列，提供容器的大部分但非全部功能
STL容器都是资源句柄，都定了拷贝和移动操作。所有容器操作都提供了基本保证，确保与基于异常的错误处理机制能够正确协同工作。
顺序容器
- vector<T, A> 空间连续分配的T类型元素序列，默认选择容器
- list<T, A> T类型元素双向链表，当需要插入/删除元素但不移动已有元素时选择它
- forward_list<T, A> T类型元素单向链表，很短的或空序列的理想选择
- deque<T, A> T类型元素双端队列，向量和链表的混合，对大多数应用而言，都比向量和链表其中之一要慢。
这些容器都定义在,和中。顺序容器为元素连续分配内存(例如vector)或将元素组织为链表(例如forward_list)，元素的类型是容器的成员value_type(或者是上表中的T)。deque(发音为 deck)采用链表和连续存储的混合方式。
除非你有充足的理由，否则应该优选vector而不是其他顺序容器。注意，vector提供了添加，删除元素的操作，这些操作都允许vector按需增长或收缩。对于包含少量元素的序列而言，vector是一种完美的支持列表操作的数据结构。
当在一个vector中插入，删除元素时，其他元素可能会移动。与之相反，链表或关联容器中的元素则不会因为插入新元素或删除其他元素而移动。
forward_list(单向链表)是一种专为空链表和极短链表优化过的数据结构。一个空forward_list只占用一个内存字。在实际应用中，有相当多的情况链表是空的(还有很多情况链表是非常短)
有序关联容器
- map<K,V,C,A> 从K到V的有序映射，一个(K,V)对序列
- multimap<K,V,C,A> 从K到V的有序映射，允许重复关键字
- set<K,C,A> K的有序集合
- multiset<K,C,A> K的有序集合，允许重复关键字
这些容器通常用平衡二叉树(通常是红黑树)实现
关键字(K)的默认序标准是 std::less
类似顺序容器，模板参数A是分配器，容器用它来分配和释放内存。对映射，A的默认值是 std::allocator<std::pair<const K,T»，对集合，A的默认值是std::allocator
无序关联容器
- unordered_map<K,V,H,E,A> 从K到V 的无序映射
- unordered_multimap<K,V,H,E,A> 从K到V 的无序映射，允许关键字重复
- unordered_set<K,H,E,A> K的无序集合
- unordered_multiset<K,H,E,A> 从K的无序集合，允许关键字重复
这些容器都是采用溢出链表法的哈希表实现。关键字类型K的默认哈希函数类型H为 std::hash。关键字类型K的默认相等判断函数类型E为 std::equal_to；相等性判定函数用来判断哈希值相同的两个对象是否相等
容器适配器是一类特殊容器，它们为其他容器提供了特殊的接口
- priority_queue<T,C,Cmp> T的优先队列，Cmp是优先级函数类型
- queue<T,C> T的队列，支持push()和pop()操作
- stack<T,C> T的栈，支持push()和pop()操作
一个priority_queue的默认优先级函数Cmp为std::less.queue的默认容器类型C为 std::deque,stack和priority_queue的默认容器类型C为std::vector
某些数据类型具有标准容器所应有的大部分特性，但又非全部。我们有时称这些数据类型为拟容器。
- T[N] 固定大小的内置数组；N个连续存储的类型为T的元素；没有size()或其他成员函数
- array<T, N> 固定大小的数组，N个连续存储的类型为T的元素，类似内置数组，但解决了大部分问题。
- basic_string<C, Tr, A> 一个连续分配空间的类型为C的字符序列，支持文本处理操作，例如连接(+, +=)；basic_string通常都经过了优化，短字符串无须使用自由存储空间。
- string basic_string
- u16string basic_string
- u32string basic_string
- wstring basic_string
- valarray 数值向量，支持向量运算，但有一些限制，这些限制是为了鼓励高性能实现；只在做大量向量运算时使用
- bitset N个二进制位的集合，支持集合操作，例如&和|
- vector vector的特例化版本，紧凑保存二进制位
对basic_string，A是其分配器，Tr是字符萃取
如果可以选择的话，应该有限选择vector,string或array这样的容器，而不是内置数组。内置数组有两个问题–数组到指针的隐式类型转换和必须要记住大小，它们都是错误的主要来源。
还应该优先选择标准字符串，而不是其他字符串或C风格字符串。C风格字符串的指针语义意味着笨拙的符号表示和程序员的额外工作，它也是主要错误来源之一(例如内存泄漏)

31.2.1

C++标准并未给标准容器规定特定的表示形式，而是指明了容器接口和一些复杂性要求。实现者会选择适当的(通常也是巧妙优化过的)实现方法来满足一般要求和常见用途。除了处理元素所需的一些内容之外，这类句柄还持有一个分配器。
对于一个vector，其元素的数据结构很可能是一个数组。vector会保存指向一个元素组的指针，还会保存元素数目和向量容量(已分配的和尚未使用的位置数)或等价的一些信息
list很可能表示为一个指向元素的链接序列以及元素数目
forward_list很可能表示为一个指向元素的链接序列
map很可能实现为一颗平衡树，树节点指向(键，值)对
unorder_map很可能实现为一个哈希表
string的实现可能为：短string的字符保存在string句柄内，而长string的元素则保存在自由存储空间中的连续区域(类似vector的元素)。类似vector，一个string也会预留空闲空间，以便扩张时不必频繁的重新分配空间
类似内置数组，array就是一个简单的元素序列，无句柄。这意味着一个局部array不会使用任何自由存储空间(除非它本身实在自由存储空间中分配的)，而且一个类的array成员也不会悄悄带来任何自由存储空间操作。

31.2.2 对元素的要求

若想作为一个容器的元素，对象类型必须允许容器拷贝，移动以及交换元素。如果容器使用拷贝构造函数或拷贝赋值操作拷贝一个元素，拷贝的结果必须是一个等价的对象。这大致意味着任何对象值相等性检测都必须得到副本和原值相等的结论。换句话说，元素拷贝必须能像int的普通拷贝一样正常工作。
类似的，移动构造函数和移动赋值操作也必须具有常规定义和常规移动语义。此外，元素类型还必须允许按常规语义交换元素。如果一个类型定义了拷贝或移动操作，则标准库swap()就能正常工作。
对元素类型的要求和细节散布在C++标准中，很难阅读，但基本上，如果一个类型具有常规的拷贝或移动操作，容器就能保存该类型元素。只要满足容器元素的基本要求和算法的特定要求(例如元素有序)，很多基本算法，例如copy(),find()和sort()都能正常运行。
当无法拷贝对象时，一个替换方案是将对象指针而不是对象本身保存在容器中。最典型的例子就是多态类型。例如，**我们使用vector<unique_prt>或vector<Shape*>，而不是vector来保证多态性行为**。

31.2.2.1 比较操作

关联容器要求其元素能够排序，很多可以应用于容器的操作也有此要求。默认情况下，< 运算符被用来定义序。如果 < 不合适，程序员必须提供一个替代操作。
排序标准必须定义一个严格弱序(strict weak ordering)。形式化地描述，即小于和相等关系(如果定义了的话)都必须是传递的。

31.3 操作概览

常量，表示操作花费的时间不依赖于容器中的元素数目；常量时间(constant time)的另一种常见表示方式是O(1)。O(n)表示操作花费的时间与元素数目成正比
所有容器的size()操作都是常量时间的。

31.3.1 成员类型

每个容器都定义了如下一组成员类型
- value_type 元素类型
- allocator_type 内存管理类型
- size_type 容器下标，元素数目等无符号类型
- difference_type 迭代器差异的带符号类型
- iterator 行为类似value_type*
- const_iterator 行为类似 const_value_type*
- reverse_iterator 行为类似 value_type*
- const_reverse_iterator 行为类似 const_value_type*
- reference const_value_type&
- const_reference 行为类似value_type*
- pointer 行为类似 value_type*
- const_pointer 行为类似 const_value_type*
- kep_type 关键字类型；仅关联容器具有
- mapped_type 映射值类型；仅关联容器具有
- key_compare 比较标准类型；仅有序容器具有
- hasher 哈希函数类型: 仅无序容器具有
- key_euqal 等价性检验函数类型；仅无需容器具有
- local_iterator 桶迭代器类型；仅无需容器具有
- const_local_iterator 桶迭代器类型；仅无需容器具有
每个容器和拟容器都提供了上表中大多数成员类型，但是不会提供无意义的类型

31.3.2 构造函数，析构函数和赋值操作

赋值操作并不拷贝或移动分配器，目标容器获得了一组新的元素，但会保留其旧分配器，新元素(如果有的话)的空间也是用此分配器分配的。
谨记，一个构造函数或是一次元素拷贝可能会抛出异常，来指出它无法完成这个任务
紧急，对大小初始化器使用 (),而对其他所有初始化器都是用 {}
容器通常都很大，因此我们几乎总是以引用方式传递容器实参。但是，由于容器是资源句柄，我们可以高效地以返回值的方式返回容器(隐含使用移动操作)。类似地，当我们不想用别名的时候，可以用移动方式传递容器实参。

31.3.3 大小和容量

大小是指容器中的元素数目；容量是指在重新分配更多内存之前容器能够保存的元素数目。
在改变大小或容量时，元素可能会被移动到新的存储位置。这意味着指向元素的迭代器(以及指针和引用)可能会失效(即，指向旧元素的位置)
指向关联容器(例如map)元素的迭代器只有当所指元素从容器中删除(erase())时才会失效。与之相反，指向顺序容器(例如vector)元素的迭代器当元素重新分配空间(例如resize(), reverse()或push_back())或所指元素在容器中移动(例如在前一个位置进行erase()或insert())时也会失效。

31.3.4 迭代器

容器可以看作按容器迭代器定义的顺序或相反的顺序排列的元素序列。对一个关联容器，元素的序由容器比较标准(默认为 < )决定
元素遍历的最常见形式是从头至尾遍历一个容器。最简单的遍历方法是使用范围for语句，它隐含的使用了begin()和end()
当我们需要了解一个元素在容器中的位置或需要同时引用多个元素时，就要直接使用迭代器。在这些情况下，auto很有用，它能帮助尽量简化代码并减少输入错误。

31.3.5 元素访问

31.3.6 栈操作

标准vector,deque和list(不包括forward_list和关联容器)提供了高效的元素序列尾部操作
栈操作
- c.push_back(x) 将x添加到c的尾元素之后(使用拷贝或移动)
- c.pop_back() 删除c的尾元素
- c.emplace_back(args) 用args构造一个对象，将它添加到c的尾元素之后
c.push_back(x)将x移动或拷贝入x，这会将c的大小增加1。如果内存耗尽或x的拷贝构造函数抛出一个异常，c.push_back(x)会失败。push_back()失败不会对容器造成任何影响，因为标准库操作都提供了强保证。

31.3.7 列表操作

31.3.8 其他操作

容器可以比较和交换
swap()操作既交换元素也交换分配器

31.4 容器

31.4.1 vector

STL的vector是默认容器–除非你有充分理由，否则应该使用它。如果你希望使用链表或内置数组替代vector，应慎重考虑后再做决定。

31.4.1.1 vector和增长

使用大小(元素数目)和容量(不重新分配空间的前提下可容纳的元素数目)零push_back()操作时的向量增长相当高效：不会在添加每个元素时都分配内存，而是在超出容量时才进行一次重新分配。C++标准并未指出超出容量时向量的增长幅度，但很多C++实现都是增加大小的一半。
容量的概念令指向vector元素的迭代器只有在真正发生重分配时才会失效。

31.3.1.2 vector和嵌套

与其他数据结构相比，vector(以及类似的连续存储元素的数据结构)有三个主要优势
- vector的元素是紧凑存储的：所有元素都不存在额外的内存开销。类型为vector的vec的内存消耗大致为 sizeof(vector) + vec.size() * sizeof(x)。其中sizeof(vector) 大约为12个字节，对大向量而言是微不足道的
- vector的遍历非常快。为访问下一个元素，我们不必利用指针间接寻址，而且对类vector结构上的连续访问，现代计算机都进行了优化。这使得vector元素的线性扫描(就像find()和copy()所做的)接近最优
- vector支持简单且高效的随机访问。这使得vector上的很多算法(例如sort()和binary_search())非常高效

31.3.1.3 vector和数组

vector是一种资源句柄，这是允许改变大小和实现高效移动语义的原因。但是这一特点偶尔也会变为缺点–尤其是与不依赖于元素和句柄分离存储的数据结构(例如内置数组和array)相比。将元素序列保存在栈中或另一个对象中可能会带来性能上的优势。

31.3.1.4 vector和string

vector是可改变大小，连续存储的char序列，string也是如此。那么我们应该如何在两者之间进行选择呢
vector是一种保存值的通用机制，并不对保存的值之间的关系做任何假设。对一个vector而言，字符串Hello,World只不过是一个13个char类型的元素的序列而已。与之相反，string的设计目的就是保存字符序列，它认为字符间的关系是非常重要的。因此，我们很少会对string中的字符进行排序，因为这会破坏字符串的含义。某些string操作反映了这一点(例如c_str(), >> 和 find() C风格字符串以0结束)。string的实现也反映了对其使用方式的假设。

31.4.2 链表

STL提供了两种链表类型
- list：双向链表
- forward_list：单向链表
list为元素插入和删除操作进行了优化。当你向一个list插入元素或是从一个list删除元素时，list中其他元素的位置不会受到影响。特别的是，指向其他元素的迭代器也不会受到影响。
默认情况下，list的元素都独立分配内存空间，而且要保存指向前驱和后继的指针。与vector相比，每个list元素占用更多内存空间(通常每个元素至少多4个字)，遍历(迭代)操作也要慢得多，因为需要通过指针进行间接寻址而不是简单的连续访问。
forward_list是单向链表。你可以将其看作一种为空链表或很短的链表专门优化的数据结构，对这类链表的操作通常是从头开始遍历。

31.4.3 关联容器

关联容器支持基于关键字的查找。它有两个变体
- 有序关联容器(ordered associative container)基于一个序标准(默认是小于比较操作 <)进行查找。这类容器用平衡二叉树实现，通常是红黑树
- 无序关联容器(unordered associative container)基于一个哈希函数进行查找。这类容器用哈希表实现，采用溢出链表策略。
两类容器都支持
- map: {键，值}对序列
- set: 不带值的map(或者你可以说关键字就是值)
最后，映射和集合，无论是有序还是无序的，都有两个变体
- 普通映射或集合：每个关键字只有唯一一项
- 多重映射或集合：每个关键字可对应多项。
一个关联容器的名字指出了它在三维空间{集合映射，普通无序，普通多重}中的位置。

31.4.3.1 有序关联容器

实际上，[]并不仅仅是insert()的简写形式，它所做的要更多一些。m[k]的结果等价于 (*(m.insert(make_pair(k,v{})).first)).second，其中V是映射类型。insert(make_pair())这种描述方式相当冗长，我们可以用emplace()取而代之：dictionary.emplace(“sea cow”, “extinct”);
关联容器中元素的关键字是不可变的。因此，我们不能改变set中的值。我们甚至不能改变不参与比较的元素的成员。如果需要修改元素，应使用map。不要尝试修改关键字：假如你成功了，就意味着查找元素的底层机制会崩溃。

31.4.3.2 无序关联容器

无序关联容器都是用哈希表实现的。对简单应用而言，无序关联容器与有序容器的差别不大，因为关联容器共享大部分操作。
unordered_map的遍历顺序取决于插入顺序，哈希函数和装载因子。特别是，元素的遍历顺序并不保证与其插入顺序一致。

31.4.3.3 构造unordered_map

31.4.3.4 哈希和相等判定函数

用户可以自定义哈希函数，定义方式有多种，不同的技术可满足不同的需求。

31.4.3.5 装载因子和桶

无序容器实现的重要部分对程序员是可见的。我们说具有相同哈希值的关键字落在同一个桶中。程序员也可以获取并设置哈希表的大小。
无序关联容器的装载因子(load factor)定义为已用空间的比例。例如，若capacity()为100个元素，size()为30，则load_factor()为0.3
桶接口的一个用途是允许对哈希函数进行实验: 一个糟糕的哈希函数会导致某些关键字值的bucket_count()异常大，即，很多关键字被映射为相同的哈希值。

31.5 容器适配器

容器适配器(container adaptor)为容器提供不同的(通常是受限的)的接口。容器适配器的设计用法就是仅通过其特殊接口使用。特别是，STL容器适配器不提供直接访问其底层容器的方式，也不提供迭代器或下标操作。
从一个容器创建容器适配器的技术是一种通用的按用户需求非侵入式适配类接口的技术。

31.5.1 stack

stack是一个容器接口，容器类型是作为模板实参传递给它的。stack通过接口屏蔽了其底层容器上的非栈操作，接口采用常规命名: top(), push()和pop()
此外，stack还提供了常用的比较运算符(==, <等)和非成员函数swap()

默认情况下，stack用deque保存其元素，但任何提供back(),push_back()和pop_back()操作的序列都可使用。例如

stack<char> s1;   // 使用deque<char>保存元素
stack<int, vector<int>> s2;  // 使用vector<int>保存元素

vector通常比deque更快，使用内存也更少
stack对底层容器使用push_back()来添加元素。因此，只要机器还有可用内存供容器申请，stack就不会溢出。
默认情况下，stack使用其底层容器的分配器。如果这不够，有几个构造函数可以指定分配器。

31.5.2 queue

queue定义在中，它是一个容器接口，允许在back()中插入元素，在front()中提取元素

31.5.3 priority_queue

priority_queue是一种队列，其中每个元素都被赋予一个优先级，用来控制元素被top()获取的顺序。priority_queue的声明非常像queue，只是多了处理一个比较对象的代码和一组从序列进行初始化的构造函数。
默认情况下,priority_queue简单的用 < 运算符比较元素，用top()返回优先级最高的元素

31.6 建议

一个STL容器定义一个序列
将vector作为默认容器使用
insert()和push_back()这样的插入操作在vector上通常比在list上更高效
将forward_list用于通常为空的序列
当设计性能时，不要盲目信任你的直觉，而要进行测试
不要盲目信任渐进复杂性度量；某些序列很短而单一操作的代价差异可能很大
STL容器都是资源句柄
map通常实现为红黑树
unordered_map是哈希表
STL容器的元素类型必须提供拷贝和移动操作
如果你希望保持多态行为，使用指针或智能指针的容器
比较操作应该实现一个严格弱序
以传引用方式传递容器参数，以传值方式返回容器
对一个容器，用()初始化器初始化大小，用{}初始化器语法初始化元素列表
用范围for循环或首位迭代器对容器进行简单遍历
如果不需要修改容器元素，使用const迭代器
当使用迭代器时，用auto避免冗长易错的输入
用reserve()壁面指向容器元素的指针和迭代器失效
未经测试不要假定reserve()会有性能收益
使用容器上的push_back()或resize()，而不是数组上的realloc()
vector和deque改变大小后，不要继续使用其上的迭代器
在需要时使用reserve()令性能可预测
不要假定[]会进行范围检查
当需要保证进行范围检查时使用at()
用emplace()方便符号表示
优选紧凑连续存储的数据结构
用emplace()避免提前初始化元素
遍历list的代价相对较高
list一般会有每个元素四个字的额外内存开销
有序容器序列由其比较对象(默认为 <)定义
无序容器(哈希容器)序列并无可预测的序
如果你需要在大量数据中快速查找元素，使用无序容器
对五自然序的元素类型，使用无序容器
如果需要按顺序遍历元素，使用有序关联容器
用实验检查你的哈希函数是否可以接受
用异或操作组合标准哈希函数得到的哈希函数通常有很好的性能
0.7通常是一个合理的装载因子
你可以为容器提供其他接口
STL适配器不提供对其底层容器的直接访问

第三十二章 STL算法

32.1 引言

STL包含标准库中的迭代器，容器，算法和函数对象几个部分

32.2 算法

中定义了大约80个标准算法。
很多算法都遵循一种常规表示方式: 返回序列的末尾来表示未找到。
无论是标准库算法还是用户自己设计的算法，都很重要
- 每个算法命名一个特定操作，描述其接口，并指定其语义
- 每个算法都可能广泛使用并被很多程序员熟知
如果你发现你写的一段代码有若干看起来没什么关联的循环，局部变量，或是有很复杂的控制结构，那么就应该考虑是否可以简化代码，将某些部分改写为具有描述性的名字以及良好定义的目的，接口和依赖关系的函数/算法。

32.2.1 序列

标准库算法的理想目标是为可优化实现的某些东西提供最通用最灵活的接口。
注意，无论一个STL算法返回什么，它都不会是实参的容器。传递给STL算法的实参是迭代器，算法完全不了解迭代器所指向的数据结构。
迭代器的存在主要是为了将算法从它所处理的数据结构上分离开来，反之亦然。

32.8 建议

STL算法操作一个或多个序列
一个输入序列是一个半开区间，由一对迭代器定义
进行搜索时，算法通常返回输入序列的末尾位置表示未找到
优选精心说明的算法而非随意代码
当你要编写一个循环时，思考它是否可以表达为一个通用算法
确保一对迭代器实参确使指定了一个序列
当迭代器对风格显得冗长时，引入容器/范围版本的算法
用谓词和其他函数对象赋予标准算法更宽泛的含义
谓词不能修改其实参
指针上默认的==和 < 极少能满足标准算法的需求
了解你使用的算法的时间复杂性，但要记住复杂性评价只是对性能的粗略引导
只在对一个任务没有更专用的算法时使用 for_each() 和 transform()
算法并不直接向其实参序列添加元素或从其中删除元素
如果不得不处理未初始化的对象，考虑 uninitialized_* 系列算法
STL算法基于其排序比较操作实现相等性比较
注意，排序和搜索C风格的字符串要求用户提供一个字符串比较操作。

第三十三章 STL迭代器

33.1 引言

迭代器是标准库算法和所操作的数据间的粘合剂。反过来，也可以说迭代器机制是为了最小化算法与所操作的数据结构间的依赖性

33.1.1 迭代器模型

与指针类似，迭代器提供了简介访问的操作(例如解引用操作 *)和移动到新元素的操作(例如，++操作移动到下一个元素)。一对迭代器定义一个半开区间 [begin:end)，即所谓序列(sequence)
- 即，begin指向序列的首元素，end指向序列的尾元素之后的位置。永远也不要从 *end 读取数据，也不要向它写入数据。
- 注意，空序列满足 begin == end；即，对任意迭代器p都有 [p:p)是空序列
为了读取一个序列，算法通常接受一对表示半开区间[begin:end)的迭代器(b, e)，并使用++编译序列直至到达末尾

33.1.2 迭代器类别

标准库提供了五种迭代器
- 输入迭代器(input iterator): 利用输入迭代器，我们可以用++向前遍历序列并用*(反复)读取每个元素。我们可以用==和!=比较输入迭代器。istream提供了这种迭代器
- 输出迭代器(output iterator): 利用输出迭代器，我们可以用++向前遍历序列并用*每次写入一个元素。ostream提供了这种迭代器
- 前向迭代器(forward iterator): 利用前向迭代器，我们可以反复使用++向前遍历序列并用*读写元素(除非元素是const的)。如果一个前向迭代器指向一个类对象我们可以用->访问其成员。我们可以用==和!=比较前向迭代器。forward_list提供了这种迭代器
- 双向迭代器(bidirection iterator): 利用双向迭代器，我们可以向前(用++)和向后(用–)遍历序列并用*(反复)读写元素(除非元素是const的)。如果一个双向迭代器指向一个类对象，我们可以用->访问其成员。我们可以用==和!=比较双向迭代器。list，map和set提供了这种迭代器
- 随机访问迭代器(random-access iterator): 对一个随机访问迭代器，我们可以用[]进行下标操作，用+加上一个整数，以及用-减去一个整数。我们可以将指向同一个序列的两个随机访问迭代器相减来获得他们的距离。我们可以用==,!=,<=, >和>=比较双向迭代器。vector提供了这种迭代器
这些迭代器类别是概念而非类，因此这个层次并非用继承实现的类层次。如果你希望用迭代器类别做一些更进阶的事情，可(直接或间接)使用iterator_traits。

33.1.3 迭代器萃取

迭代器标签的本质是类型，用来基于迭代器类型选择算法。
关键思路是：为了获得迭代器的属性，你应该访问其 iterator_traits而不是迭代器本身

33.1.4 迭代器操作

33.2 迭代器适配器

在中，标准库提供了适配器，能从一个给定的迭代器类型生成有用的相关迭代器类型
- reverse_iterator 反向遍历
- back_insert_iterator 在尾部插入
- front_insert_iterator 在头部插入
- insert_iterator 在任意位置插入
- move_iterator 移动而不是拷贝
- raw_storage_iterator 写入未初始化的存储空间

33.4 函数对象

很多标准库算法接受函数对象(或函数)参数，来控制其工作方式。常见的函数对象包括比较标准，谓词(返回bool的函数)和算术运算。在中，标准库提供了若干常用函数对象。

33.5 函数适配器

函数适配器接受一个函数参数，返回一个可用来调用该函数的函数对象。
- g = bind(f, args)
  - g(args2)等价于f(args3)是通过用args2中的实参替换args中对应的占位符(例如 _1, _2, _3)得到的
- g - mem_fn(f) 若p是一个指针，则g(p, args)表示p->f(args)，否则g(p, args)表示p.mf(args); args是一个实参列表
- g =

C++程序设计语言 第四部分 标准库

简介

第三十章 标准库概览

30.1 引言

30.1.1 标准库设施

30.2 头文件

30.3 语言支持

30.3.1 initializer_list 支持

30.3.2 范围for支持

30.4 错误处理

30.4.1 异常

30.4.1.1 标准库exception类层次

30.4.1.2 异常传播

30.4.1.3 terminate()

30.4.2 断言

30.4.3 system_error

30.4.3.1 错误码

30.4.3.2 错误类别

30.4.3.3 system_error异常

30.4.3.4 可移植的错误状态

30.5 建议

第三十一章 STL容器

31.1 引言

31.2 容器概览

31.2.1

31.2.2 对元素的要求

31.2.2.1 比较操作

31.3 操作概览

31.3.1 成员类型

31.3.2 构造函数，析构函数和赋值操作

31.3.3 大小和容量

31.3.4 迭代器

31.3.5 元素访问

31.3.6 栈操作

31.3.7 列表操作

31.3.8 其他操作

31.4 容器

31.4.1 vector

31.4.1.1 vector和增长

31.3.1.2 vector和嵌套

31.3.1.3 vector和数组

31.3.1.4 vector和string

31.4.2 链表

31.4.3 关联容器

31.4.3.1 有序关联容器

31.4.3.2 无序关联容器

31.4.3.3 构造unordered_map

31.4.3.4 哈希和相等判定函数

31.4.3.5 装载因子和桶

31.5 容器适配器

31.5.1 stack

31.5.2 queue

31.5.3 priority_queue

31.6 建议

第三十二章 STL算法

32.1 引言

32.2 算法

32.2.1 序列

32.8 建议

第三十三章 STL迭代器

33.1 引言

33.1.1 迭代器模型

33.1.2 迭代器类别

33.1.3 迭代器萃取

33.1.4 迭代器操作

33.2 迭代器适配器

33.4 函数对象

33.5 函数适配器

最近更新

标签排行

C++程序设计语言第四部分标准库

第三十章标准库概览