《C++ Primer 第五版》读书笔记 - 第二部分

C++标准库

第 8 章 IO 库

IO 类

为了支持使用宽字符的语言，标准库定义了一组类型和对象来操纵wchar_t类型的数据。宽字符版本的类型和函数的名字以一个w开始。例如，wcin、wcout和wcerr是分别对应cin、cout和cerr的宽字符版对象。宽字符版本的类型和对象与其对应的普通char版本的类型定义在同一个头文件中。

IO 对象无拷贝或赋值

由于不能拷贝 IO 对象，因此我们也不能将形参或返回类型设置为流类型。进行 IO 操作的函数通常以引用方式传递和返回流。读写一个 IO 对象会改变其状态，因此传递和返回的引用不能是const的。

条件状态

一个流一旦发生错误，其上后续的 IO 操作都会失败。只有当一个流处于无错状态时，我们才可以从它读取数据，向它写入数据。由于流可能处于错误状态，因此代码通常应该在使用一个流之前检査它是否处于良好状态。确定一个流对象的状态的最简单的方法是将它当作一个条件来使用。

IO 库定义了一个与机器无关的iostate类型，它提供了表达流状态的完整功能。这个类型应作为一个位集合来使用。IO 库定义了 4 个iostate类型的constexpr值，表示特定的位模式。这些值用来表示特定类型的 IO 条件，可以与位运算符一起使用来一次性检测或设置多个标志位。

badbit表示系统级错误，如不可恢复的读写错误。通常情况下，一旦badbit被置位，流就无法再使用了。在发生可恢复错误后，failbit被置位，如期望读取数值却读出一个字符等错误。这种问题通常是可以修正的，流还可以继续使用。如果到达文件结束位置，eofbit和failbit都会被置位。goodbit的值为 0，表示流未发生错误。如果 badbit、failbit和eofbit任一个被置位，则检测流状态的条件会失败。

管理输出缓冲

导致缓冲刷新的原因：

• 程序正常结束，作为main函数的return操作的一部分，缓冲刷新被执行。
• 缓冲区满时，需要刷新缓冲。
• 我们可以使用操纵符如endl来显式刷新缓冲区。
• 在每个输出操作之后，我们可以用操纵符unitbuf设置流的内部状态，来清空缓冲区。默认对cerr设置了unitbuf。
• 一个输出流可能被关联到另一个流。在这种情况下，当读写被关联的流时，关联到的流的缓冲区会被刷新。例如，默认情况下，cin和cerr都关联到cout。因此读cin或写cerr都会导致cout的缓冲区被刷新。

IO 库中还有两个类似endl的操纵符：flush和ends。flush刷新缓冲区，但不输出任何额外的字符；ends向缓冲区插入一个空字符，然后刷新缓冲区。

unitbuf操纵符告诉流在接下来的每次写操作之后都进行一次flush操作。而nounitbuf操纵符则重置流， 使其恢复使用正常的系统管理的缓冲区刷新机制：

cout << unitbuf;
cout << nounitbuf;

如果程序异常终止，输出缓冲区是不会被刷新的。

tie有两个重载的版本：一个版本不带参数，返回指向输出流的指针。如果本对象当前关联到一个输出流，则返回的就是指向这个流的指针，如果对象未关联到流，则返回空指针。tie的第二个版本接受一个指向ostream的指针，将自己关联到此ostream。即，x.tie(&o)将流x关联到输出流o。

每个流同时最多关联到一个流， 但多个流可以同时关联到同一个ostream。

文件输入输出

使用文件流对象

如果调用open失败，failbit会被置位。一旦一个文件流已经打开，它就保持与对应文件的关联。实际上，对一个已经打开的文件流调用open会失败，并会导致failbit被置位。随后的试图使用文件流的操作都会失败。为了将文件流关联到另外一个文件，必须首先关闭已经关联的文件。

当一个fstream对象被销毁时，close会自动被调用。

文件模式

文件模式的限制：

• 只可以对ofstream或fstream对象设定out模式。
• 只可以对ifstream或fstream对象设定in模式。
• 只有当out也被设定时才可设定trunc模式。
• 只要trunc没被设定，就可以设定app模式。在app模式下，即使没有显式指定out模式，文件也总是以输出方式被打开。
• 默认情况下，即使我们没有指定trunc，以out模式打开的文件也会被截断。为了保留以out模式打开的文件的内容，我们必须同时指定app模式，这样只会将数据追加写到文件末尾；或者同时指定in模式，即打开文件同时进行读写操作
• ate和binary模式可用于任何类型的文件流对象，且可以与其他任何文件模式组合使用。

与ifstream关联的文件默认以in模式打开；与ofstream关联的文件默认以out模式打开；与fstream关联的文件默认以in和out模式打开。

保留被ofstream打开的文件中已有数据的唯一方法是显式指定app或in模式。

string 流

第 9 章 顺序容器

顺序容器概述

与内置数组相比，array是种更安全、更容易使用的数组类型。与内置数组类似，array对象的大小是固定的。因此，array不支持添加和删除元素以及改变容器大小的操作。forward_list的设计目标是达到与最好的手写的单向链表数据结构相当的性能。因此，forward_list没有size操作，因为保存或计算其大小就会比手写链表多出额外的开销。对其他容器而言，size保证是一个快速的常量时间的操作。

容器库概览

顺序容器构造函数的一个版本接受容器大小参数，它使用了元素类型的默认构造函数。但某些类没有默认构造函数。我们可以定义一个保存这种类型对象的容器，但我们在构造这种容器时不能只传递给它一个元素数目参数。

迭代器

forward_list迭代器不支持递减运算符。

容器定义和初始化

为了创建一个容器为另一个容器的拷贝，两个容器的类型及其元素类型必须匹配。不过，当传递迭代器参数来拷贝一个范围时，就不要求容器类型是相同的了。而且，新容器和原容器中的元素类型也可以不同，只要能将要拷贝的元素转换为要初始化的容器的元素类型即可。

array<int, 42> // 保存 42 个 int 的数组
array<string, 10> // 保存 10 个 string 的数组

