该笔记是C++ Primer 第二部分，笔记参考了https://github.com/czs108/C++-Primer-5th-Notes-CN/ （未完成）

C++标准库

第八章 IO库

​ 之前已经接触到过的IO库中的设施：

• istream(输入流)类型，提供输入操作。
• ostream(输出流)类型，提供输出操作。
• cin，一个istream 对象，从标准输入读取数据。
• cout，一个ostream 对象，向标准输出写入数据。
• cerr，一个ostream 对象，通常用于输出程序错误消息，写入到标准数据
• >>运算符，用来从一个istream 对象读取输入数据
• <<运算符，用来向一个ostream 对象写入输出数据
• getline 函数，从一个给定的 istream 读取一行数据,存入一个给定的 string 对象中。

8.1 IO类

​ 头文件iostream定义了用于读写流的基本类型，fstream定义了读写命名文件的类型，sstream定义了读写内存中string对象的类型。

• 头文件iostream：

  类型	用法
  istream、wistream	从流读取数据
  ostream、wostream	向流写入数据
  iostream、wiostream	读写流

• 头文件fstream：

  类型	用法
  ifstream、wifstream	从文件读取数据
  ofstream、wofstream	向文件写入数据
  fstream、wfstream	读写文件

• 头文件sstream：

  类型	用法
  istringstream、wistringstream	从string读取数据
  ostringstream、wostringstream	向string写入数据
  stringstream、wstringstream	读写string

​ 宽字符版本的IO类型和函数的名字以w开始，如wcin、wcout和wcerr分别对应cin、cout和cerr。它们与其对应的普通char版本都定义在同一个头文件中，如头文件fstream定义了ifstream和wifstream类型。

IO类型间的关系

​ 可以将派生类的对象当作其基类的对象使用。例如：类型ifstream和istringstream 都继承自 istream。因此，我们可以像使用istream对象一样来使用ifstream和istringstream对象。

IO对象无拷贝或赋值

​ 我们不能拷贝或对IO对象赋值：

ofstream out1, out2;
out1 = out2;    // 错误：不能对流对象赋值
ofstream print(ofstream);   // 错误：不能初始化ofstream参数
out2 = print(out2);     // 错误：不能拷贝流对象

​ 读写一个IO对象会改变其状态，因此传递和返回的引用不能是const的。

条件状态

​ IO 操作一个与生俱来的问题是可能发生错误。一些错误是可恢复的，而其他错误则发生在系统深处，已经超出了应用程序可以修正的范围。

状态	含义
strm::iostate	流的条件状态
strm::badbit	流已崩溃
strm::failbit	一个IO操作失败
strm::badbit	流已崩溃
s.eof()	若流s的eofbit置位，返回true
s.fail()	若流s的failbit或badbit置位，返回true
s.bad()	若流s的badbit置位，返回true
s.good()	若流s处于有效状态，返回true
s.clear()	将流s的所有条件状态复位并将流置为有效
s.clear(flags)	将流s的条件状态置为flags
s.rdstate()	返回流的条件状态

​ 在输入过程中，若是输入的值和所定义的类型不同，则会导致输入进入错误状态。一旦一个流发生错误，则后面的操作都会错误。我们需要保证流一直处于一个无措状态。我们可以将流对象当作一个对象来使用：

int ival;
cin >> ival;// 若输入Boo则会导致输入流错误

while(cin >> word)

查询流的状态

​ IO 库定义了4个 iostate 类型的 constexpr 值,表示特定的位模式。这些值用来表示特定类型的IO条件，可以与位运算符一起使用来一次性检测或设置多个标志位。

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

​ good函数在所有错误均未置位时返回true。而bad、fail和eof函数在对应错误位被置位时返回true。此外，在badbit被置位时，fail函数也会返回true。因此应该使用good或fail函数确定流的总体状态，eof和bad只能检测特定错误。

管理条件状态

​ 每个输出流都管理一个缓冲区，用于保存程序读写的数据。导致缓冲刷新（即数据真正写入输出设备或文件）的原因有很多：

• 程序正常结束。
• 缓冲区已满。
• 使用操纵符（如endl）显式刷新缓冲区。
• 在每个输出操作之后，可以用unitbuf操纵符设置流的内部状态，从而清空缓冲区。默认情况下，对cerr是设置unitbuf的，因此写到cerr的内容都是立即刷新的。
• 一个输出流可以被关联到另一个流。这种情况下，当读写被关联的流时，关联到的流的缓冲区会被刷新。默认情况下，cin和cerr都关联到cout，因此，读cin或写cerr都会刷新cout的缓冲区。

刷新输出缓冲区

​ 操纵符 end1，它完成换行并刷新缓冲区的工作。flush 刷新缓冲区，但不输出任何额外的字符;ends 向缓冲区插入一个空字符，然后刷新缓冲区:

cout << "hi!" << endl;   // 输出 hi 和一个换行，然后刷新缓冲区
cout << "hi!" << flush;  // 输出 hi，然后刷新缓冲区，不附加任何额外字符
cout << "hi!" << ends;   // 输出 hi 和一个空字符，然后刷新缓冲区

ubitbuf操作符

​ 如果想在每次输出操作后都刷新缓冲区，可以使用unitbuf操纵符。它令流在接下来的每次写操作后都进行一次flush操作。而nounitbuf操纵符则使流恢复使用正常的缓冲区刷新机制。

cout << unitbuf;    // 所有输出操作后都会立即刷新缓冲区
// 任何输出都立即刷新，无缓冲
cout << nounitbuf;  // 回到正常的缓冲方式

​ 警告：如果程序异常终止，输出缓冲区是不会被刷新的。当一个程序崩渍后，它所输出的数据很可能停留在输出缓冲区中等待打印。

关联输入和输出流

​ 交互式系统通常应该关联输入流和输出流。这意味着所有输出，包括用户提示信息，都会在读操作之前被打印出来。即在cin前会先刷新cout缓冲区。

​ 使用tie函数可以关联两个流。它有两个重载版本：无参版本返回指向输出流的指针。如果本对象已关联到一个输出流，则返回的就是指向这个流的指针，否则返回空指针。tie的第二个版本接受一个指向ostream的指针，将本对象关联到此ostream。

cin.tie(&cout);     // 仅仅是用来展示:标准库将 cin 和 cout 关联在一起
// old tie指向当前关联到 cin 的流(如果有的话)
ostream *old_tie = cin.tie(nullptr); // cin 不再与其他流关联
// 将cin与cerr 关联;这不是一个好主意，因为 cin 应该关联到 cout
cin.tie(&cerr);     // 读取 cin 会刷新 cerr而不是 cout
cin.tie(old_tie);   // 重建 cin和 cout 间的正常关联

​ 每个流同时最多关联一个流，但多个流可以同时关联同一个ostream。向tie传递空指针可以解开流的关联。

8.2 文件输入输出

​ 头文件fstream定义了三个类型来支持文件IO：ifstream从给定文件读取数据，ofstream向指定文件写入数据，fstream可以同时读写指定文件。

操作	含义
fstream fstrm(s)	打开s文件，打开模式取决于fstream
fstream fstrm(s, mode)	以mode模式打开s文件
fstrm.close()	关闭文件
fstrm.is_open()	如果文件成功打开并尚未关闭，返回true

使用文件流对象

​ 创建文件流对象时,我们可以提供文件名(可选的)。如果提供了一个文件名，则 open会自动被调用:

ifstream in(ifile);//构造一个ifstream 并打开给定文件
ofstream out;// 输出文件流未关联到任何文件

​ 在C++11中，文件流对象的文件名可以是string对象或C风格字符数组。旧版本的标准库只支持C风格字符数组。

用fstream 代替iostream&

​ 在要求使用基类对象的地方，可以用继承类型的对象代替。因此一个接受iostream类型引用或指针参数的函数，可以用对应的fstream类型来调用。

成员函数open和close

​ 可以先定义空文件流对象，再调用open函数将其与指定文件关联。如果open调用失败，failbit会被置位。

​ 对一个已经打开的文件流调用open会失败，并导致failbit被置位。随后试图使用文件流的操作都会失败。如果想将文件流关联到另一个文件，必须先调用close关闭当前文件，再调用clear重置流的条件状态（close不会重置流的条件状态）。

自动构造和析构

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

文件模式

每个流都有一个关联的文件模式，用来指出如何使用文件。

模式	含义
in	以读方式打开
out	以写方式打开
app	每次写操作前定位到文件末尾
ate	打开文件后立即定位到文件末尾
trunc	截断文件
binary	以二进制方式读写

• 只能对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模式打开。

  ​

以out模式打开文件会丢弃已有数据

     默认情况下，打开`ofstream`对象时，文件内容会被丢弃，阻止文件清空的方法是同时指定`app`或`in`模式。

每次调用open 时都会确定文件模式

​ 流对象每次打开文件时都可以改变其文件模式。

ofstream out;   // 未指定文件打开模式
out.open("scratchpad");    // 模式隐含设置为输出和截断
out.close();    // 关闭 out，以便我们将其用于其他文件
out.open("precious", ofstream::app);   // 模式为输出和追加
out.close();

8.3string流

​ 头文件sstream定义了三个类型来支持内存IO：istringstream从string读取数据，ostringstream向string写入数据，stringstream可以同时读写string的数据。

操作	含义
sstream strm(s)	strm保存string s的拷贝
strm.str()	返回strm中的string
strm.str(s)	将string s拷贝至strm

使用istringstream

// 成员默认为公有
struct PersonInfo
{
    string name;
    vector<string> phones;
};

string line, word;   // 分别保存来自输入的一行和单词
vector<PersonInfo> people;    // 保存来自输入的所有记录
// 逐行从输入读取数据，直至 cin 遇到文件尾(或其他错误 )
while (getline(cin, line))
{
    PersonInfo info;    // 创建一个保存此记录数据的对象
    istringstream record(line);    // 将记录绑定到刚读入的行
    record >> info.name;    // 读取名字
    while (record >> word)  // 读取电话号码
        info.phones.push_back(word);   // 保持它们
    people.push_back(info);    // 将此记录追加到people末尾
}

使用ostringstream

for (const auto &entry : people)
{ // 对people中每一项
    ostringstream formatted, badNums;   // 每个循环步创建的对象
    for (const auto &nums : entry.phones)
    { // 对每个数
        if (!valid(nums))
        {
            badNums << " " << nums;  // 将数的字符串形式存入 badNums
        }
        else
            // 将格式化的字符串“写入”formatted
            formatted << " " << format(nums);
    }

    if (badNums.str().empty())   // 没有错误的数
        os << entry.name << " "  // 打印名字
            << formatted.str() << endl;   // 和格式化的数
    else  // 否则，打印名字和错误的数
        cerr << "input error: " << entry.name
            << " invalid number(s) " << badNums.str() << endl;
}

第九章 顺序容器

​ 顺序容器为程序员提供了控制元素存储和访问顺序的能力。这种顺序不依赖元素的值，而是与元素加入时的位置相对应。

9.1 顺序容器概述

​

类型	特性
vector	可变大小数组。支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢
deque	双端队列。支持快速随机访问。在头尾位置插入或删除速度很快
list	双向链表。只支持双向顺序访问。在任何位置插入或删除速度都很快
forward_list	单向链表。只支持单向顺序访问。在任何位置插入或删除速度都很快
array	固定大小数组。支持快速随机访问。不能添加或删除元素
string	类似vector，但用于保存字符。支持快速随机访问。在尾部插入或删除速度很快

​ forward_list和array是C++11新增类型。与内置数组相比，array更安全易用。forward_list没有size操作。

​ 现代C++程序应该使用标准库容器，而不是更原始的数据结构，如内置的数组。

确定使用哪种顺序容器

​ 容器选择原则：

• 除非有合适的理由选择其他容器，否则应该使用vector。

• 如果程序有很多小的元素，且空间的额外开销很重要，则不要使用list或forward_list。

• 如果程序要求随机访问容器元素，则应该使用vector或deque。

• 如果程序需要在容器头尾位置插入/删除元素，但不会在中间位置操作，则应该使用deque。

• 如果程序只有在读取输入时才需要在容器中间位置插入元素，之后需要随机访问元素。则：

  • 先确定是否真的需要在容器中间位置插入元素。当处理输入数据时，可以先向vector追加数据，再调用标准库的sort函数重排元素，从而避免在中间位置添加元素。

  • 如果必须在中间位置插入元素，可以在输入阶段使用list。输入完成后将list中的内容拷贝到vector中。

​ 不确定应该使用哪种容器时，可以先只使用vector和list的公共操作：使用迭代器，不使用下标操作，避免随机访问。这样在必要时选择vector或list都很方便。

9.2 容器库概览

​ 一般来说，每个容器都定义在一个头文件中，文件名与类型名相同。

​ 容器均定义为模板类。

list<Sales_data>	// 保存Sales_data对象的list
deque<double>	    // 保存double的deque

对容器可以保存的元素类型的限制

​ 顺序容器几乎可以保存任意类型的元素，也包括顺序容器本身（用vector类比定义二维数组就是使用这种方式）

vector<vector<string>> lines; // vector的 vector

​ 容器操作