由于大小是array类型的一部分，array不支持普通的容器构造函数。这些构造函数都会确定容器的大小，要么隐式地，要么显式地。而允许用户向一个array构造函数传递大小参数，最好情况下也是多余的，而且容易出错。一个默认构造的array是非空的：它包含了与其大小一样多的元素。这些元素都被默认初始化。如果我们对array进行列表初始化，初始值的数目必须等于或小于array的大小。如果初始值数目小于array的大小，则它们被用来初始化array中靠前的元素，所有剩余元素都会进行值初始化。在这两种情况下，如果元素类型是一个类类型，那么该类必须有一个默认构造函数，以使值初始化能够进行。

array支持拷贝或对象赋值操作。

赋值和 swap

顺序容器（array除外）定义了一个名为assign的成员，允许我们从一个不同但相容的类型赋值，或者从容器的一个子序列赋值。assign操作用参数所指定的元素（的拷贝）替换左边容器中的所有元素。

与其他容器不同，对一个string调用swap会导致迭代器，引用和指针失效。

与其他容器不同，swap两个array会真正交换它们的元素。因此，交换两个array所需的时间与array中元素的数目成正比。对于array，在swap操作之后，指针，引用和迭代器所绑定的元素保持不变，但元素值已经与另一个array中对应元素的值进行了交换。

关系运算符

每个存器类型都支持相等运算符（==和!=）；除了无序关联容器外的所有容器郁支持关系运算符（>，>=，<，<=）。关系运算符左右两边的运算对象必须是相同类型的容器，且必须保存相同类型的元素。

容器的相等运算符实除上是使用元素的==运算符实现比较的，而其他关系运算符是使用元素的<运算符。

顺序容器操作

向顺序容器添加元素

list<string> lst;
auto iter = lst.begin();
while (cin >> word)
    iter = lst.insert(iter, word); // 等价于调用 push_front

而当我们调用一个emplace成员函数时，则是将参数传递给元素类型的构造函数。emplace成员使用这些参数在容器管理的内存空间中直接构造元素。

emplace函数的参数根据元素类型而变化，参数必须与元素类型的构造函数相四配。

访问元素

删除元素

erase的第二个参数指向要删除的最后一个元素之后的位置。

特殊的 forward_list 操作

在一个forward_list中添如或删除元素的操作是通过改变给定元素之后的元素来完成的。这样，我们总是可以访问到被添加或删除操作所影响的元素。

删除奇数元素：

forward_list<int> flst = {0,1,2,3,4,5,6,7,8,9};
auto prev = flst.before_begin();
auto curr = flst.begin();
while (curr != flst.end()) {
    if (*curr % 2)
        curr = flst.erase_after(prev);
    else {
        prev = curr;
        ++curr;
    }
}

改变容器大小

容器操作可能使迭代器失效

在向容器添如元素后：

• 如果容器是vector或string， 且存储空间被重新分配，则指向容器的迭代器、指针和引用都会失效。如果存储空间未重新分配，指向插入位置之前的元素的迭代器、指针和引用仍有效，但指向插入位置之后元素的迭代器、指针和引用将会失效。
• 对于deque，插入到除首尾位置之外的任何位置都会导致迭代器、指针和引用失效。如果在首尾位置添如元素，迭代器会失效，但指向存在的元素的引用和指针不会失效。
• 对于list和forward_list，指向容器的迭代器（包括尾后迭代器和首前迭代器）、指针和引用仍有效。

当我们从一个容器中删除元素后，指向被删除元素的迭代器、指针和引用会失效，当我们删除一个元素后：

• 对于list和forward_list，指向容器其他位置的迭代器（包括尾后迭代器和首前迭代器）、引用和指针仍有效。
• 对于deque，如果在首尾之外的任何位置删除元素，那么指向被删除元素外其他元素的迭代器、引用或指针也会失效。如果是删除deque的尾元素，则尾后迭代器也会失效，但其他迭代器、引用和指针不受影响，如果是删除首元素。这些也不会受影响。
• 对于vector和string，指向被删元素之前元素的迭代器，引用和指针仍有效，注意：当我们删除元素时，尾后迭代器总是会失效。

vector 对象是如何增长的

如果需求大小小于或等于当前容量，reserve什么也不做。特别是，当需求大小小于当前容量时，容器不会退回内存空间。

我们可以调用shrink_to_fit来要求deque、vector或string退回不需要的内存空间。此函数指出我们不再需要任何多余的内存空间。但是，具体的实现可以选择忽略此请求。也就是说，调用shrink_to_fit也并不保证一定退回内存空间。

每个vector实现都可以选择自己的内存分配策略。但是必须遵守的一条原则是：只有当迫不得已时オ可以分配新的内存空间。

额外的 string 操作

构造 string 的其他方法

通常当我们从一个const char*创建string时，指针指向的数组必须以空字符结尾，拷贝操作遇到空字符时停止。如果我们还传递给构造函数一个计数值，数组就不必以空字符结尾。如果我们未传递计数值且数组也未以空字符结尾，或者给定计数值大于数组大小，则构造函数的行为是未定义的。

如果位置大于size，则构造函数抛出个out_of_range异常。如果我们传递了一个计数值，则从给定位置开始拷贝这么多个字符。不管我们要求拷贝多少个字符，标准库最多拷贝到string结尾，不会更多。

如果开始位置超过了string的大小，则substr函数抛出一个out of_range异常。如果开始位置加上计数值大于string的大小，则substr会调整计数值，只拷贝到string的末尾。

改变 string 的其他方法

assign和append函数无须指定要替换string中哪个部分：assign总是替换string中的所有内容，append总是将新字符追加到string末尾。

replace函数提供了两种指定删除元素范围的方式。可以通过一个位置和一个长度来指定范围，也可以通过一个迭代器范围来指定。

insert函数允许我们用两种方式指定插入点：用一个下标或一个迭代器。在两种情况下，新元素都会插入到给定下标（或迭代器）之前的位置。

可以用好几种方式来指定要添加到string中的字符。新字符可以来自于另一个string，来自于一个字符指针（指向的字符数组），来自于个花括号包围的字符列表，或者是一个字符和一个计数值。当字符来自于一个 string或一个字符指针时，我们可以传递一个额外的参数来控制是拷贝部分还是全部字符。

string 搜索操作

每个搜索操作都返回一个string::size_type值，表示匹配发生位置的下标。如果搜索失败，则返回一个名为string::npos的static成员。标准库将npos定义为一个const string::size_type类型并初始化为值-1。由于npos是一个unsigned类型，此初始值意味着npos等于任何string最大的可能大小。