类型别名
iterator	此容器类型的迭代器类型
const_iterator	可以读取元素，但不能修改元素的迭代器类型
size_type	无符号整数类型，足够保存此种容器类型最大可能容器的大小
difference_type	带符号整数类型，足够保存两个迭代器之间的距离
value_type	元素类型
reference	元素的左值诶性：与value_type&含义相同
const_reference	元素的const左值类型（即，const value_type&）
构造函数
C c;	默认构造函数，构造空容器
C c1(c2)	构造c2的拷贝c1
C c(b, e)	构造c，将迭代器b和e指定的范围内的元素拷贝到c（array不支持）
C c{a, b, c...}	列表初始化c
赋值与swap
c1=c2	将c1中的元素替换为c2中元素
c1 = {a, b, c...}	将c1中的元素替换为列表中元素（不适用于array）
a.swap(b)	交换a和b的元素
swap(a, b)	与a.swap(b)等价
大小
c.size()	c中元素的数组（不支持forward_list）
c.max_size()	c中可保存的最大元素数目
c.empty()	若c中存储了元素，返回false,否则返回true
添加/删除元素（不适用于array）
c.insert(args)	将args中的元素拷贝进c
c.emplace(inits)	使用inits构造c中的一个元素
c.erase(args)	删除args指定的元素
c.clear()	删除c中的所有元素，返回void
关系运算符
==, !=	所有容器都支持相等(不等运算符)
<,<=,>,>=	关系运算符(无序关联容器不支持）
获取迭代器
c.begin(), c.end()	返回指向c的首元素和尾元素之后位置的迭代器
c.cbengin(),c.cend()	返回const_iterator
反向容器的额外成员（不支持forward_list）
reverse_iterator	按逆序寻址元素的迭代器
const_reverse_iterator	不能修改元素的逆序迭代器
c.rbegin(), c.rend()	返回指向c的尾元素和首元素之前位置的迭代器
c.crbegin(), c.crend()	返回const_reverse_iterator

迭代器

迭代器范围

​ 一个迭代器范围由一对迭代器表示，两个迭代器分别指向同一个容器中的元素或者尾元素之后的位置。这两个迭代器通常被称为begin和end或者first和last，它们标记了一个容器中元素的一个范围。

​ 第二个迭代器从来不会指向范围中的最后一个元素，而是指向为元素之后的位置。

​ 迭代器在使用的过程中是左闭右开的

​ [begin,end)

​ 迭代器begin和end必须指向相同的容器，end可以与begin指向相同的位置，但不能指向begin之前的位置（编译器不会报错，由程序员确保）。

使用左闭合范围蕴含的编程假定

​ 假定begin和end构成一个合法的迭代器范围，则：

• 如果begin等于end，则范围为空。
• 如果begin不等于end，则范围内至少包含一个元素，且begin指向该范围内的第一个元素。
• 可以递增begin若干次，令begin等于end。

while (begin != end)
{
    *begin = val;   // 正确：范围非空，因此begin指向一个元素
    ++begin;    // 移动迭代器，获取下一个元素
}

容器类型成员

​ 反向迭代器就是一种反向遍历容器的迭代器，与正向迭代器相比,各种操作的含义也都发生了颠倒。例如，对一个反向迭代器执行++操作，会得到上一个元素。

​ 通过类型别名，我们可以在不了解容器中元素类型的情况下使用它。如果需要元素类型，可以使用容器的value_type。如果需要元素类型的引用，可以使用reference或const_reference。

// iter 是通过list<string>定义的一个迭代器类型
list<string>::iterator iter;
// count 是通过 vector<int>定义的一个difference type 类型
vector<int>::difference_type count;

begin和end成员

​ begin和end操作生成指向容器中第一个元素和尾后地址的迭代器。其常见用途是形成一个包含容器中所有元素的迭代器范围。

​ begin和end操作有多个版本：带r的版本返回反向迭代器。以c开头的版本（C++11新增）返回const迭代器。不以c开头的版本都是重载的，当对非常量对象调用这些成员时，返回普通迭代器，对const对象调用时，返回const迭代器。

list<string> a = {"Milton", "Shakespeare", "Austen"};
auto it1 = a.begin();    // list<string>::iterator
auto it2 = a.rbegin();   // list<string>::reverse_iterator
auto it3 = a.cbegin();   // list<string>::const_iterator
auto it4 = a.crbegin();  // list<string>::const_reverse_iterator

​ 当auto与begin或end结合使用时，返回的迭代器类型依赖于容器类型。但调用以c开头的版本仍然可以获得const迭代器，与容器是否是常量无关。

​ 当程序不需要写操作时，应该使用cbegin和cend。

容器定义和初始化

​ 每个容器类型都定义了一个默认构造函数。除 array 之外，其他容器的默认构造函数都会创建一个指定类型的空容器，且都可以接受指定容器大小和元素初始值的参数。

将一个容器初始化为另一个容器的拷贝

​ 将一个容器初始化为另一个容器的拷贝时，两个容器的容器类型和元素类型都必须相同。传递迭代器参数来拷贝一个范围时，不要求容器类型相同，而且新容器和原容器中的元素类型也可以不同，但是要能进行类型转换

// 每个容器有三个元素，用给定的初始化器进行初始化
list<string> authors = {"Milton", "Shakespeare", "Austen"};
vector<const char*> articles = {"a", "an", "the"};
list<string> list2(authors);        // 正确:类型匹配
deque<string> authList(authors);    // 错误:容器类型不匹配
vector<string> words(articles);     // 错误:容器类型必须匹配
// 正确:可以将 const char*元素转换为 string
forward_list<string> words(articles.begin(), articles.end());

列表初始化

​ C++11允许对容器进行列表初始化。

// 每个容器有三个元素，用给定的初始化器进行初始化
list<string> authors = {"Milton", "Shakespeare", "Austen"};
vector<const char*> articles = {"a", "an", "the"};

与顺序容器大小相关的构造函数

​ 除了与关联容器相同的构造函数外，顺序容器(array 除外)还提供另一个构造函数它接受一个容器大小和一个(可选的) 元素初始值。如果我们不提供元素初始值，则标准库会创建一个值初始化器 :

vector<int> ivec(10，-1);// 10个int 元素，每个都初始化为-1
list<string> svec(10，"hi!");// 10个strings;每个都初始化为"hi!"
forward list<int> ivec(10);// 10个元素，每个都初始化为 0
deque<string> svec(10);// 10 个元素，每个都是空 string

标准库array具有固定大小

​ 定义和使用array类型时，需要同时指定元素类型和容器大小。

array<int, 42>      // 类型为:保存 42个int 的数组
array<string, 10>   // 类型为:保存10个string 的数组
array<int, 10>::size_type i;   // 数组类型包括元素类型和大小
array<int>::size_type j;       // 错误:array<int>不是一个类型

​ 对array进行列表初始化时，初始值的数量不能大于array的大小。如果初始值的数量小于array的大小，则只初始化靠前的元素，剩余元素会被值初始化。如果元素类型是类类型，则该类需要一个默认构造函数。

​ 可以对array进行拷贝或赋值操作，但要求二者的元素类型和大小都相同。

​ 值得注意的是，虽然我们不能对内置数组类型进行拷贝或对象赋值操作，但 array 并无此限制:

int digs[10]=(0,1,2,3,4,5,6,7,8,9);
int cpy[10]= digs;			// 错误:内置数组不支持拷贝或赋值
array<int，10> digits=(0,1,2,3,4,5,6,7,8,9);
array<int，10>copy = digits;// 正确:只要数组类型匹配即合法

赋值和swap

使用assign（仅顺序容器）

​ 赋值运算符两侧的运算对象必须类型相同。assign允许用不同但相容的类型赋值，或者用容器的子序列赋值。

list<string> names;
vector<const char*> oldstyle;
names = oldstyle;   // 错误：容器类型不匹配
// 正确:可以将 const char*转换为 string
names.assign(oldstyle.cbegin(), oldstyle.cend());

​ 由于其旧元素被替换，因此传递给assign的迭代器不能指向调用assign的容器本身。

使用swap

​ 对于array，swap会真正交换它们的元素。因此在swap操作后，指针、引用和迭代器所绑定的元素不变，但元素值已经被交换。

array<int, 3> a = { 1, 2, 3 };
array<int, 3> b = { 4, 5, 6 };
auto p = a.cbegin(), q = a.cend();
a.swap(b);
// 输出交换后的值，即4、5、6
while (p != q)
{
    cout << *p << endl;
    ++p;
}

​ 对于其他容器类型（除string），指针、引用和迭代器在swap操作后仍指向操作前的元素，但这些元素已经属于不同的容器了。

vector<int> a = { 1, 2, 3 };
vector<int> b = { 4, 5, 6 };
auto p = a.cbegin(), q = a.cend();
a.swap(b);
// 输出交换前的值，即1、2、3
while (p != q)
{
    cout << *p << endl;
    ++p;
}

​ array不支持assign，也不允许用花括号列表进行赋值。

array<int, 10> a1 = {0,1,2,3,4,5,6,7,8,9};
array<int, 10> a2 = {0};    // 所有元素值均为 0
a1 = a2;    // 替换 a1中的元素
a2 = {0};   // 错误:不能将一个花括号列表赋予数组

​ 新标准库同时提供了成员和非成员函数版本的swap。非成员版本的swap在泛型编程中非常重要，建议统一使用非成员版本的swap。

容器大小操作

​ size成员返回容器中元素的数量；empty当size为0时返回true，否则返回false；max_size返回一个大于或等于该类型容器所能容纳的最大元素数量的值。forward_list支持max_size和empty，但不支持size。

关系运算符

​ 每个容器类型都支持相等运算符（==、!=）。除无序关联容器外，其他容器都支持关系运算符（>、>=、<、<=）。关系运算符两侧的容器类型和保存元素类型都必须相同。

​ 两个容器的比较实际上是元素的逐对比较，其工作方式与string的关系运算符类似：

• 如果两个容器大小相同且所有元素对应相等，则这两个容器相等。
• 如果两个容器大小不同，但较小容器中的每个元素都等于较大容器中的对应元素，则较小容器小于较大容器。
• 如果两个容器都不是对方的前缀子序列，则两个容器的比较结果取决于第一个不等元素的比较结果。

vector<int> v1 = { 1, 3, 5, 7, 9, 12 };
vector<int> v2 = { 1, 3, 9 };
vector<int> v3 = { 1, 3, 5, 7 };
vector<int> v4 = { 1, 3, 5, 7, 9, 12 };
v1 < v2     // true;vl和v2在元素[2]处不同:vl[2]小于等于v2[2]
v1 < v3     // false;所有元素都相等，但 v3 中元素数目更少
v1 == v4    // true;每个元素都相等，且vl和v4大小相同
v1 == v2    // false;v2元素数目比 v1 少

容器的关系运算符使用元素的关系运算符完成比较

​ 容器的相等运算符实际上是使用元素的==运算符实现的，而其他关系运算符则是使用元素的<运算符。如果元素类型不支持所需运算符，则保存该元素的容器就不能使用相应的关系运算。

9.3顺序容器操作

向顺序容器添加元素

​ 我们在对容器的操作过程中要注意不同的容器用不同的策略来分配元素空间，这些策略会直接影响性能。

使用push_back

​ 将元素添加在容器的尾部

// 从标准输入读取数据，将每个单词放到容器末尾
string word;
while (cin >> word)
    container.push_back(word);

​ 需要我们注意的是容器的元素是拷贝，当我们初始化元素或者向容器中插入元素的行为实质上放到容器中的对象值是一个拷贝值，而不是对象本身。

使用push_front

​ 将元素添加在容器的首部

list<int> ilist;
// 将元素添加到 ilist 开头
for (size_t ix =0;ix != 4;++ix)
ilist.push_front(ix);

使用insert

​ 在容器的特定部位添加元素

slist.insert(iter,"Hello!");// 将"Hello"添加到iter之前的位置

​ 有些容器不支持使用push_front，但是支持insert。我们可以使用insert来模拟push_front

vector<string> svec;
list<string> slist;
// 等价于 slist.push_front("Hello!");
slist.insert(slist.begin(), "Hello!");
// vector不支持push_front,但我们可以插入到begin()之前
// 警告：插到vector末尾之外的任何位置都可能很慢
svec.insert(svec.begin(), "Hello!");

​ 将元素插入到 vector、deque和string中的任何位置都是合法的。然而这样做可能很耗时。

​ insert可以通过接受更多参数来做到插入范围内元素的操作

svec.insert(svec.end()， 10，"Anna");
// 这行代码将10个元素插入到 svec 的末尾，并将所有元素都初始化为 string“Anna"

​ 在新标准库中，接受元素个数或范围的insert版本返回指向第一个新增元素的迭代器，而旧版本中这些操作返回void。如果范围为空，不插入任何元素，insert会返回第一个参数。

​ 使用insert的返回值，可以在容器中一个特定的位置反复插入元素：

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

使用emplace操作

​ 标准库增加了三个直接构造而不是拷贝元素的操作：emplace_front、emplace_back和emplace，其分别对应push_front、push_back和insert。当调用push或insert时，元素对象被拷贝到容器中。而调用emplace时，则是将参数传递给元素类型的构造函数，直接在容器的内存空间中构造元素。

// 在c的末尾构造一个Sales_data对象
// 使用三个参数的Sales_data构造函数
c.emplace_back("978-0590353403", 25, 15.99);
// 错误：没有接受三个参数的push_data构造函数
c.push_back("978-0590353403", 25, 15.99);
// 正确：创建一个临时的Sales_data对象传递给push_back
c.push_back(Sales_data("978-0590353403", 25, 15.99));

访问元素

​ 每个顺序容器都有一个front成员函数，而除了forward_list之外的顺序容器还有一个back成员函数。这两个操作分别返回首元素和尾元素的引用。在调用front和back之前，要确保容器非空。

// 在解引用一个选代器或调用 front 或 back 之前检查是否有元素
if (!c.empty()){
    // val和val2是c中第一个元素值的拷贝
    auto val = *c.begin()， val2=c.front();
    // va13和 val4是c中最后一个元素值的拷贝
    auto last = c.end();
    auto val3 = *(--last); // 不能递减 forward_list 选代器
    auto val4 = c.back(); // forward_list 不支持
}

访问成员函数返回的是引用

​ 在容器中访问元素的成员函数（即，front、back、下标和at）返回的都是引用。如果容器是一个const对象，则返回值是const的引用。如果容器不是const的，则返回值是普通引用，我们可以用来改变元素的值。

if (!c.empty()) {
    c.front() = 42;			//将42赋予c中的第一个元素
    auto &v = c.back();		//获得指向最后一个元素的引用
    v = 1024;			   //改变 c中的元素
    auto v2 = c.back();	    // v2 不是一个引用，它是 c.back()的一个拷贝	
    v2=0;				  //未改变c中的元素
}

下标操作和安全的随机访问

​ 在下标访问的过程中我们要保证下标是有效的，为了防止出现意外，我们可以使用at成员函数。at成员函数类似于下标运算符，但如果下标越界，at会抛出一个out_of_range异常。

vector<string> svec;  // 空vector
cout << svec[0];      // 运行错误：svec中没有元素
cout << svec.at(0);   // 抛出一个out_of_range异常

删除数据

​ 删除deque中除首尾位置之外的任何元素都会使所有迭代器、引用和指针失效。删除vector或string的元素后，指向删除点之后位置的迭代器、引用和指针也都会失效。

pop_front和pop_back成员函数

​ pop_front和pop_back函数分别删除首元素和尾元素。vector和string类型不支持pop_front，forward_list类型不支持pop_back。

erase成员函数

​ erase函数删除指定位置的元素。可以删除由一个迭代器指定的单个元素，也可以删除由一对迭代器指定的范围内的所有元素。两种形式的erase都返回指向删除元素（最后一个）之后位置的迭代器。

list<int> lst ={0,1,2,3,4,5,6,7,8,9);
auto it =lst.begin();
while (it != lst.end())
	if (*it % 2)// 若元素为奇数
		it = ist.erase(it); // 删除此元素
	else
	++it;

​ 删除多个元素

// 删除两个迭代器表示的范围内的元素
// 返回指向最后一个被删元素之后位置的选代器
eleml = slist.erase(eleml，elem2); // 调用后，elem == elem2

slist.clear(); // 删除容器中所有元素
slist.erase(slist.begin()，slist.end()); // 等价调用

特殊的forward_list操作

​ 在forward_list中添加或删除元素的操作是通过改变给定元素之后的元素来完成的。

forward list<int> flst = (0,1,2,3,4,5,6,7,8,9);
auto prev = flst.before_begin();	//表示 flst的“首前元素”
auto curr = flst.begin();			//表示flst 中的第一个元素
while (curr != flst,end()) {		// 仍有元素要处理
    if (*curr % 2)						// 若元素为奇数
        curr = flst.erase after(prev); // 删除它并移动 curr
    else {
        prev = curr;// 移动选代器 curr，指向下一个元素，prev 指向
        ++cuur;		//curr之前的元素
    }
}

改变容器大小

​ resize函数接受一个可选的元素值参数，用来初始化添加到容器中的元素，否则新元素进行值初始化。如果容器保存的是类类型元素，且resize向容器添加新元素，则必须提供初始值，或元素类型提供默认构造函数。

list<int> ilist(10，42);// 10个int:每个的值都是42
ilist.resize(15);//将5个值为0的元素添加到 ilist 的末尾
ilist.resize(25，-1);//将10个值为-1的元素添加到 ilist 的末尾
ilist.resize(5);//从ilist 末尾删除 20 个元素

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

向容器中添加或删除元素可能会使指向容器元素的指针、引用或迭代器失效。失效的指针、引用或迭代器不再表示任何元素，使用它们是一种严重的程序设计错误。

• 向容器中添加元素后：
  • 如果容器是vector或string类型，且存储空间被重新分配，则指向容器的迭代器、指针和引用都会失效。如果存储空间未重新分配，指向插入位置之前元素的迭代器、指针和引用仍然有效，但指向插入位置之后元素的迭代器、指针和引用都会失效。
  • 如果容器是deque类型，添加到除首尾之外的任何位置都会使迭代器、指针和引用失效。如果添加到首尾位置，则迭代器会失效，而指针和引用不会失效。
  • 如果容器是list或forward_list类型，指向容器的迭代器、指针和引用仍然有效。
• 从容器中删除元素后，指向被删除元素的迭代器、指针和引用失效：
  • 如果容器是list或forward_list类型，指向容器其他位置的迭代器、指针和引用仍然有效。
  • 如果容器是deque类型，删除除首尾之外的任何元素都会使迭代器、指针和引用失效。如果删除尾元素，则尾后迭代器失效，其他迭代器、指针和引用不受影响。如果删除首元素，这些也不会受影响。
  • 如果容器是vector或string类型，指向删除位置之前元素的迭代器、指针和引用仍然有效。但尾后迭代器总会失效。

必须保证在每次改变容器后都正确地重新定位迭代器。

不要保存end函数返回的迭代器。

9.4 vector对象是如何增长的

​ 由于vector和string在增加时分配新的空间效率过慢，所以vector和string的实现通常会分配比新的空间需求更大的内存空间

管理容量的成员函数·

​ reserve操作允许我们通知容器我们需要存储多少个元素。reserve不会改变容器中元素的数量，仅仅影响vector预先分配多大的内存。

c.reserve(n);

capacity和size

​ capacity函数返回容器在不扩充内存空间的情况下最多可以容纳的元素数量。size函数是指已经保存的元素的数目。

​ 只有当需要的内存空间超过当前容量时，reserve才会真正改变容器容量，分配不小于需求大小的内存空间。当需求大小小于当前容量时，reserve并不会退回内存空间。因此在调用reserve之后，capacity会大于或等于传递给reserve的参数。

​ 在C++11中可以使用shrink_to_fit函数来要求deque、vector和string退回不需要的内存空间（并不保证退回）。

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

9.5 额外的string操作

构造string的其他方法

​ 从另一个string对象拷贝字符构造string时，如果提供的拷贝开始位置（可选）大于给定string的大小，则构造函数会抛出out_of_range异常。

substr操作

​ substr操作返回一个 string，它是原始string 的一部分或全部的贝。可以传递给 substr一个可选的开始位置和计数值

string s("hello world");
string s2 = s.substr(0，5);// s2 =hello
string s3 = s.substr(6);// s3= world
string s4 =s.substr(6，11);// s3= world
string s5 = s.substr(12);// 抛出一个out of range 异常

​ 如果传递给substr函数的开始位置超过string的大小，则函数会抛出out_of_range异常。

改变string的其他方法

​ 除了接受迭代器的 insert 和erase 版本外，string还提供了接受下标的版本下标指出了开始删除的位置，或是 insert 到给定值之前的位置:

s.insert(s.size()，5，'!'); //在s 末尾插入5个感叹号
s.erase(s.size() - 5，5);// 从 s删除最后 5个字

append 和replace 函数

​ append函数是在string末尾进行插入操作的简写形式。

string s("C++ Primer"), s2 = s;     // 将s和s2初始化为"C++ Primer"
s.insert(s.size(), " 4th Ed.");     // s == "C++ Primer 4th Ed."
s2.append(" 4th Ed.");     // 等价方法:将”4th Ed."追加到s2;s== s2

​ replace函数是调用erase和insert函数的简写形式。

// 将”4th”替换为”5th"的等价方法
s.erase(11, 3);         // s == "C++ Primer Ed."
s.insert(11, "5th");    // s == "C++ Primer 5th Ed."
// 从位置11开始，删除3个字符并插入”5th"
s2.replace(11, 3, "5th");   // 等价方法: s == s2

string搜索操作

​ string 搜索函数返回string::size_type 值，该类型是一个unsigned类型。因此，用一个 int 或其他带符号类型来保存这些函数的返回值不是一个好主意

​ find 函数完成最简单的搜索。它查找参数指定的字符串，若找到，则返回第一个匹配位置的下标，否则返回npos

指定在哪里开始

​ 我们可以传递给 find 操作一个可选的开始位置。这个可选的参数指出从哪个位置开始进行搜索。默认情况下，此位置被置为 0。一种常见的程序设计模式是用这个可选参数在字符串中循环地搜索子字符串出现的所有位置:

string::size_type pos = 0;
// 每步循环查找name 中下一个数
while ((pos = name.find first of(numbers, pos))
				!= string::npos){
    cout << "found number at index: " << pos
    	<< " element is " << name[pos] << endl;
    ++pos;// 移动到下一个字符
}

逆向搜索

​ 标准库还提供了类似的但由右至左搜索的操作。rfind 成员函数搜索最后一个匹配，即子字符串最靠右的出现位置。

compare函数

​ 根据 s 是等于、大于还是小于参数指定的字符串，s.compare 返回0、正数或负数。

数值转化

​ C++11增加了string和数值之间的转换函数。

​ 进行数值转换时，string参数的第一个非空白字符必须是符号（+或-）或数字。它可以以0x或0X开头来表示十六进制数。对于转换目标是浮点值的函数，string参数也可以以小数点开头，并可以包含e或E来表示指数部分。

​ 如果给定的string不能转换为一个数值，则转换函数会抛出invalid_argument异常。如果转换得到的数值无法用任何类型表示，则抛出out_of_range异常。

9.6 容器适配器

​ 除了顺序容器外，标准库还定义了三个顺序容器适配器:stack、queue 和priority_queue。适配器 (adaptor)是标准库中的一个通用概念。容器、代器和函数都有适配器。

定义一个适配器

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

// 在vector上实现的空栈
stack<string, vector<string>> str_stk;
// str_stk2在vector 上实现，初始化时保存 svec 的拷贝
stack<string, vector<string>> str_stk2(svec);

​ 所有适配器都要求容器具有添加和删除元素的能力，因此适配器不能构造在array上。适配器还要求容器具有添加、删除和访问尾元素的能力，因此也不能用forward_list构造适配器。

栈适配器

栈适配器stack定义在头文件stack中。队列适配器queue和priority_queue定义在头文件queue中。

队列适配器

queue使用先进先出的存储和访问策略。进入队列的对象被放置到队尾，而离开队列的对象则从队首删除。

第十章 泛式算法

​ 标准库并未给每个容器都定义成员函数来实现这些操作，而是定义了一组泛型算法：称它们为“算法”，是因为它们实现了一些经典算法的公共接口。

10.1 概述

​ 大多数算法都定义在头文件algorithm中，此外标准库还在头文件numeric中定义了一组数值泛型算法。一般情况下，这些算法并不直接操作容器，而是遍历由两个迭代器指定的元素范围进行操作。

​ find函数将范围中的每个元素与给定值进行比较，返回指向第一个等于给定值的元素的迭代器。如果无匹配元素，则返回其第二个参数来表示搜索失败。

int val = 42;   // 我们要寻找的值
// 如果在 vec 中找到想要的元素，则返回结果指向它，否则返回结果为 vec.cend()
auto result = find(vec.cbegin(), vec.cend(), val);
// 报告结果
cout << "The value " << val
    << (result == vec.cend() ? " is not present" : " is present") << endl;

​ 迭代器参数令算法不依赖于特定容器，但依赖于元素类型操作。

​ 泛型算法本身不会执行容器操作，它们只会运行于迭代器之上，执行迭代器操作。算法可能改变容器中元素的值，或者在容器内移动元素，但不会改变底层容器的大小（当算法操作插入迭代器时，迭代器可以向容器中添加元素，但算法自身不会进行这种操作）。

10.2 初识泛型算法

​ 虽然大多数算法遍历输入范围的方式相似，但它们使用范围中元素的方式不同。理解算法的最基本的方法就是了解它们是否读取元素、改变元素或是重排元素顺序。

只读算法

​ find和count都是只读算法，这类算法只会读取去输入范围内的元素，而不会改变元素。

​ 另一种只读算法是accumulate，它定义在头文件numeric中。接受三个参数，前两个参数指定需要求和的元素范围，第三个参数是和的初值（决定加法运算类型和返回值类型）。

// 对 vec 中的元素求和，和的初值是 0
int sum = accumulate(vec.cbegin(), vec.cend(), 0);

算法和元素类型

​ accumulate 将第三个参数作为求和起点，序列中元素的类型必须与第三个参数匹配，或者能够转换为第三个参数的类型。由于string定义了+运算符，所以我们可以通过调用accumulate来将 vector 中所有 string 元素连接起来:

string sum = accumulate(v.cbegin(), v.cend(), string(""));
// 错误:const char*上没有定义+运算符
string sum = accumulate(v.cbegin(), v.cend(), "");

​ 建议在只读算法中使用cbegin和cend函数。

操作两个序列的算法

​ 另一个只读算法是 equal，用于确定两个序列是否保存相同的值。它接受三个迭代器参数，前两个参数指定第一个序列范围，第三个参数指定第二个序列的首元素。equal函数假定第二个序列至少与第一个序列一样长。

// roster2中的元素数目应该至少与roster1一样多
equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());

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

写容器元素的算法

​ fill函数接受两个迭代器参数表示序列范围，还接受一个值作为第三个参数，它将给定值赋予范围内的每个元素。

// 将每个元素重置为0
fill(vec.begin(), vec.end(), 0);

​ 由于 fill 向给定输入序列中写入数据，因此，只要我们传递了一个有效的输入序列，写入操作就是安全的。

算法不检查写操作

​ fill_n函数接受单个迭代器参数、一个计数值和一个值，它将给定值赋予迭代器指向位置开始的指定个元素。

// 使用 vec，赋予它不同值
fill_n(vec.begin(), vec.size(), 0);
// 函数 fill_n 假定写入指定个元素是安全的
fill_n(dest，n，val)
// 灾难:修改 vec中的10个(不存在)元素
fill_n(vec.begin()，10，0);

​ 向目的位置迭代器写入数据的算法都假定目的位置足够大，能容纳要写入的元素。

介绍back_inserter

​ 插入迭代器是一种向容器内添加元素的迭代器。通过插入迭代器赋值时，一个与赋值号右侧值相等的元素会被添加到容器中。

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

vector<int> vec;    // 空向量
auto it = back_inserter(vec);   // 通过它赋值会将元素添加到vec中
*it = 42;   // vec中现在又一个元素，值为42
// 正确:back_inserter 创建一个插入迭代器，可用来向 vec 添加元素
fill_n(back_inserter(vec), 10, 0);  // 添加10个元素到vec