string numbers("0123456789"), name("r2d2");
string::size_type pos = 0;
// 每次迭代查找 name 中下一个数
while ((pos = name.find_first_of(numbers, pos)) != string::npos) {
    // ... 输出
    ++pos;
}

compare 函数

数值转换

string s2 = "pi = 3.14";
// 转换 s2 中以数字开始的第一个子串
d = stod(s2.substr(s2.find_first_of("+-.0123456789")));

容器适配器

适配器是标准库中的一个通用概念。容器、迭代器和函数都有适配器。本质上，一个适配器是一种机制，能使某种事物的行为看起来像另外一种事物一样。一个容器适配器接受一种已有的容器类型，使其行为看起米像一种不同的类型。

每个适配器都定义两个构造函数：默认构造函数创建一个空对象，接受一个容器的构造函数拷贝该容器来初始化适配器。例如，假定deq是一个deque<int>，我们可以用deq来初始化一个新的stack。

默认情况下，stack和queue是基于deque实现的，priority_queue是在vector之上实现的。我们可以在创建一个适配器时将一个命名的顺序容器作为第二个类型参数，来重载默认容器类型。

// 在 vector 上实现的空栈
stack<string, vector<string>> str_stk;

对于一个给定的适配器，可以使用哪些容器是有限制的。所有适配器都要求容器具有添加和删除元素的能力。因此，适配器不能构造在array之上。类似的，我们也不能用forward_list来构造适配器，因为所有适配器都要求容器具有添加、删除以及访问尾元素的能力。

stack只要求push_back、pop_back和back操作，因此可以使用除array和forward_list之外的任何容器类型来构造。

queue适配器要求back、push_back、front和push_front，因此它可以构造于list或deque之上，但不能基于vector构造。

priority_ queue除了front、push_back和pop_back操作之外还要求随机访问能力，因此它可以构造于vector或deque之上，但不能基于list构造。

每个容器适配器都基于底层容器类型的操作定义了自己的特殊操作。我们只可以使用适配器操作，而不能使用底层容器类型的操作。

第 10 章 泛型算法

概述

泛型算法本身不会执行容器的操作，它们只会运行于迭代器之上，执行迭代器的操作。算法可能改变容器中保存的元素的值，也可能在容器内移动元素，但永远不会直接添加或删除元素。

初识泛型算法

除了少数例外，标准库算法都对一个范围内的元素进行操作。我们将此元素范围称为“输入范围”。接受输入范围的算法总是使用前两个参数来表示此范围，两个参数分别是指向要处理的第一个元素和尾元素之后位置的代器。

只读算法

accumulate函数接受三个参数，前两个指出了需要求和的元素的范围，第三个参数是和的初值。序列中元素的类型必须与第三个参数匹配，或者能够转换为第三个参数的类型。

equal用于确定两个序列是否保存相同的值。它将第一个序列中的每个元素与第二个序列中的对应元素进行比较。如果所有对应元素都相等，则返回true，否则返回false。此算法接受三个迭代器：前两个表示第一个序列中的元素范围，第三个表示第二个序列的首元素。

由于equal利用迭代器完成操作，因此我们可以通过调用equal来比较两个不同类型的容器中的元素。而且，元素类型也不必一样，只要我们能用==来比较两个元素类型即可。

那些只接受一个单一选代器来表示第二个序列的算法，都假定第二个序列至少与第一个序列一样长。

写容器元素的算法

一些算法将新值赋予序列中的元素，当我们使用这类算法时，必须注意确保序列原大小至少不小于我们要求算法写入的元素数目。

一些算法会自己向输入范围写入元素。这些算法本质上并不危险，它们最多写入与给定序列一样多的元素。 例如，算法fill接受一对迭代器表示一个范围，还接受一个值作为第三个参数。fill将给定的这个值赋予输入序列中的每个元素。

一些算法接受一个迭代器来指出一个单独的目的位置。这些算法将新值赋予一个序列中的元素，该序列从目的位置迭代器指向的元素开始。例如，函数fill_n接受一个单迭代器、一个计数值和一个值。它将给定值赋予迭代器指向的元素开始的指定个元素。

插入迭代器是一种向容器中添加元素的迭代器。通常情况，当我们通过一个迭代器向容器元素赋值时，值被赋予迭代器指向的元素。而当我们通过一个插入迭代器赋值时，一个与赋值号右侧值相等的元素被添加到容器中。

back_inserter是定义在头文件iterator中的一个函数，它接受一个指向容器的引用，返回一个与该容器绑定的插入迭代器。当我们通过此迭代器赋值时，赋值运算符会调用push_back将一个具有给定值的元素添加到容器中

copy算法接受三个迭代器，前两个表示一个输入范围，第三个表示目的序列的起始位置。此算法将输入范围中的元素拷贝到目的序列中。copy返回的是其目的位置迭代器（递增后）的值。

replace算法读入一个序列，并将其中所有等于给定值的元素都改为另一个值。此算法接受 4 个参数：前两个是迭代器，表示输入序列，后两个一个是要搜索的值， 另一个是新值。

如果我们希望保留原序列不变，可以调用replace_copy。此算法接受额外第三个迭代器参数，指出调整后序列的保存位置。

重排容器元素的算法

调用unique后容器的大小并未改变，但这些元素的顺序被改变了一一相邻的重复元素被“删除”了。unique并不真的删除任何元素，它只是覆盖相邻的重复元素，使得不重复元素出现在序列开始部分。 unique返回的迭代器指向最后一个不重复元素之后的位置。此位置之后的元素仍然存在，但我们不知道它们的值是什么。使用erase删除无用的元素。

定制操作

向算法传递函数

谓词是一个可调用的表达式，其返回结果是一个能用作条件的值。标准库算法所使用的谓词分为两类：一元谓词（只接受单一参数）和二元谓词（有两个参数）。接受谓词参数的算法对输入序列中的元素调用谓词。因此，元素类型必须能转换为谓词的参数类型。

接受一个二元谓词参数的sort版本用这个谓词代替<比较元素。此操作必须在输入序列中所有可能的元素值上定义一个一致的序。