拷贝算法

​ copy函数接受三个迭代器参数，前两个参数指定输入序列，第三个参数指定目的序列的起始位置。它将输入序列中的元素拷贝到目的序列中，返回目的位置迭代器（递增后）的值。

int a1[] = { 0,1,2,3,4,5,6,7,8,9 };
int a2[sizeof(a1) / sizeof(*a1)];     // a2 与 a1大小一样
// ret 指向拷贝到 a2 的尾元素之后的位置
auto ret = copy(begin(a1), end(a1), a2);    // 把a1的内容拷贝给a2

​ replace函数接受四个参数，前两个迭代器参数指定输入序列，后两个参数指定要搜索的值和替换值。它将序列中所有等于第一个值的元素都替换为第二个值。

// 将所有值为0的元素改为42
replace(ilst.begin(), ilst.end(), 0, 42);

​ 相对于replace，replace_copy函数可以保留原序列不变。它接受第三个迭代器参数，指定调整后序列的保存位置。

// 使用back_inserter按需要增长目标序列
replace_copy(ilst.cbegin(), ilst.cend(), back_inserter(ivec), 0, 42);

​ 很多算法都提供“copy”版本，这些版本不会将新元素放回输入序列，而是创建一个新序列保存结果。

重排容器元素的算法

​ sort函数接受两个迭代器参数，指定排序范围。它利用元素类型的<运算符重新排列元素。

消除重复单词

void elimDups(vector<string> &words)
{
    // 按字典序排序 words，以便查找重复单词
    sort(words.begin(), words.end());
    // unique 重排输入范围，使得每个单词只出现一次
    // 排列在范围的前部，返回指向不重复区域之后一个位置的迭代器
    auto end_unique = unique(words.begin(), words.end());
    // 使用向量操作 erase删除重复单词
    words.erase(end_unique, words.end());
}

使用unique

​ unique函数重排输入序列，消除相邻的重复项，返回指向不重复值范围末尾的迭代器。

10.3 定制操作

	默认情况下，很多比较算法使用元素类型的`<`或`==`运算符完成操作。可以为这些算法提供自定义操作来代替默认运算符。

向算法传递函数

谓词

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

// 比较函数，用来按长度排序单词
bool isShorter(const string &s1, const string &s2)
{
    return s1.size() < s2.size();
}
// 按长度由短至长排序 words
sort(words.begin(), words.end(), isShorter);

排序算法

​ 稳定排序函数stable_sort可以维持输入序列中相等元素的原有顺序。

elimDups(words); // 将words 按宇典序重排，并消除重复单词
// 按长度重新排序，长度相同的单词维持字典序
stable sort(words.begin(), words.end(), isShorter);
for (const auto &s : words) // 无须拷贝字符串
	cout << s << " ";// 打印每个元素，以空格分隔
cout << endl;

lambda表达式

​ find_if函数接受两个迭代器参数和一个谓词参数。迭代器参数用于指定序列范围，之后对序列中的每个元素调用给定谓词，并返回第一个使谓词返回非0值的元素。如果不存在，则返回尾迭代器。

介绍lambda

​ 对于一个对象或表达式，如果可以对其使用调用运算符()，则称它为可调用对象（callable object）。可以向算法传递任何类别的可调用对象。

​ 一个lambda表达式表示一个可调用的代码单元，类似未命名的内联函数，但可以定义在函数内部。其形式如下：

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

​ 其中，capture list（捕获列表）是一个由lambda所在函数定义的局部变量的列表（通常为空）。return type、parameter list和function body与普通函数一样，分别表示返回类型、参数列表和函数体。但与普通函数不同，lambda必须使用尾置返回类型，且不能有默认实参。

​ 定义lambda时可以省略参数列表和返回类型，但必须包含捕获列表和函数体。省略参数列表等价于指定空参数列表。省略返回类型时，若函数体只是一个return语句，则返回类型由返回表达式的类型推断而来。否则返回类型为void。

auto f = [] { return 42; };
cout << f() << endl;    // 打印 42

向lambda传递参数

​ 通常，实参和形参的类型必须匹配。但与普通函数不同，lambda 不能有默认参数。因此，一个 lambda 调用的实参数目永远与形参数目相等。一旦形参初始化完毕，就可以执行函数体了。

[](const string &a, const string &b)
	{ return a.size() < b.size();}

​ 可以使用此lambda 来调用stable_sort:

// 按长度排序，长度相同的单词维持宇典序
stable sort(words.begin()， words.end()，
			[](const string &a, const string &b)
				{ return a.size() < b.size();});

使用捕获列表

​ 在本例中，我们的 lambda 会捕获 sz，并只有单一的 string 参数。其函数体会将string 的大小与捕获的 sz 的值进行比较:

[sz](const string &a)
	{ return a.size() >= sz;};

​ 一个 lambda 只有在其捕获列表中捕获一个它所在函数中的局部变量，才能在函数体中使用该变量。

调用find_if

​ lambda可以使用其所在函数的局部变量，但必须先将其包含在捕获列表中。捕获列表只能用于局部非static变量，lambda可以直接使用局部static变量和其所在函数之外声明的名字。

// 获取一个选代器，指向第一个满足 size()>= sz的元素
auto wc = find_if(words.begin(), words.end(),
                    [sz](const string &a) { return a.size() >= sz; });

for_each算法

for_each函数接受一个输入序列和一个可调用对象，它对输入序列中的每个元素调用此对象。

// 打印长度大于等于给定值的单词，每个单词后面接一个空格
for_each(wc, words.end(),
            [] (const string &s) { cout << s << " "; });

完整的 biggies

void biggies(vector<string> &words,
			vector<string>::size type sz)
{
    elimDups(words); // 将words 按宇典序排序，删除重复单词
    // 按长度排序，长度相同的单词维持字典序
    stable sort(words.begin()， wordsend()
    			[](const string &a, const string &b)
    				{ return a.size() < b.size();});
    // 获取一个迭代器，指向第一个满足 size()>= sz 的元素
    auto wc = find if(words.begin()， words.end()
    [sz](const string &a)
    { return a.size() >= sz; });
    // 计算满足 size >= sz 的元素的数目
    auto count = words.end() - wc;
    cout << count <<" "<< make plural(count，"word",
    "s")
    <<" of length "<< sz << " or longer" << endl;
    // 打印长度大于等于给定值的单词，每个单词后面接一个空格
    for each(wc，words.end()，
    [](const string &s){cout << s << "";});
    cout << endl;
    }
    

lambda捕获和返回

值捕获

​ 被lambda捕获的变量的值是在lambda创建时拷贝，而不是调用时拷贝。在lambda创建后修改局部变量不会影响lambda内对应的值。

size_t v1 = 42; // 局部变量
// 将v1拷贝到名为f的可调用对象
auto f = [v1] { return v1; };
v1 = 0;
auto j = f();   // j为42;f保存了我们创建它时 v1的拷贝

引用捕获

​ lambda可以以引用方式捕获变量，但必须保证lambda执行时变量存在。

size_t v1 = 42; // 局部变量
// 对象f2包含v1引用
auto f2 = [&v1] { return v1; };
v1 = 0;
auto j = f2();  // j为0;f2保存vl的引用，而非拷贝

隐式捕获

​ 可以让编译器根据lambda代码隐式捕获函数变量，方法是在捕获列表中写一个&或=符号。&为引用捕获，=为值捕获。

​ 可以混合使用显式捕获和隐式捕获。混合使用时，捕获列表中的第一个元素必须是&或=符号，用于指定默认捕获方式。显式捕获的变量必须使用与隐式捕获不同的方式。

// os 隐式捕获，引用捕获方式;c 显式捕获，值捕获方式
for_each(words.begin(), words.end(),
            [&, c] (const string &s) { os << s << c; });
// os 显式捕获，引用捕获方式;c 隐式捕获，值捕获方式
for_each(words.begin(), words.end(),
            [=, &os] (const string &s) { os << s << c; });

可变lamba

​ 默认情况下，对于值方式捕获的变量，lambda不能修改其值。如果希望修改，就必须在参数列表后添加关键字mutable。

size_t v1 = 42; // 局部变量
// f 可以改变它所捕获的变量的值
auto f = [v1] () mutable { return ++v1; };
v1 = 0;
auto j = f();   // j 为 43

​ 对于引用方式捕获的变量，lambda是否可以修改依赖于此引用指向的是否是const类型。

指定lambda返回类型

​ transform函数接受三个迭代器参数和一个可调用对象。前两个迭代器参数指定输入序列，第三个迭代器参数表示目的位置。它对输入序列中的每个元素调用可调用对象，并将结果写入目的位置。

transform(vi.begin(), vi.end(), vi.begin(),
            [](int i) -> int { if (i < 0) return -i; else return i; });

​ 为lambda定义返回类型时，必须使用尾置返回类型。

参数绑定

标准bind函数

​ bind函数定义在头文件functional中，相当于一个函数适配器，它接受一个可调用对象，生成一个新的可调用对象来适配原对象的参数列表。一般形式如下：

auto newCallable = bind(callable, arg_list);

​ 其中，newCallable本身是一个可调用对象，arg_list是一个以逗号分隔的参数列表，对应给定的callable的参数。之后调用newCallable时，newCallable会再调用callable，并传递给它arg_list中的参数。arg_list中可能包含形如_n的名字，其中n是一个整数。这些参数是占位符，表示newCallable的参数，它们占据了传递给newCallable的参数的位置。数值n表示生成的可调用对象中参数的位置：_1为newCallable的第一个参数，_2为newCallable的第二个参数，依次类推。这些名字都定义在命名空间placeholders中，它又定义在命名空间std中，因此使用时应该进行双重限定。

使用placeholders名字

using std::placeholders::_1;
using namespace std::placeholders;
bool check_size(const string &s, string::size_type sz);
// check6 是一个课调用对象，接受一个string类型的参数
// 并用此string和值6来调用check_size
auto check6 = bind(check_size, _1, 6);
string s = "hello";
bool b1 = check6(s);    // check6(s) 会调用 check_size(s, 6)

bind的参数

​ bind函数可以调整给定可调用对象中的参数顺序。

// 按单词长度由短至长排序
sort(words.begin(), words.end(), isShorter);
// 按单词长度由长至短排序
sort(words.begin(), words.end(), bind(isShorter, _2, _1));

用bind重排参数顺序

​ 默认情况下，bind函数的非占位符参数被拷贝到bind返回的可调用对象中。但有些类型不支持拷贝操作。

​ 如果希望传递给bind一个对象而又不拷贝它，则必须使用标准库的ref函数。ref函数返回一个对象，包含给定的引用，此对象是可以拷贝的。cref函数生成保存const引用的类。

ostream &print(ostream &os, const string &s, char c);
for_each(words.begin(), words.end(), bind(print, ref(os), _1, ' '));

10.4 再探迭代器

除了为每种容器定义的迭代器之外，标准库还在头文件iterator中定义了另外几种迭代器。

• 插入迭代器（insert iterator）：该类型迭代器被绑定到容器对象上，可用来向容器中插入元素。
• 流迭代器（stream iterator）：该类型迭代器被绑定到输入或输出流上，可用来遍历所关联的IO流。
• 反向迭代器（reverse iterator）：该类型迭代器向后而不是向前移动。除了forward_list之外的标准库容器都有反向迭代器。
• 移动迭代器（move iterator）：该类型迭代器用来移动容器元素。

插入迭代器

​ 插入器是一种迭代器适配器，它接受一个容器参数，生成一个插入迭代器。通过插入迭代器赋值时，该迭代器调用容器操作向给定容器的指定位置插入一个元素。

​ 插入器有三种类型，区别在于元素插入的位置：

• back_inserter：创建一个调用push_back操作的迭代器。
• front_inserter：创建一个调用push_front操作的迭代器。
• inserter：创建一个调用insert操作的迭代器。此函数接受第二个参数，该参数必须是一个指向给定容器的迭代器，元素会被插入到该参数指向的元素之前。

​ 只有在容器支持push_front的情况下,我们才可以使用front_insertero类似的，只有在容器支持 push_back的情况下，我们才能使用back_inserter。

list<int> lst = { 1,2,3,4 };
list<int> lst2, lst3;   // 空lists
// 拷贝完成之后，lst2 包含 4 3 2 1
copy(lst.cbegin(), lst.cend(), front_inserter(lst2));
// 拷贝完成之后，lst2 包含 1 2 3 4
copy(lst.cbegin(), lst.cend(), inserter(lst3, lst3.begin()));

iostream迭代器

​ istream_iterator从输入流读取数据，ostream_iterator向输出流写入数据。这些迭代器将流当作特定类型的元素序列处理。

istream_iterator操作

​ 当创建流迭代器时，必须指定迭代器读写的对象类型。istream_iterator使用>>来读取流，因此istream_iterator要读取的类型必须定义了>>运算符。创建istream_iterator时，可以将其绑定到一个流。如果默认初始化，则创建的是尾后迭代器。

istream_iterator<int> int_it(cin);  // 从cin读取int
istream_iterator<int> int_eof;      // 尾后迭代器
ifstream in("afile");
istream_iterator<string> str_it(in);   // 从"afile"读取字符串

​ 对于一个绑定到流的迭代器，一旦其关联的流遇到文件尾或IO错误，迭代器的值就与尾后迭代器相等。下面是一个用istream_iterator从标准输入读取数据，存入一个vector的例子：

istream iterator<int> in iter(cin);// 从 cin 读取 int
istream iterator<int> eof;// istream 尾后选代器
while (in iter != eof)// 当有数据可供读取时
// 后置递增运算读取流，返回迭代器的旧值
//解引用选代器，获得从流读取的前一个值
vec.push back(*in iter++);

​ 可以直接使用流迭代器构造容器。

istream_iterator<int> in_iter(cin), eof;    // 从cin读取int
vector<int> vec(in_iter, eof);      // 从迭代器范围构造vec

​ 将istream_iterator绑定到一个流时，标准库并不保证迭代器立即从流读取数据。但可以保证在第一次解引用迭代器之前，从流中读取数据的操作已经完成了。

使用算法操作流迭代器

​ 用一对istream_iterator来调用accumulate:

istream iterator<int> in(cin), eof;
cout << accumulate(in, eof,0) << endl;

istream_iterator 允许使用懒惰求值

​ 当我们将一个istream iterator 绑定到一个流时，标准库并不保证选代器立即从流读取数据。具体实现可以推迟从流中读取数据，直到我们使用迭代器时才真正读取。

ostream_iterator 操作

​ 定义ostream_iterator对象时，必须将其绑定到一个指定的流。不允许定义空的或者表示尾后位置的ostream_iterator。

​ *和++运算符实际上不会对ostream_iterator对象做任何操作。但是建议代码写法与其他迭代器保持一致。

ostream_iterator<int> out_iter(cout, " ");
for (auto e : vec)
    *out_iter++ = e;    // 赋值语句将元素写道cout
cout << endl;

​ 可以为任何定义了<<运算符的类型创建istream_iterator对象，为定义了>>运算符的类型创建ostream_iterator对象。

反向迭代器

​ 显示一个名为vec的假设的vector上的4钟迭代器：

​ 递增反向迭代器会移动到前一个元素，递减会移动到后一个元素。

sort(vec.begin(), vec.end());   // 按"正常序"排序vec
// 按逆序排列：将最小元素放在vec末尾
sort(vec.rbegin(), vec.rend());

反向迭代器需要递减运算符

​ 我们只能从既支持++也支持--的迭代器来定义反向迭代器。流迭代器不支持递减运算，因为不可能在一个流中反向移动。因此，不能从forward_list或流迭代器创建反向迭代器。

反向迭代器和其他迭代器间的关系

​ 调用反向迭代器的base函数可以获得其对应的普通迭代器。

// 在一个逗号分隔的列表中查找最后一个元素
auto rcomma = find(line.crbegin(), line.crend(), ',');
// 错误:将逆序输出单词的字符
cout << string(line.crbegin(), rcomma) << endl;
// 正确:得到一个正向迭代器，从逐号开始读取字符直到 line 末尾
cout << string(rcomma.base(), line.cend()) << endl;

​ 反向迭代器的目的是表示元素范围，而这些范围是不对称的。用普通迭代器初始化反向迭代器，或者给反向迭代器赋值时，结果迭代器与原迭代器指向的并不是相同元素。

10.5 范式算法

​ 算法所要求的迭代器操作可以分为5个选代器类别 (iterator category)，每个算法都会对它的每个选代器参数指明须提供哪类迭代器：

迭代器类型	功能
输入迭代器	只读，不写；单遍扫描，只能递增
输出迭代器	只写，不读；单遍扫描，只能递增
前向迭代器	可读写；多遍扫描，只能递增
双向迭代器	可读写；多遍扫描，可递增递减
随机访问迭代器	可读写；多遍扫描，支持全部迭代器运算

五类迭代器

​ C++标准指定了泛型和数值算法的每个迭代器参数的最小类别。对于迭代器实参来说，其能力必须大于或等于规定的最小类别。向算法传递更低级的迭代器参数会产生错误（大部分编译器不会提示错误）。

迭代器类别：

• 输入迭代器（input iterator）：可以读取序列中的元素，只能用于单遍扫描算法。必须支持以下操作：

  • 用于比较两个迭代器相等性的相等==和不等运算符!=。
  • 用于推进迭代器位置的前置和后置递增运算符++。
  • 用于读取元素的解引用运算符*；解引用只能出现在赋值运算符右侧。
  • 用于读取元素的箭头运算符->。

• 输出迭代器（output iterator）：可以读写序列中的元素，只能用于单遍扫描算法，通常指向目的位置。必须支持以下操作：

  • 用于推进迭代器位置的前置和后置递增运算符++。
  • 用于读取元素的解引用运算符*；解引用只能出现在赋值运算符左侧（向已经解引用的输出迭代器赋值，等价于将值写入其指向的元素）。

• 前向迭代器（forward iterator）：可以读写序列中的元素。只能在序列中沿一个方向移动。支持所有输入和输出迭代器的操作，而且可以多次读写同一个元素。因此可以使用前向迭代器对序列进行多遍扫描。

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

• 随机访问迭代器（random-access iterator）：可以在常量时间内访问序列中的任何元素。除了支持所有双向迭代器的操作之外，还必须支持以下操作：

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

算法形参模式

​ 大多数算法的形参模式是以下四种形式之一：

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

​ 其中alg是算法名称，beg和end表示算法所操作的输入范围。几乎所有算法都接受一个输入范围，是否有其他参数依赖于算法操作。dest表示输出范围，beg2和end2表示第二个输入范围。

接受单个目标迭代器的算法

​ dest 参数是一个表示算法可以写入的目的位置的选代器。算法假定:按其需要写入数据，不管写入多少个元素都是安全的。

​ 向输出迭代器写入数据的算法都假定目标空间足够容纳要写入的数据。

接受第二个输入序列的算法

​ 接受单独一个迭代器参数表示第二个输入范围的算法都假定从迭代器参数开始的序列至少与第一个输入范围一样大。

算法命名规范

​ 除了参数规范，算法还遵循一套命名和重载规范。这些规范处理诸如:如何提供一个操作代替默认的<或==运算符以及算法是将输出数据写入输入序列还是一个分离的目的位置等问题。

一些算法使用重载形式传递一个谓词

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

unique(beg，end);//使用 == 运算符比较元素
unique(beg，end，comp); // 使用comp 比较元素

_if版本的算法

​ 接受谓词参数的算法都有附加的_if后缀。

find(beg, end, val);       // 查找输入范围中 val 第一次出现的位置
find_if(beg, end, pred);   // 查找第一个令 pred 为真的元素

区分拷贝元素的版本和不拷贝的版本

​ 将执行结果写入额外目的空间的算法都有_copy后缀。

reverse(beg, end);              // 反转输入范围中元素的顺序
reverse_copy(beg, end, dest);   // 将元素按逆序拷贝到 dest

​ 一些算法同时提供_copy和_if版本。

//从v1中删除奇数元素
remove if(vl.begin()，vl.end(),
				[](int i) ( return i%2;));
// 将偶数元素从 v1拷贝到 v2;v1不变
remove _copy_if(vl.begin()，vl.end()，back inserter(v2),
					[](int i) [ return i2;});

10.6 特定容器算法

​ 对于list和forward_list类型，应该优先使用成员函数版本的算法，而非通用算法。

​ 链表特有版本的算法操作会改变底层容器。

第十一章 关联容器

​ 关联容器和顺序容器有着根本的不同:关联容器中的元素是按关键字来保存和访问的。与之相对，顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的。

​ 关联容器支持高效的关键字查找和访问操作。2个主要的关联容器（associative-container）类型是map和set。

• map中的元素是一些键值对（key-value）：关键字起索引作用，值表示与索引相关联的数据。
• set中每个元素只包含一个关键字，支持高效的关键字查询操作：检查一个给定关键字是否在set中。

标准库提供了8个关联容器，它们之间的不同体现在三个方面：

• 是map还是set类型。
• 是否允许保存重复的关键字。
• 是否按顺序保存元素。

​ 允许重复保存关键字的容器名字都包含单词multi；无序保存元素的容器名字都以单词unordered开头。

• 有序容器：

  类型	特性
  map	保存键值对的关联数组
  set	只保存关键字的容器
  multimap	关键字可重复出现的map
  multiset	关键字可重复出现的set

• 无序容器：

  类型	特性
  unordered_map	用哈希函数管理的map
  unordered_set	用哈希函数管理的set
  unordered_multimap	关键字可重复出现的unordered_map
  unordered_multiset	关键字可重复出现的unordered_set

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

11.1 使用关联容器

​ map类型通常被称为关联数组（associative array）。关联数组与“正常”数组类似，不同之处在于其下标不必是整数。

使用map

​ 从map中提取一个元素时，会得到一个pair类型的对象。pair是一个模板类型，保存两个名为first和second的公有数据成员。map所使用的pair用first成员保存关键字，用second成员保存对应的值。

// 统计每个单词再输入中出现的次数
map<string, size_t> word_count;     // string到size_t的空map
string word;
while (cin >> word)
    ++word_count[word];     // 提取 word 的计数器并将其加 1
for (const auto &w : word_count)    // 对map中的每个元素
    // 打印结果
    cout << w.first << " occurs " << w.second
        << ((w.second > 1) ? " times" : " time") << endl;

使用set

​ 上个示例程序的一个合理扩展是:忽略常见单词，如"the"、"and""or"等。我们可以使用 set 保存想忽略的单词，只对不在集合中的单词统计出现次数:

// 统计每个单词再输入中出现的次数
map<string, size_t> word_count;     // string到size_t的空map
set<string> exclude = {"The","But","And","Or","An","the","but","and","or","an","a"};

string word;
while (cin >> word)
    // 只统计不在 exclude 中的单词
    if(exclude.find(word) == exclude.end())
    	++word_count[word];     // 获取并递增 word的计数器
for (const auto &w : word_count)    // 对map中的每个元素
    // 打印结果
    cout << w.first << " occurs " << w.second
        << ((w.second > 1) ? " times" : " time") << endl;

​ set类型的find成员返回一个迭代器。如果给定关键字在set中，则迭代器指向该关键字，否则返回的是尾后迭代器。

11.2 关联容器概述

​ 关联容器都支持9.2节中介绍的普通容器的操作。关联容器不支持顺序容器的位置相关的操作。关联容器中的元素是根据关键字存储的，这些操作对关联容器没有意义。而且，关联容器也不支持构造函数或插入操作这些接受一个元素和一个数量值的操作。

​ 处理与顺序容器相同的操作外，关联容器还支持一些顺序容器不支持的操作和类型别名，此外无序容器还提供一些用来调整哈希性能的操作。

​ 关联容器的迭代器都是双向的。

定义关联容器

​ 定义map时，必须指定关键字类型和值类型；定义set时，只需指定关键字类型。

​ 初始化map时，提供的每个键值对用花括号{}包围。

map<string, size_t> word_count;   // 空容器
// 列表初始化
set<string> exclude = { "the", "but", "and" };
// 三个元素；authors将姓映射为名
map<string, string> authors =
{
    {"Joyce", "James"},
    {"Austen", "Jane"},
    {"Dickens", "Charles"}
};