stable_sort算法维持相等元素的原有顺序。

lambda 表达式

find_if算法接受一对迭代器，表示一个范围，它的第三个参数是一个谓词。该算法对输入序列中的每个元素调用给定的这个谓词。它返回第一个使谓词返回非 0 值的元素，如果不存在这样的元素， 则返回尾迭代器。

我们可以向一个算法传递任何类别的可调用对象。对于一个对象或一个表达式，如果可以对其使用调用运算符，则称它为可调用的。

一个lambda表达式表示一个可调用的代码单元。我们可以将其理解为一个未命名的内联函数。一个lambda具有一个返回类型、一个参数列表和一个函数体。但与函数不同，lambda可能定义在函数内部。一个lambda表达式具有如下形式：

[capture list] (parameter list) -> return type { function body }

其中，capture list（捕获列表）是一个lambda所在函数中定义的局部变量的列表（通常为空）。与普通函数不同，lambda必须使用尾置返回来指定返回类型。

我们可以忽略参数列表和返回类型，但必须永远包含捕获列表和函数体。

如果忽略返回类型，lambda根据函数体中的代码推断出返回类型。如果函数体只是一个return语句，则返回类型从返回的表达式的类型推断而来。否则，返回类型为void。

lambda不能有默认参数。

捕获列表指引lambda在其内部包含访问局部变量所需的信息。

for_each算法接受一个可调用对象，并对输入序列中每个元素调用此对象。

捕获列表只用于局部非static变量，lambda可以直接使用局部static变量和在它所在函数之外声明的名字。

lambda 捕获和返回

当定义一个lambda时，编译器生成一个与lambda对应的新的（未命名的）类类型。

默认情况下，从lambda生成的类都包含一个对应该由lambda捕获的变量的数据成员。类似任何普通类的数据成员，lambda的数据成员也在lambda对象创建时被初始化。

与参数不同，被捕获的变量的值是在lambda创建时拷贝，而不是调用时拷贝：

void fcn1()
{
    size_t v2 = 42;
    auto f = [v1] { return v1; };
    v1 = 0;
    auto j = f(); // j 为 42
}

如果我们采用引用方式捕获一个变量，就必须确保被引用的对象在lambda执行的时候是存在的。

我们也可以从一个函数返回lambda。函数可以直接返回一个可调用对象，或者返回一个类对象，该类含有可调用对象的数据成员。如果函数返回一个lambda，则与函数不能返回一个局部变量的引用类似，此lambda也不能包含引用捕获。

如果我们捕获一个指针或迭代器，或采用引用捕获方式，就必须确保在lambda执行时，绑定到迭代器、指针或引用的对象仍然存在。而且，需要保证对象具有预期的值。

默认情况下，对于一个值被拷贝的变量，lambda不会改变其值。如果我们希望能改变个被捕获的变量的值，就必须在参数列表首加上关键字mutable。并且被拷贝的变量作为lambda的数据成员，每次调用lambda对成员的改动会累积。

参数绑定

bind标准库函数定义在头文件functional中，可以将bind函数看作一个通用的函数适配器，它接受一个可调用对象，生成一个新的可调用对象来“适应”原对象的参数列表。

调用bind的一般形式为：

auto newCallable = bind(callable, arg_list);

其中，newCallable本身是一个可调用对象，arg_list是一个逗号分隔的参数列表，对应给定的callable的参数。即，当我们调用newCallable时，newCallable会调用callable，并传递给它arg_list中的参数。arg_list中的参数可能包含形如_n的名字，其中_n是一个整数。这些参数是“占位符”，表示 newCallable的参数，它们占据了传递给newCallable的参数的“位置”。数值n表示生成的可调用对象中参数的位置。

名字_n都定义在一个名为placeholders的命名空间中，而这个命名空间本身定义在std命名空间中。

auto g = bind(f, a, b, _2, c, _1);

会将g(_1, _2)映射到f(a, b, _2, c, _1)。

如果我们希望传递给bind一个引用对象，就必须使用标准库ref函数。函数ref返回一个对象，包含给定的引用，此对象是可以拷贝的。标准库中还有一个cref函数，生成一个保存const引用的类。函数ref和cref也定义在头文件functional中。

再探迭代器

• 插入迭代器：这些迭代器被绑定到一个容器上，可用来向容器插入元素。
• 流迭代器：这些迭代器被绑定到输入或输出流上，可用来遍历所除了关联的 IO 流。
• 反向迭代器：这些迭代器向后而不是向前移动。除了forward_list之外的标准库容器都有反向迭代器。
• 移动迭代器：这些专用的迭代器不是拷贝其中的元素，而是移动它们。

插入迭代器

插入器有三种类型，差异在于元素插入的位置：

• back_inserter创建一个使用push_back的迭代器。
• front_inserter创建一个使用push_front的迭代器。
• inserter创建一个使用insert的迭代器。此函数接受第二个参数，这个参数必须是一个指向给定容器的迭代器。元素将被插入到给定迭代器所表示的元素之前。

如果it是由inserter生成的迭代器，则下面这样的赋值语句

*it = val;

其效果与下面代码一样

it = c.insert(it, val); // it 指向新加入的元素
++it; //递増 it 使它指向原来的元素

iostream 迭代器

istream_iterator读取输入流，ostream_iterator向一个输出流写数据。这些迭代器将它们对应的流当作一个特定类型的元素序列来处理。

创建stream_iterator时，我们可以将它绑定到一个流。默认的初始化迭代器当做尾后值使用。

当我们将一个istream_iterator绑定到一个流时，标准库并不保证迭代器立即从流读取数据。具体实现可以推迟从流中读取数据，直到我们使用迭代器时才真正读取。标准库中的实现所保证的是，在我们第一次解引用迭代器之前，从流中读取数据的操作已经完成了。如果我们创建了一个istream_iterator，没有使用就销毁了，或者我们正在从两个不同的对象同步读取同一个流，那么何时读取可能就很重要了。

必须将ostream_iterator绑定到一个指定的流，不允许空的或表示尾后位置的ostream_iterator。

反向迭代器

对于反向迭代器，递增（以及递减）操作的含义会颠倒过来。递增一个反向迭代器（++it）会移动到前一个元素；递减一个迭代器（--it）会移动到下一个元素。

sort(vec.rbegin(), vec.rend()); // 降序排序

假设有一个名为line的string，保存一个逗号分隔的单词列表。希望打印最后一个单词：

auto rcomma = find(line.crbegin(), line.crend(), ',');
cout << string(line.crbegin(), rcomma) << endl; // 错误：将逆序输出最后一个单词

reverse_iterator的base成员函数会返回其对应的普通迭代器：

cout << string(rcomma.base(), line.cend()) << endl;

[line.crbegin(), rcomma)和[rcomma.base(), line.cend())指向line中相同的元素范围。为了实现这一点，rcomma和rcomma.base()必须生成相邻位置而不是相同位置，crbegin()和cend()也是如此。

反向迭代器的目的是表示元素范围，而这些范围是不对称的，这导致一个重要的结果：当我们从一个普通迭代器初始化一个反向迭代器，或是给一个反向迭代器赋值时，结果迭代器与原迭代器指向的并不是相同的元素。

泛型算法结构

对每个迭代器参数来说，其能力必须与规定的最小类别至少相当。向算法传递一个能力更差的迭代器会产生错误。

5 类迭代器

输入迭代器：可以读取序列中的元素。一个输入迭代器必须支持

• 用于比较两个迭代器的相等和不相等运算符（==、!=）
• 用于推进迭代器的前置和后置递增运算（++）
• 用于读取元素的解引用运算符（*）：解引用只会出现在赋值运算符的右侧
• 箭头运算符（->），等价于(*it).member，即，解引用迭代器，并提取对象的成员

不能保证输入迭代器的状态可以保存下来并用来访问元素。因此，输入迭代器只能用于单遍扫描算法，算法find和accumulate要求输入迭代器；而istream_iterator是一种输入迭代器。

输出迭代器：可以看作输入迭代器功能上的补集一一只写而不读元素。输出迭代器必须支持

• 用于推进迭代器的前置和后置递增运算（++）
• 解引用运算符（*），只出现在赋值运算符的左侧（向一个已经解引用的输出迭代器赋值，就是将值写入它所指向的元素）

类似输入迭代器，输出迭代器只能用于单遍扫描算法。用作目的位置的迭代器通常都是输出迭代器。例如，copy函数的第三个参数就是输出迭代器。ostream_iterator类型也是输出迭代器。

前向迭代器：可以读写元素。这类迭代器只能在序列中沿一个方向移动。前向迭代器支持所有输入和输出迭代器的操作，而且可以多次读写同一个元素。因此，我们可以保存前向迭代器的状态，使用前向迭代器的算法可以对序列进行多遍扫描。算法replace要求前向迭代器，forward_list上的迭代器是前向迭代器。

双向迭代器：可以正向/反向读写序列中的元素。除了支持所有前向迭代器的操作之外，双向迭代器还支持前置和后置递减运算符（--）。算法reverse要求双向迭代器，除了forward_list之外，其他标准库都提供符合双向迭代器要求的迭代器。

随机访问迭代器：提供在常量时间内访问序列中任意元素的能力。此类迭代器支持双向迭代器的所有功能，此外还支持：

• 用于比较两个迭代器相对位置的关系运算符（<、=、>和>=）
• 迭代器和一个整数值的加减运算（+、+=、-和-=），计算结果是迭代器在序列中前进（或后退）给定整数个元素后的位置
• 用于两个迭代器上的减法运算符（-），得到两个迭代器的距离
• 下标运算符（iter[n]），与*(iter + n)等价

算法sort要求随机访问迭代器。array、deque、string和vector的迭代器都是随机访问迭代器，用于访问内置数组元素的指针也是。

算法形参模式

大多数算法具有如下 4 种形式之一：

alg(beg, end, other args);
alg(beg, end, dest, other args);
alg(beg, end, beg2, other args);
alg(beg, end, beg2, end2, other args)i;

dest参数是一个表示算法可以写入的目的位置的迭代器。向输出迭代器写入数据的算法都假定目标空间足够容纳写入的数据。更常见的情况是，dest被绑定到一个插入迭代器或是一个ostream_iterator。

接受单独的beg2或是接受beg2和end2的算法用这些迭代器表示第二个输入范围。这些算法通常使用第二个范围中的元素与第一个输入范围结合来进行一些运算。 接受单独的beg2（不接受end2）的算法假定从beg2开始的范围与beg和end所表示的范围至少一样大。

算法命名规范

接受谓词参数来代替<或==运算符的算法，以及那些不接受额外参数的算法，通常都是重载的函数。函数的一个版本用元素类型的运算符来比较元素：另一个版本接受一个额外谓词参数，来代替<或==。

接受一个元素值的算法通常有另一个不同名的（不是重载的）版本，该版本接受一个谓词代替元素值。接受谓词参数的算法都有附加的_if后缀。

默认情况下，重排元素的算法将重排后的元素写回给定的输入序列中。这些算法还提供另一个版本，将元素写到一个指定的输出目的位置。如我们所见，写到额外目的空间的算法都在名字后面附加一个_copy。一些算法同时提供copy和if版本。这些版本接受一个目的位置迭代器和一个谓词：

remove_if(v1.begin(), v1.end(), [](int i) { return i % 2; });
remove_copy_if(v1.begin(), v1.end(), back_inserter(v2), [](int i) { return i % 2; });

特定容器算法

与其他容器不同，链表类型list和forward_list定义了几个成员函数形式的算法，特別是，它们定义了独有的sort、merge、remove、reverse和unique。

链表特有版本与通用版本间的一个至关重要的区别是链表版本会改变底层的容器。例如，remove的链表版本会删除指定的元素。unique的链表版本会删除第二个和后继的重复元素。链表版本的merge函数会销毁给定的链表——元素从参数指定的链表中删除，被合并到调用merge的链表对象中。在merge之后，来自两个链表中的元素仍然存在，但它们都已在同一个链表中。

第 11 章 关联容器

允许重复关键字的容器的名字中都包含单词multi；不保持关键字按顺序存储的容器的名字都以单词unordered开头。

类型map和multimap定义在头文件map中；set和multiset定义在头文件set中；无序容器则定义在头文件unordered_map和unordered_set中。

使用关联容器

当从map中提取一个元素时（比如范围for语句），会得到一个pair类型的对象。map所使用的pair用first成员保存关键字，用second成员保存对应的值。