​ 与以往一样，初始化器必须能转换为容器中元素的类型。对于 set，元素类型就是关键字类型。 ​ 当初始化一个 map 时，必须提供关键字类型和值类型。我们将每个关键字-值对包围在花括号中:

​ {key，value}

​ 来指出它们一起构成了 map 中的一个元素。在每个花括号中，关键字是第一个元素，值是第二个。因此，authors 将姓映射到名，初始化后它包含三个元素。

**初始化multimap或multiset **

map和set中的关键字必须唯一，multimap和multiset没有此限制。

// 定义一个有20个元素的 vector，保存0到9每个整数的两个拷贝
vector<int> ivec;
for(vector<int>::size type i =0;i != 10;++i) {
    ivec.push back(i);
    ivec.push back(i);// 每个数重复保存一次
}
// iset包含来自 ivec 的不重复的元素:miset 包含所有 20 个元素
set<int> iset(ivec.cbegin(),ivec.cend());
multiset<int> miset(ivec.cbegin(), ivec.cend());
cout << ivec.size() << endl;// 打印出20
cout << iset.size() << endl;// 打印出10
cout << miset.size() << endl;// 打印出20

关联字类型的要求

​ 对于有序容器——map、multimap、set和multiset，关键字类型必须定义元素比较的方法。默认情况下，标准库使用关键字类型的<运算符来进行比较操作。

​ 传递给排序算法的可调用对象必须满足与关联容器中关键字一样的类型要求。

有序容器的关键词类型

​ 可以向一个算法提供我们自己定义的比较操作，与此类似，也可以提供自己定义的操作来代替关键词上的<运算符。所提供的操作必须再关键词类型上定义一个严格弱序。可以将严格弱序看作是”小于等于“。无论我们怎么定义比较函数，它必须具备如下基本性质：

• 两个关键字不能同时“小于等于”对方;如果 k1“小于等于”k2，那么 k2 绝不能“小于等于”k1。
• 如果 k1“小于等于”k2，且 k2“小于等于”k3，那么 k1 必须“小于等于”k3。
• 如果存在两个关键字，任何一个都不“小于等于”另一个，那么我们称这两个关键字是“等价”的。如果 k1“等价于”k2，且 k2“等价于”k3，那么 k1 必须“等价于”k3。

使用关键字类型的比较函数

​ 用来组织容器元素的操作的类型也是该容器类型的一部分。如果需要使用自定义的比较操作，则必须在定义关联容器类型时提供此操作的类型。操作类型在尖括号中紧跟着元素类型给出。

bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs)
{
    return lhs.isbn() < rhs.isbn();
}

// bookstore中多条记录可以有相同的 ISBN
// bookstore 中的元素以 ISBN 的顺序进行排列
multiset<Sales_data, decltype(compareIsbn)*> bookstore(compareIsbn);

pair类型

​ pair定义在头文件utility中。一个pair可以保存两个数据成员，分别命名为first和second。

pair<string, string> anon;        // 保存两个string
pair<string, size_t> word_count;  // 保存一个string和一个size_t
pair<string, vector<int>> line;   // 保存string和vector<int>

​ pair的默认构造函数对数据成员进行值初始化。也可以为每个成员提供初始化器：

// 这条语句创建一个名为 author 的 pair，两个成员被初始化为"James"和"Joyce"
pair<string,string> author{"James","Joyce"};

创建pair对象的函数

​ 在C++11中，如果函数需要返回pair，可以对返回值进行列表初始化。早期C++版本中必须显式构造返回值。

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

11.3 关联容器操作

​ 关联容器定义了类型别名来表示容器关键字和值的类型。

类型	含义
key_type	容器的关键字类型
mapped_type	map的值类型
value_type	对于set，与key_type相同 对于map，为pair<const key_type, mapped_type>

​ 对于set类型，key_type和value_type是一样的。set中保存的值就是关键字。对于map类型，元素是键值对。即每个元素是一个pair对象，包含一个关键字和一个关联的值。由于元素关键字不能改变，因此pair的关键字部分是const的。另外，只有map类型（unordered_map、unordered_multimap、multimap、map）才定义了mapped_type。

set<string>::value_type v1;        // v1 是一个string
set<string>::key_type v2;          // v2 是一个string
map<string, int>::value_type v3;   // v3 是一个<const string, int>
map<string, int>::key_type v4;     // v4 是一个string
map<string, int>::mapped_type v5;  // v5 是一个int

关联容器迭代器

​ 解引用关联容器迭代器时，会得到一个类型为容器的value_type的引用。对map而言，value_type是pair类型，其first成员保存const的关键字，second成员保存值。

// 获得指向 word_count 中一个元素的选代器
auto map_it = word_count.begin();
// *map_it 是指向一个pair<const string，size_t>对象的引用
cout << map_it->first;          // 打印此元素的关键字
cout << " " << map_it->second;  // 打印此元素的值
map_it->first = "new key";      // 错误:关键字是 const 的
++map_it->second;               // 正确：我们可以通过迭代器改变元素

​ 必须记住，一个map的value type是一个pair，我们可以改变 pair的值，但不能改变关键字成员的值。

set的迭代器是const的

虽然set同时定义了iterator和const_iterator类型，但两种迭代器都只允许只读访问set中的元素。类似map，set中的关键字也是const的。

set<int> iset = {0,1,2,3,4,5,6,7,8,9};
set<int>::iterator set_it = iset.begin();
if (set_it != iset.end())
{
    *set_it = 42;       // 错误：set中的关键字是只读的
    cout << *set_it << endl;    // 正确：可以读关键字
}

遍历关联容器

​ map和set都支持begin和end操作。使用迭代器遍历map、multimap、set或multiset时，迭代器按关键字升序遍历元素。

// 获得一个指向首元素的迭代器
auto map_it = word_count.cbegin();
// 比较当前迭代器和尾后迭代器
while (map it != word_count.cend()) {
    // 解引用迭代器，打印关键字-值对
    cout << map_it->first << " occurs "
    	 << map_it->second <<" times" << endl;
    ++map_it;//递增选代器，移动到下一个元素
}

关联容器和算法

​ 通常不对关联容器使用泛型算法，主要是由于const的特性使然。set中的元素是const的，map中的元素是pair，其中第一个元素是const的。

添加元素

​ 使用insert成员可以向关联容器中添加元素。向map和set中添加已存在的元素对容器没有影响。

vector<int> ivec={2,4,6,8,2,4,6,8);			// ivec有8个元素
set<int> set2;					 	       // 空集合
set2.insert(ivec.cbegin()， ivec.cend());	// set2有4个元素
set2.insert((1,3,5,7,1,3,5,7));				//set2 现在有 8个元素

​ insert 有两个版本，分别接受一对迭代器，或是一个初始化器列表

向map添加元素

​ 通常情况下，对于想要添加到map中的数据，并没有现成的pair对象。可以直接在insert的参数列表中创建pair。

// 向word_count插入word的4种方法
word_count.insert({word, 1});
word_count.insert(make_pair(word, 1));
word_count.insert(pair<string, size_t>(word, 1));
word_count.insert(map<string, size_t>::value_type(word, 1));

检测insert的返回值

​ insert或emplace的返回值依赖于容器类型和参数：

• 对于不包含重复关键字的容器，添加单一元素的insert和emplace版本返回一个pair，表示操作是否成功。pair的first成员是一个迭代器，指向具有给定关键字的元素；second成员是一个bool值。如果关键字已在容器中，则insert直接返回，bool值为false。如果关键字不存在，元素会被添加至容器中，bool值为true。
• 对于允许包含重复关键字的容器，添加单一元素的insert和emplace版本返回指向新元素的迭代器。

展开递增语句

++((ret.first)->second); // 等价的表达

// 展开讲解
ret //保存 insert 返回的值，是一个 pair。
ret.first //是 pair 的第一个成员，是一个map 选代器，指向具有给定关键字的元素。
ret.first-> //解引用此迭代器，提取 map 中的元素，元素也是一个 pair。
ret.first->second //map 中元素的值部分。
++ret.first->second //递增此值。

向multiset或multimap添加元素

multimap<string， string> authors;
// 插入第一个元素，关键字为 Barth， John
authors.insert({"Barth, John","Sot-Weed Factor"));
// 正确:添加第二个元素，关键字也是 Barth， John
authors.insert({"Barth, John","Lost in the Funhouse"));

删除元素

​ 与顺序容器不同，关联容器提供了一个额外的erase操作。它接受一个key_type参数，删除所有匹配给定关键字的元素（如果存在），返回实际删除的元素数量。对于不包含重复关键字的容器，erase的返回值总是1或0。若返回值为0，则表示想要删除的元素并不在容器中。

// 删除一个关键字，返回删除的元素数量
if (word count.erase(removal word))
	cout <<"ok: " << removal word << " removed\n";
else cout <<"oops:" << removal word << " not found!\n";

​ 对允许重复关键词的容器，删除元素的数量可能大于1

auto cnt = authors.erase("Barth,John");

map的下标操作

操作	含义
c[k]	返回关键字为k的元素；若k不存在，则向c中添加并进行值初始化
c.at(k)	返回关键字为k的元素；若k不存在，则抛出out_of_range异常

map <string，size t> word count;// empty map
// 插入一个关键字为 Anna 的元素，关联值进行值初始化;然后将 1赋予它
word count["Anna"] = 1;

使用下标操作的返回值

​ map下标运算符接受一个关键字，获取与此关键字相关联的值。如果关键字不在容器中，下标运算符会向容器中添加该关键字，并值初始化关联值。

​ 由于下标运算符可能向容器中添加元素，所以只能对非const的map使用下标操作。

​ 对map进行下标操作时，返回的是mapped_type类型的对象；解引用map迭代器时，返回的是value_type类型的对象。

cout << word count["Anna"];// 用Anna作为下标提取元素:会打印出1
++word count["Anna"];// 提取元素，将其增 1
cout << word count["Anna"];// 提取元素并打印它;会打印出 2

访问元素

操作	含义
c.find(k)	返回指向第一个关键字为k的元素的迭代器或尾后迭代器
c.count(k)	返回关键字为k的元素的数量
c.lower_bound(k)	返回指向第一个关键字不小于k的元素的迭代器
c.upper_bound(k)	返回指向第一个关键字大于k的元素的迭代器
c.equal_range(k)	返回一个迭代器pair，表示关键字为k的元素范围

对map使用find代替下标操作

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

if (word count.find("foobar") == word_count.end())
cout<< "foobar is not in the map"<< endl;

在multimap或multiset中查找元素

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

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;   // 记录已经打印了多少本书
}

​ 当我们遍历一个multimap或multiset 时，保证可以得到序列中所有具有给定关键字的元素。

一种不同的，面向迭代器的解决方法

​ lower_bound和upper_bound操作都接受一个关键字，返回一个迭代器。如果关键字在容器中，lower_bound返回的迭代器会指向第一个匹配给定关键字的元素，而upper_bound返回的迭代器则指向最后一个匹配元素之后的位置。如果关键字不在multimap中，则lower_bound和upper_bound会返回相等的迭代器，指向一个不影响排序的关键字插入位置。因此用相同的关键字调用lower_bound和upper_bound会得到一个迭代器范围，表示所有具有该关键字的元素范围。

// authors和search_item 的定义，与前面的程序一样
// beg和end 表示对应此作者的元素的范围
for (auto beg = authors.lower_bound(search_item),
        end = authors.upper_bound(search_item);
    beg != end; ++beg)
    cout << beg->second << endl;    // 打印每个题目

​ lower_bound和upper_bound有可能返回尾后迭代器。如果查找的元素具有容器中最大的关键字，则upper_bound返回尾后迭代器。如果关键字不存在，且大于容器中任何关键字，则lower_bound也返回尾后迭代器。

equal_range函数

​ equal_range操作接受一个关键字，返回一个迭代器pair。若关键字存在，则第一个迭代器指向第一个匹配关键字的元素，第二个迭代器指向最后一个匹配元素之后的位置。若关键字不存在，则两个迭代器都指向一个不影响排序的关键字插入位置。

// authors和search_item 的定义，与前面的程序一样
// pos 保存选代器对，表示与关键字匹配的元素范围
for (auto pos = authors.equal_range(search_item);
        pos.first != pos.second; ++pos.first)
    cout << pos.first->second << endl;  // 打印每个题目

11.4 无序容器

​ 新标准库定义了4个无序关联容器，这些容器使用哈希函数和关键字类型的==运算符组织元素。

​ 如果关键字类型固有就是无序的，或者性能测试发现问题可以用哈希技术解决，就可以使用无序容器。

使用无序容器

​ 无序容器和对应的有序容器通常可以相互替换。但是由于元素未按顺序存储，使用无序容器的程序输出一般会与有序容器的版本不同。

// 统计出现次数，但单词不会按宇典序排列
unordered map<string,size t> word count;
string word;
while (cin >> word)
	++word_count[word];// 提取并递增 word 的计数器

for(const auto &w :word_count) //对map 中的每个元素
// 打印结果
cout << w.first << " occurs " << w.second
		<< ((w.second>1) ?" times":"time") << endl;

​ 对于每个单词，我们将得到相同的计数结果。但单词不太可能按字典序输出。

管理桶