关联容器概述

定义关联容器

每个关联容器都定义了一个默认构造函数，它创建一个指定类型的空容器。我们也可以将关联容器初始化为另一个同类型容器的拷贝，或是从一个值范围来初始化关联容器，只要这些值可以转化为容器所需类型就可以。在新标准下，我们也可以对关联容器进行值初始化。

对map使用列表初始化时，用花括号包围的每一个元素是一个键-值对：{key, value}。

关键字类型的要求

对于有序容器，关键字类型必须定义元素比较的方法。默认情况下，标准库使用关键字类型的<运算符来比较两个关键字。

也可以提供自己定义的操作来代替关键字上的<运算符。所提供的操作必须在关键字类型上定义一个严格弱序，具备如下基本性质：

• 两个关键字不能同时“小于等于”对方：如果k1“小于等于”k2，那么k2绝不能“小于等于”k1
• 如果k1“小于等于”k2，且k2“小于等于”k3，那么k1必须“小于等于”k3。
• 如果存在两个关键字，任何一个都不“小于等于”另一个，那么我们称这两个关键字是“等价”的。如果k1“等价于”k2，且k2“等价于”k3，那么k1必须“等价于”k3。如果两个关键字是等价的，那么容器将它们视作相等来处理。当用作map的关键字时，只能有一个元素与这两个关键字关联，我们可以用两者中任意一个来访问对应的值。

用来组织一个容器中元素的操作的类型也是该容器类型的一部分。为了指定使用自定义的操作，必须在定义关联容器类型时提供此操作的类型。自定义的操作类型必须在尖括号中紧跟着元素类型给出。在尖括号中出现的每个类型，就仅仅是一个类型而己。当我们创建一个容器（对象）时，才会以构造函数参数的形式提供真正的比较操作（其类型必须与在尖括号中指定的类型相吻合）。例如：

bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs)
{
    return lhs.isbn() < rhs.isbn();
}
multiset<Sales_data, decltype(conpareIsbn)*> bookstore(compareIsbn);

pair 类型

pair定义在头文件utility中。pair的默认构造函数对数据成员进行值初始化。

pair<string, int> process(vector<string> &v)
{
    // ...
    if (!v.empty())
        return {v.back(), v.back().size()}; // 列表初始化
    else
        return pair<string, int>(); // 隐式构造返回值
}

关联容器操作

关联容器迭代器

当解引用一个关联容器迭代器时，我们会得到一个类型为容器的value_type的值的引用。

一个map的value_type是一个pair，我们可以改变pair的值，但不能改变关键字成员的值。

一个set中的关键字也是const的。

当使用一个选代器遍历一个map、multimap、set或multiset时，迭代器按关键字升序遍历元素。

关键字是const意味着不能将关联容器传递给修改或重排容器元素的算法。

关联容器可用于只读取元素的算法。但是，很多这类算法都要搜索序列。由于关联容器中的元素不能通过它们的关键字进行（快速）查找，因此对其使用泛型搜索算法几乎总是个坏主意。

在实际编程中，如果我们真要对一个关联容器使用算法，要么是将它当作一个源序列，要么当作一个目的位置。

添加元素

删除元素

map 的下标操作

我们不能对一个multimap或一个unordered_multimap进行下标操作，因为这些容器中可能有多个值与一个关键字相关联。由于下标运算符可能插入一个新元素，我们只可以对非const的map使用下标操作

当对一个map进行下标操作时，会获得一个mapped_type对象：但当解引用一个map迭代器时，会得到一个value_type对象。

与其他下标运算符相同的是，map的下标运算符返回一个左值，所以我们既可以读也可以写元素。

访问元素

有时，我们只是想知道一个给定关键字是否在map中，而不想改变map。这样就不能使用下标运算符来检查一个元素是否存在，因为如果关键字不存在的话，下标运算符会插入一个新元素。在这种情况下，应该使用find。

如果一个multimap或multiset中有多个元素具有给定关键字，则这些元素在容器中会相邻存储。

如果关键字在容器中，lower_bound返回的迭代器将指向第一个具有给定关键字的元素，而upper_bound返回的迭代器则指向最后一个匹配给定关键字的元素之后的位置。如果元素不在multimap中，则lower_bound和upper_bound会返回相等的迭代器一一指向一个不影响排序的关键字插入位置。

string search_item("Alain de Botton");
auto entries = authors.count(search_item);
auto iter = authors.find(search_item); 

while(entries) {
    cout << iter->second << endl;
    ++iter; 
    --entries;
}

for (auto beg = authors.lower_bound(search_item), end = authors.upper_bound(search_item); beg != end; ++beg)
    cout << beg->second << endl;

for (auto pos = authors.equal_range(search_item); pos.first != pos.second; ++pos.first)
    cout << pos.first->second << endl;

无序容器

无序关联容器不是使用比较运算符来组织元素，而是使用一个哈希函数和关键字类型的==运算符。在某些应用中，维护元素的序代价非常高昂，此时无序容器也很有用。 虽然理论上哈希技术能获得更好的平均性能，但在实际中想要达到很好的效果还需要进行一些性能测试和调优工作。因此，使用无序容器通常更为简单（通常也会有更好的性能）。

默认情况下，无序容器使用关键字类型的==运算符来比较元素，它们还使用一个hash<key_type>类型的对象来生成每个元素的哈希值。标准库为内置类型（包括指针）提供了hash模板。还为一些标准库类型，包括 string和智能指针类型定义了hash。因此，我们可以直接定义关键字是内置类型（包括指针类型）、string还是智能指针类型的无序容器。但是，我们不能直接定义关键字类型为自定义类类型的无序容器。

重载==运算符和哈希值计算函数：

size_t hasher(const Sales_data &sd) 
{
    return hash<string>()(sd.isbn());
}
bool eqOp(const Sales_data &lhs, const Sales_data &rhs)
{
    return lhs.isbn() == rhs.isbn();
}
using SD_multiset = unordered_multiset<Sales_data, decltype(hasher)*, decltype(eqOp)*>;
SD_multiset bookstore(42, hasher, eqOp);

// 如果定义了==运算符，可以只重载哈希函数：
unordered_set<Foo, decltype(FooHash)*> fooSet(10, Foohash);