​ 无序容器在存储上组织为一组桶，每个桶保存零或多个元素。无序容器使用一个哈希函数将元素映射到桶。为了访问一个元素，容器首先计算元素的哈希值，它指出应该搜索哪个桶。容器将具有一个特定哈希值的所有元素都保存在相同的桶中。因此无序容器的性能依赖于哈希函数的质量和桶的数量及大小。

无序容器管理操作
桶接口
c.bucket_count()	正在使用的桶的数目
c.max_bucket_count ()	容器能容纳的最多的桶的数量
c.bucket_size(n)	第 n个桶中有多少个元素
c.bucket(k)	关键字为 k 的元素在哪个桶中
桶迭代
local_iterator	可以用来访问桶中元素的迭代器类型
const_local_iterator	桶迭代器的 const 版本
c.begin(n)，c.end(n)	桶n的首元素选代器和尾后选代器
c.cbegin(n)，c.cend(n)	与前两个函数类似，但返回 const_local_iterator
哈希策略
c.load_factor()	每个桶的平均元素数量，返回 float 值
c.max_load_factor()	c试图维护的平均桶大小，返回 float 值。c 会在需要时添加新的桶，以使得 load_factor<=max_load_factor
c.rehash(n)	重组存储，使得 bucket_count>=n且bucket_count>size/max_load_factor
c.reserve(n)	重组存储，使得c可以保存n 个元素且不必 rehash

无序容器对关键字类型的要求

​ 默认情况下，无序容器使用关键字类型的==运算符比较元素，还使用一个hash<key_type>类型的对象来生成每个元素的哈希值。标准库为内置类型和一些标准库类型提供了hash模板。因此可以直接定义关键字是这些类型的无序容器，而不能直接定义关键字类型为自定义类类型的无序容器，必须先提供对应的hash模板版本。

// 定义重载函数
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();
}

// 我们使用这些函数来定义一个 unordered_multiset
using SD_multiset = unordered multiset<Sales data,
					decltype(hasher)*，decltype(egOp)*>;
// 参数是桶大小、哈希函数指针和相等性判断运算符指针
SD_multiset bookstore(42，hasher， egOp);

// 如果我们的类定义了==运算符，则可以只重载哈希函数:
// 使用 EooHash 生成哈希值;Eoo 必须有==运算符
unordered set<Foo， decltype(FooHash)*> fooSet(10，FooHash);

第十二章 动态内存

​ 程序用堆来存储动态分配的对象。动态对象的生存期由程序控制。

12.1 动态内存与智能指针

​ C++中的动态内存管理通过一对运算符完成：new在动态内存中为对象分配空间并返回指向该对象的指针，可以选择对对象进行初始化；delete接受一个动态对象的指针，销毁该对象并释放与之关联的内存。

​ 新标准库提供了两种智能指针类型来管理动态对象。智能指针的行为类似常规指针，但它自动释放所指向的对象。这两种智能指针的区别在于管理底层指针的方式：shared_ptr允许多个指针指向同一个对象；unique_ptr独占所指向的对象。标准库还定义了一个名为weak_ptr的伴随类，它是一种弱引用，指向shared_ptr所管理的对象。这三种类型都定义在头文件memory中。

shared_ptr类

​ 智能指针是模板，创建时需要指明指针可以指向的类型。默认初始化的智能指针中保存着一个空指针。

shared_ptr<string> p1;      // shared_ptr，可以指向string
shared_ptr<list<int>> p2;   // shared_ptr，可以指向int的list

​ 智能指针的使用方式与普通指针类似。解引用一个智能指针返回它指向的对象。如果在一个条件判断中使用智能指针，效果就是检测它是否为空:

// 如果p1不为空，检查它是否指向一个空 string
if(pl && p1->empty())
	*pl ="hi";// 如果pl指向一个空string，解引用pl，将一个新值赋予 string

shared_ptr和unique_ptr都支持的操作：

操作	含义
shared_ptr<T> sp unique_ptr<T> up	默认初始化为空指针
p	若p指向一个对象，则为true
*p	解引用p
p->mem	等价于(*p).mem
p.get()	返回p中的指针

shared_ptr独有的操作：

操作	含义
p.use_count()	返回p的引用计数
p.unique()	若p.use_count() == 1，则返回true

make_shared函数

​ make_shared函数（定义在头文件memory中）在动态内存中分配一个对象并初始化它，返回指向此对象的shared_ptr。

// 指向一个值为42的int的 shared ptr
shared_ptr<int> p3 = make_shared<int>(42);
// p4 指向一个值为”9999999999"的 string
shared_ptr<string> p4 = make_shared<string>(10, '9');
// p5指向一个值初始化的int，即，值为0
shared_ptr<int> p5 = make_shared<int>();

​ 通常用auto定义一个对象来保存make_shared的结果，这种方式较为简单。

// p6 指向一个动态分配的空 vector<string>
auto p6 =make_shared<vector<string>>();

shared_ptr的拷贝和赋值

​ 进行拷贝或赋值操作时，每个shared_ptr会记录有多少个其他shared_ptr与其指向相同的对象。

auto p = make_shared<int>(42);  // p指向的对象只有p一个引用者
auto q(p);  // p和q指向相同对象，此对象有两个引用者

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

auto r = make_shared<int>(42);  // r指向的int 只有一个引用者
r = q;  // 给r赋值，令它指向另一个地址
        // 递增q 指向的对象的引用计数
        // 递减r原来指向的对象的引用计数
        // r 原来指向的对象已没有引用者，会自动释放

​ 到底是用一个计数器还是其他数据结构来记录有多少指针共享对象，完全由标准库的具体实现来决定。关键是智能指针类能记录有多少个 shared_ptr 指向相同的对象，并能在恰当的时候自动释放对象

shared_ptr销毁对象

​ shared_ptr自动销毁所管理的对象，还会自动释放相关联的内存。通过shared_ptr的析构函数来完成。

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

使用了动态生存期的资源的类

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

• 不确定需要使用多少对象。

• 不确定所需对象的准确类型。

• 需要在多个对象间共享数据。

使用动态内存的一个常见原因是允许多个对象共享相同的状态

直接管理内存

​ 相对于智能指针，使用new和delete管理内存很容易出错。

使用new 动态分配和初始化对象

​ 默认情况下，动态分配的对象是默认初始化的。所以内置类型或组合类型的对象的值将是未定义的，而类类型对象将用默认构造函数进行初始化。

string *ps = new string;    // 初始化为空string
int *pi = new int;     // pi指向一个未初始化的int

​ 可以使用值初始化方式、直接初始化方式、传统构造方式（圆括号()）或新标准下的列表初始化方式（花括号{}）初始化动态分配的对象。

int *pi = new int(1024);            // pi指向的对象的值为 1024
string *ps = new string(10, '9');   // *ps为”9999999999"
// vector有10个元素，值依次从0到9
vector<int> *pv = new vector<int>{0,1,2,3,4,5,6,7,8,9};
string *ps1 = new string;     // 默认初始化为空 string
string *ps = new string();    // 值初始化为空 string
int *pi1 = new int;      // 默认初始化;*pi1的值未定义
int *pi2 =new int();     //值初始化为0;*pi2为0

​ 只有当初始化的括号中仅有单一初始化器时才可以使用auto。

auto p1 = new auto(obj);    // p指向一个与 obj类型相同的对象
                            // 该对象用obj进行初始化
auto p2 = new auto{a,b,c};  // 错误:括号中只能有单个初始化器		

动态分配的 const 对象

​ 可以用new分配const对象，返回指向const类型的指针。动态分配的const对象必须初始化。

// 分配并初始化一个 const int
const int *pci = new const int(1024);
// 分配并跌认初始化一个 const 的空 string
const string *pcs = new const string;

内存耗尽

​ 默认情况下，如果new不能分配所要求的内存空间，会抛出bad_alloc异常。使用定位new（placement new）可以阻止其抛出异常。定位new表达式允许程序向new传递额外参数。如果将nothrow传递给new，则new在分配失败后会返回空指针。bad_alloc和nothrow都定义在头文件new中。

// 如果分配失败，new 返回一个空指针
int *p1 = new int;            // 如果分配失败，new抛出 std::bad_alloc
int *p2 = new (nothrow) int;  // 如果分配失败，new 返回一个空指针

释放动态内存

​ 我们通过delete表达式来将动态内存归还给系统。delete表达式接受一个指针，指向我们想要释放的对象：

delete p;// p 必须指向一个动态分配的对象或是一个空指针

​ 与new类型类似，delete 表达式也执行两个动作:销毁给定的指针指向的对象:释放对应的内存。

指针值和delete

​ 我们传递给 delete 的指针必须指向动态分配的内存，或者是一个空指针。释放一块并非 new 分配的内存，或者将相同的指针值释放多次，其行为是未定义的。虽然一个const 对象的值不能被改变，但它本身是可以被销毁的。如同任何其他动态对象一样，想要释放一个 const 动态对象，只要 delete 指向它的指针即可:

int i，*pil = &i，*pi2 = nullptr;
double *pd= new double(33)，*pd2=pd;
delete i;// 错误:不是一个指针
delete pil; // 未定义:pil指向一个局部变量
delete pd;// 正确
delete pd2; //未定义:pd2 指向的内存已经被释放了
delete pi2;// 正确:释放一个空指针总是没有错误的

const int *pci = new const int(1024);
delete pci;//正确:释放一个 const 对象

动态对象的生存期直到被释放时为止

​ 由内置指针(而不是智能指针)管理的动态内存在被显式释放前一直都会存在

使用 new和delete管理动态内存存在三个常见问题:

1. 忘记 delete 内存。忘记释放动态内存会导致人们常说的“内存泄漏”问题，因为这种内存永远不可能被归还给自由空间了。查找内存泄露错误是非常困难的，因为通常应用程序运行很长时间后，真正耗尽内存时，才能检测到这种错误。
2. 使用已经释放掉的对象。通过在释放内存后将指针置为空，有时可以检测出这种错误。
3. 同一块内存释放两次。当有两个指针指向相同的动态分配对象时，可能发生这种错误。如果对其中一个指针进行了delete 操作,对象的内存就被归还给自由空间了如果我们随后又 delete 第二个指针，自由空间就可能被破坏。

​ 坚持只使用智能指针，就可以避免所有这些问题。对于一块内存，只有在没有任何智能指针指向它的情况下，智能指针才会自动释放它。

delete 之后重置指针，这只是提供了有限的保护

​ 在delete之后指针变成了空悬指针即，指向一块曾经保存数据对象但现在已经无效的内存的指针。为了防止后续的错误访问，应该在delete之后将指针值置空。

share_ptr和new结合使用

​ 可以用new返回的指针初始化智能指针。该构造函数是explicit的，因此必须使用直接初始化形式。

shared_ptr<int> p1 = new int(1024);    // 错误: 必须使用直接初始化形式
shared_ptr<int> p2(new int(1024));     // 正确:使用了直接初始化形式

​ 默认情况下，用来初始化智能指针的内置指针必须指向动态内存，因为智能指针默认使用delete释放它所管理的对象。如果要将智能指针绑定到一个指向其他类型资源的指针上，就必须提供自定义操作来代替delete。

不要混合使用内置指针和智能指针

​ 当将shared_ptr绑定到内置指针后，资源管理就应该交由shared_ptr负责。不应该再使用内置指针访问shared_ptr指向的内存。

// 在函数被调用时 ptr 被创建并初始化
void process(shared_ptr<int> ptr)
{
    // 使用 ptr
}   // ptr 离开作用域，被销毁

shared_ptr<int> p(new int(42));   //引用计数为1
process(p);     // 拷贝p会递增它的引用计数;在 process 中引用计数值为 2
int i = *p;     // 正确:引用计数值为 1

int *x(new int(1024));   // 危险:X是一个普通指针，不是一个智能指针
process(x);     // 错误:不能将 int*转换为一个 shared ptr<int>
process(shared_ptr<int>(x));    // 合法的，但内存会被释放!!
int j = *x;     // 未定义的:x是一个空悬指针!

不要使用get初始化另一个智能指针或为智能指针赋值

​ 智能指针的get函数返回一个内置指针，指向智能指针管理的对象。主要用于向不能使用智能指针的代码传递内置指针。使用get返回指针的代码不能delete此指针。

​ 不要使用get初始化另一个智能指针或为智能指针赋值。

shared_ptr<int> p(new int(42));    // 引用计数为 1
int *q = p.get();   // 正确:但使用 q 时要注意，不要让它管理的指针被释放
{   // 新程序块
    // 未定义:两个独立的 shared ptr 指向相同的内存
    shared_ptr<int>(q);
} // 程序块结束，q 被销毁，它指向的内存被释放
int foo = *p;   // 未定义:p指向的内存已经被释放了

​ get 用来将指针的访问权限传递给代码，你只有在确定代码不会 delete 指针的情况下，才能使用 get。特别是，永远不要用 get 初始化另一个智能指针或者为另一个智能指针赋值。

其他shared_ptr 操作

​ 可以用reset函数将新的指针赋予shared_ptr。与赋值类似，reset会更新引用计数，如果需要的话，还会释放内存空间。reset经常与unique一起使用，来控制多个shared_ptr共享的对象。

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