第 12 章 动态内存

动态内存与智能指针

智能指针定义在memory头文件中。

shared_ptr 类

我们可以认为每个shared_ptr都有一个关联的计数器，通常称其为引用计数。无论何时我们拷贝一个shared_ptr，计数器都会递增。例如，当用一个shared_ptr初始化另一个shared_ptr，或将它作为参数传递给一个函数以及作为函数的返回值时，它所关联的计数器就会递增。当我们给shared_ptr赋予一个新值或是shared_ptr被销毁（例如一个局部的shared_ptr离开其作用域）时，计数器就会递减。一旦一个shared_ptr的计数器变为 0，它就会自动释放自己所管理的对象。

如果你将shared_ptr存放于一个容器中，而后不再需要全部元素，而只使用其中一部分，要记得用erase删除不再需要的那些元素。

程序使用动态内存出于以下三种原因之：

1. 程序不知道自己需要使用多少对象
2. 程序不知道所需对象的准确类型
3. 程序需要在多个对象间共享数据

直接管理内存

运算符new分配内存，delete释放new分配的内存。

默认情况下，动态分配的对象是默认初始化的。

我们可以使用直接初始化方式来初始化一个动态分配的对象：传统的构造方式（使用圆括号）或列表初始化（使用花括号）；也可以对动态分配的对象进行值初始化，只需在类型名之后跟一对空括号即可。

如果我们提供了一个括号包围的初始化器，就可以使用auto从此初始化器来推断我们想要分配的对象的类型。但是，由于编译器要用初始化器的类型来推断要分配的类型，只有当括号中仅有单一初始化器时才可以使用auto。

类似其他任何const对象，一个动态分配的const对象必须进行初始化。

默认情况下，如果new不能分配所要求的内存空间，它会抛出一个类型为bad_alloc的异常。我们可以改变使用new的方式来阻止它抛出异常：

int *p = new (nothrow) int; // 如果分配失败，new 返回一个空指针

定位new表达式允许我们向new传递额外的参数。在此例中，我们传递给它一个由标准库定义的名为nothrow的对象。

我们传递给delete的指针必须指向动态分配的内存，或者是一个空指针。释放一块并非new分配的内存，或者将相同的指针值释放多次，其行为是未定义的。

当我们delete一个指针后，指针值就变为无效了。虽然指针已经无效，但在很多机器上指针仍然保存着（已经释放了的）动态内存的地址。在delete之后，指针就变成了人们所说的空悬指针，即，指向一块曾经保存数据对象但现在已经无效的内存的指针。 避免空悬指针的问题：在指针即将要离开其作用域之前释放掉它所关联的内存。这样，在指针关联的内存被释放掉之后，就没有机会继续使用指针了。如果我们需要保留指针，可以在delete之后将nullptr赋予指针，这样就清楚地指出指针不指向任何对象。

shared_ptr 和 new 结合使用

接受指针参数的智能指针构造函数是explicit的。因此， 我们不能将一个内置指针隐式转换为一个智能指针，必须使用直接初始化形式来初始化一个智能指针。

出于相同的原因，一个返回shared_ptr的函数不能在其返回语句中隐式转换一个普通指针，我们必须将shared_ptr显式绑定到一个想要返回的指针上：

shared_pte<int> clone(int p) {
    return new int(p); // 不合法：隐式转换为 shared_ptr<int>
    return shared_ptr<int>(new int(p)); // 合法：显示创建 shared_ptr<int>
}

void process(shared_ptr<int> ptr)
{
    // 使用 ptr
} // ptr 离开作用域，被销毁

// 使用此函数的正确方法
shared_ptr<int> p(new int(42));
process(p);
int i = *p;

// 错误方法
int *x(new int(1024));
process(x); // 不合法：不能将 int *转换为一个 shared_ptr<int>
process(shared_ptr<int>(x)); // 合法，但是内存会被释放
int j = *x; // 未定义的：x 是空悬指针

当将一个shared_ptr绑定到一个普通指针时，我们就将内存的管理责任交给了这个shared_ptr。一旦这样做了，我们就不应该再使用内置指针来访问shared_ptr所指向的内存了。

get函数是为了这样一种情况而设计的：我们需要向不能使用智能指针的代码传递一个内置指针。使用get返回的指针的代码不能delete此指针。

虽然编译器不会给出错误信息，但将另一个智能指针也绑定到get返回的指针上是错误的：一个智能指针释放这个内存会导致另一个智能指针变成空悬指针，并且另一个指针被销毁时会发生二次delete。

if (!p.unique())
    p.reset(new string(*p)); // 我们不是唯一用户；分配新的拷贝
*p += newVal; // 现在我们是唯一的用户，可以改变对象的值

智能指针和异常

如果使用智能指针，即使程序块过早结束，智能指针类也能确保在内存不再需要时将其释放。

如果在new和delete之间发生异常，且异常未在当前中被捕获，则内存就永远不会被释放了。在当前函数之外没有指针指向这块内存，因此就无法释放它了。

管理不具有良好定义的析构函数的类，定义一个删除器函数来代替delete对shared_ptr中保存的指针进行释放：

struct destination; // 表示正在连接什么
struct connection; // 使用连接所需的信息
connection connect (destination*); // 打开连接
void disconnect(connection); // 关闭给定的链接

void end_connection(connection *p) { disconnect(*p); }

void f(destination &d)
{
    connection c = connect(&d);
    shared_ptr<connection> p(&c, end_connection);
    // 使用连接
    // 当 f 退出时（即使是由于异常而退出），connection 会被正常关闭
}

当p被销毁时，它不会对自己保存的指针执行delete，而是调用end_connection。

正确使用智能指针的基本规范：

• 不使用相同的内置指针值初始化（或reset）多个智能指针。
• 不delete get()返回的指针。
• 不使用get()初始化或reset另一个智能指针。
• 如果你使用get()返回的指针，记住当最后一个对应的智能指针销毁后，你的指针就变为无效了。
• 如果你使用智能指针管理的资源不是new分配的内存，记住传递给它一个删除器。

unique_ptr

一个unique_ptr“拥有”它所指向的对象。与shared_ptr不同，某个时刻只能有一个unique_ptr指向一个给定对象。当unique_ptr被销毁时，它所指向的对象也被销毁。

当我们定义一个unique_ptr时，需要将其绑定到一个new返回的指针上。类似shared_ptr，初始化unique_ptr必须采用直接初始化形式。由于一个unique_ptr拥有它指向的对象，因此unique_ptr不支持普通的拷贝或赋值操作。

虽然我们不能拷贝或赋值unique_ptr，但可以通过调用release或reset将指针的所有权从一个（非const）unique_ptr转移给另一个unique_ptr：

release返回的指针通常被用来初始化另一个智能指针或者给另一个智能指针赋值，如果不用另一个智能指针来保存release返回的指针，我们的程序就要负责资源的释放。

不能拷贝unique ptr的规则有一个例外：我们可以拷贝或赋值一个将要被销毁的unique_ptr。最常见的例子是从函数返回一个unique_ptr，还可以返回一个局部对象的拷贝。

void f(destination &d)
{
    connection c = connect(&d);
    unique_ptr<connection, decltype(end_connection)*> p(&c, end_connection);
}

weak_ptr

weak_ptr是一种不控制所指向对象生存期的智能指针，它指向由一个shared_ptr管理的对象。将一个weak_ptr绑定到一个shared_ptr不会改变shared_ptr的引用计数。一旦最后一个指向对象的shared_ptr被销毁，对象就会被释放。即使有weak_ptr指向对象，对象也还是会被释放。

由于对象可能不存在，我们不能使用weak_ptr直接访问对象，而必须调用lock。此函数检查weak_ptr指向的对象是否仍存在。如果存在，lock返回一个指向共享对象的shared_ptr。与任何其他shared_ptr类似，只要此shared_ptr存在，它所指向的底层对象也就会一直存在。

auto p = make_shared<int>(42);
weak_ptr<int> wp(p);
if (shared_ptr<int> np = wp.lock()) {
    // np 和 p 共享对象
}

动态数组

new 和数组

为了让new分配一个对象数组，我们要在类型名之后跟一对方括号，在其中指明要分配的对象的数目。也可以用一个表示数组类型的类型别名来分配一个数组。

int *pia = new int[10];
typedef int arrT[42];
int *p = new arrT;

由于分配的内存并不是一个数组类型，因此不能对动态数组调用begin或end。这些函数使用数组维度来返回指向首元素和尾后元素的指针。出于相同的原因，也不能用范围for语句来处理（所谓的）动态数组中的元素。

默认情况下new分配的数组是默认初始化的，可以对数组中的元素进行值初始化：在数组大小后跟一对空括号或者初始化列表。

如果初始化器数目大于元素数目，则new表达式失败，不会分配任何内存，抛出一个类型为bad_array_new_length的异常，定义在头文件new中。

虽然我们用空括号对数组中元素进行值初始化，但不能在括号中给出初始化器，这意味着不能用auto分配数组。

当我们用new分配一个大小为 0 的数组时，new返回一个合法的非空指针。此指针保证与new返回的其他任何指针都不相同。对于零长度的数组来说，此指针就像尾后指针一样，我们可以像使用尾后迭代器一样使用这个指针。

为了释放动态数组，我们使用一种特殊形式的delete——在指针前加上一个空方括号对。

delete [] pa;

数组中的元素按逆序销毁。

如果我们在delete一个指向数组的指针时忽略了方括号（或者在delete一个指向单一对象的指针时使用了方括号），其行为是未定义的。

shared_ptr不直接支持管理动态数组，如果希望使用shared_ptr管理一个动态数组，必须提供自己定义的删除器：

shared_ptr<int> sp(new int[10], [](int *p) {delete[] p; });

shared_ptr未定义下标运算符，而且智能指针类型不支持指针算术运算。因此，为了访问数组中的元素，必须用get获取一个内置指针，然后用它来访问数组元素。

allocator 类

标准库allorator类定义在头文件memory中，它帮助我们将内存分配和对象构造分离开来。它提供一种类型感知的内存分配方法，它分配的内存是原始的、未构造的。

为了使用allocate返回的内存，我们必须用construct造对象。使用未构造的内存，其行为是未定义的。

当我们用完对象后，必须对每个构造的元素调用destroy来销毁它们。

uninitialized_copy返回（递增后的）目的位置代器。

使用标准库：文本查询程序

class QueryResult;
class TextQuery {
public:
    using line_no = std::vector<std::string>::size_type;
    TextQuery(std::ifstream&);
    QueryResult query(const std::string&) const;
private:
    std::shared_ptr<std::vector<std::string>> file;
    std::map<std::string, std::shared_ptr<std::set<line_no>>> wm;
}
class QueryResult {
    friend std::ostream& print(std::ostream&, const QueryResult&);
public:
    QueryResult(std::string s, std::shared_ptr<std::set<line_no>> p, std::shared_ptr<std::vector<std::string>> f): sought(s), lines(p), file(f) { }
private:
    std::string sought;
    std::shared_ptr<std::set<line_no>> lines;
    std::shared_ptr<std::vector<std::string>> file;
}

TextQuery::TextQuery(ifstream &is): file(new vector<string>)
{
    string text;
    while (getline(is, text)) {
        file->push_back(text);
        int n = file->size() - 1;
        istringstream line(text);
        string word;
        while (line >> word) {
            auto &lines = wm[word];
              if (!lines)
                lines.reset(new set<line_no>);
            lines->insert(n);
        }
    }
}

QueryResult TextQuery::query(const string &sought) const
{
    static shared_ptr<set<line_no>> nodata(new set<line_no>);
    auto loc = wm.find(sought);
    if (loc == wm.end())
        return QueryResult(sought, nodata, file);
    else
        return QueryResult(sought, loc->second, file);
}

ostream &print(ostream &os, const QueryResult &qr)
{
    os << qr.sought << " occurs " << qr.lines->size() << " " << make_pural(qr.lines->size(), "time", "s") << endl;
    for (auto num : *qr.lines)
        os << "\t(line " << num + 1 << ") " << *(qr.file->begin() + num) << endl;
    return os;
}

void runQueries(ifstream &infile)
{
    TextQuery tq(infile);
    while(true) {
        cout << "enter word to look for, or q to quit: ";
        string s;
        if(!(cin >> s) || s == 'q') break;
        print(cout, tq.query(s)) << endl
    }
}