智能指针和异常

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

void f()
{
    shared_ptr<int> sp(new int(42));    // 分配一个新对象
    // 这段代码抛出一个异常，且在 f中未被捕获
} // 在函数结束时 shared ptr 自动释放内存

​ 如果使用内置指针管理内存，且在 new 之后在对应的 delete 之前发生了异常，则内存不会被释放:

void f()
{
    int *ip = new int(42);    // 动态分配一个新对象
    // 这段代码抛出一个异常，且在 f 中未被捕获
    delete ip;     // 在退出之前释放内存
}

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

智能指针和哑类

​ 有些类不具有良好定义的析构函数，如c和c++在使用的网络库：

struct destination;    // 表示我们正在连接什么
struct connection;     // 使用连接所需的信息
connection connect(destination*);   // 打开连接
void disconnect(connection);    // 关闭给定的连接
void f(destination &d /* 其他参数 */)
{
	//获得一个连接;记住使用完后要关闭它
    connection c = connect(&d);
    shared_ptr<connection> p(&c, end_connection);
    // 使用连接
    // 如果我们在 f 退出前忘记调用 disconnect，就无法关闭 C了
}

使用我们自己的释放操作

​ 我们必须首先定义一个函数来代替 delete。这个删除器函数必须能够完成对 shared ptr中保存的指针进行释放的操作。

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

智能指针规范：

• 不使用相同的内置指针值初始化或reset多个智能指针。
• 不释放get返回的指针。
• 不使用get初始化或reset另一个智能指针。
• 使用get返回的指针时，如果最后一个对应的智能指针被销毁，指针就无效了。
• 使用shared_ptr管理并非new分配的资源时，应该传递删除函数。

unique_ptr

​ 与shared_ptr不同，同一时刻只能有一个unique_ptr指向给定的对象。当unique_ptr被销毁时，它指向的对象也会被销毁。

​ make_unique函数（C++14新增，定义在头文件memory中）在动态内存中分配一个对象并初始化它，返回指向此对象的unique_ptr。

unique_ptr<int> p1(new int(42));
// C++14
unique_ptr<int> p2 = make_unique<int>(42);

​ 由于unique_ptr独占其指向的对象，因此unique_ptr不支持普通的拷贝或赋值操作。

unique ptr<string> pl(new string("Stegosaurus"));
unique_ptr<string> p2(p1); // 错误:unique ptr 不支持拷贝
unique ptr<string> p3;
p3=p2;//错误:unique ptr 不支持赋值、

​ release函数返回unique_ptr当前保存的指针并将其置为空。

​ reset函数成员接受一个可选的指针参数，重新设置unique_ptr保存的指针。如果unique_ptr不为空，则它原来指向的对象会被释放。

// 将所有权从p1(指向 string stegosaurus)转移给 p2
unique_ptr<string> p2(p1.release());    // release将p1置为空
unique_ptr<string> p3(new string("Trex"));
// 将所有权从p3 转移给 p2
p2.reset(p3.release()); // reset 释放了p2原来指向的内存

​ 调用release会切断unique_ptr和它原来管理的对象之间的联系。release返回的指针通常被用来初始化另一个智能指针或给智能指针赋值。如果没有用另一个智能指针保存release返回的指针，程序就要负责资源的释放。

p2.release();   // 错误: P2 不会释放内存，而且我们丢失了指针
auto p = p2.release();   // 正确，但我们必须记得 delete(p)

传递unique_ptr 参数和返回unique_ptr

​ 不能拷贝unique_ptr的规则有一个例外：可以拷贝或赋值一个即将被销毁的unique_ptr（移动构造、移动赋值）。

unique_ptr<int> clone(int p)
{
    unique_ptr<int> ret(new int (p));
    // . . .
    return ret;
}

标准库的较早版本包含了一个名为auto_ptr的类，它具有 unique_ptr的部分特性，但不是全部。特别是，我们不能在容器中保存 auto_ptr，也不能从函数中返回auto_ptr。虽然auto_ptr仍是标准库的一部分，但编写程序时应该使用unique_ptro。

向unique_ptr 传递删除器

​ 类似shared_ptr，默认情况下unique_ptr用delete释放其指向的对象。unique_ptr的删除器同样可以重载，但unique_ptr管理删除器的方式与shared_ptr不同。定义unique_ptr时必须在尖括号中提供删除器类型。创建或reset这种unique_ptr类型的对象时，必须提供一个指定类型的可调用对象（删除器）。

// p 指向一个类型为 objT 的对象，并使用一个类型为 delT 的对象释放 objT 对象
// 它会调用一个名为 fcn 的 delT 类型对象
unique_ptr<objT, delT> p (new objT, fcn);

void f(destination &d /* 其他需要的参数 */)
{
    connection c = connect(&d);  // 打开连接
    //当 p被销毁时，连接将会关闭
    unique_ptr<connection, decltype(end_connection)*> p(&c, end_connection);
    // 使用连接
    // 当 f退出时(即使是由于异常而退出)，connection 会被正确关闭
}

weak_ptr

​ weak_ptr是一种不控制所指向对象生存期的智能指针，它指向一个由shared_ptr管理的对象。将weak_ptr绑定到shared_ptr不会改变shared_ptr的引用计数。如果shared_ptr被销毁，即使有weak_ptr指向对象，对象仍然有可能被释放。

操作	含义
weak_ptr<T> w(sp)	w与shared_ptr sp指向相同对象
w.use_count()	返回与w共享对象的shared_ptr的数量·
w.expired()	若w.use_count() == 0，则返回true
w.lock()	若w.expired() == true，则返回空shared_ptr；否则返回一个指向w的对象的shared_ptr

​ 创建一个weak_ptr时，需要使用shared_ptr来初始化它。

auto p = make_shared<int>(42);
weak_ptr<int> wp(p);    // wp 弱共享p;p的引用计数未改变

​ 使用weak_ptr访问对象时，必须先调用lock函数。该函数检查weak_ptr指向的对象是否仍然存在。如果存在，则返回指向共享对象的shared_ptr，否则返回空指针。

if (shared_ptr<int> np = wp.lock())
{
    // 如果 np不为空则条件成立
    //在if中，np与p共享对象
}

12.2 动态数组

​ 使用allocator类可以将内存分配和初始化过程分离，这通常会提供更好的性能和更灵活的内存管理能力。

​ 大多数应用应该使用标准库容器而不是动态分配的数组。使用容器更为简单、更不容易出现内存管理错误并且可能有更好的性能。

new和数组

​ 使用new分配对象数组时需要在类型名之后跟一对方括号，在其中指明要分配的对象数量（必须是整型，但不必是常量）。new返回指向第一个对象的指针（元素类型）。

// 调用get_size确定分配多少个int
int *pia = new int[get_size()];   // pia 指向第一个int

​ 也可以用一个表示数组类型的类型别名来分配一个数组，这样，new 表达式中就不需要方括号了:

typedef int arrT[42];// arrT 表示 42个int 的数组类型
int *p = new arrT;// 分配一个42个int 的数组;p指向第一个nt

分配一个数组会得到一个元素类型的指针

​ 由于new分配的内存并不是数组类型，因此不能对动态数组调用begin和end，也不能用范围for语句处理其中的元素。

​ 要记住我们所说的动态数组并不是数组类型，这是很重要的。

初始化动态分配对象的数组

​ 默认情况下，new分配的对象是默认初始化的。可以对数组中的元素进行值初始化，方法是在大小后面跟一对空括号()。在新标准中，还可以提供一个元素初始化器的花括号列表。如果初始化器数量大于元素数量，则new表达式失败，不会分配任何内存，并抛出bad_array_new_length异常。

int *pia = new int[10];     // 10个未初始化的 int
int *pia2 = new int[10]();    // 10个值初始化为0的int
string *psa = new string[10];    // 10个空string
string *psa2 = new string[10]();    // 10 个空 string
// 10 个 int 分别用列表中对应的初始化器初始化
int *pia3 = new int[10] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
// 10个 string，前 4 个用给定的初始化器初始化，剩余的进行值初始化
string *psa3 = new string[10] { "a", "an", "the", string(3,'x') }; 

​ 虽然可以使用空括号对new分配的数组元素进行值初始化，但不能在括号中指定初始化器。这意味着不能用auto分配数组

动态分配一个空数组是合法的

​ 动态分配一个空数组是合法的，此时new会返回一个合法的非空指针。对于零长度的数组来说，该指针类似尾后指针，不能解引用。

char arr[0];// 错误:不能定义长度为 0的数组
char *cp =new char[0]; // 正确:但cp 不能解引用

释放动态数组

​ 使用delete[]释放动态数组。

delete p;       // p必须指向一个动态分配的对象或为空
delete [] pa;   // pa 必须指向一个动态分配的数组或为空

​ 如果我们在delete一个数组指针时忘记了方括号,或者在 delete一个单一对象的指针时使用了方括号，编译器很可能不会给出警告。我们的程序可能在执行过程中在没有任何警告的情况下行为异常。

智能指针和动态数组

​ unique_ptr可以直接管理动态数组，定义时需要在对象类型后添加一对空方括号[]。

// up 指向一个包含 10 个未初始化int 的数组
unique_ptr<int[]> up(new int[10]);
up.release();   // 自动用 delete[]销毁其指针

​ 当一个unique_ptr指向一个数组时，我们不能使用点和箭头成员运算符。但是我们可以使用下标运算符来访问数组中的元素。

for (size_t i=0; i!=10; ++i)
	up[i] =i;//为每个元素赋予一个新值

​ 与unique_ptr不同，shared_ptr不直接支持动态数组管理。如果想用shared_ptr管理动态数组，必须提供自定义的删除器。

// 为了使用 shared_ptr，必须提供一个删除器
shared_ptr<int> sp(new int[10], [](int *p) { delete[] p; });
sp.reset();    // 使用我们提供的lambda释放数组，它使用delete[]

​ shared_ptr未定义下标运算符，智能指针类型也不支持指针算术运算。因此如果想访问shared_ptr管理的数组元素，必须先用get获取内置指针，再用内置指针进行访问。

// shared_ptr未定义下标运算符，并且不支持指针的算术运算
for (size_t i = 0; i != 10; ++i)
    *(sp.get() + i) = i;    // 使用 get 获取一个内置指针

allocator类

allocator类

​ allocator类是一个模板，定义时必须指定其可以分配的对象类型。

allocator<string> alloc;    // 可以分配 string的allocator 对象
auto const p = alloc.allocate(n);   // 分配n个未初始化的 string

allocator 分配未构造的内存

​ allocator分配的内存是未构造的，程序需要在此内存中构造对象。新标准库的construct函数接受一个指针和零或多个额外参数，在给定位置构造一个元素。额外参数用来初始化构造的对象，必须与对象类型相匹配。

auto q = p;     // q指向最后构造的元素之后的位置
alloc.construct(q++);    // *q 为空字符串
alloc.construct(q++, 10, 'c');  // *q 为 cccccccccc
alloc.construct(q++, "hi");     // *q 为 hi!

​ 直接使用allocator返回的未构造内存是错误行为，其结果是未定义的。

cout << endl;// 正确:使用 string 的输出运算符
cout << endl;// 灾难:q指向未构造的内存!

​ 对象使用完后，必须对每个构造的元素调用destroy进行销毁。destroy函数接受一个指针，对指向的对象执行析构函数。

while (q != p)
    alloc.destroy(--q);  // 释放我们真正构造的 string

​ 我们只能对真正构造了的元素进行 destroy 操作

​ deallocate函数用于释放allocator分配的内存空间。传递给deallocate的指针不能为空，它必须指向由allocator分配的内存。而且传递给deallocate的大小参数必须与调用allocator分配内存时提供的大小参数相一致。

alloc.deallocate(p, n);

拷贝和填充未初始化内存的算法

​ 标准库还为 allocator 类定义了两个伴随算法，可以在未初始化内存中创建对象。它们都定义在头文件memory 中。

allocator算法
uninitialized_copy(b,e,b2)	从迭代器b和e指出的输入范围中拷贝元素到迭代器b2 指定的未构造的原始内存中。b2 指向的内存必须足够大，能容纳输入序列中元素的拷贝
uninitialized_copy_n(b,n,b2)	从迭代器 b 指向的元素开始，拷贝 n 个元素到 b2开始的内存中
uninitialized_fill(b,e,t)	在迭代器 b和 e指定的原始内存范围中创建对象，对象的值均为 t的拷贝
uninitialized_fill_n(b,n,t)	从迭代器 b 指向的内存地址开始创建 n 个对象。b 必须指向足够大的未构造的原始内存，能够容纳给定数量的对象

​ 作为一个例子，假定有一个 int 的 vector，希望将其内容拷贝到动态内存中。我们将分配一块比 vector 中元素所占用空间大一倍的动态内存，然后将原vector 中的元素拷贝到前一半空间，对后一半空间用一个给定值进行填充:

// 分配比 vi 中元素所占用空间大一倍的动态内存
auto p=alloc.allocate(vi.size() *2);
// 通过拷贝 vi 中的元素来构造从 p开始的元素
auto q =uninitialized_copy(vi.begin()，vi.end()， p);
// 将剩余元素初始化为 42
uninitialized_fill_n(q, vi.size()，42);