七. IO库

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

1. IO类

到目前为止，我们使用过的IO类型和对象都是操作char数据的。默认情况下，这些对象都是关联到用户的控制台窗口的。当然，我们有时需要读写命名文件。而且使用IO操作处理string中的字符会很方便。此外应用程序可能读写需要宽字符支持的语言。

IO库类型和头文件
头文件	类型
iostream(定义了用于读写流的基本类型)	istream, wistream从流读取数据 ostream, wostream向流写入数据 iostream, wiostream读写流
fstream(定义了读写命名文件的类型)	ifstream, wifstream从文件读取数据 ofstream, wofstream向文件写入数据 fstream, wfstream读写文件
sstream(定义了读写内存string对象的类型)	istringstream, wistringstream从string读取数据 ostringstream, wostringstream向string写入数据 stringstream, wstringstream读写string

为了支持使用宽字符的语言，标准库定义了一组类型和对象来操纵wchar_t类型的数据。宽字符版本的类型和函数的名字以一个w开始。例如wcin, wcout和wcerr分别对应cin, cout, cerr的宽字符版对象。宽字符版本的类型和对象与其对应的普通char版本的类型定义在同一个头文件。
IO类型间的关系：概念上，设备类型和字符大小都不会影响我们要执行的IO操作。比如，我们可以从>>读取数据，而不用管是从一个控制台窗口，一个磁盘，还是一个string对象读取。类似，我们也不用管读取的字符存入char对象内，还是需要一个wchar_t对象存储
标准库使我们能忽略这些不同类型的流之间的差异，这是通过继承机制实现的。利用模板，我们可以使用具有继承关系的类，而不必了解继承机制如何工作的细节。继承机制使我们可以声明一个特定的类继承自另一个类。可以将一个派生类对象当作其基类对象来使用。
类型ifstream和istringstream都继承自istream。因此，我们可以像使用istream对象一样来使用ifstream对象和istringstream对象。即，我们如何使用cin(istream对象)的，就可以同样的使用这些类型的对象。例如，可以对一个ifstream或istringstream对象调用getline, 也可以使用>>从一个ifstream或istringstream对象读取数据。类似的，类型ofstream, ostringstream都继承ostream。因此，如何使用cout,就可以如何使用这些类型对象
本节剩下部分所介绍的标准库流特性都可以无差别的应用于普通流、文件流、string流，以及char或宽字符流版本。

①IO对象无拷贝或赋值

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;

/**
 * 由于不能拷贝IO对象，因此我们不能将形参或返回类型设置为流类型
 * 进行IO操作的函数通常以引用方式传递和返回流。
 * 读写一个IO对象会改变其状态，因此传递和返回的引用不能是const的
 */
ofstream out1, out2;
out1=out2;//✖，不能对流对象赋值
ofstream print(ofstream);//✖，不能初始化ofstream参数
out2=print(out2);//✖，不能拷贝流对象

②条件状态

IO操作一个与生俱来的问题是可能发生操作。一些错误是可恢复的，而其他操作则发生在系统深处，超出应用程序修复范围。下面列出了IO类定义的一些函数和标志，帮我们访问和操作流的条件状态。

IO库条件状态
strm::iostate	strm是一种IO类型，在IO库类型和头文件列出。iostate是一种机器相关的类型，提供了表达条件状态的完整功能。
strm::badbit	strm::badbit用来指出流已崩溃
strm::failbit	strm::failbit用来指出一个IO操作失败了
strm::eofbit	strm::eofbit用来指出流到达了文件结束
strm::goodbit	strm::goodbit用来指出流未处于错误状态。此值保证为0
s.eof()	若流s的eofbit置位，则返回true
s.fail()	若流s的failbit或badbit置位，则返回true
s.bad()	若流s的badbit置位，则返回true
s.good()	若流s处于有效状态，则返回true
s.clear()	将流s中所有条件状态位复位，将流的状态设置为有效。返回void
s.clear(flags)	根据给定的flags标志位，将流s中对应条件状态位复位。flags的类型为strm::iostate。返回void。
s.setstate(flags)	根据给定的flags标志位，将流s中对应条件状态位置位(表示发生了对应错误)。flags类型同上
s.rdstate()	返回流s的当前条件状态，返回值类型为strm::iostate

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;

int main()
{
    int ival;
    cin>>ival;
    /**
     * 若我们在标准输入上键入Boo, 读操作就会失败。代码中的
     * 输入运算符 期待读取一个int, 但却得到了一个字符B。这样cin
     * 会进入错误状态。类似的，若我们输入文件结束标识，cin也会进入错误状态
     * 
     * 一个流一旦发送错误，其上后续IO操作都会失败。只有当一个流处于无错误
     * 状态时，我们才可以从他读取数据，向他写入数据。由于流可能处于错误状态，因此
     * 代码在使用一个流之前检查它是否处于良好状态。确定一个流对象的状态的最简单
     * 的方法使将它当做一个条件使用
     * 
     * while循环检查>>表达式返回的流的状态。如果输入操作成功，流保持有效状态，
     * 则条件为真
     */
    while (cin>>ival);
}

查询流的状态：将流作为条件使用，只能告诉我们流是否有效，而无法告诉我们发生了什么。有时我们需要知道流为什么失败，以便选择对应的处理方式去处理。
IO库定义了一个与机器无关的iostate类型，它提供了表达流状态的完整功能。这个类型应作为一个位集合来使用。IO库定义了4个iostate类型的constexpr值表示特定的位模式。这些值用来表示特定类型的IO条件，可以与位运算符一起使用来一次性检测或设置多个标志位。
badbit表示系统级错误，如不可恢复的读写错误。通常情况下，一旦badbit被置位，流就无法使用了。在发生可恢复错误后，failbit被置位，如期望读取数值却读出一个字符等错误。这种问题通常是可修正的，流还可以继续使用。如果达到文件结束位置，eofbit和failbit都会被置位。goodbit的值为0, 表示流未发送错误。若baidbit、failbit、eofbit任何一个被置位，则检测流状态的条件失败。
标准库还定义了一组函数来查询这些标志位的状态。操作good在所有错误均未置位的情况下返回true。而bad、fail、eof则在对应错误位被置位时返回true。badbit被置位，fail也会返回true。
管理条件状态：通过流对象的clear()、clear(flags)、setstate(flags)、rdstate()函数。

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;

int main()
{
    auto old_state=cin.rdstate();//记住cin当前状态
    cin.clear();//使cin有效, good()返回true
    process_input(cin);//某处使用cin
    cin.setstate(old_state);//将cin置为原有状态

    /**
     * 下面将failbit和badbit复位，但保持eofbit不变
     * 位运算方式检测
     */
    cin.clear(cin.rdstate() & ~cin.failbit & ~cin.badbit);
}

③管理输出缓冲

每个输出流都管理一个缓冲区，用来保存程序读写数据。

    /**
     * 下面代码，文本串可能立即打印出来，但也可能被操作系统
     * 保存在缓冲区中，随后打印
     * 
     * 有了缓冲区机制，操作系统就可以将程序的多个输出操作组合成单一的
     * 系统级写操作。由于设备的写操作可能很耗时，允许os将多个输出
     * 操作组合为单一的设备写操作可以带来性能提升
     */
    cout<<"das"<<endl;

导致缓冲刷新(数据真正写到输出设备或文件)的原因：
[1] 程序正常结束，作为main函数的return操作的一部分,缓冲刷新被执行
[2] 缓冲区满时，需要刷新缓冲，而后新的数据才能继续写入缓冲区。
[3] 可以使用操纵符如end(结束当前行，并将与设备关联的缓冲区中的内容刷到设备中)来显示刷新缓冲区。
[4] 在每个输出操作之后，可以使用操纵符unitbuf设置流的内部状态，来清空缓冲区。默认情况下，读cerr是设置unitbuf的，因此写到cerr的内容都是立即刷新的。
[5] 一个输出流可能被关联到另一个流。此时，当读写被关联的流时，关联到的流的缓冲区会被刷新。例如，默认cin和cerr都关联到cout。因此，读cin和写cerr都会导致cout的缓存区刷新。

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;

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


    /**
     * 用unitbuf操纵符：
     * 若想在每次输出操作后都刷新缓冲区，用unitbuf操纵符，
     * 他告诉流在接下来每次写操作后都进行一次flush操作
     * 而nounitbuf操纵符则重置流，使其恢复正常的系统管理的
     * 缓冲区刷新机制
     */
     cout<<unitbuf;//所有输出操作后都会立即刷新缓冲
     cout<<nounitbuf;//恢复正常缓冲机制
     /**
      * 程序崩溃，输出缓冲区不会被刷新：
      * 程序崩溃后，它输出的数据很可能停留在输出缓冲区中等待打印。
      * 当调试一个崩溃的程序时，要确保输出的数据确时已经刷新，否则
      * 可能浪费大量时间去追踪代码为什么没有被执行。
      */


     /**
      * 关联输入和输出流:
      * 当一个输入流被关联到一个输出流时，任何试图从输入流
      * 读取数据的操作都会先刷新关联的输出流。
      *
      * 交互式系统通常应该关联输入和输出流。这意味，包括用户提示信息
      * 都会在读操作前被打印出来
      */
     int val;
     cin>>val;//cout的缓冲区被刷新



     /**
      * tie:
      * tie有两个重载版本：一个版本不带参数，返回指向输出流的指针。
      * 如果本对象当前关联到一个输出流，则返回的就是指向这个流的
      * 指针，如果对象未关联到流，返回空指针。
      *
      * tie的第二个版本接受一个指向ostream的指针，将自己关联到
      * 此ostream。即，x.tie(&o)将流x关联到输出流o, 并返回
      * 之前关联的流，若之前没有关联流，则返回空指针
      *
      * 我们既可以将一个istream关联到另一个ostream，也可以将
      * 一个ostream关联到另一个ostream
      */
     cin.tie(&cout);//仅仅用来展示：标准库将cin和cout关联到一起
     //old_tie指向当前关联到cin的流
     ostream *old_tie=cin.tie(nullptr);//cin不再与其他流关联
     cin.tie(&cerr);//读取cin会刷新cerr而不是cout
     cin.tie(old_tie);//重建cin和cout的关联
}

2. 文件输入输出

头文件fstream定义了三个类型来支持文件IO:ifstream从一个给定文件读取数据，ofstream向一个给定文件写入数据，以及fstream可以读写文件。
这些类型提供的操作与我们之前已经使用过的对象cin和cout的操作一样。特别是，我们可以用IO运算符(<<、>>)来读写文件，可以用getline从一个ifstream读取数据，包括上节七-1的内容也都使用本节这些类型。
除了继承iostream类型的行为外，fstream中定义的类型还增加了一些新的成员来管理与流关联的文件。我们可以对fstream、ifstream、ofstream对象调用这些操作，但不能对其他IO类型调用这些操作。

fstream特有的操作
fstream fstrm;	创建一个未绑定的文件流。fstream是头文件fstream中定义的一个类型。
fstream fstrm(s);	创建一个fstream，并打开名为s的文件。s可以是string类型，或是一个指向C风格字符串的指针。这些构造函数都是explicit的。默认的文件模式mode依赖于fstream的类型
fstream fstrm(s, mode);	与前一个构造函数相同，但按指定mode打开文件。
fstrm.open(s); fstrm.open(s, mode)	打开名为s的文件，并将文件与fstrm绑定。s可以是string类型，或是一个指向C风格字符串的指针。默认的文件mode依赖于fstream的类型。返回void。
fstrm.close()	关闭与fstrm绑定的文件。返回void
fstrm.is_open()	返回一个bool值，指出与fstrm关联的文件是否成功打开且尚未关闭。

①使用文件流对象

string ifile="tfile.txt";
ifstream in(ifile);//构造一个ifstream并打开给定文件(提供文件名, open()自动被调用)
ofstream out;//输出文件流并未关联到任何文件

用fstream代替iostream&:在要求使用基类对象的地方，可以用继承类型来代替。iostream->fstream(sstream)、istream->ifstream、ostream->ofstream。
成员函数open和close:作用在上表

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>
using namespace std;

int main()
{
    string file="tfile";
    ifstream in(file);//构件ifstream并打开文件file

    ofstream out;//输出文件流并未与任何文件关联
    out.open(file);//打开指定文件
    //如果open失败, failbit会被置位。
    //因为open可能会失败，要进行open是否成功检测
    if(out) {//与cin用作条件相似，只有当文件打开成功,才能执行下面操作,open失败，条件为假
    }

    /**
     * 一旦一个文件流已经打开，他就与对应文件保持关联。
     * 对一个已经打开的文件流调用open会失败，并会导致
     * failbit被置位.随后所有试图使用文件流的操作都会
     * 失败。为了将文件流关联到另一个文件，必须首先
     * 关闭已经关联的文件。
     */
     in.close();
     in.open(file+"2");//若open成功，则open会设置流的状态，使得good()为true
}

自动构造和析构：当一个fstream对象被销毁时，close会自动被调用.

int main(int argc, char *argv[])
{
    /**
     * main函数接受一个要处理的文件列表
     * 对每个传递给程序的文件执行循环操作
     */
    for(auto p=argv+1;p!=argv+argc;++p)
    {
        ifstream input(*p);//创建输入流并打开文件
        if(input) {如果文件打开成功，处理此文件}
        else cerr<<"不能打开："+string(*p);
    }//每个循环步input都会离开作用域，因此被销毁
    /**
     * 每个循环步构造一个新的名为input的ifstream对象，并打开它来读取给定的文件
     * 因为input是循环的局部变量，它在每个循环步中都要创建和销毁一次。
     * 当一个fstream对象被销毁时，会自动调用close
     */
}

②文件模式

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

文件模式
in	以读方式打开
out	以写方式打开
app	每次写操作前均定位到文件末尾
ate	打开文件后立即定位到文件末尾
trunc	截断(清空)文件
binary	以二进制方式进行IO

无论用哪种方式打开文件，都可以指定文件模式。指定文件模式有如下限制：
[1] 只可以对ofstream或fstream对象设定out模式
[2] 只可以对ifstream或fstream对象设定in模式
[3] 只有当out也被设定时，才可设定trunc模式
[4] 只要trunc没被设定，就可以设定app模式。在app模式下，即使没有显式指定out模式，文件也总以输出模式被打开
[5] 默认情况下，即使我们没有指定trunc,以out模式打开的文件也会被截断。为了保留以out模式打开的文件内容，我们必须同时指定app模式，这样只会将数据追加到文件末尾;或同时指定in模式(读的话，原来的不能删除)，即打开文件同时进行读写操作。
[6] ate和binary模式可以用于任何类型的文件流对象，且可以与其他任何文件模式组合使用。
-
每个文件流类型都定义了一个默认文件模式，当我们未指定文件模式，会使用默认文件模式。与ifstream关联的文件默认以in模式打开；与ofstream关联的文件默认以out模式打开；与fstream关联的文件默认以in个out模式打开。
-
以out模式打开文件会丢弃已有数据：
默认情况下，当我们打开一个ofstream时，文件的内容会被丢弃。阻止一个ofstream清空给定文件内容的方法使同时指定app模式

    string file="tfile";
    //下面几条语句, file都将被截断
    ofstream out1(file);//隐含以输出模式打开文件并截断文件
    ofstream out2(file, ofstream::out);//隐含截断文件
    ofstream out3(file, ofstream::out|ofstream::trunc);//可使用|运算符将不同文件模式组合使用
    
    //为了保留文件内容，必须显式指定app模式
    ofstream app1(file, ofstream::app);//隐含为输出模式
    ofstream app2(file, ofstream::out|ofstream::app);//保留ofstream唯一方法是显示指定app或in模式

每次调用open时都会确定文件模式：
对于一个给定流，每当打开文件时，都可以改变其文件模式

    string file="tfile";
    ofstream out;//未指定文件打开模式
    out.open(file);//模式隐含设置为输出和截断
    out.close();//关闭out
    out.open(file, ofstream::app);//模式为输出和追加

3. string流

sstream头文件定义了三个类型来支持内存IO, 这些类型可以向string写入数据，从string读取数据，就想string是一个IO流一样。
istringstream从string读取数据, ostringstream向string写入数据，而头文件stringstream可读可写。与fstream类似，头文件sstream中定义的类型都继承自我们已经使用过的iostream头文件中定义的类型。此外，sstream中定义的类型还增加了一些成员来管理与流相关联的string。

stringstream特有的操作
sstream strm;	strm是一个未绑定的stringstream对象。sstream是头文件sstream中定义的一个类型。
sstream strm(s);	strm是一个sstream对象，保存string s的一个拷贝。次构造函数是explicit的。
strm.str();	返回strm保存的string的拷贝
strm.str(s);	将string s拷贝到strm中。返回void

①使用istringstream

当我们对整行文本处理，其他一些工作是处理行内的单个单词时，可用istringstream。

人名 号码
a 123 345
b 231321 32131

struct PersonInfo {
    string name;
    vector<string> phones;
};

int main(int argc, char *argv[])
{
    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);
    }
    /**
     * getline读取整条记录
     * 记录保存到record中, 并读取
     * 
     * record从string中读取数据，读完后会触发文件结束
     */
}

②使用ostringstream

当我们逐步构造输出，最后一起打印时，ostringstream有用。

struct PersonInfo {
    string name;
    vector<string> phones;
};

int main(int argc, char *argv[])
{

    vector<PersonInfo> people;//保存所有记录
    //检查所有号码，将有效的改变格式并统一输出，无效的最后输出另一个文件
    for(const auto &entry:people)//对people中每一项
    {
        ostringstream formatted, badNum;//每个循环步创建的对象
        for(const auto &nums:entry.phones)//当前人的所有电话
        {
            if(!valid(nums)) badNum<<" "<<nums;//将错误号码存入
            else formatted<<" "<<format(nums);//将格式化的号码写入    
        }
        
        if(badNum.str().empty()) //没有错误的数
            os<<entry.name<<" "
                <<formatted.str()<<endl;
        else
            cerr<<"错误："<<entry.name
                <<"无效号:"<<badNum.str()<<endl;
    }
}

八. 顺序容器

一个容器就是一些特点类型对象的集合。顺序容器为程序员提供了控制元素存储和访问顺序的能力。这种顺序不依赖于元素的值，而是与元素加入容器时的位置对应。
标准库还提供了三种容器适配器，分别为容器操作定义了不同接口，来与容器类型适配

1. 顺序容器概述

所有顺序容器都提供了快速顺序访问元素的能力。但是，这些容器在以下方面都有不同的性能折中：
[1] 向容器添加、删除元素的代价
[2] 非顺序访问容器元素的代价

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

除了固定大小的array外，其他容器都提供高效、灵活的内存管理。
string和vector将元素保存在连续的内存空间中。所以，由元素下标计算地址非常快。但是在中间位置插入和删除元素慢，需要移动。而且，添加一个元素有时需要分配额外的存储空间，在这种情况下，每个元素都必须移动到新的存储空间。
list和forward_list两个容器目的是为了令容器任何位置添加和删除都很快速，但是不不支持元素的随机访问。且与vector、deque、array比，这两个容器额外内存开销很大(ne指针)。
forward_list和array是新C++标准增加的类型。与内置数组相比，array是一种更安全、更容易使用的数组类型。与内置数组类似，array对象大小固定，因此array不支持添加和删除元素以及改变容器大小操作。
新标准库的容器比旧版快的多。现代，C++程序应该使用标准库容器，而不是更原始的数据结构，如内置数组。
-
确定使用哪种顺序容器：
[1] 除非有很好理由选择其他容器，否则应使用vector
[2] 若程序有很多小的元素，且空间的额外开销重要, 不要用list或forward_list
[3] 随机访问->vector、deque
[4] 中间插入和删除->list、forward_list
[5] 头尾插入删除，中间不会插入删除->deque
[6] 若程序只有在读取输入时才需要在容器中间位置插入元素，随后要随机访问元素则：若要求有序，可在vector插入，然后sort，避免在中间插入；若需要在中间插入，在输入阶段用list，输入完成后，将list内容拷贝到一个vector中。

2. 容器库概览

容器类型的操作形成了一种层次：
某些操作是所有容器类型都提供的
另外一些操作仅针对顺序、关联、无序容器
还有一些操作只适用于一小部分容器
本节将介绍所有容器都适用的操作，本章剩余部分将介绍仅适用于顺序容器的操作。
一般来说，每个容器都定义在一个头文件中。文件名与类型名相同。容器定义均为模板类。
-
对容器可以保存的元素类型的限制：顺序容器几乎可以保存任意类型的元素。我们可以定义一个容器，其元素的类型是另一个容器。

vector<vector<string>> lines;

虽然我们可以在容器中保存几乎任何类型，但某些容器操作对元素类型有其自己的特殊要求。
例如，顺序容器构造函数的一个版本接受容器大小参数，它使用了元素类型的默认构造函数。但某些类没有默认构造函数。我们可以定义一个保存这种类型对象的容器，但我们在构造这种容器时不能只传递给他一个元素数目参数：

//假定noDefault是一个没有默认构造函数的类型
vector<noDefault> v1(10, init);//✔，提供了元素初始化器
vector<noDefault> v2(10);//✖，必须提供一个元素初始化器

容器操作
类型别名
iterator	此容器类型的迭代器类型
const_iterator	可以读取元素，但不能修改元素的迭代器类型
size_type	无符号整数类型，足以保存此种容器类型最大可能容器的大小
difference_type	带符号整数类型，足够保存两个迭代器间的距离
value_type	元素类型
reference	元素左值类型；与value_type&含义相同
const_reference	元素的const左值类型(const value_type&)
构造函数
C c	默认构造函数，构造空容器(array参见后面)
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)	与上面等价
大小
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.cbegin(), 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)

②容器类型成员

每个容器都定义了多个类型：容器操作中的类型别名一栏
在反向迭代器中，各种操作的含义发生变化。比如，对一个反向迭代器执行++操作，会得到上一个元素。
类型别名：通过类型别名，我们可以在不了解容器中元素类型的情况下使用它。如果需要元素类型，可用value_type, 若要元素类型的引用reference、const_reference。

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

③begin和end成员

上表中获取迭代器和反向迭代器部分。
以c开头的版本是c++11引入的，用以支持auto和begin、end函数的结合使用。
以c开头的函数是重载过的，即有两个begin函数，一个返回非常量迭代器，一个返回常量迭代器。同指针，普通迭代器可转换为常量迭代器，反之不行。

list<string> a;
list<string>::iterator it5=a.begin();
list<string>::const_iterator it6=a.begin();
auto it7=a.begin();//当a是const时，it7是const_iterator
auto it8=a.rbegin();//it8是常量迭代器
//当不需要写操作时，应cbegin和cend

④容器定义和初始化

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

容器定义和初始化
C c	默认构造函数。若C是array，则c中元素默认初始化；否则c为空
C c1(c2) C c1=c2	c1初始化为c2的拷贝。c1和c2必须是相同类型(容器类型和元素类型；对于array，两者必须有相同大小)
C c{a, b, c...} C c={a, b, c...}	c初始化为列表中元素的拷贝。列表中元素类型必须与C的元素类型相容。对于array,列表中的元素数目必须<=arry大小，任何遗漏的元素进行值初始化
C c(b, e)	c初始化为迭代器b和e指定范围中的元素拷贝（不含e指向的元素）。范围中元素类型必须和C元素类型相容(array不适用)
C seq(n);只有顺序容器(除了array)的构造函数才能接受大小参数	seq包含n个元素，这些元素进行了值初始化。此构造函数是explicit的。（string不适用）
C seq(n, t)	seq包含n个初始化为值t的元素

标准库array具有固定大小：与内置数组一样，标准库array的大小也是类型的一部分。当定义一个array时，除了指定元素类型，还要指定容器大小。

/**
 * array不支持普通的容器构造函数，这些构造函数都会确定容器大小
 * (隐式，显式)。允许用户向array构造函数传递参数，最好情况
 * 也是多余的，且容易出错。
 * 
 */
array<int, 42> a;//类型为42个int的数组
array<int, 10>::size_type i;//必须指定大小

/**
 * array大小固定特性也影响了它所定义的构造函数行为。与其他容器
 * 不同，默认构造的array是非空的：它包含了与其大小一样多的元素。
 * 这些元素都被默认初始化。
 * 
 * 若对array列表初始化，初始值的数目必须<=array大小。若初始值
 * 数目<array大小，则它被用来初始化靠前元素，剩下元素值初始化。
 * 
 * 在这两种情况下。若元素类型是一个类类型，那么该类必须有一个默认
 * 构造函数，以便值初始化能够进行
 */
array<int, 10> a1;//10个默认初始化的Int
array<int, 10> a2={0, 1, 2, 3, 4, 5, 6, 7, 8, 9};//列表初始化
array<int, 10> a3={42};//a3[0]为42, 剩余元素为0
/**
 * array可以拷贝和对象赋值(内置数组不行)
 * 元素类型和大小都要匹配，大小也是类型一部分
 */
int dig[3]={0, 1, 2};
int cpy[3]=dig;//✖，内置数组不支持赋值和拷贝
array<int, 10> copy=a2;//✔

⑤赋值和swap

容器赋值运算
c1=c2	将c1中的元素替换为c2中元素的拷贝。c1和c2必须有相同元素类型
c={a, b, c...}	c1中元素替换为初始化列表中元素的拷贝(array不适用)
swap(c1, c2) c1.swap(c2)	交换c1和c2中的元素。c1、c2必须具有相同元素类型。swap通常比从c2向c1拷贝元素快得多
assign操作(仅顺序容器)不适用于关联容器和array
seq.assign(b, e)	将seq中的元素替换为迭代器b和e所表示范围的元素。迭代器b和e不能指向seq中的元素
seq.assign(il)	将seq中的元素替换为初始化列表il中的元素
seq.assign(n, t)	将seq中的元素替换为n个值为t的元素
注：赋值相关运算会导致指向左边容器内部的迭代器、引用和指针失效。而swap不会(容器类型为array和string情况除外)。

    /**
     * 第一个赋值后，左边容器将与右边容器相等。
     * 若两个容器原来大小不同，赋值后两者大小
     * 都与右边容器大小相同
     *
     * 第二个赋值运算后,c1的大小变为3，即花括号中值的数目
     */
    vector<int> c1, c2;
    c1=c2;
    c1={1, 2, 3};

    /**
     * 因为右边运算大小可能和左边不同，所以array类型
     * 不支持assign，也不允许花括号包围的值列表进行赋值
     */

使用assign(仅顺序容器，array除外):赋值运算要求左边和右边的运算对象具有相同的类型。但assign允许我们从一个不同但相容的类型赋值，或者从容器的一个子序列赋值。assign操作用参数所指定的元素(的拷贝)替换左边容器中的所有元素。

    list<string> names;
    vector<const char*> oldstyle;
    names=oldstyle;//✖，容器类型不匹配
    //✔，可将const char*转换为string
    //由于旧元素被替换，因此传递给assign的迭代器不能指向调用assign的容器
    names.assign(oldstyle.cbegin(), oldstyle.cend());
    
    list<string> slist1(1);//1个元素，为空string
    slist1.assign(10, "hi");//10个元素每个都是hi

使用swap:

    vector<string> s1(10);
    vector<string> s2(24);
    /**
     * swap后s1包含24个，s2包含10个
     * 除array外，交换两个容器内容很快，元素本身未交换，
     * swap只是交换了两个容器的内部数据结构。除array外，
     * swap不进行拷贝、删除、插入操作，常数时间完成。
     * 
     * 元素不会移动意味着，除string外指向容器的迭代器、引用、
     * 指针在swap操作后不会失效。他们仍指向swap操作前所指向的元素。
     * 但是在swap后这些元素属于不同容器了。例如，iter交换前
     * 指向s1[3], 交换后指向s2[3].
     * 
     *   与其他容器不同，对一个string调用swap会导致迭代器、引用、指针失效.
     *   与其他容器不同，swap两个array会真正交换他们的元素。因此，交换两个
     * array与array中元素数目成正比。
     *   对于array，swap后，指针、引用、迭代器所绑定元素不变，但元素值已经与
     *  另一个array中对应元素的值进行了交换。
     */
    swap(s1, s2);

⑥容器大小操作

除了一个例外，每个容器类型都有三个与大小相关的操作。成员函数size返回容器中元素数目；empty当size为0时返回true, 否则返回false;max_size返回一个大于或等于该容器所能容纳的最大元素数的值。
forward_list支持max_size和empty，但不支持size.

⑦关系运算符

每个容器类型都支持相等运算符(==和!=)；除了无序关联容器外的所有容器都支持关系运算符(>, >=, <, <=)。关系运算符左右两边的运算对象必须是相同类型的容器，且必须保存相同类型的元素。
比较两个容器实际上是进行元素的逐对比较，和string类似：
[1] 如果两个容器具有相同大小且所有元素都两两对应相等，则两个容器相等；否则两个容器不等。
[2] 如果两个容器大小不同，但较小容器中每个元素都等于较大容器中的对应元素，则较小容器小于较大容器。
[3] 如果两个容器都不是另一个容器的前缀前缀子序列，则他们的比较结果取决于第一个不相等的元素的比较结果。

    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, v1[2]<=v2[2]
    v1<v3;//fasle, 所有元素相等，但v3数目小
    v1==v4;//true
    v1==v2;//false, v2元素数目少

容器的关系运算符使用元素的关系运算符完成比较：只有当其元素类型也定义了相应的比较运算符时，我们才可以使用关系运算符比较两个容器。

3. 顺序容器操作

顺序容器和关联容器的不同之处在于两者组织元素的方式。上面介绍了所有容器都支持的操作，从此往后将介绍顺序容器特有操作。

①向顺序容器添加元素

向顺序容器添加元素操作
这些操作会改变容器大小，array不支持。 forward_list有自己专有版本的insert和emplace,后面介绍。 forward_list不支持push_back和emplace_back。 vector和string不支持push_front和emplace_front。
c.push_back(t) c.emplace_back(args)	在c的尾部创建一个值为t或有args创建的元素，返回void
c.push_front(t) c.emplace_front(args)	在c的头部创建一个值为t或由args创建的元素，返回void
c.insert(p, t) c.emplace(p, args)	在迭代器p指向的元素之前创建一个值为t或由args创建的元素，返回指向新添加元素的迭代器。
c.insert(p, n, t)	在迭代器p指向的元素之前插入n个值为t的元素。返回指向新添加的第一个元素的迭代器；若n为0, 则返回p
c.insert(p, b, e)	将迭代器b和e指定的范围内的元素插入到迭代器p指向的元素之前。b和e不能指向c中的元素。返回指向新添加的第一个元素的迭代器；若范围为空，则返回p
c.insert(p, il)	il是一个花括号包围的元素值列表。将这些值插入到迭代器p指向的元素之前。返回指向新添加的第一个元素的迭代器；若列表为空返回p
向一个vector、string、deque插入元素使所有指向容器的迭代器、引用和指针失效。要牢记，使用这些操作时，不同容器使用不同的策略来分配元素空间，直接影响性能。在一个vector和string的尾部之外的任何位置，或是deque的首尾之外的任何位置添加元素，都要移动元素。向一个vector或string添加元素可能引起整个对象存储空间的重新分配。重新分配一个对象的存储空间需要分配新的内存，并将元素从旧的空间移动到新的空间中。

push_back的调用者在尾部创建一个新的元素，并将size扩大1.
当我们用一个对象初始化容器时，或将一个对象插入到容器时，实际上放入到容器中的是对象值的一个拷贝，而不是对象本身。
使用emplace操作：新标准引入了三个成员：emplace_front、emplace、emplace_back，这些操作构造而不是拷贝元素。当调用push或insert成员函数时，我们将元素类型的对象传递给她们，这些对象被拷贝到容器中。而当我们调用一个emplace成员函数时，则是将参数传递给元素类型的构造函数。emplace成员使用这些参数在容器管理的内存空间中直接构造元素。

    //使用三个参数的Sales_data构造函数
    c.emplace_back("das", 25, 15.99);
    //✖，没有接受三个参数的push_back版本
    c.push_back("das", 25, 15.99);
    //✔，创建一个临时的Sales_data对象传递给push_back
    c.push_back(Sales_data("das", 21, 20.0));
    /**
     * 其中对emplace_back的调用和第二个push_back调用都会创建新的
     * Sales_data对象。在调用emplace_back时，会在容器管理的内存
     * 中直接创建对象。而调用push_back会创建一个临时对象，并将其压入容器
     * 
     * 
     * emplace函数的参数根据元素类型而变化，参数必须与元素类型的构造函数匹配
     */
     c.emplace_back();//使用Sales_data默认构造函数

②访问元素

在顺序容器中访问元素的操作
at和下标操作只适用于string、vector、deque和array。 back不适用于forward_list
c.back()	返回c中尾元素的引用。若c为空，函数行为未定义。
c.front()	返回c中首元素的引用。若c为空，函数行为未定义。
c[n]	返回c中下标为n的元素的引用，n是一个无符号整数。若n>=c.size(), 则函数行为未定义
c.at(n)	返回下标为n的元素的引用。如果下标越界，则抛出out_of_range异常

若容器中没有元素，访问操作的结果是未定义的。
访问成员函数返回的是引用：容器是const则返回const引用，否则返回普通引用。

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

    }

下标操作和安全的随机访问：c[n]产生未定义行为，运行时错误，而c.at(n)抛出out_of_range异常，后者可确保下标是合法的。

③删除元素

顺序容器的删除操作
由于这些操作会改变容器大小，不使用array forward_list有特殊版本的erase forward_list不支持pop_back；vector和string不支持pop_front
c.pop_back()	删除c中尾元素。若c为空，则函数行为未定义。函数返回void
c.pop_front()	删除c中首元素。若c为空，则函数行为未定义。函数返回void
c.erase(p)	删除迭代器p所指的元素，返回一个指向被删除元素之后元素的迭代器，若p指向尾元素，则返回尾后迭代器。若p是尾后迭代器，则函数行为未定义
c.erase(b, e)	删除迭代器b和e所指定范围内的元素。返回一个指向最后一个被删除元素之后元素的迭代器，若e本身是尾后迭代器，则函数也返回尾后迭代器
c.clear()	删除c中所有元素。返回void
删除deque除首尾位置之外的任何元素都会使所有迭代器、引用和指针失效。指向vector或string删除点之后位置的迭代器、引用、指针都会失效。

④特殊的forward_list操作

为了理解forward_list为什么有特殊版本的添加和删除操作，考虑从一个单向链表中删除一个元素会发生什么。如下图所示，删除一个元素会改变序列中的链接。删除elem3会改变elem2,elem2原来指向elem3，删除elem3后elem2会指向elem4。

当添加或删除一个元素时，删除或添加的元素之前的那个元素的后继会发生改变。为了添加或删除一个元素，我们需要访问其前驱，以便改变前驱链接。但是forward_list是单向链表。在一个单向链表中，没有简单的方法获取一个元素的前驱。出于这个原因，在一个forward_list中添加或删除元素的操作通过改变给定元素之后的元素来完成的。这样，我们可以访问到被添加或删除操作所影响的元素。
由于这些操作与其他容器的操作的实现方式不同，所以forward_list定义了自己的添加删除操作。例如为了删除elem3，应该用指向elem2的迭代器调用erase_after。为了支持这些操作，forward_list也定义了before_begin，它返回一个首前迭代器。这个迭代器允许我们在链表首元素之前添加删除元素。

在forward_list中插入或删除元素的操作
lst.before_begin() lst.cbefore_begin()	返回指向链表首元素之前不存在的元素的迭代器。此迭代器不能解引用。第二个返回一个const_iterator
lst.insert_after(p, t) lst.insert_after(p, n, t) lst.insert_after(p, b, e) lst.insert_after(p, il)	在迭代器p之后的位置插入元素。t是一个对象，n是数量，b和e是表示范围的一对迭代器（be不能指向lst内），il是一个花括号列表。返回一个指向最后一个插入元素的迭代器。如果范围为空，返回p。若p为尾后迭代器，则函数行为未定义
emplace_after(p, args)	使用args在p指定的位置之后创建一个元素。返回一个指向这个新元素的迭代器。若p为尾后迭代器，则函数行为未定义
lst.erase_after(p) lst.erase_after(b, e)	删除p指向的位置之后的元素，或删除从b之后(不含b)直到e之间的元素，返回一个指向被删除元素之后元素的迭代器，若不存在这样的元素，返回尾后迭代器。如果p指向lst的尾元素或者是一个尾后迭代器，则函数行为未定义。

⑤改变容器大小

顺序容器大小操作
c.resize(n)	不适用于array。调整c的大小为n个元素。若n<c.size(), 丢弃多出的元素。若必须添加新元素(n>c.size())，对新元素进行值初始化
c.resize(n, t)	调整c的大小为n个元素。任何新添加的元素都初始化为值t
如果resize缩小容器，则指向被删除元素的迭代器、指针、引用都会失效；对vector、string、deque进行resize可能导致迭代器、指针和引用失效。

顺序容器大小操作

c.resize(n)

不适用于array。调整c的大小为n个元素。若n<c.size(), 丢弃多出的元素。若必须添加新元素(n>c.size())，对新元素进行值初始化

c.resize(n, t)

调整c的大小为n个元素。任何新添加的元素都初始化为值t

如果resize缩小容器，则指向被删除元素的迭代器、指针、引用都会失效；

对vector、string、deque进行resize可能导致迭代器、指针和引用失效。

resize操作接受一个可选元素值参数，用来初始化新添加元素。若未提供此参数，则进行值初始化。若容器保存的是类类型元素，且resize向容器添加新元素，则我们必须提供初始值，或元素类型必须提供默认构造函数。

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

向容器中添加删除元素的操作，可能会使指向容器元素的指针、引用或迭代器失效。一个失效的指针、引用、迭代器不表示任何元素。
向容器添加元素后：
[1] 若容器是vector或string, 且存储空间被重新分配，则指向容器的迭代器、指针、引用都会失效。如果存储空间未重新分配，指向插入位置之前的元素的迭代器、指针、引用仍有效，但指向插入位置之后元素的迭代器、指针、引用将会失效。
[2] 对于deque，插入到除首尾位置之外的任何位置都会导致迭代器、指针、引用失效。如果在首尾位置插入元素，迭代器失效，但指向存在的元素的引用和指针不会失效。
[3] 对应list、forward_list，指向容器的迭代器(包括尾后、首前迭代器)、指针、引用仍有效。
当我们从一个容器删除元素后，指向被删除元素的迭代器、引用、指针会失效，因为元素被删除了。当我们删除一个元素后：
[1] 对于list、forward_list，指向容器的迭代器(包括尾后、首前迭代器)、指针、引用仍然有效。
[2] 对于deque，如果在首尾之外任何位置删除元素，那么指向被删除元素外其他元素的迭代器、指针、引用会失效。如果删除尾元素，则尾后迭代器也会失效，但其他迭代器、引用、指针不受影响；如果删除首元素，这些也不会受影响。
[3] 对于vector、string，指向被删除元素之前元素的迭代器、指针、引用仍有效, 之后的无效。当我们删除元素时，尾后迭代器总会失效。
-
管理迭代器：当使用迭代器(或指向容器元素的引用或指针)时，最小化要求迭代器必须保持有效的程序片段是一个好方法。添加删除元素可能导致上述失效，必须保证每次改变容器操作之后都能正确重新定位迭代器。对vector、string、deque尤为重要。
编写改变容器的循环程序：

    /**
     * 添加删除vector、string、deque元素必须考虑迭代器、引用、
     * 指针可能失效问题。程序必须保证每个循环步都更新迭代器、引用、指针。
     * 如果循环中调用的是insert、erase。那么更新迭代器很容易，
     * 这些操作都返回迭代器。
     * 
     * 此程序删除vector中偶数元素，并复制每个奇数元素。我们在调用insert和erase
     * 后都更新迭代器，因为二者会使迭代器失效。
     */
    vector<int> vi={0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    auto iter=vi.begin();
    while(iter!=vi.end())//vi.end()时刻使用最新尾后迭代器
    {
        if(*iter%2)//如果当前元素为奇数
        {
            iter=vi.insert(iter, *iter);//复制当前元素，iter指向新插入元素位置
            iter+=2;//向前移动迭代器，跳过当前元素以及插入到他之前的元素
        }
        else iter=vi.erase(iter);//删除偶数元素
        //不应向前移动元素，iter指向我们删除的元素之后的元素
    }

不要保存end返回的迭代器：当添加删除vector或string元素后，或在deque首元素之外任何位置删除元素后，原来end返回的迭代器总会失效。因此，添加或删除元素的循环程序必须反复调用end,而不能使用之前保存的end返回的迭代器。

    //此循环行为未定义
    vector<int> v;
    auto begin=v.begin(),
        end=v.end();//保存尾后迭代器不对，下面更新，end会失效
    while(begin!=end)//while(begin!=v.end())每个循环步添加删除元素后，重新计算end
    {
        //做一些处理
        //插入新值，对begin重新赋值，否则他会失效
        ++begin;//向前移动begin, 因为我们想在此元素后插入元素
        begin=v.insert(begin, 42);
        ++begin;//跳过我们刚加入的元素
    }

4. vector对象是如何增长的

为了支持快速随机访问，vector(string)将元素连续存储，且容器大小是可变的。
考虑向vector和string添加元素：若没有空间容纳新元素，容器不可能简单将他们添加到内存其他位置，因为其要连续存储。容器必须分配新的内存空间来保存已有元素和新的元素，将已有元素从旧位置移动到新空间中，然后添加新元素，释放就空间。如果我们没添加一次元素，就执行这样的策略，性能会很差。
为了避免这种代价，标准款采用了可减少容器空间重新分配次数的策略。当不得不获取新的内存空间时，vector和string的实现通常会分配比新的空间需求更大的内存空间。容器预留这些空间作为备用，可用来保存更多的新元素。这样，就不需要每次添加新元素都重新分配容器的内存空间了。
管理容量的函数：vector和string类型提供了一些成员函数，允许我们与他的实现中内存分配部分互动。

容器大小管理操作
shrink_to_fit只适用于vector、string和deque capacity和reserve只适用于vector和string
c.shrink_to_fit()	请将capacity()减少为与size()大小相同
c.capacity()	不重新分配内存空间的话,c可以保存多少元素
c.reserve(n)	分配至少能容纳n个元素的内存空间。（元素数量和内存空间时两码事，内存空间是容器，元素是实际存储的东西）

reserve不改变容器中元素数量，它仅影响vector预先分配多大的内存空间。
只有当需要的内存空间超过当前容量，reserve调用才会改变vector的容量。
如果需求大小小于等于当前容量，reserve什么也不做。特别的，当需求大小小于当前容量时，容器不会退回内存空间。因此，在调用reserve后，capacity将会大于等于传递给reserve的参数。
这样，调用reserve永远也不会减少容器占用的内存空间。类似的，resize成员函数只改变容器中元素的数目，而不是容器的容量。同样不能使用resize来减少容器预留的内存空间。
在新标准库中，我们可以调用shrink_to_fit来要求deque、vector、string退回不需要的内存空间。但是，具体的实现可以选择忽略此请求，即：调用该函数也不保证一定退回内存空间。
capacity和size:容器size指它保存的元素数目；而capacity则是在不分配新的内存空间的前提下它最多可以保存多少元素。

    vector<int> v;
    cout<<v.size()<<" "<<v.capacity()<<endl;//size为0，capacity为0依赖于具体实现

    for(int i=0;i<10;++i) v.emplace_back(i);
    cout<<v.size()<<" "<<v.capacity()<<endl;//size为10，capacity>=10 为16依赖于具体实现
    v.reserve(50);//分配至少容纳50个元素的内存空间
    cout<<v.capacity()<<endl;//50

每个vector都可以选择自己的内存分配策略，但是：只有当迫不得已时才可以分配新的内存空间。
只有在执行insert时size与capacity相等，或者调用resize或reserve时给定的大小超过当前capacity，才会分配内存空间。

5. 额外的string操作

除了顺序容器的共同操作，string类型还提供了一些额外的操作。

①构造string的其他方法

除了第二章第2节，以及和其他顺序容器相同的构造函数。string还支持另外三个构造函数。

构造string的其他方法
n、len2、pos2都是无符号值。
string s(cp, n)	s是cp指向的数组中前n个字符的拷贝。此数组至少应该包含n个字符
string s(s2, pos)	s是string s2从下标pos2开始的字符的拷贝。若pos2>s2.size(),构造函数行为未定义
string s(s2, pos2, len2)	s是string s2从下标pos2开始len2个字符的拷贝。若pos2>s2.size(), 构造函数行为未定义。不管len2值为多少，构造函数至多拷贝s2.size()-pos2个字符。

这些构造函数接受一个string或一个const char*参数。
通常当我们从一个const cgar*创建string时必须以空字符结尾，拷贝遇到空字符截止。但是若给了计数值，不必以空字符结尾。

    const char *cp="Hello World!!!";//以空字符结束的数组
    char noNull[]={'H', 'i'};//不是以空字符结尾
    string s1(cp);//拷贝cp中的字符直到遇到空字符,s1为Hello World!!!
    string s3(noNull);//未定义：noNull不是以空字符结尾

substr操作：substr返回一个string, 他是原始string的一部分或全部的拷贝。可以传递给sunstr一个可选的开始位置和计数值。若开始位置超过了string大小，substr抛出out_of_range异常。若开始位置加上计数值大于string大小，substr会调整计数值，只拷贝到string的末尾。
s.substr(pos, n)：返回一个string，包含s中从pos开始的n个字符的拷贝。pos默认值为0。n的默认值为s.size()-pos，即拷贝从pos开始的所有字符

string s("hello world");
s.substr(0,5);//hello
s.substr(6);//world

②改变string的其他方法

修改string操作
s.insert(pos, args)	在pos之前插入args指定的字符。pos可以是一个下标或一个迭代器。接受下标的版本返回一个指向s的引用；接受迭代器的版本返回指向第一个插入字符的迭代器
s.erase(pos, len)	删除从位置pos开始的len个字符。如果len被省略，则删除从pos开始直至s末尾的所有字符。返回一个指向s的引用
s.assign(args)	将s中的字符替换为args指定的字符。返回一个指向s的引用
s.append(args)	将args追加到s,返回一个指向s的引用
s.replace(range, args)	删除s中范围range内的字符，替换为args指定的字符。range或者是一个下标和一个长度，或者是一对指向s的迭代器。返回一个指向s的引用。
args可以是下列形式之一；append和assign可以使用所有形式。 str不能与s相同，迭代器b和e不能指向s
str	字符串str
str, pos, len	str中从pos开始最多len个字符
cp, len	从cp指向的字符数组的前len个字符
cp	cp指向的以空字符结尾的字符数组
n, c	n个字符c
b, e	迭代器b和e指定的范围内的字符
初始化列表	花括号分隔的，以逗号分隔的字符列表

replace和insert所允许的args形式依赖于range和pos是如何指定的
replace	replace	insert	insert	args可以是
(pos, len, args)	(b, e, args)	(pos, args)	(iter(迭代器),args)
是	是	是	否	str
是	否	是	否	str, pos, len
是	是	是	否	cp, len
是	是	否	否	cp
是	是	是	是	n, c
否	是	否	是	b2, e2
否	是	否	是	初始化列表

③string搜索操作

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

string搜索操作
搜索操作返回指定字符出现的下标，如果未找到则返回npos。 if(string::npos==s.find(args)) static const size_type npos = -1;
s.find(args)	查找s中args第一次出现的位置
s.rfind(args)	查找s中args最后一次出现的位置
s.find_first_of(args)	在s中查找args中任何一个字符第一次出现的位置
s.find_last_of(args)	在s中查找args中任何一个字符最后一次出现的位置
s.find_first_not_of(args)	在s中查找第一个不在args中的字符
s.find_last_not_of(args)	在s中查找最后一个不在args中的字符
args必须是以下形式之一
c, pos	从s中位置pos开始查找字符c。pos默认为0
s2, pos	从s中位置pos开始查找字符串s2。pos默认为0（可不加pos）
cp, pos	从s中位置pos开始查找指针cp指向的以空字符结尾的C风格字符串。pos默认为0
cp, pos, n	从s中位置pos开始查找指针cp指向的数组的前n个字符。pos和n无默认值。

④compare函数

类似C标准库的strcmp函数，根据s是等于、大于、小于参数指定的字符串，s.compare返回0、正数、负数。

s.compare的几种参数形式
s2	比较s和s2
pos1, n1, s2	将s从pos1开始的n1个字符与s2比较
pos1, n1, s2, pos2, n2	将s从pos1开始的n1个字符与s2中从pos2开始的n2个字符进行比较
cp	比较s与cp指向的以空字符结尾的字符数组
pos1, n1, cp	将s中从pos1开始的n1个字符与cp指向的以空字符结尾的字符数组进行比较
pos1, n1, cp, n2	将s从pos1开始的n1个字符与指针cp指向的地址开始的n2个字符比较

⑤数值转换

string和数值之间的转换
to_string(val)	一组重载函数，返回数值val的string表示。val可以是任何算术类型。对每个浮点型和int或更大的整型，都有相应版本的to_string。与往常一样，小整型会被提升。
stoi(s, p, b)	返回s的起始子串(表示整数内容)的数值，返回值类型分别是int、long、unsigned long、long long、unsigned long long。b表示转换所用的基数，默认为10(可以不写这个参数)。p是size_t指针，用来保存s中第一个非数值字符的下标，p默认为0，即, 函数不保存下标。
stol(s, p, b)
stoul(s, p, b)
stoll(s, p, b)
stoull(s, p, b)
stof(s, p)	返回s的起始子串(表示浮点数内容)的数值，返回值类型分别是float、double或long double。参数p的作用与整数转换函数中的一样，默认为0
stod(s, p)
stold(s, p)

    string s="pi = 3.14";
    //转换s中以数字开始的第一个子串，d=3.14
    double d=stod(s.substr(s.find_first_of("+-.0123456789")));
    /**
     * string参数中第一个非空白符必须是符号(+或-)或数字。它也可以以0x或0X开头
     * 表示十六进制数。
     * 
     * 对于那些将字符串转换为浮点值的函数，string参数也可以以小数点开头，并可以包含e或E来表示指数
     * 部分。
     * 
     * 对于那些将字符串转换为整型值的函数，根据基数不同，string参数可以包含字母，对应大于数字9的数
     */

6. 容器适配器

除了顺序容器外，标准库还定义了三个顺序容器适配器：stack、queue、priority_queue。适配器是标准库中的一个通用概念。容器、迭代器、函数都有适配器。本质上，一个适配器是一种机制，能使某种事物的行为看起来像另外一种事务一样。一个容器适配器接受一种已有容器类型，使其行为看起来像一种不同的类型。例如，stack适配器接受一个顺序容器(除array或forward_list外)，并使操作看起来像一个stack一样。

所有容器适配器都支持的操作和类型
size_type	一种类型，足以保存当前类型的最大对象的大小
value_type	元素类型
container_type	实现适配器的底层容器类型
A a;	创建一个名为a的空适配器
A a(c);	创建一个名为a的适配器，带有容器c的一个拷贝
关系运算符	每个适配器都支持所有关系运算符：==、!=、<、<=、>、>=这些运算符返回底层容器的比较结果
a.empty()	若a包含任何元素，返回false, 否则返回true
a.size()	返回a中的元素数目
swap(a, b) a.swap(b)	交换a和b的内容，a和b必须有相同类型，包括底层容器类型也必须相同。
swap(a, b) a.swap(b)	交换a和b的内容，a和b必须有相同类型，包括底层容器类型也必须相同。

定义一个适配器：每个适配器都定义两个构造函数：默认构造函数创建一个空对象，接受一个容器的构造函数拷贝该容器来初始化适配器。
默认情况下，stack和queue是基于deque实现的，priority_queue是在vector之上实现的。我们可以在创建一个适配器时，将一个命名的顺序容器作为第二个类型参数，来重载默认容器类型。
因为所有适配器要求添加删除、访问尾元素操作，所以容器不能用array和forward_list。
stack只要求push_back、pop_back和back,因此可以除array和forward_list之外的任何容器类型来构造stack
queue适配器要求back、push_back、front、push_front，因此他可以构造于list或deque之上，但不能基于vector构造。
priority_queue除了front、push_back、pop_back之外还要求随机访问能力，因此它可以构造于vector或deque之上。但是不能基于list构造。

    deque<int> deq;
    stack<int> stk(deq);

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

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

栈独有操作
栈默认基于deque实现，也可以在list或vector实现
s.pop()	删除栈顶元素，但是不返回该值
s.push(item) s.emplace(args)	创建一个新元素压入栈顶，该元素通过拷贝或移动ite,实现，或者由args构造
s.push(item) s.emplace(args)	创建一个新元素压入栈顶，该元素通过拷贝或移动ite,实现，或者由args构造
s.top()	返回栈顶元素，但不将元素弹出栈

队列适配器：queue和priority_queue适配器定义在queue头文件中

queue和priority_queue独有操作
queue默认基于deque实现，priority_queue默认基于vector实现 queue也可以用list或vector实现，priority_queue也可以用deque实现
q.pop()	弹出queue的首元素或priority_queue的最高优先级的元素，但不返回此元素
q.front()	返回首元素(front)或尾元素(back)，但不删除此元素只适用于queue
q.back()	返回首元素(front)或尾元素(back)，但不删除此元素只适用于queue
q.top()	返回优先级最高的元素，但不删除该元素
q.push(item)	在queue末尾或priority_queue适当位置创建一个元素，其值为item,或有args构造
q.emplace(args)	在queue末尾或priority_queue适当位置创建一个元素，其值为item,或有args构造

queue:FIFO
priority_queue:为队列中元素建立优先级。新加入的元素会排在所有优先级比它自己低的已有元素之前。

九. 泛型算法

顺序容器只定义了很少操作：添加删除等
用户可能还希望其他操作：查找特定元素等。
标准库并未给每个容器都定义成员函数来实现这些操作，而是定义了一组泛型算法：称他们为“算法”，是因为他们实现了一些经典算法的公共接口，如排序和搜索；称他们是“泛型的”，是因为他们可以用于不同类型的元素和多种容器类型(标准库类型和内置数组等),以及我们将看到的，还能用于其他类型的序列。

1. 概述

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

    int val=42;//我们查找的值
    vector<int> vec={0, 42};
    //在vec中查找，则返回结果指向他，否则返回vec.cend()
    /**
     * 标准库算法find:
     * 传递给find的前两个参数是迭代器，第三个参数是查找的值。
     * find将每个元素与给定值比较，返回指向第一个等于给定值的元素的迭代器
     * 若范围无匹配元素，返回第二个参数表示搜索失败
     * 
     * 可以使用find在任何容器查找
     */
    auto result=find(vec.cbegin(), vec.cend(), val);
    int a[10];
    int* result2=find(begin(a), end(a), val);
    auto result3=find(a+1, a+4, val);//在指定范围查找

算法如何工作：为了弄清楚这些算法如何作用于不同类型，更进一步观察find.
[1] 访问序列首元素
[2] 比较此元素与我们要查找的值
[3] 如果此元素与我们要查找的值匹配，则返回标识此元素的值
[4] 否则find前进到下一个元素，重复步骤2，3
[5] 若到达序列尾，find应停止
[6] 如果find到达序列尾，它应返回一个指出元素未找到的值。此值和步骤3的返回值必须有相容类型
这些步骤都不依赖容器所保存的元素类型。因此，只要有一个迭代器可用来访问元素，find就完全不依赖于容器类型(甚至无需理会保存元素的是不是容器)
-
迭代器令算法不依赖于容器，......：在上述find函数流程中，除了第二步，其他步骤可以用迭代器操作来实现。
......，但算法依赖于元素类型的操作：虽然迭代器的使用令算法不依赖于容器类型，但大多数算法都使用了元素类型上的操作(==、>等)。大多数算法提供了一种方法，允许我们使用自定义的操作来代替默认的运算符
泛型算法本身不会执行容器操作，他们只会运行于迭代器上，执行迭代器的操作。这带来一个假定：算法永远不会改变底层容器大小(可能改变值，移动元素，但不会添加删除元素)。
标准库定义了一类特殊迭代器，称为插入器。与普通只能遍历的迭代器比，其能做更多事情。当给这类迭代器赋值时，他门会在底层的容器上执行插入操作。因此，当一个算法操作这样一个迭代器时，迭代器可以完成向容器添加元素的效果，但算法自身永远不会做这样的操作。

2. 初识泛型算法

除了少数例外，标准库算法都对一个范围内的元素进行操作，将此元素范围称作‘输入范围’。接受输入范围的算法总是使用前两个参数表示此范围，这两个参数，分别表示要处理的第一个元素和尾后元素的迭代器。

①只读算法

这些算法只会读取输入范围内的元素，从而不改变元素。
那些只接受一个单一迭代器来表示第二个序列的算法，都假定第二个序列至少与第一个序列一样长。

    //上面的find算法就是只读算法
    /**
     * 另一个只读算法是accumulate,它定义在头文件numeric
     * accumulate函数接受三个参数，前两个指出了需要求和的元素
     * 范围，第三个元素是和的初值
     *
     * 序列中元素的类型必须与第三个参数匹配或者能转换成第三个参数的类型
     */
     vector<int> v(9, 1);
     int sum=accumulate(v.cbegin(), v.cend(), 0);//sum为v中元素和，初值为0
     vector<string> v1={"a", "ab"};
     string s= accumulate(v1.cbegin(), v1.cend(), string(""));
     //第三个参数是""是错误的，const char*没有定义+运算符


     /**
      * 另一个只读算法是equal，用于确定两个序列是否保存相同的值。
      * 它将第一个序列中的每个元素与第二个序列中的对应元素比较，若所有
      * 对应元素都相等返回true, 否则返回false.
      *
      * 此算法接受三个迭代器：前两个表示第一个序列中的元素范围，第三个表示第二个序列的
      * 首元素。
      *
      * 由于equal利用迭代器完成操作，所以我们可以通过调用equal来比较两个不同类型的容器
      * 中的元素。而且，元素类型也不必一样，只要我们能用==来比较两个元素类型即可。
      * 例如在此例中，roster1可以是vector<string>，而roster2是list<const char*>
      *
      * 但是equal基于一个非常重要的假设：它假定第二个序列至少与第一个序列一样长
      */
      equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());

②写容器元素的算法

一些算法将新值赋予序列中元素。当我们使用这类算法时，必须注意确保序列原大小至少不小于我们要求算法写入的元素数目。算法不会执行容器操作，因此他们自身不可能改变容器的大小。
一些算法会自己向输入范围写入元素。这些算法本质并不危险，他们最多写入与给定序列一样多的元素。

    vector<int> v(9, 1);
    fill(v.begin(), v.end(), 0);//将每个元素置为0

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

    vector<int> v1;//空vector
    fill_n(v1.begin(), v1.size(), 0);//将所有元素置为0
    fill_n(v1.begin(), 10, 0);//✖, v1中没有元素，这条语句时未定义的

介绍back_inserter:一种保证算法有足够元素空间来容纳输出数据的方法是使用插入迭代器。插入迭代器是一种向容器中添加元素的迭代器。通常，当我们通过一个迭代器向容器元素内赋值时，值被赋予迭代器指向的元素。而当我们通过一个插入迭代器赋值时，一个与赋值号右侧相等的元素被添加到容器中。
back_inserter是定义在头文件iterator中的一个函数。其接受一个指向容器的引用，返回一个与该容器绑定的插入迭代器。当我们通过此迭代器赋值时，赋值运算符会调用push_back将一个具有给定值的元素添加到容器中

    vector<int> v;//空向量
    auto it= back_inserter(v);//通过它赋值元素将添加到v中
    *it=42;//v中有一个元素，值为42
    
    //我们常常使用back_inserter来创建一个迭代器，作为算法的目的位置来使用
    /**
     * 在每步迭代中，fill_n向给定序列的一个元素赋值。由于我们穿的参数是back_inserter
     * 返回的迭代器，因此每次赋值都会在vec上调用push_back。最终这条fill_n调用语句向v的末尾添加
     * 了10个元素，每个元素值都为0
     */
    fill_n(back_inserter(v), 10, 0);

拷贝算法：拷贝算法是另一个向目的位置迭代器指向的输出序列中的元素写入数据的算法。此算法接受三个迭代器，前两个表示一个输入范围，第三个表示目的序列的起始位置。此算法将输入范围中的元素拷贝到目的序列中。传递给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算法读入一个序列，并将其中所有等于给定值的元素都改为另一个值。此算法接受4个
     * 参数：前两个是迭代器，表示输入序列，后两个一个是要搜索的值，另一个是新值。它将所有等于第一个值的
     * 元素都替换为第二个值
     */
     //将所有值为0的元素改为42
    replace(ilst.begin(), ilst.end(), 0, 42);
    /**
     * 若我们想保留原序列不变，可以调用replace_copy。此算法
     * 接受额外第三个迭代器参数，指出调整后序列的保存位置
     * 
     * ilst并未改变，ivec包含ilst的一份拷贝，不过在ilst中值为0
     * 的元素在ivec中都变为42
     */
     //使用back_inserter按需要增长目标序列
    replace_copy(ilst.cbegin(), ilst.cend(),
                 back_inserter(ivec), 0, 42);

③重排容器元素的算法

某些算法会重排容器中元素的顺序，一个明显的例子是sort，他会重排输入序列中的元素，使之有序，他是利用元素类型的<运算符来实现排序的。
消除重复单词，使用unique：为了消除重复单词，首先将vector排序，使得重复单词都相邻出现。然后使用unique来重排vector，使得不重复的元素出现在vector开始部分。由于算法不能执行容器的操作，我们用vector的erase成员来完成真正的删除操作

    vector<string> words={"a", "ab", "ab"};
    sort(words.begin(), words.end());//按字典序排序
    //重排输入范围，使每个单词只出现一次，排在范围前部。返回指向不重复区域之后一个位置的迭代器
    auto end_unique= unique(words.begin(), words.end());
    //即使没有相同元素，end_unqiue会时words.end()。删除空范围也没事
    words.erase(end_unique, words.end());//删除重复元素

3. 定制操作

很多算法都会比较输入序列中的元素。默认情况下，这类算法使用元素类型的<或==运算符来完成比较。标准库还为这些算法定义了额外版本，允许我们提供自己定义的操作来代替默认运算符。
例如,sort算法默认使用元素类型的<运算符。但是我们希望的排序顺序与<所定义的顺序不同，或是我们的序列保存的是未定义<运算符的元素类型(类类型)。在这两种情况下，都需要重载sort默认行为。

①向算法传递函数

对于vector<string>(不含重复string), 希望内部string按单词长度排序，大小相同再按字典序排序。为了按长度重排vector，我们将使用sort第二个版本，它将接收第三个参数，此参数是一个谓词。
谓词：谓词是一个可调用的表达式，其返回结果是一个能用作条件的值。标准库算法所使用的谓词分为两类：一元谓词(他们只接受单一参数)和二元谓词(他们有两个参数)。接受谓词参数的算法对输入序列中的元素调用谓词。因此，元素类型必须能转换为谓词的参数类型。
在一元谓词中，谓词只接受一个参数，这个参数就是当前元素。容器的每个元素会依次传递给谓词，用于检查条件或进行某些操作。
在二元谓词中，谓词接受两个参数，分别代表正在比较的两个元素。标准算法如 std::sort() 和 std::equal() 使用二元谓词来决定两个元素之间的关系，或定义自定义的比较逻辑。
因此，无论是一元还是二元谓词，参数始终对应当前处理的元素。在一元谓词中，只有一个元素参与判断；在二元谓词中，两个元素参与比较。

    vector<string> words={"a", "ab", "ab"};
    /**
     * 接受一个二元谓词参数的sort版本用这个谓词代替<来比较元素
     */
    sort(words.begin(), words.end(), isShorter);
    
     /**
      * 希望words按大小重排的同时，还具有相同长度的元素按字典序排列
      * 为了保持相同长度单词按字典序排列，可以使用stable_sort算法。
      * 这种稳定排序算法维持相等元素原有顺序
      */
    
    elimDups(words);//将words按字典序重排，并消除重复单词
    //按长度重新排序，长度相同的单词维持字典序
    stable_sort(words.begin(), words.end(), isShorter);

②lambda表达式

根据算法接受一元谓词还是二元谓词，我们传递给算法的谓词必须严格接受一个或两个参数。但是，有时我们希望进行的操作需要更多参数，超出了算法对谓词的限制。
例如，对于上面的按长度重排序程序，我们改为求大于等于一个给定长度的单词有多少。命名此函数为biggies。

bool isShorter(const string &s1, const string &s2)
{
    return s1.size()<s2.size();
}

void biggies(vector<string> &words, vector<string>::size_type sz)
{
    elimDups(words);//将单词按字典序排序并删除重复单词
    stable_sort(words.begin(), words.end(), isShorter);//按长度排序，长度相同维持字典序
    //获取一个迭代器，指向第一个满足size()>=sz的元素
    //计算满足size()>=sz的元素数目
}

可以使用标准库find_if算法来查找第一个大于等于给定长度的元素。find_if接受一对迭代器，表示一个范围。但是与find不同的是，find_if的第三个参数是一个谓词。find_if算法对输入序列中的每个元素调用给定的这个谓词。它返回第一个使用谓词返回非0值的元素的迭代器，若不存在这样的元素返回尾后迭代器(返回第二个迭代器参数)。
编写一个函数，令其接受一个string和一个长度(两个参数)，并返回一个bool值表示该string的长度是否大于给定长度，这是很容易的。但是，find_if接受一元谓词，我们传给find_if的任何函数都必须只有一个参数,没办法接受第二个参数来表示长度。为了解决此问题，我们使用lambda。
介绍lambda:我们可以向一个算法传递任何类别的可调用对象。对于一个对象或一个表达式，如果可以对其使用调用运算符，则称它为可调用的。
到目前为止，使用过的仅有的两种可调用对象是函数和函数指针。还有其他两种可调用对象：重载了函数调用运算符的类和lambda。
一个lambda表达式表示一个可调用的代码单元。我们可以将其理解为一个未命名的内联函数。与任何函数类似，一个lambda具有一个返回类型、一个参数列表和一个函数体。但与函数不同，lambda可能定义在函数内部。一个lambda表达式具有以下形式：

    /**
     * capture list(捕获列表)是一个lambda所在函数中定义的局部变量的列表(通常为空)
     * 
     * return type,parameter list,function body与任何普通函数一样，分别表示
     * 返回类型，参数列表，函数体。
     * 
     * 但是与普通函数不同，lambda必须使用尾置返回来指定返回类型
     * 
     * 我们可以忽略参数列表和返回类型，但必须永远包含捕获列表和函数体
     * lambda中忽略括号和参数列表等价于指定一个空参数列表。
     * 在此例中，当调用f时，参数列表是空的。
     * 如果忽略返回类型，lambda依据函数体的代码推断返回类型
     * 若函数体只是一个return x;则由x推断类型。否则返回类型为void
     */
    [capture list](parameter list) -> return type {function body}
    auto f=[] {return 42;};//定义了一个可调用对象，它不接受参数，返回42
    
    //lambda的调用方式与普通函数一样，都是使用调用运算符
    cout<<f()<<ends;

向lambda传递参数：与普通函数调用类似，调用一个lambda时给定的实参用来初始化lambda的形参。通常实参和形参类型必须匹配。但与普通函数不同，lambda不能有默认参数。因此，一个lambda调用的实参数目永远与形参数目相等。当用于for_each这样的算法时，会根据参数数量，传递对应数量元素作为lambda的参数。

    //比较字符长度
    /**
     * 空捕获列表表名此lambda不使用它所在函数中的任何局部变量
     */
    [](const string &a, const string &b) -> bool
    {
        return a.size()<b.size();
    }

使用捕获列表：

/**
 * 现在可以解决find_if只接受一元谓词的问题了
 * 我们希望表达式能将输入序列中每个string的长度与biggies中的sz值比较
 * 
 * 虽然一个lambda可以出现在一个函数中，使用其局部变量，但他只能使用那些
 * 明确指明的变量。一个lambda通过将局部变量包含在其捕获列表中来指出将会使用这些变量
 * 
 * 本例子中，会捕获sz, 并只有单一string参数
 */
 [sz](const string &a)
 {
     return a.size()>=sz;
 }

调用find_if:

    /**
     * 返回一个迭代器，指向第一个长度不小于给定参数sz的元素
     * 若这样的元素不存在，返回第二个参数的拷贝
     */
    auto wc= find_if(words.begin(), words.end(),
                     [sz](const string &a){return a.size()>=sz});

for_each算法：此算法接受一个可调用对象，并对输入序列中每个元素调用此对象
捕获列表只用于局部非static变量，lambda可以直接使用局部static变量
和它所在函数之外声明的名字。

    //打印长度大于给定值的单词
    /**
     * s是自己的参数
     * 一个lambda可以使用定义在当前函数之外的名字
     * cout是定义在头文件iostream中的
     * 因此，只要在biggies出现的作用域中包含了头文件iostream，lambda就
     * 可以使用cout
     */
    for_each(wc, words.end(), 
             [](const string &s){cout<<s<<" ";});

完整biggies:

void biggies(vector<string> &words, vector<string>::size_type sz)
{
    elimDups(words);//将单词按字典序排序并删除重复单词
    //按长度排序，长度相同维持字典序
    stable_sort(words.begin(), words.end(),
                [](const string &a, const string &b){return a.size()<b.size();});

    //获取一个迭代器，指向第一个满足size()>=sz的元素
    //计算满足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;
    //打印长度大于等于给定值的单词
    for_each(wc, words.end(),
             [](const string &s){cout<<s<<" ";});
}

③lambda捕获和返回

当定义一个lambda时，编译器生成一个与lambda对应的新的(未命名)类类型。
目前，可以这样理解，当向一个函数传递一个lambda时，同时定义了一个新类型和该类型的一个对象：传递的参数就是此编译器生成的类类型的未命名对象。类似的，当使用auto定义一个用lambda初始化的变量时，定义了一个从lambda生成的类型的对象。默认情况下，从lambda生成的类都包含一个对应该lambda所捕获的变量的数据成员。类似任何普通类的数据成员，lambda的数据成员也在lambda对象创建时被初始化。

lambda捕获列表
[]	空捕获列表。lambda不能使用所在函数中的变量。一个lambda只有捕获变量后才能使用它们
[names]	names是一个逗号分隔的名字列表，这些名字都是lambda所在函数的局部变量。默认情况下，捕获列表中的变量都被拷贝。名字前如果使用了&，则采用引用方式使用
[&]	隐式捕获列表，采用引用捕获方式。lambda体中所使用的来自所在函数的实体都采用引用方式使用
[=]	隐式捕获列表，采用值捕获方式。lambda将拷贝所使用的来自所在函数的实体的值
[&, identifier_list]	identifier_list是一个逗号分隔的列表，包含0个或多个来自所在函数的变量。这些变量采用值捕获方式，而任何隐式捕获的变量都采用引用方式捕获。identifier_list中的名字前不能使用&。
[=, identifier_list]	identifier_list中的变量都采用引用方式捕获，而任何隐式捕获的变量都采用值方式捕获。identifier_list中的名字不能包括this，且这些名字前必须使用&。

值捕获：类似参数传递，变量的捕获方式也可以是值或引用。与传值参数类似，采用值捕获的前提是变量可以拷贝。与参数不同，被捕获的变量的值是在lambda创建时拷贝，而不是调用时拷贝。

void fnc1()
{
    size_t v1=42;//局部变量
    //将v1拷贝到名为f的可调用对象
    auto f=[v1] {return v1;};
    v1=0;
    auto j=f();//j为42;由于被捕获的值是在lambda创建时拷贝，所以后面的修改不会影响lambda内对应的值
}

引用捕获:引用捕获与返回引用有着相同限制。若我们采用引用方式捕获一个变量，就必须确保被引用对象在lambda执行的时候是存在的。lambda捕获的是局部变量，这些变量在函数执行完毕后就不存在了。如果lambda可能在函数结束后执行，捕获的引用指向的局部变量已经消失。

void fnc2()
{
    size_t v1=42;//局部变量
    //将v1拷贝到名为f的可调用对象
    auto f=[&v1] {return v1;};
    v1=0;
    auto j=f();//j为0;f2保存v1的引用而非拷贝
    /**
     * 当我们在lambda函数体使用v1时，实际上使用的是v1所绑定的对象
     */
}

引用捕获有时是必要的。比如流对象os，不能被拷贝，所以只能通过
获得其引用或指针对象。
for_each(words.begin(), words.end(),
         [&os, c](const string &s){os<<s<<c;});

隐式捕获：除了显式列出我们希望使用的来自所在函数的变量外，还可以让编译器根据lambda体中的代码来推断我们要使用哪些变量。为了指示编译器推断捕获列表，应在捕获列表中写一个=或&。=表示采用值捕获, &表示采用引用捕获。如果希望对一部分变量采用值捕获，对其他变量采用引用捕获。可以混合使用隐式捕获和显式子捕获。如上表所示。

可变lambda:默认情况，对于一个值被拷贝的变量，lambda不会改变其值。若希望能改变一个被捕获的变量的值，就必须在参数列表首加上关键字mutable。因此，可变lambda能省略参数列表。

void fnc3()
{
    size_t v1=42;//局部变量
    //f可以改变它所捕获的变量的值, 没有mutable， ++v1会报错
    auto f=[v1]()mutable{return ++v1;};
    v1=0;
    auto j=f();//j为43
}

一个引用捕获的变量是否可以修改，依赖于此引用指向的是一个const类型还是非const类型。

void f4()
{
    size_t v1=42;//局部变量
    //v1是一个非const变量的引用
    //可以通过f2中的引用改变它
    auto f2=[&v1]{return ++v1;};
    v1=0;
    auto j=f2();//j为1
}

指定lambda返回类型：之前的lambda语句都只包含单一的return语句(此时编译器可以推断返回类型)。因此，我们还未遇到必须指定返回类型的情况。默认情况，如果一个lambda体包含return 之外的任何语句，则编译器假定此lambda返回void。与返回void的函数类似，被推断返回void的lambda不能返回值。

    vector<int> v;
    /**
     * 使用标准库transform算法和一个lambda将一个序列中每个负数替换为绝对值
     * 
     * 函数transform接受三个迭代器和一个可调用对象。前两个迭代器表示输入序列。
     * 第三个迭代器表示目的地位置。算法对输入序列中每个元素调用可调用对象，并将
     * 结果写到目的位置。
     * 
     * 而本例子中，输入序列起始位置，和目的位置相同，所以相当于替换原序列
     * 本例子单一返回语句可以推断出是什么类型
     */
    transform(v.begin(), v.end(), v.begin(),
              [](int i){return i<0?-i:i;});

    //✖，不能推断lambda类型。编译器推断lambda返回void类型，但他返回int
    transform(v.begin(), v.end(), v.begin(),
              [](int i){if(i<0) return -i;else return i;});
    
    //✔，当我们需要为一个lambda返回类型时，必须使用尾置返回类型
    transform(v.begin(), v.end(), v.begin(),
              [](int i) -> int 
              {if(i<0) return -i;else return i;});

④参数绑定

对于那种只在一两个地方使用的简单操作，lambda是最有用。如果我们需要
在很多地方使用相同操作，通常应该定义一个函数，而不是多次编写相同的
lambda表达式。类似，如果一个操作需要很多语句才能完成，通常使用函数更好。
如果lambda的捕获列表为空，通常可以使用函数代替它。
但是对于捕获局部变量的lambda，很难用函数代替。例如，上面的find_if只能接受一个一元谓词，但是有时需要两个参数的函数，此时只能用lambda来获得两个参数。

/**
 * 下面这个函数就不能作为find_if的参数,他是二元谓词
编写一个函数，令其接受一个string和一个长度(两个参数)，并返回一个bool值表示该string的长度是否大于给定长度，这是很容易的。但是，find_if接受一元谓词，我们传给find_if的任何函数都必须只有一个参数,没办法接受第二个参数来表示长度。为了解决此问题，我们使用lambda。
 * 我们是查找字符串中>=sz的长度的位置
 */
bool check_size(const string &s, string::size_type sz)
{
    return s.size()>=sz;
}

为了使用check_size来代替lambda，必须解决如何向sz形参传递一个参数的问题
标准库bind函数：我们可以解决向check_size传递一个长度参数的问题，方法是使用一个新的名为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表示
生成的可调用对象参数的位置；_1为newCallable的第一个参数；_2为第二个参数。

绑定check_size的sz参数：使用bind生成一个调用check_size的对象。

bool check_size(const string &s, string::size_type sz)
{
    return s.size()>=sz;
}

int main(int argc, char *argv[])
{
    //check6是一个可调用对象，接受一个string类型的参数
    //并用此string和值6来调用chek_size
    /**
     * 此bind调用只有一个占位符，表示check6只接受单一参数。
     * 占位符出现在arg_list的第一个位置，表示check6的此参数
     * 对应check_size的第一个参数。此参数是一个const string&
     * 因此，调用check_size必须传递给它一个string类型的参数，
     * check6会将此参数传给check_size
     * 
     * 名字_n都定义在一个名为placeholders的命名空间中，而这个命名空间
     * 本身定义在std命名空间中。
     * using std::placeholders::_1;
     * 
     * 对于每个占位符，使用上述声明麻烦。可以使用下述形式：
     * using namespace namespace_name;
     * 这种形式是说说明希望来自namespace_name的名字
     * 都可以在我们的程序中直接使用
     */
    auto check6=bind(check_size, std::placeholders::_1, 6);
    string s="hello";
    bool b1=check6(s);//check6会调用check_size(s, 6)

    using namespace std::placeholders;
    //改变原lambda的调用
    auto wc=find_if(words.begin(), words.end(), 
                    [sz](const string &a){return a.size()>=sz;});
    //生成一个Bind可调用对象, 将check_size的第二个参数绑定到sz的值
    //当find_if对words中的string调用这个对象时，这些对象会调用check_size
    //将给定的string和sz传递给他。
    auto wc=find_if(words.begin(), words.end(),
                    bind(check_size, _1, sz));
}

bind的参数：

/**
 * 上面，可以用bind修正参数的值。更一般的，可以用bind绑定给定可调用对象中
 * 的参数或重新安排其顺序。例如，假定f是一个可调用对象，他有五个参数
 * 
 * 对bind的调用，生成一个新的可调用对象，他有两个参数，分别用占位符_2和_1
 * 表示。这个新的可调用对象将它自己的参数作为第三个、第五个参数传递给f。f的
 * 第一个、第二个、第四个参数分别被绑定到给定的值a、b和c上
 * 
 * 传递给g的参数按位置绑定到占位符。即，第一个参数绑定到_1, 第二个参数绑定到_2
 * 因此，当我们调用g时，第一个参数被传递给f最后一个作为参数，第二个参数被传递
 * 给f作为第三个参数
 * g(_1, _2)->f(a, b, _2, c, _1)
 */
 //g是一个有两个参数的可调用对象
 auto g=bind(f, a, b, _2, c, _1);

用bind重排参数顺序：

bool isShorter(const string &a, const string &b)
{
    return a.size()<=b.size();
}

int main(int argc, char *argv[])
{
    vector<string> words;
    //sort重载<
    //按单词长度由短至长排序
    sort(words.begin(), words.end(), isShorter);
    //按单词长度由长至短排序
    sort(words.begin(), words.end(), bind(isShorter, _2, _1));
    /**
     * 第一个调用，sort需要比较两个元素A、B时，他会调用isShorter(A, B)
     * 第二个调用, 传递给isShorter被交换过来了，isShorter(B, A)
     */
}

绑定引用参数：默认情况下，bind的那些不是占位符的参数被拷贝到bind返回的可调用对象中。但是与lambda相似，有时对有些绑定的参数我们希望以引用的方式传递，或者是要绑定的类型无法拷贝。

vector<string> words;

ostream &print(ostream &os, const string &s, char c)
{
    return os<<s<<c;
}

int main(int argc, char *argv[])
{
    //例如，为了替换一个引用方式捕获ostream的lambda
    for_each(words.begin(), words.end(),
             [&os, c] (const string &s) {os<<s<<c;});

    //可以很容易编写一个函数，完成相同工作, 但是不能直接用bind代替对os的捕获
    //下面✖，原因在于bind拷贝其参数, 而我们不能拷贝一个ostream
    for_each(words.begin(), words.end(), bind(print, os, _1, ' '));
    
    //若希望传递给bind一个对象而不拷贝它，就必须使用标准库ref函数
    //函数ref返回一个对象，包含给定的引用，此对象是可以拷贝的。
    //标准库还有一个cref函数，生成一个保存const引用的类。
    //与bind相同, 函数ref和cref都定义在头文件functional
    for_each(words.begin(), words.end(),
             bind(print, ref(os), _1, ' '));
}

4. 再探迭代器

除了为每个容器定义的迭代器外，标准库在头文件iterator中还定义了额外几种迭代器。
插入迭代器：这些迭代器被绑定到一个容器上，可用来向容器插入元素。
流迭代器：这些迭代器被绑定到输入或输出流上，可以用来遍历所关联的IO流。
反向迭代器：这些迭代器向后而不是向前移动。除了forward_list之外的标准库容器都有反向迭代器。
移动迭代器：这些专用的迭代器不是拷贝其中的元素，而是移动他们。

①插入迭代器

插入器是一种迭代器适配器，它接受一个容器，生成一个迭代器，能实现向给定容器添加元素。当我们通过一个插入迭代器进行赋值时，该迭代器调用容器操作来向给定容器的指定位置插入一个元素。

插入迭代器操作
it=t	在it指定的当前位置插入值t。假定c是it绑定的容器，依赖于插入迭代器的不同种类，此赋值会分别调用c.push_back(t)、c.push_front(t)、c.insert(t, p),其中 p为传递给inserter的迭代器位置。
*it, ++it, it++	这些操作虽然存在，但是不会对it做任何事情。每个操作都返回it。

插入器有三种类型，差异在于元素插入的位置：
back_inserter创建一个使用push_back(容器要支持)的迭代器。
front_inserter创建一个使用push_front(容器要支持)的迭代器
inserter创建一个使用insert的迭代器。此函数接受两个参数，这个参数必须是一个指向给定容器的迭代器。元素被插入到给定迭代器所表示的元素前。
当调用inserter(c, iter)时，我们得到一个迭代器接下来使用它时，会将元素插入到iter~~原来所指向~~的元素之前的位置

    *it=val;
    //等价于上面
    it=c.insert(it, val);//it指向新加入的元素
    ++it;//递增it使它指向原来的元素

    list<int> lst={1, 2, 3, 4};
    list<int> lst2, lst3;//空
    //拷贝完成后，lst2包含4 3 2 1, copy第三个参数是目的位置的起始位置
    copy(lst.cbegin(), lst.cend(), front_inserter(lst2));
    //拷贝完成后，lst3包含1 2 3 4。Push_back也不会颠倒
    copy(lst.cbegin(), lst.cend(), inserter(lst3, lst3.begin()));

②iostream迭代器

虽然iostream类型不是容器，但标准库定义了可以用于这些IO类型对象的迭代器。istream_iterator读取输入流,ostream_iterator向一个输出流写数据。这些
迭代器将它们对应的流当作一个特定类型的元素序列来处理。通过使用流迭代器，我们可以用泛型算法从流对象读取数据以及向其写入数据。

istream_iterator
istream_iterator<T> in(is);	in从输入流is读取类型为T的值
istream_iterator<T> end;	读取类型为T的值的istream_iterator迭代器，表示尾后位置
in1==in2; in1!=in2	in1和in2必须读取相同类型。如果他们都是尾后迭代器，或绑定到相同的输入，则两者相等
*in	返回从流中读取的值
in->mem	与(*in).mem含义相同
++in, in++	使用元素类型所定义的>>运算符从输入流中读取下一个值。与以往一样，前置版本返回一个指向递增后迭代器的引用，后置版本返回旧值。

    /**
     * 当创建一个流迭代器时，必须指定迭代器将要读写的对象类型。
     * 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"读取字符串

    //下面是一个用istream_iterator从标准输入读取数据，存入一个vector
    vector<int> v;
    istream_iterator<int> in_iter(cin);//从cin读取int
    istream_iterator<int> eof;//尾后迭代器
    while(in_iter!=eof)//当有数据可供读取时
    {
        //后置递增运算符读取流，返回迭代器旧值
        //解引用迭代器，获得一个从流读取的前一个值
        //*和++都是右结合律, 但是++比*优先级高, ++是后置返回旧迭代器
        v.push_back(*in_iter++);
    }
    
    /**
     * 重写上面程序为下面,体现istream_iterator优越性
     * 
     * 使用一对表示元素范围的迭代器来构造v1.这两个迭代器是
     * istream_iterator，表示元素范围是从关联的流中读取数据
     * 获得的。这个构造函数从cin读取数据，直到遇到文件尾或者一个不是int的
     * 数据为止
     */
     vector<int> v1(in_iter, eof);

使用算法操作流迭代器：

    istream_iterator<int> in(cin), eof;
    //此调用会从标准输入流读取值的和
    cout<<accumulate(in, eof, 0)<<endl;

istream_iterator允许使用懒惰求值：当我们istream_iterator绑定到一个流时，标准库并不保证立即从流读取数据。具体实现可以推迟从流读取数据，直到我们使用迭代器时才真正读取。标准库中的实现所保证的是，在我们第一次解引用迭代器前，从流中读取数据的操作已经完成了。对于大多数程序来说，立即读取还是推迟读取没什么差别。但是，如果我们创建了一个istream_iterator
，没有使用就销毁了，或者我们正在从两个不同的对象同步读取一个流，那么何时读取就很重要了。
ostream_iterator操作：我们可以对任何具有输出运算符(<<运算符)的类型定义ostream_iterator。当创建一个ostream_iterator时，我们可以提供(可选)第二参数，他是一个字符串，在输出每个元素后都会打印此字符串。此字符串必须是一个C风格字符串(一个字符串字面常量或者一个指向以空字符结尾的字符数组的指针)。必须将ostream_iterator绑定到一个指定的流，不允许空的或表示尾后位置的ostream_iterator

ostream_iterator操作
ostream_iterator<T> out(os)	out将类型为T的值写到输出流os中
ostream_iterator<T> out(os, d)	out将类型为T的值写到输出流os中，每个值后面都输出一个d。d指向一个空字符结尾的字符数组
out=val	用<<运算符将val写入到out所绑定的ostream中。val的类型必须与out可写的类型兼容
*out、++out、out++	不对out做任何事情，返回out

    //我们可以用ostream_iterator来输出值的序列
    vector<int> v={1, 2, 3};
    ostream_iterator<int> out_iter(cout, " ");
    //此程序将v中的每个元素写到cout，每个元素后加一个空格.每次向out_iter赋值
    //时，写操作就会被提交
    for(auto e:v) out_iter=e;//或*out_iter++=e;打印1 2 3
    cout<<endl;
    //可以通过调用copy来打印v中元素，比循环更简单
    copy(v.cbegin(), v.cend(), out_iter);//打印1 2 3

使用流迭代器处理类类型：只要类类型定义了输入运算符(>>)和输出运算符(<<), 就可以定义对应的流迭代器，并使用流迭代器的操作。
在 C++ 中，为类类型定义输入运算符 (>>) 和输出运算符 (<<) 通常是通过重载这两个运算符来实现的。这些运算符通常被定义为友元函数，以便能够访问类的私有和受保护成员。

③反向迭代器

反向迭代器是在容器中从尾元素向首元素反向移动的迭代器。对于反向迭代器，递增递减操作的含义会颠倒过来。递增一个反向迭代器(++it)会移动到前一个元素；递减一个迭代器(--it)会移动到下一个元素。除了forward_list外，其他容器都支持反向迭代器。通过rbegin、rend、crbegin、crend成员函数来获得反向迭代器，返回首前元素和尾元素。

    vector<int> v={0, 1, 2, 3, 4, 5};
    //从尾元素反向迭代
    for(auto r_iter=v.crbegin();r_iter!=v.crend();++r_iter)
        cout<<*r_iter<<endl;//5 4 3....1 0
        
    //虽然颠倒递增和递减运算符含义含义可能令人混淆，但是可以让算法透明的向前或向后处理容器
    //可以通过向sort传递反向迭代器，使其成为递减序
    sort(v.begin(), v.end());//递增序
    sort(v.rbegin(), v.rend());//递减序，从后往前是递增

反向迭代器需要递减运算符：只能从既支持++也支持--的迭代器来定义反向迭代器。除forward_list外，标准容器上的其他迭代器都支持++和--运算符。但是流迭代器不支持--因为不可能在一个流中反向移动。因此，不可能从一个forward_list或一个流迭代器创建反向迭代器。
反向迭代器和其他迭代器间的关系：

    string line="first,middle,last";
    //我们希望找到line中第一个单词
    auto comma=find(line.cbegin(), line.cend(), ',');
    cout<<string(line.cbegin(), comma)<<endl;

    //希望打印最后一个单词, 从最后一个字符往前搜
    auto rcomma=find(line.crbegin(), line.crend(), ',');
    cout<<string(line.crbegin(), rcomma)<<endl;//✖，将输出逆序，tsal
    
    /**
     * 因为我们使用的是反向迭代器，会反向处理string
     * 我们希望正序打印，则要将反向迭代器rcomma转化为正常的迭代器
     * 通过调用reverse_iterator的base成员函数来完成，此成员函数
     * 会返回其对应的普通迭代器
     * 
     * 为了实现左闭合区间，rcomma和rcomma.base()生成的是相邻位置
     */
     cout<<string(rcomma.base(), line.cend())<<endl;//last

5. 泛型算法结构

算法所要求的迭代器操作可分为5个迭代器类别。

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

第二种算法分类的方式是按是否读、写或重排序列中的元素来分类。

①5类迭代器

类似容器，迭代器也定义了一组公共操作。一些操作所有迭代器都支持，另外
一些只有特定类别的迭代器才支持。迭代器按它们所提供的操作来分类，这种分类形成了一种层次，一个高层次类别的迭代器支持低层次类别迭代器的所有操作。
C++标准指明了泛型和数值算法的每个迭代器的最小类别。例如find算法在一个序列上进行一遍扫描，对元素进行只读操作，因此至少需要输入迭代器(单扫，只能递增)。
对于向算法传递错误类别的迭代器问题，很多编译器不会给任何警告或提示。
输入迭代器：可以读取序列中的元素。输入迭代器只用于顺序访问。对于一个输入迭代器*it++是有效的，但递增它可能导致所有其他指向流的迭代器失效。因此，输入迭代器只能用于单遍扫描算法。算法find和accumulate要求输入迭代器；而istream_iterator是一种输入迭代器。一个输入迭代器必须支持：
[1] 用于比较两个迭代器的相等和不相等运算符：==和!=
[2] 用于推进迭代器的前置和后置递增运算符(++)
[3] 用于读取元素的解引用运算符(*)；解引用只会出现在赋值运算符的右侧。
[4] 箭头运算符(->)，等价于(*it).member，即，解引用迭代器，并提取对象的成员。
-
输出迭代器：可以看作输入迭代器功能上的补集---只写不读元素。我们只能向一个输出迭代器赋值一次。类似输入迭代器，输出迭代器只能单遍扫描。例如copy函数第三个参数就是输出迭代器。ostream_iterator类型也是输出迭代器。输出迭代器必须支持以下操作：
[1] 用于迭代器的前置和后置递增运算符(++)
[2] 解引用运算符(*)，只出现在赋值运算符左侧
-
前向迭代器：可以读写元素。这类迭代器只沿一个方向移动。前向迭代器支持所有输入和输出迭代器的操作，而且可以多次读写同一个元素。因此，我们可以保存前向迭代器的状态，使用前向迭代器的算法可以对序列多次扫描。算法replace要求前向迭代器，forward_list上的迭代器是前向迭代器。
双向迭代器：可以正向/反向读写序列中的元素。除了支持所有前向迭代器操作外，双向迭代器还支持前置和后置递减运算符。算法reverse要求双向迭代器，除了forward_list外，其他标准款都提供符合双向迭代器要求的迭代器。
随机访问迭代器：提供在常量时间内访问序列中任意元素的能力。算法sort要求随机访问迭代器。array、deque、string和vector的迭代器都是随机访问迭代器，用于访问内置数组元素的指针也是。此类迭代器支持双向迭代器的所有功能。此外还支持第二章第4.2表中所有操作：
[1] 比较两个迭代器相对位置:<,<=,>,>=
[2] 迭代器和一个整数值的加减运算(+,+=,-,-=),计算结果是迭代器在序列中前进后退给定整数个元素后的位置
[3] 用于两个迭代器的减法，得到两个迭代器距离
[4] 下标运算符(iter[n])，与*(iter[n])等价

②算法形参模式

在任何其他算法分类上，还有一组参数规范。大多数算法具有以下4种
形式。

    /**
     * 其中alg是算法的名字，beg和end表示算法所操作的输入范围。
     * dest指目的地
     * beg2和end2指第二个范围
     * other args只非特定参数
     */
    alg(beg, end, other args);
    alg(beg, end, dest, other args);
    alg(beg, end, beg2, other args);
    alg(beg, end, beg2, end2, other args);

接受单个目标迭代器的算法：dest参数是一个表示算法可以写入的目的位置的迭代器。算法假定：按其需要写入的数据不管写入多少个元素都是安全的(目的容量够)。dest可被绑定到插入迭代器(可保证空间足够)或ostream_iterator(写入到输出流，因此写多少元素都行)
接受第二个输入序列的算法：接受单独的beg2或beg2和end2的算法，用这些迭代器表示第二个输入范围。接受单独beg2的算法假定从beg2开始的范围和beg、end表示的范围至少一样大

③算法命名规范

除了参数规范，算法还遵循一套命名和重载规范。如；如何提供一个默认
操作代替默认<或==运算符以及算法是将输出数据写入输入序列还是一个
分离的目的位置。
一些算法使用重载形式传递一个谓词：

/**
 * 接受谓词参数来代替<或==运算符的算法，以及那些不接受额外参数的算法，
 * 通常都是重载函数。函数的一个版本用元素类型的运算符来比较元素；另一个
 * 版本接受一个额外谓词来代替<或==
 * 
 * 由于两个版本参数个数不同，所以调用不会产生歧义
 */
 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(v1.begin(), v1.end(),
               [](it i){return i%2;});
     //将偶数元素重v1拷贝到v2;v1不变
    remove_copy_if(v1.begin(), v1.end(), back_inserter(v2),
                   [](int i){return i%2==0;});

6. 特定容器算法

与其他容器不同，链表类型list和forward_list定义了几个成员函数形式的算法。通用版本的sort要求随机访问迭代器，因此不能用于list和forward_list，因为这两个类型分别提供双向迭代器和前向迭代器。
链表定义的其他算法的通用版本可以用于链表，但代价太高。
对于list和forward_list应该优先使用成员函数版本算法而非通用算法

list和forward_list成员函数版本的算法
这些操作都返回void
lst.merge(lst2) lst.merge(lst2, comp)	将来自lst2的元素合并入lst。lst和lst2都必须是有序的。元素将从lst2中删除。在合并后lst2变为空。第一个版本使用<运算符；第二个版本使用给定的比较操作
lst.remove(val) lst.remove_if(pred)	调用erase删除与给定值相等或令一元谓词为真的每个元素
lst.reverse()	翻转lst中元素
lst.sort() lst.sort(comp)	使用<或给定比较操作排序元素
lst.unique() lst.unique(pred)	调用erase删除同一个值的连续拷贝。第一个版本使用==, 第二个版本使用二元谓词

splice成员：链表还定义了splice算法，此算法是链表数据结构特有的，不需要通过通用版本。

list和forward_list的splice成员函数的参数
lst.splice(args)或flst.splice_after(args)
(p, lst2)	p是一个指向lst中元素的迭代器，或一个指向flst首前位置的迭代器。函数将lst2的所有元素移动到lst中p之前的位置或是flst中p之后的位置。将元素从lst2中删除。lst2的类型必须与lst或flst相同，且不能是同一个链表。
(p, lst2, p2)	p2是一个指向lst2中位置的有效迭代器。将p2指向的元素移动到lst中，或将p2之后的元素移动到flst中。lst2可以是与lst或flst相同的链表
(p, lst2, b, e)	b、e必须表示lst2合法范围。将给定元素从lst2移动到lst或flst。lst2与lst(flst)可以是相同链表，但p不能指向给定范围中元素

链表特有的操作会改变容器：多数链表特有算法与通用版本相似，但不完全相同。链表特有版本与通用版本一个区别是：链表版本会改变底层容器。例如remove链表版本会删除指定的元素。unique链表版本会删除第二个和后继重复元素。类似的merge和splice会销毁其参数。

十. 关联容器

关联容器支持高效的关键字查找和访问。两个主要关联容器类型是map和set。map中的元素是关键字-值：关键字起索引，值是数据。set中每个元素只包含一个关键字。类型map和multimap定义在头文件map中；set和multiset定义在头文件set;无序容器定义在头文件unordered_map和unordered_set。

关联容器类型
按关键字有序保存元素
map	关联数组；保存键值对
set	关键字就是值，只保存关键字
multimap	关键字可重复出现的map
multiset	关键字可重复出现的set
无序集合
unordered_map	用哈希函数组织的map
unordered_set	用哈希函数组织的set
unordered_multimap	哈希组织的map;关键字可重复出现
unordered_multiset	哈希组织的set;关键字可重复出现

1. 使用关联容器

    //统计每个单词在输入中出现的次数, 单词按字典序排列
    map<string, size_t> word_count;
    string word;
    while(cin>>word) ++word_count[word];
    /**
     * 当从map中提取一个元素时，会得到一个pair类型的对象
     * pair是一个模板类型，保存两个名为first和second的(公有)
     * 数据成员。map所用的pair用first成员保存关键字，用second
     * 保存值
     */
    for(const auto &w:word_count)
        cout<<w.first<<" "<<w.second<<endl;
    word_count.clear();


    //可以用set保存想忽略的词
    set<string> exclude={"the", "or", "and"};
    while(cin>>word)//若关键字在set中返回指向该关键字的迭代器，否则返回尾后迭代器
        if(exclude.find(word)==exclude.end())
            ++word_count[word];

2. 关联容器概述

关联容器都支持第八章第2节所列的普通容器操作，但不支持顺序容器位置
相关的操作，例如push_back。因为关联容器中的元素是根据关键字存储的，
这些操作对关联容器没有意义。
除了与顺序容器相同的操作外，关联容器还支持一些顺序容器不支持的操作和类型别名。此外，无序容器还提供一些用来调整哈希性能的操作。关联容器的迭代器都是双向的。

①定义关联容器

定义map要指明建和值的类型，set要指明键的类型。

    map<string, size_t> word_count;
    //列表初始化
    set<string> exclude={"the", "but"};
    //三个元素；姓映射为名
    map<string, string> authors={{"w", "wcc"},
                                 {"z", "xcc"}};

初始化multimap或multiset:此类关联容器允许关键字重复。

    //定义一个有20个元素的vector，保存0到9每个整数的两个拷贝
    //我们将使用此vector初始化一个set和一个multiset
    vector<int> v;
    for(int i=0;i<10;++i)
    {
        v.push_back(i);
        v.push_back(i);
    }
    
    set<int> iset(v.cbegin(), v.cend());
    multiset<int> miset(v.cbegin(), v.cend());
    cout<<v.size()<<" "<<iset.size()<<" "<<miset.size();//20 10 20

②关键字类型的要求

关联容器对其关键字的类型有一些限制。对于无序容器将在后面介绍。对于有序容器，关键字必须定义元素比较的方法。默认情况下，标准库使用关键字类型的<运算符来比较两个关键字。(传递给排序算法的可调用对象必须满足与关联容器中关键字一样的类型要求)
有序容器的关键字类型：可以向一个算法提供自己定义的比较操作，与之类似，也可以提供自己定义的操作来代替关键字上的<运算符。如果一个类型定义了<运算符，则它可用作关键字类型。所提供的操作必须在关键字类型上定义一个严格弱序即<=。比较函数必须具有如下性质：
[1] 两个关键字不能同时<=对方
[2] k1<=k2, k2<=k3则k1<=k3
[3] 如果两个关键字，任何一个都不小于等于另一个，则说这两个关键字是等价的。若两个关键字等价，容器将它们视作相等处理。当用作map关键字时，只能有一个元素与这两个关键字关联，我们可以使用两者中任何一个访问对应值。
-
使用关键字类型的比较函数：用来组织一个容器中元素的操作的类型也是该容器的一部分。为了指定自定义操作，必须在定义关联容器类型时提供此操作的类型。用尖括号指出要定义哪种类型，自定义的操作类型必须在尖括号中紧跟着元素类型给出。在尖括号中出现的每个类型，仅仅是一个类型。当创建一个容器(对象)时，才会以构造函数参数的形式提供真正的比较操作。

/**
 * 我们不能直接定义一个Sales_data的multiset，
 * 因为Sales_data没有<运算符。但是可以用下面的
 * 比较函数定义一个multiset,此函数定义了isbn成员
 * 的严格弱序
 */
bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs)
{
    return lhs.isbn()<rhs.isbn();
}

int main(int argc, char *argv[])
{
    /**
     * 为了使用自己定义的操作，在定义multiset时我们必须提供两个类型：
     * 关键字类型Sales_data，以及比较操作类型：是一种函数指针类型，可以
     * 指向compareIsbn。当定义次此类容器的对象时，需要提供想要使用的操作的指针
     *
     * 可以用compareIsbn代替&compareIsbn作为构造函数的参数，因为当我们使用
     * 一个函数名字时，在需要的情况下他可以转化为一个指针
     */                                                  //&compareIsbn
     multiset<Sales_data, decltype(compareIsbn)*> bookstore(compareIsbn);
}

③pair类型

pair标准库类型，它定义在头文件utility中。pair的数据成员是public的

pair上的操作
pair<T1, T2> p;	p是一个pair，两个类型分别为T1和T2的成员都进行了值初始化。
pair<T1, T2> p(v1, v2)	p是一个成员类型为T1和T2的pair;first和second成员分别用v1和v2进行初始化。
pair<T1, T2> p={v1, v2};	等价于p(v1, v2)
make_pair(v1, v2)	返回一个用v1和v2初始化的pair。pair的类型从v1、v2的类型推断出来。
p.first	返回p的名为first的(公有)数据成员
p.second	返回p的名为second的(公有)数据成员
p1 relop p2	关系运算符(<,<=,>,>=)按字典序定义。例如：当p1.first<p2.first或!(p2.first<p1.first)&&p1.second<p2.second成立时，p1<p2为true。利用元素的<运算符来实现
p1==p2 p1!=p2	当first和second成员分别相等时，两个pair相等。相等性判断利用元素的==运算符实现。

    pair<string, vector<int>> line;
    pair<string, string> author{"zxx", "ass"};

创建pair对象的函数：

pair<string, int> process(vector<string> &v)
{
    if(!v.empty()) return {v.back(), v.back().size()};//列表初始化
    else return pair<string, int>();//隐式构造返回值
    
    /**
     * 较早C++版本中不允许{}包围的初始化器返回pair这种类型对象，
     * 必须显式构造返回值。或用make_pair
     */
    return pair<string, int>(v.back(), v.back().size());
    return make_pair(v.back(), v.back().size());
}

3. 关联容器操作

除了第八章第2中列出的类型，关联容器还定义了下面的类型，这些类型表示容器关键字和值的类型。

关联容器额外的类型别名
key_type	此容器类型的关键字类型
mapped_type(只有map类型有)	每个关键字关联的类型。只适用于map
value_type	对于set，与key_type相同对于map，为pair<const key_type, mapped_type>

关联容器额外的类型别名

key_type

此容器类型的关键字类型

mapped_type(只有map类型有)

每个关键字关联的类型。只适用于map

value_type

对于set，与key_type相同

对于map，为pair<const key_type, mapped_type>

    //使用域作用符来提取一个类型的成员
    map<string, int>::key_type;
    set<string>::value_type v1;//v1是一个一个string
    set<string>::key_type v2;//v2是一个string
    map<string, int>::value_type v3;//v3是一个pair<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，我们可以改变pair的值，但不能改变关键字成员的值(常量).

    map<string, int> word_count;
    //获得指向word_count中一个元素的迭代器
    auto map_it=word_count.begin();
    //*map_it是指向一个pair<const string, size_t>对象的引用
    cout<<map_it->first<<" "<<map_it->second;
    map_it->first="x";//✖，常量无法改变
    ++map_it->second;//✔

set的迭代器是const的:

    /**
     * 虽然set类型同时定义了iterator和const_iterator类型，
     * 但两种类型都只允许只读访问set中的元素。与map关键字一样，set中
     * 的关键字也是const的
     */
     set<int> iset={0, 1, 2};
     set<int>::iterator set_it=iset.begin();
     if(set_it!=iset.end())
         cout<<*set_it<<endl;

遍历关联容器：本程序的输出是按字典序排列的。当使用一个迭代器遍历一个map、multimap、set、multiset时，迭代器按关键字升序遍历元素。

    map<string, int> map_count;
    auto map_it=map_count.begin();
    while(map_it!=map_count.end())
    {
        cout<<map_it->first<<" "<<map_it->second<<endl;
        ++map_it;
    }

关联容器和算法：通常不对关联容器使用泛型算法。关键字是const这一特性意味着不能将关联容器传递给修改或重排序的算法。因为，这类算法要向
元素写入值，而关键字是const。
关联容器可用于只读元素的算法。但是很多这类算法都要搜索序列。
由于关联容器中的元素不能通过他们的关键字快速查找，因此对关联
容器使用搜索算法也不好。
实际中，若对一个关联容器使用算法，要么将它当成源序列，要么将它
当做一个目的位置。

②添加元素

由于map和set(以及对应的无序类型)包含不重复的关键字，因此插入一个已存在的元素对容器没有任何影响。

关联容器insert操作
c.insert(v) c.emplace(args)	v是value_type类型的对象；args用来构造一个元素。对于map和set,只有当元素的关键字不在c中时才插入(或构造)元素。函数返回一pair，包含一个迭代器，指向具有指定关键字的元素，以及一个指示是否插入成功的bool值。（元素已存在存在插入什么都不做，返回false；否则插入成功，返回true）对于multimap和multiset，总会插入(构造)给定元素，并返回一个指向新元素的迭代器
c.insert(b, e) c.insert(il)	b和e是迭代器，表示一个c::value_type类型值的范围；il是这种值的花括号列表。函数返回void 对于map和set,只插入关键字不在c中的元素。对于multimap、multiset,则会插入范围中的每个元素
c.insert(p, v) c.emplace(p, args)	类似insert(v)(或emplace(args)), 但将迭代器p作为一个提示，指出从哪里开始搜索新元素应该存储的位置。返回一个迭代器，指向具有给定关键字的元素。

关联容器insert操作

c.insert(v)

c.emplace(args)

v是value_type类型的对象；args用来构造一个元素。
对于map和set,只有当元素的关键字不在c中时才插入(或构造)元素。函数返回一pair，包含一个迭代器，指向具有指定关键字的元素，以及一个指示是否插入成功的bool值。（元素已存在存在插入什么都不做，返回false；否则插入成功，返回true）
对于multimap和multiset，总会插入(构造)给定元素，并返回一个指向新元素的迭代器

c.insert(b, e)

c.insert(il)

b和e是迭代器，表示一个c::value_type类型值的范围；il是这种值的花括号列表。函数返回void
对于map和set,只插入关键字不在c中的元素。对于multimap、multiset,则会插入范围中的每个元素

c.insert(p, v)

c.emplace(p, args)

类似insert(v)(或emplace(args)), 但将迭代器p作为一个提示，指出从哪里开始搜索新元素应该存储的位置。返回一个迭代器，指向具有给定关键字的元素。

    vector<int> ivec={0, 1, 2};
    set<int> s2;
    s2.insert(ivec.begin(), ivec.end());
    s2.insert({1,2, 3,3});

    string word;
    map<string, int> word_count;
    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));
    word_count[word]=1;

检测insert的返回值:如上表描述

    map<string, size_t> word_count;
    string word;
//统计每个单词出现次数
    while(cin>>word)
    {
        //若word已在，insert什么也不做
        auto ret=word_count.insert({word, 1});
        if(!ret.second) ++ret.first->second;
    }

展开递增语句：

对于++ret.first->second;
等价于++((ret.first)->second);

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

③删除元素

从关联容器删除元素
c.erase(k)	从c中删除每个关键字为k的元素。返回一个size_type值，指出删除元素的数量
c.erase(p)	从c中删除迭代器p指定的元素。p必须指向c中一个真实元素，不能等于c.end()。返回一个指向p之后元素的迭代器，若p指向c中的尾元素，则返回c.end()
c.erase(b, e)	删除迭代器对b和e所表示范围中的元素。返回e

④map的下标操作

map和unordered_map的下标操作
c[k]	返回关键字为k的元素；若k不在c中，添加一个关键字为k的元素，对其值初始化
c.at(k)	访问关键字为k的元素，带参数检查；若k不在c中，抛出out_of_range异常

    /**
     * 在word_count搜索关键字为Anna的元素，未找到
     * 将一个新键值对插入word_count,值初始化为0
     * 提取新插入的元素，并将1赋予它
     */
    map<string, size_t> word_count;
    word_count["Anna"]=1;

使用下标操作的返回值：map的下标运算符与我们用过的其他下标运算符的另一个不同之处是其返回类型。通常情况下，解引用一个迭代器所返回的类型与下标运算符返回的类型是一样的。但对map则不然：当对一个map进行下标操作时，会获得一个mapped_type对象；但当解引用一个map迭代器时，会得到一个value_type对象。与其他下标运算符相同的是，map下标运算符返回一个左值，既可以读也可以写.

    map<string, size_t> word_count;
    word_count["Anna"]=1;
    cout<<word_count["Anna"];
    ++word_count["Anna"];

⑤访问元素

在一个关联容器中查找元素的操作
lower_bound和upper_bound不适用于无序容器。下标和at操作只适用于非const的map和unordered_map。
c.find(k)	返回一个迭代器，指向第一个关键字为k的元素，若k不在容器中，返回尾后迭代器
c.count(k)	返回关键字等于k的元素数量
c.lower_bound(k)	返回一个迭代器，指向第一个关键字不小于>=k的元素
c.upper_bound(k)	返回一个迭代器，指向第一个关键字大于>k的元素
c.equal_range(k)	返回一个迭代器pair，表示关键字等于k的元素的范围。若k不存在，pair的两个成员均等于c.end()

对map使用find代替下标操作：对于map和unordered_map，下标运算符提供了最简单的提取元素的方法。但是，若关键字未在map中，下标操作会插入一个具有给定关键字的元素，会带来非预期行为。
在multimap或multiset中查找元素：如果一个multimap或multiset中有多个元素具有给定关键字，则这些元素在容器中会相邻存储。

    /**
     * 给定一个作者到著作的映射，打印一个给定作者的所有著作
     */
    multimap<string, string> authors;//作者->著作 
    string search_author("Anna");//要查的作者
    size_t entries=authors.count(search_author);//当前作者著作数量
    auto iter=authors.find(search_author);//此作者第一本书
    while(entries)
    {
        cout<<iter->second<<endl;//打印书名
        ++iter;//到下一本书；
        --entries;
    }

一种不同的，面向迭代器的解决方法：还可以用lower_bound和upper_bound来解决上面的问题。这两个操作都接受一个关键字，返回一个迭代器。若关键字在容器中, lower_bound返回的迭代器将指向第一个具有给定关键字的元素，而upper_bound返回的迭代器指向最后一个匹配给定关键字的元素之后的位置。
若元素不在（lower_bound无==）multimap中，则lower_bound和upper_bound会返回相等的迭代器(若k小于所有关键字，则二者返回指向第一个关键字的迭代器，若k大于所有关键字，则二者返回尾后迭代器，若k处在关键字中间，则会返回一个合适位置)----指向一个不影响排序的关键字插入位置。因此，用相同的关键字调用二者会得到一个迭代器范围，表示具有该关键字的元素范围。
k是最大的关键字，则upper_bound返回尾后迭代器。

    /**
     * 给定一个作者到著作的映射，打印一个给定作者的所有著作
     */
    multimap<string, string> authors;//作者->著作
    string search_author("Anna");//要查的作者
    for(auto beg=authors.lower_bound(search_author),end=authors.upper_bound(search_author);
        beg!=end;++beg)
        cout<<beg->second<<endl;

equal_range函数：第三种方法

    /**
     * 给定一个作者到著作的映射，打印一个给定作者的所有著作
     */
    multimap<string, string> authors;//作者->著作
    string search_author("Anna");//要查的作者
    for(auto pos=authors.equal_range((search_author));
        pos.first!=pos.second;++pos.first)
        cout<<pos.first->second<<endl;

⑥一个单词转换的map

例子程序省略。

4. 无序容器

C++11定义了4个无序关联容器。这些容器不是使用比较运算符来组织元素，而是使用一个哈希函数和关键字类型的==运算符。无序通常比有序性能好，因为有序需要代价维持。
使用无序容器：除了哈希管理操作，无序容器提供了与有序容器相同的操作。这意味着我们曾用于map和set操作也能用于unordered_map和unordered_set.
类似，无序容器也有允许重复关键字的版本。因此，通常可以用一个无序容器替换对应有序容器，反之一样。但是由于元素未按顺序存储，一个无序容器的程序的输出通常与有序版本不同。

    //统计单词出现次数，但单词不会按字典序排列
    unordered_map<string, int> word_count;
。。。

管理桶：无序容器在存储组织上为一组桶，每个桶保存0个或多个元素。无序容器使用一个哈希函数将元素映射到桶。为了访问一个元素，容器首先计算哈希值，它指出应该搜索哪个桶。容器将具有一个特点哈希值的所有元素都保存在相同的桶中。如果，容器允许重复关键字，所有具有相同关键字的元素也都会在同一个桶。因此，无序容器的性能依赖于哈希函数的质量和桶的数量和大小。
对于相同的参数，哈希函数必须总是产生相同的结果。理想情况下，哈希函数还能将每个特定的值映射到唯一的桶。但是，将不同关键字的元素映射到相同的桶也是允许的。当一个桶，保存多个元素时，需要顺序搜索这些元素来查找我们想要的那个。计算一个元素的哈希值和在桶中搜索通常都是很快的操作。
但是如果一个桶中保存了很多元素，那么查找一个特定元素需要大量比较操作。
无序容器提供了一组管理通的函数，这些成员函数允许我们查询容器的状态以及在必要时强制容器重组。

无序容器管理操作
桶接口
c.bucket_count()	正在使用的桶的数目
c.max_bucket_cout()	容器能容纳的最多的桶的数量
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模板。还为一些标准库类型，包括string和智能指针类型定义了hash。因此，我们可以直接定义关键字是内置类型、string还是智能指针类型的无序容器。
但是，我们不能直接定义关键字类型为自定义类类型的无序容器。与容器不同，不能直接使用哈希模板，而必须提供我们自己的hash模板版本。我们不使用默认的hash, 而是使用类似于为有序容器重载关键字类型的默认比较操作。

//为了能将Sales_data用作关键字，我们需要提供函数
//代替==运算符和哈希值计算函数。我们从定义这些重载
//函数开始
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();
}

//第二三传递hash函数和等于函数
using SD_multiset=unordered_multiset<Sales_data, decltype(hasher)*, decltype(eqOp)*>;
SD_multiset bookstore(42, hasher, eqOp);

//若类定义了==，则可以只重载哈希函数
//Foo有==运算符
unordered_set<Foo, decltype(FooHash)*> fooSet(10, FooHash);

十一. 动态内存

静态内存用来保存局部static对象、类static数据成员以及定义在任何函数之外的变量。栈内存用来保存定义在函数内的非static对象。分配在静态或栈内存中的对象由编译器自动创建和销毁。对于栈对象，仅在其定义的程序块运行时才存在；static对象在使用前分配，在程序结束时销毁。
除了静态内存和栈内存，每个程序还有一个内存池。这部分内存被称作自由空间或堆。程序用堆来存储动态分配的对象，即那些在程序运行时才分配的对象。动态对象的生存周期由程序来控制，即当动态对象不再使用时，我们必须显式的销毁他们。

1. 动态内存与智能指针

在C++中，动态内存的管理是通过一对运算符完成的:new，在动态内存中为对象分配空间并返回一个指向该对象的指针，我们可以选择对对象进行初始化；delete接受一个动态对象的指针，销毁该对象，并释放与之关联的内存。
动态内存的使用很容易出问题，因为很难确保在正确的时间释放内存。有时会忘记释放内存，导致内存泄漏；有时在尚有指针引用内存的情况下释放了它，导致产生引用非法内存的指针。
为了更容易安全的使用动态内存，C++11提供了两种智能指针类型来管理动态对象。智能指针行为类似常规指针，区别是它负责自动释放所指的对象。C++11提供的这两种智能指针的区别在于管理底层指针的方式：shared_ptr允许多个指针指向同一对象；unique_ptr则独占所指向的对象。标准库还定义了一个名为weak_ptr的伴随类，他是一种弱引用，指向share_ptr所管理的对象。这三种类型都定义在memory头文件中。

①shared_ptr类

类似vector，智能指针也是模板。因此，当我们创建一个智能指针时，必须提供指针可指向的类型。默认初始化的智能指针中保存一个空指针。

    shared_ptr<string> p1;//可指向string
    shared_ptr<list<int>> p2;//可指向int的list
    
    /**
     * 智能指针的使用方式与普通指针类似。解引用一个智能指针返回它指向的对象。
     * 若一个条件判断中使用智能指针，效果就是检测它是否为空
     */
    //如果p1不空，检查他是否指向一个空string
    if(p1&&p1->empty()) *p1="hi";

shared_ptr和unique_ptr都支持的操作
shared_ptr<T> sp; unique_ptr<T> up;	空智能指针，可以指向类型为T的对象
p	将p作为一个条件判断，若p指向一个对象，则为true
*p	解引用p,获得它指向的对象
p->mem	等价于(*p).mem
p.get()	返回p中保存的指针。小心使用，若智能指针释放了其对象，返回的指针所指向的对象也就消失了。
swap(p, q) p.swap(q)	交换p和q中的指针

shared_ptr独有的操作
make_shared<T>(args)	返回一个shared_ptr，指向一个动态分配类型为T的对象。使用args初始化此对象。
shared_ptr<T> p(q)	p是shared_ptr q的拷贝；此操作会递增q中的计数器。q中的指针必须能转化为T*
p=q	p和q都是shared_ptr，所保存的指针必须能相互转换。此操作会递减p的引用计数，递增q的引用计数；若p的引用计数变为0，则将其管理的原内存释放。
p.unique()	若p.use_count为1，返回true；否则返回false
p.use_count()	返回与p共享对象的智能指针数量；可能很慢，主要用于调试。

make_shared函数：最安全的分配和使用动态内存的方法是调用一个名为make_shared的标准款函数。此函数在动态内存中分配一个对象并初始化它，返回指向此对象的shared_ptr,其也定义在memory头文件

    /**
     * 类似emplace。
     * 传递的参数必须和某个构造函数匹配
     * 不传任何参数，就会值初始化
     */
    shared_ptr<int> p3=make_shared<int>(42);
    shared_ptr<string> p4= make_shared<string>(9, '9');//9个9
    shared_ptr<int> p5= make_shared<int>();//p5指向一个值初始化的int,值为0
    auto p6= make_shared<vector<string>>();//p6指向一个动态分配的空vector<string>

shared_ptr的拷贝和赋值：

/**
 * 当进行拷贝或赋值操作时，每个shared_ptr都会记录有多少个其他shared_ptr指向相同的对象
 * 我们可以认为每个shared_ptr都有一个关联的计数器，通常称其为引用计数。
 * 
 * 无论何时拷贝一个shared_ptr，计数器都会递增。例如：当用一个shared_ptr初始化另一个shared_ptr，
 * 或将它作为参数传递给一个函数以及作为函数返回值时，其所关联的计数器就会递增。当给shared_ptr
 * 赋予一个新值或是shared_ptr被销毁(局部shared_ptr离开作用域)，计数器就会递减
 * 
 * 一旦一个shared_ptr的计数器变为0，它就会自动释放自己所管理的对象
 */
    auto p= make_shared<int>(42);//p指向的对象只有p一个引用者
    auto q(p);//p和q指向相同对象，此对象有两个引用者
    auto r= make_shared<int>(42);//r指向的int只有一个引用者
    r=q;//给r赋值，令他指向另外一个地址，递增q指向的对象的引用计数, 递减r指向对象的引用计数，r指向的对象无引用者，自动释放

shared_ptr自动销毁所管理的对象：当指向一个对象的最后一个shared_ptr被销毁时，shared_ptr类会自动销毁此对象。它通过另一个特殊的成员函数---析构函数完成销毁工作。类似于构造函数，每个类都有一个析构函数，控制此类型对象销毁时做什么操作。析构函数一般用来对象所分配的资源。shared_ptr的析构函数会递减它所指向的对象的引用计数。如果引用计数器变为0，shared_ptr的析构函数就会销毁对象，并释放它占用的内存。
shared_ptr还会自动释放相关联的内存：当动态对象不再被使用，shared_ptr类会自动释放动态对象。
若将shared_ptr存放在容器中，而后不在需要全部元素，需要删除不再需要的元素，以便释放内存。

shared_ptr<Foo> factory(T arg)
{
    return make_shared<Foo>(arg);
}

void use_factory(T arg)
{
    shared_ptr<Foo> p= factory(arg);
}//p离开了作用域，其指向的内存会被释放。p在函数结束时销毁，递减计数器并检查是否为0

shared_ptr<Foo> use_factory(T arg)
{
    shared_ptr<Foo> p= factory(arg);
    return p;//返回p时，对引用计数器递增
}//p离开作用域，但是其指向的内存不会被释放

使用了动态生存期的资源的类：程序使用动态内存出于以下原因
[1] 程序不知道自己需要使用多少对象
[2] 程序不知道所需对象的准确类型
[3] 程序需要在多个对象间共享数据(静态和栈内存，编译器会自动释放)
对于[3], 之前使用的类，分配的资源与对应对象生存周期一致。但某些类分配的资源具有与原对象相独立的生存周期。

vector<string> v1;
{//新作用域
    vector<string> v2={"a"};
    v1=v2;//从v2拷贝元素到v1
}//v2被销毁，其中元素被销毁。v1有一个元素，是v2元素的拷贝

Blob<string> b1;
{//新作用域
    Blob<string> b2={"a"};
    b1=b2;//b1和b2共享相同元素
}//b2被销毁，但b2中的元素不能销毁；b1指向最初b2创建的元素

定义StrBlob类：定义一个管理string的类名为StrBlob。可用某个容器来管理string元素，但是不能在一个Blob对象内直接保存vector,因为一个对象的成员
在对象销毁时也会被销毁。为了实现vector元素继续存在，将vector保存在动态内存中。
为了实现数据共享，为每个StrBlob设置一个shared_ptr来管理动态分配的vetcor。此shared_ptr的成员将记录有多少StrBlob共享相同的vector,并在vector的最后一个使用者被销毁时释放vector

class StrBlob
{
public:
    typedef vector<string>::size_type size_type;
    StrBlob();//默认构造函数
    StrBlob(initializer_list<string> il);//可变参数，列表初始化
    size_type size() {return data->size();}//返回vector元素数量
    bool empty() const {return data->empty();}
    //添加和删除元素
    void push_back(const string &t) {data->push_back(t);}
    void pop_back()
    {
        check(0, "空");
        data->pop_back();
    }
    //元素访问
    string& front()
    {
        //若vector为空, check会抛出异常
        check(0, "空");
        return data->front();
    }
    string& back()
    {
        check(0, "空");
        return data->back();
    }

private:
    //对StrBlob的拷贝赋值和销毁会引起shared_ptr的计数器变化，直到无引用者，该对象销毁，释放内存
    shared_ptr<vector<string>> data;//若data[i]不合法会抛出异常
    /**
     * 检查给定索引i是否在合法范围
     * @param i 
     * @param msg 描述错误信息，被传给异常处理程序
     */
    void check(size_type i, const string &msg) const
    {
        if(i>=data->size())
            throw out_of_range(msg);
    }
};

②直接管理内存

C++定义了两个运算符来分配和释放动态内存。运算符new分配内存，delete释放new分配的内存。相对于智能指针，使用这两个运算符管理内存非常容易出错。此外，这两个运算符不能依赖类对象拷贝、赋值和销毁操作的任何默认定义。因此，使用智能指针更容易编写和调试。
使用new动态分配和初始化对象：在自由空间分配的内存是无名的，因此new无法为其分配的对象命名，而是返回一个指向该对象的指针。
默认情况，动态分配的对象是默认初始化的，这意味着内置类型或组合类型的对象的值未定义，而类类型采用默认构造函数进行初始化。
出于与变量初始化相同的原因，通常对动态分配的对象进行初始化。

    int *pi=new int;//pi指向一个动态分配的、未初始化的无名对象
    string *ps=new string;//初始化为空string

    //可以使用直接初始化来初始化一个动态分配的对象
    int *pi2=new int(1024);
    string *ps2=new string(10, '9');
    vector<int> *pv=new vector<int>{0, 1, 2};

    //对动态分配的对象进行值初始化，只需在类名后跟空括号
    string *ps3=new string;//默认初始化空string
    string *ps4=new string();//值初始化为空string
    int *pi1=new int;//默认初始化；*pi1值未定义
    int *pi22=new int();//值初始化为0
    
    //若提供了一个括号包围的初始化器，则可用auto推断类型。但是编译器
    //要想用初始化器来推断要分配的类型，只有括号中仅有单一初始化器才能用auto
    auto p1=new auto(obj);//p指向一个与obj类型相同的对象，并用obj初始化
    auto p2=new auto{a, b, c};//错括号中只能有单个初始化器

动态分配的const对象：

    /**
     * 对于定义了默认构造函数，其const动态对象可以隐式初始化
     * 而其他类型必须显式初始化。
     * 
     * 由于分配对象是const的，new返回的指针是一个指向const的指针
     */
    const int *pi=new const int(1024);//分配并初始化一个const int
    const string *ps=new const string;//分配并默认初始化一个const的空string

内存耗尽：一个程序一旦用光了它的所有可用内存，new表达式就会失败。默认情况下，若new不能分配所要求的内存空间，他会抛出一个类型为bad_alloc的异常。

    int *p1=new int;//若分配失败，抛出bad_alloc异常
    int *p2=new (nothrow)int;//改变new使用方式，阻止抛出异常：分配失败，返回空指针
    /**
     * 我们称上述形式的new为定位new.其允许我们向new表达式传递额外的参数。
     * 此例中，我们传递标准库定义的nothrow的对象，意图告诉它不能抛出异常，
     * 分配失败会返回空指针
     */

释放动态内存：为了防止内存耗尽，在动态内存使用完毕后，必须将其归还系统。通过delete实现。delete表达式接受一个指针，指向我们想要释放的对象。

    delete p;//p必须指向一个动态分配的对象或是一个空指针
    //与new类似，delete执行两个动作：销毁给定的指针指向的对象；释放对应内存

指针值和delete:传给delete的指针必须是动态分配的对象或是一个空指针。释放一块非new分配的内存，或将相同的指针释放多次，其行为是未定义的。

    /**
     * 编译器不会区分一个指针指向的是静态还是动态分配的对象
     * 也不会分辨内存是否已被释放
     */
    int i, *pi1=&i, *pi2= nullptr;
    double *pd=new double(33), *pd2=pd;
    delete i;//✖，i不是指针
    delete pi1;//✖，未定义，pi1指向局部变量
    delete pd;//✔
    delete pd2;//✖，未定义，pd2指向的内存已被释放
    delete pi2;//✔，释放空内存
    /**
     * 虽然一个const对象的值不能改变，但其本身可以销毁
     */
    const int *pci=new const int(1024);
    delete pci;//✔

动态对象的生存期直到释放时为止：shared_ptr管理的内存在最后一个shared_ptr销毁时会被自动释放。但通过内置指针类型来管理内存就不是。对于一个内置指针管理的动态对象，直到被显式释放前，它都是存在的。返回指向动态内存的指针(不是智能指针)的函数给其调用者增加了一个额外负担，调用者必须记得释放内存。

//factory返回一个指针，指向一个动态分配的对象
Foo* factory(T arg)
{
    return new Foo(arg);//调用者负责释放此内存
}

void use_factory(T arg)
{
    Foo *p= factory(arg);
    //使用p但没delete他
}//p离开了作用域，但其指向的内存没有被释放

void use_factory2(T arg)
{
    Foo *p= factory(arg);
    delete p;//释放p
}

Foo* use_factory(T arg)
{
    Foo *p= factory(arg);
    return p;//调用者必须释放p,再返回上一层
}

动态内存的管理非常容易出错：
[1] 忘记delete内存(内存泄漏)。内存耗尽时才能发现
[2] 使用已经释放的对象。释放后指针为空
[3] 同一内存释放两次。当有两个指针指向相同的动态分配对象时，可能发生这种错误。先对第一个指针delete,对象内存被归还自由空间。随后又delete第二个指针，自由空间可能被破坏
坚持使用智能指针可以避免上述问题
delete后重置指针值...:当delete一个指针后，指针值就变为无效了。虽然指针已经无效，但在很多机器上仍保存着(已经释放了的)动态内存的地址。在delete后，指针就变成了空悬指针，即，指向一块曾经保存数据但现在已经无效的内存的指针。
未初始化指针的所有缺点空悬指针都有。避免空悬指针的问题：在指针即将离开其作用域前释放掉它所关联的内存。在指针关联的内存释放后，就没机会继续使用指针了。如果我们需要保留指针，可以在delete将nullptr赋予指针。
...这只是提供了有限的保护：动态内存一个基本问题时可能有多个指针指向相同的内存。在delete内存后重置指针的方法只针对这个指针有效，对其他任何扔指向(已释放)内存的指针没用。

③shared_ptr和new结合使用

定义和改变shared_ptr的其他方法
shared_ptr<T> p(q)	p管理内置指针q所指向的对象；q必须指向new分配的内存，且能转化为T*类型
shared_ptr<T> p(u)	p从unique_ptr u那里接管了对象的所有权；将u置空
shared_ptr<T> p(q,d)	p接管了内置指针q所指向的对象的所有权。q必须能转换为T*类型。p将使用可调用对象d来替代delete
shared_ptr<T> p(p2,d)	p是shared_ptr p2的拷贝，唯一区别是p将用可调用对象d来替代delete
p.reset() p.reset(q) p.reset(q, d)	若p是唯一指向其对象的shared_ptr，reset会释放此对象。若传递了可选的参数内置指针q, 会令p指向求，否则会将p置为空。若还传递了参数d, 将会调用d而不是delete来释放q

shared_ptr<double> p1;//空
shared_ptr<int> p2(new int(42));//✔，使用了直接初始化
/**
 * 接受指针参数的智能指针构造函数是explicit的。因此，我们不能将一个
 * 内置指针隐式的转换为一个智能指针，必须使用直接初始化形式来初始化一个智能指针。
 */
shared_ptr<int> p11=new int(1024);//✖，必须直接初始化
shared_ptr<int> p22(new int(1024));//✔，直接初始化
/**
 * p11的初始化隐式的要求编译器用一个new返回的int*来创建一个shared_ptr。
 * 由于不能进行内置指针到智能指针的隐式转换，因此这条语句错误。
 * 同样的，一个返回shared_ptr的函数不能在其返回语句中隐式转换一个普通指针
 */
shared_ptr<int> clone(int p)
{
    return new int(p);//✖，隐式转换为shared_ptr
    return shared_ptr<int>(new int(p));//✔
}

默认情况下，一个用来初始化智能指针的普通指针必须指向动态内存，因为智能指针默认使用delete释放它所关联的对象。我们可以将智能指针绑定到一个指向其他类型的资源的指针上，但必须提供自己的操作来替代delete.
-
不要混合使用普通指针和智能指针...:shared_ptr可以协调对象的析构，但这仅限于其自身的拷贝(也是shared_ptr)之间。这也是为什么推荐使用make_shared而不是new的原因。这样，能在分配对象的同时就将shared_ptr与之绑定，从而避免了无意中将同一块内存绑定到多个独立创建的shared_ptr上。

//在函数调用时ptr被创建并初始化
/**
 * 该函数是值传递的，因此实参会被拷贝到ptr
 * 拷贝一个shared_ptr会递增其引用计数。
 * 在该函数运行过程中, 引用计数至少为2
 * 当函数结束，ptr引用计数递减，但不会为0.因此
 * 当局部变量ptr被销毁时，ptr指向的内存不会被销毁
 */
void process(shared_ptr<int> ptr)
{
    //使用ptr
}//ptr离开作用域，被销毁

int main(int argc, char *argv[])
{
    shared_ptr<int> p(new int(42));//引用计数为1
    process(p);//引用计数为2
    int i=*p;//✔，引用计数值为1
    /**
     * 虽然不能传递给process一个内置指针，但可以传给它一个(临时)
     * shared_ptr, 这个shared_ptr是用一个内置指针显示构造的
     * 但是可能导致错误。
     */
    int *x(new int(1024));//危险：x是普通指针，不是一个智能指针
    process(x);//✖
    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();//✔，但是不能delete p
    {//新程序块
        //未定义：两个独立的shared_ptr指向相同的内存
        shared_ptr<int>(q);
    }//程序块结束，q被销毁，它指向的内存被释放
    int foo=*p;//未定义，p指向的内存已被释放了
    /**
     * p和q指向相同的内存。由于他们是相互独立创建的，因此各自的引用计数器都是1.
     * 当q所在的程序块结束时，q被销毁，会导致q指向的内存被释放。从而p变成一个空悬
     * 指针，意味着当我们试图使用p时，将产生未定义行为。而且，当p被销毁时，
     * 这块内存会被第二次delete
     */

其他shared_ptr操作：

    shared_ptr<int> p(new int(0));
    p=new int(1024);//✖, 不能将一个指针赋予shared_ptr
    p.reset(new int(1024));//✔，p指向一个新对象
    /**
     * 与赋值相似， reset会更新引用计数，如果需要，会释放p所指的对象。
     * reset经常与unqieue一起使用，来控制多个shared_ptr共享的对象。
     * 在改变底层对象之前，我们检查自己是否是当前对象仅有的用户，如果不是
     * 在改变前制作一份新的拷贝
     */
     if(!p1.unique()) 
         p1.reset(new string(*p1));//我们不是唯一用户；分配新的拷贝
     *p1+=newVal;//现在知道自己是唯一用户，可以改变对象的值

④智能指针和异常

使用异常处理的程序能在发生异常后令程序流程继续，这种程序需要确保异常发生后资源能被正确的释放。一个简单方法是使用智能指针。如果使用智能指针，即使程序块过早结束，智能指针类也能确保内存不再需要时将其释放。

/**
 * 无论正常结束还是异常，局部变量sp都会被销毁
 * sp被销毁时，智能指针会检查引用计数，所以内存会被释放
 */
void f()
{
    shared_ptr<int> sp(new int(42));//分配一个新对象
    //这段代码抛出一个异常，且在f中未被捕获
}//在函数结束时，shared_ptr自动释放内存

/**
 * 如果使用内置指针管理内存，且在new之后delete之前发生异常
 * 且异常在f2中未被捕获，则内存不会被释放
 */
void f2()
{
    int *ip=new int(42);
    //这段代码抛出异常，且未被捕获
    delete ip;//在退出前释放内存
}

所有标准库类在内的很多C++类都定义了析构函数，负责清理对象使用的资源。但是不是所有类都是这样良好定义的，特别是那些为C和C++两种语言设计的类，通常要求用户显示的释放所使用资源。
那些分配了资源，又没有定义析构函数来释放这些资源的类，程序员可能会忘记释放资源。类似的，如果在资源分配和释放之间发生了异常，程序也会发生资源泄露。
与管理动态内存类似，我们通常可以使用类似的技术(智能指针)来管理不具有良好定义的析构函数的类。

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

void f(destination &d)
{
    //获得一个连接；使用完后要关闭
    connection c=connect(&d);
    //使用连接
    //若我们在f退出前忘记调用disconnect，就无法关闭c了
    /**
     * 如果connection有一个析构函数，就可以在f结束时由析构函数自动关闭连接。
     * 但是connection没有析构函数。
     * 这个问题和上面用shared_ptr避免内存泄露几乎等价。
     * 使用shared_ptr保证connection被正确关闭
     */
}

使用我们自己的释放操作：默认情况下，shared_ptr假定他们指向的是动态内存。因此，当一个shared_ptr被销毁时，它默认的对他管理的指针进行delete操作，为了使用shared_ptr来管理一个connection，我们必须首先定义一个函数来代替deleet。这个删除器函数必须能够完成对shared_ptr中保存的指针进行释放的操作。在本例中，我们的删除器必须接受单个类型为connection*的参数。

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

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

/**
 * 当我们创建一个shared_ptr时，可传递一个(可选的)指向删除器函数的参数
 */
void f(destination &d)
{
    connection c= connect(&d);
    shared_ptr<connection> p(&c, end_connection);
    //使用连接
    //当f退出时(即使异常退出), connection会被正确关闭
    /**
     * p被销毁时，不会对自己保存的指针delete,而是调用end_connection
     * 即使p异常销毁, 由于shared_ptr引用计数器机制，使其能被释放
     */
}

智能指针陷阱:为了正确使用智能指针，必须遵循以下规范：
[1] 不使用相同的内置指针初始化(或reset)多个智能指针
[2] 不delete get()返回的指针
[3] 不使用get()初始化或reset另一个指针
[4] 如果使用get()返回的指针，记住当最后一个对应智能指针销毁后，你的指针就无效了
[5] 如果你使用智能指针管理的资源不是new分配的内存，记住传递给它一个删除器

⑤unique_ptr

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

unique_ptr操作(其余在十一1①)
unique_ptr<T> u1 unique_ptr<T,D> u2	空unique_ptr, 可以指向类型为T的对象。u1会使用delete来释放它的指针；u2会使用一个类型为D的可调用对象来释放它的指针
unique_ptr<T,D> u(d)	空unique_ptr，指向类型为T的对象，用类型为D的对象d代替delete
u=nullptr	释放u所指的对象，将u置为空
u.release()	u放弃对指针的控制权(没有释放内存)，返回指针，并将u置空
u.reset() u.reset(q) u.reset(nullptr)	释放u指向的对象。如果提供了内置指针q,令u指向这个对象；否则将u置为空

    /**
     * 定义一个unique_ptr时，需要将其绑定到一个new返回的指针上。
     * 类似shared_ptr，初始化unique_ptr必须采用直接初始化形式。
     */
    unique_ptr<double> p1;
    unique_ptr<int> p2(new int(42));
    ************************************************************
    /**
     * 由于一个unique_ptr拥有它指向的对象，因此unique_ptr
     * 不支持普通的拷贝或赋值操作
     */
    unique_ptr<string> p1(new string("dsad"));
    unique_ptr<string> p2(p1);//✖，unique_ptr不支持拷贝
    unique_ptr<string> p3;
    p3=p2;//✖，unique_ptr不支持赋值操作
    *************************************************************
    /**
     * 虽然我们不能拷贝或赋值unique_ptr，但是可以通过调用release
     * 或reset将指针的所有权从一个(非const)unique_ptr转移到
     * 另一个unique
     */
    //将所有权从p1转移给p2
    unique_ptr<string> p2(p1.release());//将p1置为空
    unique_ptr<string> p3(new string("Tex"));
    p2.reset(p3.release());//reset释放了p2原来指向的内存
    **************************************************************
    
    p2.release();//✖，p2不会释放内存，而且我们丢失了指针
    auto p=p2.release();//✔，但必须记得delete(p),因为没有用智能指针保存release返回的指针

传递unique_ptr和返回unique_ptr：

/**
 * 不能拷贝unqiue_ptr的规则有一个例外：我们可以拷贝或赋值一个将要被销毁的unique_ptr
 * 最常见的例子是从函数返回一个unique_ptr
 * 
 * 对于下面的两个函数，编译器知道要返回的对象将被销毁
 * 在此情况，编译器执行特殊拷贝
 */
unique_ptr<int> clone(int p)
{
    //✔, new int(p)传给了构造函数
    return unique_ptr<int>(new int(p));
}

//还可以返回一个局部对象的拷贝
unique_ptr<int> clone(int p)
{
    unique_ptr<int> ret(new int(p));
    return ret;
}

向后兼容：标准库较早版本包含了一个名为auto_ptr的类，它具有unique_ptr部分特性，但不是全部。特别的，我们不能在容器中保存auto_ptr，也不能从函数返回auto_ptr。编写程序应该用unique_ptr。
向unique_ptr传递删除器：unique_ptr默认情况用delete释放他指向的对象。与shared_ptr一样，我们可以重载一个unique_ptr默认的删除器。unique_ptr管理删除器的方式和shared_ptr不同。
重载一个unique_ptr中的删除器会影响到unique_ptr类型已经如何构造(或reset)
该类型对象。与重载关联容器的比较操作类似，必须在尖括号中unique_ptr指向类型之后提供删除器类型。在创建或reset一个这种unique_ptr类型的对象时，必须提供一个指定类型的可调用对象(删除器)

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

//重写连接程序，用unique_ptr代替shared_ptr
void f(destionation &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的名字抓住了这种智能指针弱共享对象的特点。

weak_ptr
weak_ptr<T> w	空weak_ptr可以指向类型为T的对象
weak_ptr<T> w(sp)	与shared_ptr sp指向相同对象的weak_ptr。T必须能转换为sp指向的类型
w=p	p可以是一个shared_ptr或一个weak_ptr。赋值后w和p共享对象
w.reset()	将w置为空
w.use_count()	与w共享对象的shared_ptr的数量
w.expired()	w.use_count()为0，返回true;否则返回false
w.lock()	若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
   if(shared_ptr<int> np=wp.lock()) {//若np不为空，条件成立
       
   }

核查指针类：作为weak_ptr用途的一个展示，我们将为Strblob类定义一个伴随指针类，命名为StrBlobPtr，会保存一个weak_ptr，指向StrBlob的data成员，这是初始化时提供给它的。通过使用weak_ptr不会影响一个给定的StrBlob所指向的vector生存周期。但是，可以阻止用户访问一个不再存在的vector的企图。

class StrBlob
{
public:
    typedef vector<string>::size_type size_type;
    StrBlob();//默认构造函数
    StrBlob(initializer_list<string> il);//可变参数，列表初始化
    size_type size() {return data->size();}//返回vector元素数量
    bool empty() const {return data->empty();}
    //添加和删除元素
    void push_back(const string &t) {data->push_back(t);}
    void pop_back()
    {
        check(0, "空");
        data->pop_back();
    }
    //元素访问
    string& front()
    {
        //若vector为空, check会抛出异常
        check(0, "空");
        return data->front();
    }
    string& back()
    {
        check(0, "空");
        return data->back();
    }



private:
    //对StrBlob的拷贝赋值和销毁会引起shared_ptr的计数器变化，直到无引用者，该对象销毁，释放内存
    shared_ptr<vector<string>> data;//若data[i]不合法会抛出异常
    /**
     * 检查给定索引i是否在合法范围
     * @param i
     * @param msg 描述错误信息，被传给异常处理程序
     */
    void check(size_type i, const string &msg) const
    {
        if(i>=data->size())
            throw out_of_range(msg);
    }
};

class StrBlobPtr
{
public:
    StrBlobPtr(): curr(0){}
    StrBlobPtr(StrBlob &a, size_t sz=0):wptr(a.data), curr(sz) {}
    string& deref() const;
    StrBlobPtr& incr();//前缀递增

private:
    //若检查成功，check返回一个指向vector的shared_ptr
    shared_ptr<vector<string>> check(size_t i, const string &msg) const
    {
        auto ret=wptr.lock();//vector还存在吗?
        if(!ret) throw runtime_error("未绑定的StrBlobPtr");
        if(i>=ret->size()) throw out_of_range(msg);
        return ret;//否则返回指向vector的shared_ptr
    }
    //保存一个weak_ptr, 意味着底层vector可能被销毁
    weak_ptr<vector<string>> wptr;
    size_t curr;//在数组当前位置
};

指针操作：后面学习如何定义自己的运算符。现在定义名为deref和incr的函数，分别用来解引用和递增StrBlobPtr.

string& StrBlobPtr::deref() const 
{
    auto p= check(curr, "deference past end");//检查合法性
    return (*p)[curr];//*p是对象所指的vector
}

StrBlobPtr& StrBlobPtr::incr() 
{
    check(curr, "到尾巴");//若已经到尾巴则不递增
    ++curr;
    return *this;
}
//为了访问data成员，指针类必须声明为StrBlob的friend

2. 动态数组

new和delete运算符一次分配/释放一个对象，但某些应用需要一次为很多对象分配内存的功能。例如vector和string都是在连续内存中保存他们的元素，因此当容器需要重新分配内存时，必须一次性为很多元素分配内存。
为了支持这种需求，C++语言和标准库提供了两种一次分配一个对象数组的方法。C++提供new, 标准库提供allocator类。

①new和数组

为了让new分配数组，要在类名后跟一对方括号，在其中指明要分配数量。分配成功后会返回指向第一个对象的指针。

    int *pia=new int[9];//方括号中必须是整型，但不用是常量
    //也可以用表示数组类型的类型别名来分配数组，这样new中不用[]
    typedef int arrT[42];
    int *p=new arrT;//即，new int[42]

分配一个数组会得到一个元素类型的指针：虽然我们通常称new T[]分配的内存为‘动态数组’，但用new分配一个数组时，我们并未得到一个数组类型对象，而是得到一个数组元素类型的指针。即使我们用别名定义了一个数组类型，new也不会分配一个数组类型的对象。
由于分配的内存不是一个数组类型，因此不能对动态数组调用begin或end。这些类型用数组维度来返回首和尾后指针。出于相同原因，也不能用范围for来处理(所谓的)动态数组中的元素。
初始化动态分配对象的数组：默认情况下，无论是单个分配还是数组中的，都是默认初始化。若在大小后跟空括号，则对其进行值初始化

    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, 值初始化
    //新标准中，可以提供一个元素初始化器的花括号列表
    int *pia3=new int[10]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    string *psa3=new string[10]{"a", "ab", string (3, 'x')};//前三个用给定值，后面用值初始化
    
    //虽然用空括号对数组元素值初始化，但不能在括号给初始化器，则不能用auto分配数组

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

    /**
     * 可以用任意表达式来确定要分配对象的数目
     */
    size_t n=get_size();//get_size返回需要的元素数目
    int *p=new int[n];//分配数组保存元素
    for(int *q=p;q!=p+n;++q) {}
    /**
     * 若get_size返回0, 代码仍能正常工作
     * 虽然不能创建一个大小为0的静态数组，但当n为0
     * 时，调用new[n]时合法的。
     */
    char arr[0];//✖
    char *cp=new char[0];//✔，但cp不能解引用
    /**
     * 当我们用new分配一个大小为0的数组时，new返回一个合法的非空指针。
     * 此指针保证与new返回的其他任何指针都不同。对于零长度数组来说，此指针就像尾后
     * 指针一样，可以像使用尾后迭代器一样使用这个指针。
     */

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

    delete p;//p必须指向一个动态分配的对象或为空
    delete [] pa;//pa必须指向一个动态分配的数组或为空
    /**
     * 第二条语句销毁pa指向的数组中的元素，并释放对应的内存。
     * 数组中的元素按逆序销毁，即，最后一个首先被销毁，然后是
     * 倒数第二个
     * 
     * 空方括号是必须的，否则行为未定义
     */
     
    typedef int arrT[42];
    int *p=new arrT;//分配一个42个int的数组;p指向第一个元素
    delete [] p;//方括号是必须的，因为是数组

智能指针和动态数组：标准库提供了一个可以管理new分配的数组的unique_ptr版本。为了用一个unique_ptr管理动态数组，我们必须在对象类型后面根一对空括号。

指向数组的unique_ptr
指向数组的unique_ptr不支持成员访问运算符(点和箭头运算符) 其他unique_ptr操作不变
unique_ptr<T[]> u	u可以指向一个动态分配的数组，数组元素类型为T
unique_ptr<T[]> u(p)	u指向内置指针p所指向的动态分配数组。p必须能转换为类型T*
u[i]	返回u拥有的数组中位置i处的对象，u必须指向一个数组

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

与unique_ptr不同, shared_ptr不直接支持管理动态数组。如果希望使用shared_ptr管理一个动态数组，必须提供自己定义的删除器。默认情况下shared_ptr使用delete销毁它指向的对象，不能销毁动态数组。

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

    /**
     * shared_ptr不直接支持动态数组管理这一特性会影响我们如何访问数组中的元素
     */
    //shared_ptr未定义下标运算符，并且不支持指针的算术运算
    for(size_t i=0;i!=10;++i)
        *(sp.get()+i)=i;//使用get获得内置指针

②allocator类

new有一些灵活性上的局限，一方面它将内存分配和对象构造组合在了一起。类似的，delete将对象析构和内存释放组合在了一起。我们分配单个对象时，通常希望将内存分配和对象初始化组合在一起，在这种情况下，我们几乎肯定知道对象应有什么值。
当分配一大块内存时，我们通常计划在这块内存上按需构造对象。我们希望将内存分配和对象构造分离。这意味着我们可以分配大块内存，但只在真正需要时才真正执行对象创建操作。

    //一般，将内存分配和对象构造组合在一起可能会导致不必要的浪费
    string *const p=new string[n];//构造n个空string
    string s;
    string *q=p;//q指向第一个string
    while(cin>>s&&q!=p+n)
        *q++=s;//赋予*q一个新值
    const size_t size=q-p;//记住我们读取了多少个string
    //使用数组
    delete[] p;//释放
    /**
     * new表达式分配并初始化了n个string。但是，我们可能不需要n个string
     * 这样，我们就创造了一些永远也用不到的对象。而且，对于那些确实要使用
     * 的对象，我们也在初始化后立即赋予了他们新值。每个使用到的元素都被
     * 赋值了两次：第一次在默认初始化时，随后是在赋值时。
     * 
     * 更重要的是，那些没有默认构造函数的类就不能动态分配数组了。
     */

allocator类：标准库allocator类定义在头文件memory中，它帮助我们将内存分配和对象构造分离开来。它提供一种类型感知的内存分配方法，它分配的内存是原始的、未构造的。
类似vector, allocator是一个模板，定义一个allocator必须指明其可分配的类型。当一个allocator对象分配内存时，会根据给定的对象类型来确定恰当的内存大小和对齐位置。

标准库allocator类及算法
allocator<T> a	定义了一个名为a的allocator对象，他可以为类型为T的对象分配内存
a.allocate(n)	分配一段原始的、未构造的内存，保存n个类型为T的对象，返回一个指向这块内存起始位置的指针
a.deallocate(p, n)	释放从T*指针p中地址开始的内存，这块内存保存了n个类型为T的对象；p必须是一个先前由allocate返回的指针，且n必须是p创建时所要求的大小。在调用deallocate之前，用户必须对每个在这块内存中创建的对象调用destroy
a.construct(p, args)	p必须是一个类型为T*的指针，指向一块原始内存；arg被传递给类型为T的构造函数，用来在p指向的内存中构造一个对象（args类似make_shared的参数）
a.destroy(p)	p为T*类型的指针，此算法对p指向的对象执行析构函数

allocator分配未构造的内存：allocator分配的内存是未构造的，我们按需要在此内存中构造对象。

    int n=10;
    allocator<string> alloc;//可以分配string的allocator对象
    auto const p=alloc.allocate(n);//分配n个未初始化的string, 这个allocate的调用为n个string分配了内存

    auto q=p;//q指向最后构造的元素之后的位置，此时一个元素都没构造，所以q在起始位置
    alloc.construct(q++);//起始位置构造了空字符串
    alloc.construct(q++, 10, 'c');//第二个位置为10个'c'组成的字符串
    alloc.construct(q++, "hi");//第三个位置为"hi"
    //还未构造对象就是用原始内存是错误的
    
    //当我们用完对象后，必须对每个构造的元素调用destroy来销毁它们
    //一旦元素被销毁，可以用这块内存保存其他string，也可以将其归还系统
    while(q!=p) alloc.destroy(--q);//释放真正构造的string
    
    //destory执行析构函数，deallocate释放内存, 传递给deallocate的指针不能为空
    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必须指向足够大的未构造的原始内存，能够容纳给定数量的对象.对象的值均为t的拷贝

③使用标准库:文本查询程序

略。

十二. 拷贝控制

当定义一个类时，我们显式或隐式的指定在此类型的对象拷贝、移动、赋值和销毁时做什么。一个类通过定义五种特殊的成员函数来控制这些操作，包括：拷贝构造函数、拷贝赋值运算符、移动构造函数、移动赋值运算符和析构函数。拷贝和移动构造函数定义了当用同类型的另一个对象初始化本对象时做什么。拷贝和移动赋值运算符定义了将一个对象赋予同一个类型的另一个对象时做什么。析构函数定义了当此类型对象销毁时做什么。我们称这些操作为拷贝控制操作。
如果一个类没有定义所有这些拷贝控制成员，编译器会自动为他定义缺失的操作。因此，很多类会忽略这些拷贝控制操作，但对一些类来说，依赖这些操作的默认定义会导致灾难。
最关键的是认识到什么时候使用这些拷贝控制操作。

1.拷贝、赋值与销毁

①拷贝构造函数

如果一个构造函数的第一个参数是自身类类型的引用，且任何额外参数都有默认值，则此构造函数是拷贝构造函数。

/**
 * 拷贝构造函数第一个参数必须是引用类型
 * 虽然可以定义一个非const引用的拷贝构造函数，但此参数几乎总是const
 * 拷贝构造函数在很多情况被隐式的使用，因此其不该是explicit
 */
class Foo
{
public:
    Foo();//默认构造函数
    Foo(const Foo&);//拷贝构造函数
};

合成拷贝构造函数：若我们没有为一个类定义拷贝构造函数，编译器会为我们定义一个。与合成默认构造函数不同，即使我们定义了其他构造函数，编译器也会为我们合成一个拷贝构造函数。
对于某些类来说，合成拷贝构造函数用来阻止我们拷贝该类类型的对象。而一般情况，合成的拷贝构造函数会将其参数的成员逐个拷贝到正在创建的对象中。编译器从给定对象中依次将每个非static成员拷贝到正在创建的对象中。
每个成员的类型决定了它如何拷贝：对于类类型的成员，会使用其拷贝构造函数来拷贝；内置类型的成员则直接拷贝。虽然我们不能直接拷贝一个数组，但合成拷贝构造函数会逐元素的拷贝一个数组类型的成员。如果数组元素是类类型，则使用元素的拷贝构造函数来进行拷贝

class Sales_data
{
public:
    //其他成员和构造函数的定义如前
    Sales_data(const Sales_data&);//与合成的拷贝构造函数等价的拷贝构造函数声明
private:
    string bookNo;
    int units_sold=0;
    double revenue=0.0;
};
//与Sales_data的合成的拷贝构造函数等价
Sales_data::Sales_data(const Sales_data &orig) :
bookNo(orig.bookNo), //使用string的拷贝构造函数
units_sold(orig.units_sold), //拷贝orig.units_sold
revenue(orig.revenue)   //拷贝orig.revenue
{}//空函数体

拷贝初始化：理解直接初始化和拷贝初始化的区别。

    string dots(10, '.');//直接初始化
    string s(dots);//直接初始化
    string s2=dots;//拷贝初始化
    string null_book="99sda";//拷贝初始化
    string nines=string (10, '9');//拷贝初始化

当使用直接初始化时，实际上是要求编译器使用普通的函数匹配来选择与我们提供的参数最匹配的构造函数。
当使用拷贝初始化时，我们要求编译器将右侧运算对象拷贝到正在创建的对象中，如果需要的话还需要进行类型转换。
拷贝初始化通常使用拷贝构造函数来完成。但是，如果一个类有一个移动构造函数，则拷贝初始化有时会使用移动构造函数而非拷贝构造函数来完成。现在只需了解拷贝初始化何时发生，以及拷贝初始化是依赖拷贝构造函数或移动构造函数来完成的就可以。
拷贝初始化发生情况：
[1] =
[2] 将一个对象作为实参传递给一个非引用类型的实参
[3] 用花括号列表初始化一个数组中的元素或一个聚合类中的成员
[4] 某些类型还会对它们所分配的对象使用拷贝初始化。例如，当初始化标准库容器或调用其insert或push成员时，容器会对其元素进行拷贝初始化。与之相对，用emplace成员创建的元素都进行直接初始化。
-
参数和返回值：在函数调用过程中，具有非引用类型的参数要进行拷贝初始化。类似的，当一个函数具有非引用的返回类型时，返回值会被用来初始化调用方的结果。
拷贝构造函数被用来初始化非引用类类型参数，解释了为什么拷贝构造函数自己的参数必须是引用类型。如果其参数不是引用类型，则调用永远不会成功---为了调用拷贝构造函数，我们必须拷贝它的实参，但为了拷贝实参，我们又需要调用拷贝构造函数，如此无限循环。
拷贝初始化的限制：如果我们使用的初始值要求通过一个explicit的构造函数来进行类型转换，那么使用拷贝初始化还是直接初始化就不是无关紧要的了.

    vector<int> v1(10);//✔，直接初始化
    vector<int> v2=10;//✖，接受大小参数的构造函数是explicit的
    void f(vector<int>);//f的参数进行拷贝初始化
    f(10);//✖，不能用一个explicit的构造函数拷贝一个实参，无法隐式转换
    f(vector<int>(10));//✔，从一个int直接构造一个临时vector

编译器可以绕过拷贝构造函数：在拷贝初始化过程中，编译器可以跳过拷贝/移动构造函数，直接创建对象。

    string null_book="9a";//拷贝初始化
    string null_book2("9a");//编译器略过了拷贝构造函数

②拷贝赋值运算符

与类控制对象如何初始化一样，类也可以控制其对象如何赋值。与拷贝构造函数一样，如果类未定义自己的拷贝赋值运算符，编译器会为他合成一个。参数不是必须是&类型，拷贝构造函数必须是。

    Sales_data trans, accum;
    trans= accum;//使用Sales_data的拷贝赋值运算符

重载赋值运算符：在介绍合成赋值运算符之前，我们需要了解一点重载运算符。重载运算符本质上是函数，其名字由operator关键字后接表示要定义的运算符的符号组成。因此，赋值运算符就是一个名为operator=的函数。类似任何其他函数，运算符函数也有一个返回类型和参数列表。
重载运算符的参数表示运算符的运算对象。某些运算符，包括赋值运算符，必须定义为成员函数。如果一个运算符是一个成员函数，其左侧运算对象就绑定到隐式的this参数。对于一个二元运算符，例如赋值运算符，其右侧运算对象作为显式参数传递。

class Foo
{
    /**
     * 为了与内置类型的赋值保持一致，赋值运算符通常返回一个指向
     * 其左侧运算对象的引用。标准库通常要求保存在容器中的类型要具有
     * 赋值运算符，且返回值是左侧运算对象的引用
     */
public:
    Foo& operator=(const Foo&);//
};

合成拷贝赋值运算符：如果一个类未定义自己的拷贝赋值运算符，编译器会为他生成一个合成拷贝赋值运算符。类似拷贝构造函数，对于某些类，合成拷贝赋值运算符用来禁止该类型对象的赋值。
如果拷贝赋值运算符并非出于上述目的，它会将右侧运算对象的每个非static赋予左侧运算对象的对应成员，这是通过成员类型的拷贝赋值运算符来完成的。对于数组类型的成员，逐个赋值数组元素。合成拷贝赋值运算符返回一个指向左侧运算对象的引用。

Sales_data& Sales_data::operator=(const Sales_data &rhs)
{
    bookNo=rhs.bookNo;//调用string::operator=
    units_sold=rhs.units_sold;//调用内置int赋值
    ...
    return *this;//返回一个此对象的引用
}

③析构函数

析构函数执行与构造函数相反的操作：构造函数初始化对象的非static数据成员，还可能做一些其他工作；析构函数释放对象使用的资源，并销毁对象的非static成员
析构函数是类的一个成员函数，名字由波浪号接类名构造。它没有返回值，也不接受参数。
由于析构函数不接受参数，因此他不会被重载。对于一个给定类，只会有唯一一个析构函数，

class Foo
{
public:
    ~Foo();//析构函数
};

析构函数完成什么工作：析构函数有一个函数体和一个析构部分。在一个构造函数中，成员的初始化是在函数体执行前完成的，且按照他们在类中出现的顺序进行初始化(初始化部分)。在一个析构函数中，首先执行函数体，然后销毁成员。成员按初始化顺序的逆序销毁。
在对象最后一次使用之后，析构函数的函数体可执行类设计者希望执行的任何收尾工作。通常，析构函数释放对象在生存期分配的所有资源。
在一个析构函数中，不存在类似构造函数中初始化列表的东西来控制成员如何销毁，析构部分是隐式的。成员销毁时发生什么完全依赖于成员的类型。销毁类类型的成员需要执行成员自己的析构函数。内置类型没有析构函数，所以销毁内置类型什么也不做。
隐式销毁一个内置指针类型的成员不会delete它所指向的对象。与普通指针不同，智能指针是类类型，所有具有析构函数，因此智能指针成员在析构阶段会被自动销毁。
什么时候会调用析构函数：无论何时一个对象被销毁，就会自动调用其析构函数。
[1] 变量在离开其作用域时被销毁
[2] 当一个对象被销毁时，其成员被销毁
[3] 容器(无论是标准库容器还是数组)被销毁时，其元素被销毁。
[4] 对于动态分配的对象，当对指向他的指针应用delete运算符时被销毁
[5] 对于临时对象，当创建它的完整表达式结束时被销毁。
由于析构函数自动运行，程序可以按需分配资源，而无需担心何时释放这些资源。
当指向一个对象的引用或指针离开作用域(内置类型无析构函数)，析构函数不会执行。
-
合成析构函数：当一个类未定义自己的析构函数时，编译器会为他定义一个合成析构函数。对于某些类，合成析构函数被用来阻止该类型的对象被销毁。如果不是这种情况，合成析构函数的函数体为空。先执行函数体，再销毁成员(根据其类型)

④三/五法则

有三个基本操作可以控制类的拷贝操作：拷贝构造函数、拷贝赋值运算符和析构函数。在新标准下，一个类还可以定义一个移动构造函数和一个移动赋值运算符。
需要析构函数的类也需要拷贝和赋值操作：一个类是否要定义自己版本的拷贝控制成员，一个基本原则是首先确定这个类是否需要一个析构函数。如果类需要析构函数，它几乎肯定也要拷贝构造函数和拷贝赋值运算符。

/**
 * 这个类在构造函数中分配动态内存
 * 合成析构函数不会delete一个指针数据成员
 * 因此该类需要定义一个析构函数来释放构造函数分配的内存
 */
class HasPtr
{
public:
    HasPtr(const string &s=string()):ps(new string(s)), i(0) {}
    ~HashPtr()//✖，HasPtr需要一个拷贝构造函数和一个拷贝赋值运算符
    {
        delete ps;
    }
    
private:
    string *ps;
    int i;
};

/**
 * 上述类：
 * 构造函数中分配的内存将在HasPtr对象销毁时释放。
 * 严重错误：这个版本的类使用了合成的拷贝构造函数和拷贝赋值运算符
 * 。这些函数简单拷贝指针成员，这意味着多个HasPtr对象可能指向相同的内存
 */
/**
 * 当f返回时，hp和ret都被销毁，在两个对象上都会调用HasPtr的析构函数。此
 * 析构函数会delete ret和hp中的指针成员。但这两个对象包含相同的指针值。
 * 会导致此指针被delete两次。
 */
HasPtr f(HasPtr hp)//传值参数，拷贝
{
    HasPtr ret=hp;//拷贝给定的HasPtr
    return ret;//ret和hp被销毁
}

//此外f的调用者还会使用传递给f的对象
HasPtr p("some values");
f(p);//当f结束时，p.ps指向的内存被释放

需要拷贝操作的类也需要赋值操作，反之亦然：例如一个类为每个对象分配一个独有序号。则需要拷贝构造函数为每个新创建的对象生成一个新的独有序号，别的数据成员都拷贝。这个类还需要自定义拷贝赋值运算符避免将序号赋予目的对象。但这个类不需要自定义析构函数。

⑤使用=default

可以通过将拷贝控制成员定义为-defaukt来显式的要求编译器生成合成版本。
当我们在类内用=default修饰成员的声明时，合成的函数将隐式的声明为内联的。若不希望合成的成员是内联函数，应该只对成员的类外定义使用=default，就像下面拷贝赋值运算符所做的那样。

class Sales_data
{
public:
    //拷贝控制成员，使用default
    Sales_data()=default;
    Sales_data(const Sales_data&)=default;
    Sales_data& operator=(const Sales_data &);
    ~Sales_data()=default;
};
Sales_data& Sales_data::operator=(const Sales_data &)=default;

⑥阻止拷贝

虽然大多数类应该定义(显式隐式)拷贝构造函数和拷贝赋值运算符，但对于某些类来说，这些操作没有意义。在此情况下，定义类时必须采用某种机制阻止拷贝或赋值。例如，iostrem类阻止了拷贝，以避免多个对象写入或读取相同的IO缓存。为了阻止拷贝，应定义拷贝控制成员，以免编译器生成合成版本的。
定义删除函数：在新标准下，可以通过将拷贝构造函数和拷贝赋值运算符定义为删除函数来阻止拷贝。删除函数：虽然声明了它，但不能以任何方式使用它。在函数的参数列表后面加上=delete来指出希望将它定义为删除的。

/**
 * 与default不同，=delete必须出现在函数第一次声明的时候，这个差异与这些声明的含义
 * 在逻辑上是吻合的。一个默认的成员只影响为这个成员而生成的代码，因此=default直到
 * 编译器生成代码时才需要。另一方面，编译器需要知道一个函数是删除的，以便禁止试图使用
 * 它的操作
 * 
 * 与=default另一个不同是，我们可以为任何函数指定=delete(我们只能对编译器可以合成的默认构造函数
 * 和拷贝控制成员使用=default)。我们希望引导函数匹配过程时，删除函数有时也是有用的，
 */
struct NoCopy
{
    NoCopy()=default;//合成默认构造函数
    NoCopy(const NoCopy&)=delete;//阻止拷贝
    NoCopy &operator=(const NoCopy&)=delete;//阻止赋值
    ~NoCopy()=default;//使用合成的析构函数
};

析构函数不能是删除的成员：不能删除析构函数，若析构函数被删除，就无法销毁此类型的对象了。对于一个删除了析构函数的类型，编译器将不允许定义该类型的变量或创建该类的临时对象。
如果一个类的某个成员的类型删除了析构函数，我们也不能定义该类的变量或临时对象。原理同上。
对于删除了析构函数的类型，虽然不能定义这种类型的变量或成员，但可以动态分配这种类型的对象。但是不能释放这些对象

struct NoDtor
{
    NoDtor()=default;//使用合成默认构造函数
    ~NoDtor()=delete;//我们不能销毁NoDoctor类型的对象
};
NoDtor nd;//✖，NoDtor的析构函数是删除的
NoDtor *p=new NoDtor();//✔，但是不能delete p

合成的拷贝控制成员可能是删除的：若未定义拷贝控制成员或构造函数，编译器会定义合成版本的。对于某些类来说，编译器将这些合成的成员定义为删除的函数：
[1] 如果类的某个成员的析构函数是删除的或不可访问的(例如private), 则类的合成析构函数被定义为删除的。
[2] 若类的某个成员的拷贝构造函数是删除的或不可访问的，则类的合成拷贝构造函数被定义为删除的。若类的某个成员的析构函数是删除的或不可访问的，则类合成的拷贝构造函数也被定义为删除的。
[3] 若类的某个成员的拷贝赋值运算符是删除的或不可访问的或是类有一个const的(const是常量，不能再次赋值)或引用成员(引用赋值，改变的是引用指向对象的值，而不是引用本身，即使赋值后，引用本身还是指向原来左侧对象)，则类的合成拷贝赋值运算符被定义为删除的。
[4] 若类的某个成员的析构函数是删除的或不可访问的，或是类有一个引用成员(他是引用别人)，他没有类内初始化器，或是类有一个const成员(const成员必须初始化)，他没有类内初始化器且其类型未显式定义默认构造函数，则该类的默认构造函数被定义为删除的。
本质：如果一个类有数据成员不能默认构造、拷贝、赋值或销毁，则对应的成员函数将被定义为销毁的。
一个成员有删除的或不可访问的析构函数导致合成的默认和拷贝构造函数被定义为删除的，若没这条规则，我们可能会创建出无法销毁的对象。
-
private拷贝控制：在新标准发布前，类是通过将其拷贝构造函数和拷贝赋值运算符声明为private的来阻止拷贝。

class PrivateCopy
{//私有的，普通用户代码无法访问，友元和成员函数扔可以拷贝对象。
 //为了阻止友元和成员函数拷贝，我们将拷贝控制成员声明为private的，但不定义它们
    PrivateCopy(const PrivateCopy&);
    PrivateCopy &operator=(const PrivateCopy&);
public:
    PrivateCopy()=default;
    ~PrivateCopy();//用户可以定义此类型对象，但无法拷贝它
};

2. 拷贝控制和资源管理

管理类外资源的类必须定义拷贝控制成员。这种类需要析构函数释放资源，所以需要析构函数，，几乎肯定要一个拷贝构造函数和一个拷贝赋值运算符。
为了定义这些成员，首先要确定此类型对象的拷贝语义。一般来说有两种选择：可以定义拷贝操作，使类的行为看起来像一个值或像一个指针。
类的行为像一个值，意味着它应该也有自己的状态。当我们拷贝一个像值一样的对象时，副本和原对象是完全独立的。改变副本不会对原对象有任何影响，反之亦然。
类的行为像一个指针，则共享状态。当拷贝一个这种类的对象时，副本和原对象使用相同的底层数据。改变副本也会改变原对象，反之亦然。
标准库容器和string类的行为像一个值，shared_ptr类提供类似指针的行为。IO类和unique_ptr不允许拷贝或赋值，因此它们的行为既不像值也不像指针。
对于下面的HasPtr类有两个成员，int和string指针。通常，类直接拷贝内置类型(不包括指针，指针是共享态，拷贝了不独立)；这些成员本身就是值，因此通常应让它们的行为像值一样。而如何拷贝指针成员决定了像HasPtr这样的类是具有类值行为还是类指针行为。

①行为像值的类

为了提供类值的行为，对于类管理的资源，每个对象都应该有一份自己的拷贝。这意味着对于ps指向的string, 每个HasPtr对象都必须有自己的拷贝。为了实现类值行为，HasPtr需要：
[1] 定义一个拷贝构造函数，完成string的拷贝，而不是拷贝指针
[2] 定义一个析构函数来释放string
[3] 定义一个拷贝赋值运算符来释放对象当前的string, 并从右侧运算对象拷贝string

class HasPtr
{
public:
    HasPtr(const string &s=string()):ps(new string(s)), i(0) {}//逻辑上默认构造函数
    HasPtr(const HasPtr &p):ps(new string(*p.ps)), i(p.i) {}//string是类值的，所以其拷贝构造函数new string()也是值行为
    HasPtr& operator=(const HasPtr &);//拷贝赋值运算符
    ~HasPtr()
    {
        delete ps;
    }
private:
    string *ps;
    int i;
};
HasPtr& HasPtr::operator=(const HasPtr &rhs)
{
    auto newp=new string(*rhs.ps);//拷贝底层string, 先赋予临时对象，防止自赋值时出现异常
    delete ps;//释放旧内存
    ps=newp;
    i=rhs.i;
    return  *this;//返回本对象
}

关键概念：赋值运算符

如果将一个对象赋予它自身，赋值运算符必须能正确工作。
大多数赋值运算符组合了析构函数和拷贝构造函数的工作

当编写一个赋值运算符时，一个好的模式是先将右侧运算对象拷贝到一个局部临时对象中。当拷贝完成后，销毁左侧运算对象的现有成员就是安全的了。

HasPtr& HasPtr::operator=(const HasPtr &rhs)
{
    delete ps;//释放旧内存
    ps=new string(*rhs.ps);//✖，若是自赋值，*rhs.ps访问一个已被释放的对象
    i=rhs.i;
    return  *this;//返回本对象
}

②定义行为像指针的类

对于行为类似指针的类，我们需要为其定义拷贝构造函数和拷贝赋值运算符，来拷贝指针成员本身而不是他指向的string。类仍然需要自己的析构函数来释放接受string参数的构造函数分配的内存。但在本例，只有当最后一个指向string的HasPtr销毁时，才可释放string.
令一个类展现类似指针的行为的最好方法是用shared_ptr来管理类中的资源。拷贝(赋值)一个shared_ptr会拷贝(赋值)shared_ptr所指向的指针。shared_ptr类自己记录有多少用户共享它所指的对象。当没有用户使用对象，shared_ptr负责释放资源。
但是，有时我们希望直接管理资源。在这种情况下，使用引用计数有用。
引用计数：工作方式
[1] 除了初始化对象外，每个构造函数(拷贝构造函数除外)还要创建一个引用计数，用来记录有多少对象与正在创建的对象共享状态。当我们创建一个对象时，只有一个对象共享状态，因此将计数器初始化为1。
[2] 拷贝构造函数不分配新的计数器，而是拷贝给定对象的数据成员，包括计数器。拷贝构造函数递增共享的计数器，指出给定对象的状态又被一个新用户共享。
[3] 析构函数递减计数器，指出共享状态的用户少了一个。如果计数器变为0，则析构函数释放状态
[4] 拷贝赋值运算符递增右侧运算对象的计数器，递减左侧运算对象的计数器。如果左侧运算对象的计数器变为0，拷贝赋值运算符必须销毁其状态。
-
计数器存放位置：不能直接作为HasPtr对象的成员，不易更新。计数器保存在动态内存中。当创建一个对象时，分配一个新的计数器。当拷贝或赋值对象时，拷贝指向计数器的指针。
实现：

class HasPtr
{
public:
    HasPtr(const string &s=string()):ps(new string(s)), i(0), use(new size_t(1)) {}//逻辑上默认构造函数
    HasPtr(const HasPtr &p):ps(new string(*p.ps)), i(p.i), use(p.use)
    {
        ++*use;//拷贝时，递增计数器
    }
    HasPtr& operator=(const HasPtr &);//拷贝赋值运算符
    ~HasPtr();
private:
    string *ps;
    int i;
    size_t *use;//用来记录有多少对象共享*ps的成员
};

//当计数器为0时才释放内存
HasPtr::~HasPtr()
{
    if(--*use==0)
    {
        delete ps;//释放string内存
        delete use;//释放计数器内存
    }
}

//递增右侧，递减左侧，适当时候释放内存
HasPtr& HasPtr::operator=(const HasPtr &rhs)
{
    ++*rhs.use;//递增右侧
    if(--*use==0)//递减左侧
    {
        delete ps;
        delete use;
    }
    
    ps=rhs.ps;//指针拷贝
    i=rhs.i;
    use=rhs.use;
    return *this;//返回本对象
}

3. 交换操作

除了定义拷贝控制成员，管理资源的类通常还定义一个名为swap的函数。
如果一个类定义了自己的swap, 那么算法将使用类自定义版本。否则使用标准库定义的swap。
编写自己的swap函数：

//行为像值的类
class HasPtr
{
    friend void swap(HasPtr&, HasPtr&);

public:
    HasPtr(const string &s=string()):ps(new string(s)), i(0) {}//逻辑上默认构造函数
    HasPtr(const HasPtr &p):ps(new string(*p.ps)), i(p.i) {}//string是类值的，所以其拷贝构造函数new string()也是值行为
    HasPtr& operator=(const HasPtr &);//拷贝赋值运算符
    ~HasPtr()
    {
        delete ps;
    }
private:
    string *ps;
    int i;
};

inline void swap(HasPtr &lhs, HasPtr &rhs)
{
    using std::swap;
    swap(lhs.ps, rhs.ps);//交换指针，而不是string数据
    swap(lhs.i, rhs.i);//交换int成员
}

swap函数应该调用swap, 而不是std::swap: 上述代码，在一般情况下swap调用的不是std::swap. 在本例中，数据成员是内置类型的，无特定版本的swap, 所以在本例中对swap的调用会调用标准库std::swap.
但是，假如一个类的成员有自己类型特定的swap函数，调用std::swap就是错误的了。例如，有一个类Foo,他有一个类型为HasPtr的成员h, 若我们未定义Foo版本的swap, 那么就会使用标准库版本的swap。如我们所见，标准库swap对HasPtr管理的string进行了不必要的拷贝(类值耗时)。
可以为Foo编写一个swap函数，来避免这些拷贝。

void swap(Foo &lhs, Foo &rhs)
{
    //✖，这个函数使用了标准库版本的swap, 而不是HasPtr版本
    std::swap(lhs.h, rhs.h);
}

/**
 * 上述代码编译通过。但是与使用默认版本的swap没有任何性能差异
 * 问题在于我们显式调用了标准库版本的swap, 但我们希望用HasPtr
 * 的swap(交换指针)
 */
void swap(Foo &lhs, Foo &rhs)
{
    using std::swap;
    swap(lhs.h, rhs.h);//HasPtr版本的swap
}
/**
 * 如果存在类型特定的swap版本，其匹配程度会优于std中定义的版本（
 * 第十五章第3会解释），特例化匹配程度优先于模板
 * 
 * 为什么swap函数中的using声明没有隐藏HasPtr版本swap声明？
 * 第十七章第2第③会解释，实参是类，还会查找实参所在的命名空间
 */

在赋值运算符中使用swap:定义swap的类通常用swap来定义它们的赋值运算符。这些运算符使用了一种名为拷贝并交换的技术。这种技术将左侧运算对象与右侧运算对象的一个副本进行交换

//行为像值的类
class HasPtr
{
    friend void swap(HasPtr&, HasPtr&);

public:
    HasPtr(const string &s=string()):ps(new string(s)), i(0) {}//逻辑上默认构造函数
    HasPtr(const HasPtr &p):ps(new string(*p.ps)), i(p.i) {}//string是类值的，所以其拷贝构造函数new string()也是值行为
    HasPtr& operator=(HasPtr);//拷贝赋值运算符
    ~HasPtr()
    {
        delete ps;
    }
private:
    string *ps;
    int i;
};

inline void swap(HasPtr &lhs, HasPtr &rhs)
{
    using std::swap;
    swap(lhs.ps, rhs.ps);//交换指针，而不是string数据
    swap(lhs.i, rhs.i);//交换int成员
}

/**
 * 在此版本的赋值运算符，参数不是引用(也是为了下面的自赋值)，因此右侧对象以传值方式传给
 * 了赋值运算符。因此，rhs是右侧运算对象的一个副本(类值的拷贝构造函数)。
 * 且string也是副本， //rhs仅是一个副本罢了
 */
/**
 * 这个技术自动处理了自赋值情况天然安全。
 * 它通过改变左侧对象前，拷贝右侧对象保证了自身赋值的正确
 */
HasPtr& HasPtr::operator=(HasPtr rhs)
{
    //交换左侧运算对象和局部变量rhs的内容，rhs指向本对象曾经使用的内存
    swap(*this, rhs);//HasPtr的swap
    return *this;//rhs被销毁(执行析构函数)，从而delete了rhs中的指针
}

4. 拷贝控制示例

两个类名为Message和Folder, 分别表示电子邮件消息和消息目录。每个Message对象可以出现在多个Folder中。但是任意给定的Message的内容只有一个副本。
为了记录Message位于哪些Folder中，每个Message都会保存一个它所在Folder的指针的set, 同样的，每个Folder都保存一个它包含的Message的指针的set.
Message会提供save和remove操作，来向一个给定的Folder添加或删除一条Message。创建一个新的Message会指明内容，但不会指出Folder, 所以需要save
拷贝一个Meaagse时，副本和原对象是两个不同的Message对象。因此，拷贝Message的操作包括消息内容和Folder指针set的拷贝
销毁Message时，所有包含此消息的Folder都删除此Message的指针
当把一个Message赋予另一个Message对象时，左侧Message内容被右侧替代。同时更新Folder, 从原来包含左侧Folder把它删除，并添加到右侧的Folder
析构函数和拷贝赋值运算符都必须从包含一条Message的所有Folder中删除它。拷贝构造函数和拷贝赋值运算符都要将一个Message添加到给定的一组Folder。我们将定义两个private工具函数来完成这些工作(代码复用)
Folder也包含类似的拷贝控制成员，来添加或删除它保存的Message。假定Folder类包含名为addMsg和remMsg的成员，分别完成在给定Folder对象的消息集合中添加和删除Message的工作。
Message类：

class Message;
class Folder
{
    /**
     * 略
     */
public:
    void addMsg(Message*);
    void remMsg(Message*);
};

class Message
{
    friend class Folder;
    friend void swap(Message&, Message&);
public:
    //Folder被隐式初始化为空集合
    explicit Message(const string &str=""):contents(str) {}//默认构造函数
    //拷贝控制成员, 用来管理指向本Message的指针
    Message(const Message&);//拷贝构造函数
    Message& operator=(const Message&);//拷贝赋值运算符
    ~Message();//析构函数
    //从给定Folder集合中添加/删除本Messsage
    void save(Folder&);
    void remove(Folder&);
private:
    string contents;//实际消息文本
    set<Folder*> folders;//包含本Message的Folder
    /**
     * 拷贝构造函数、拷贝赋值运算符和析构函数所使用的工具函数
     * 将本Message添加到指向参数的Folder中
     */
     void add_to_Folders(const Message&);
     //从folders中的每个Folder中删除本Message
     void remove_from_Folders();
};

void Message::save(Folder &f)
{
    folders.insert(&f);//将给定Folder添加到我们的Folder列表中
    f.addMsg(this);//将本Message添加到f的Message集合中
}

void Message::remove(Folder &f)
{
    folders.erase(&f);//将给定的Folder从我们的Folder列表中删除
    f.remMsg(this);//将本Message从f的Message集合中删除
}

void Message::add_to_Folders(const Message &m)
{
    for(auto f:m.folders)//对每个包含m的Folder
        f->addMsg(this);//向该Folder添加一个指向本Message的指针
}

Message::Message(const Message &m) : contents(m.contents), folders(m.folders)
{
    add_to_Folders(m);//将本消息添加到指向m的Folder中
}

//从对应的Folder中删除本Messgage
void Message::remove_from_Folders()
{
    for(auto f:folders)
        f->remMsg(this);//对folders中每个指针，从该Folder中删除本Message
}

Message::~Message()
{
    remove_from_Folders();
}

/**
 * 要组织好代码，处理好自赋值情况
 * @param rhs
 * @return
 */
Message& Message::operator=(const Message &rhs)
{
    //通过先删除指针再插入它们来处理自赋值情况
    remove_from_Folders();//更新已有Folder
    contents=rhs.contents;//从rhs拷贝消息
    folders=rhs.folders;//从rhs拷贝Folder指针
    add_to_Folders(rhs);//将本message添加到那些Folder中
    return *this;
    //若先add_to_message再remove_from_folders，会将此Message从他所在的所有Folder中删除
}

void swap(Message &lhs, Message &rhs)
{
    using std::swap;//在本例中严格说不需要，但这是一个好习惯
    //将每个消息从它原来所在的Folder中删除
    for(auto f:lhs.folders)
        f->remMsg(&lhs);
    for(auto f:rhs.folders)
        f->remMsg(&rhs);
    //交换contents和Folder指针set
    swap(lhs.folders, rhs.folders);//使用swap(set&, set&)
    swap(lhs.contents, rhs.contents);//使用swap(string&, string&)
    //将每个Message的指针添加到它的新Folder中
    for(auto f:lhs.folders)
        f->addMsg(&lhs);
    for(auto f:rhs.folders)
        f->addMsg(&rhs);
}

5. 动态内存管理

某些类需要在运行时分配可变大小的内存空间。这种类通常可以使用标准库容器来保存他们的数据(vetor等)。
但是，这一策略并不是对每个类都适用；某些类需要自己进行内存分配。这些类一般来说必须定义自己的拷贝控制成员来管理所分配的内存。
例如，我们将实现标准库vector类的一个简化版本，即不使用模板，类只用于string.因此被命名为StrVec
-
StrVec类的设计:同vector, 当空间足够容纳更多元素，则在下一个可用位置构造元素。若无可用空间，则重新分配空间，然后将已有元素移动到新空间，释放旧空间，并添加新元素。
我们将使用一个allocator来获得原始内存，并利用其方法构造，删除，释放。
每个StrVec有三个指针成员指向其元素所使用的内存：
[1] elements指向分配的内存中的首元素
[2] first_free，指向最后一个实际元素之后的位置
[3] cap, 指向分配的内存末尾之后的位置
除了这些指针外，StrVec还有一个名为alloc的静态成员，其类型为allocator<string>。alloc成员会分配StrVec使用的内存。我们的类还有四个工具函数：
[1] alloc_n_copy会分配内存，并拷贝一个给定范围中的元素。
[2] free会销毁构造的元素并释放内存。
[3] chk_n_alloc会调用reallocate来分配更多内存
[4] reallocate在内存用完时为StrVec分配新内存
还有一些vector接口中的一些成员
-
在重新分配内存的过程中移动而不是拷贝元素：
reallocate会做什么: 为一个新的、更大的string数组分配内存；在内存空间的前一部分构造对象，保存现有元素。销毁原内存空间的元素，并释放内存。
由上可以看出，为一个StrVec重新分配内存空间会引起从旧内存空间到新内存空间逐个拷贝string。
虽然不知道string实现细节，但知道其类值，新string和旧string是相互独立的。因此，拷贝一个string必须为构成它的字符分配空间，而销毁一个string必须释放占用的内存。
拷贝一个string影响性能，但reallocate最后只需要一个string, 拷贝这些string中的数据时多余的。在重新分配内存空间时，若能避免分配和释放string的额外开销，会提升性能
移动构造函数和std::move:
通过使用新标准库引入两种机制，就可以避免string的拷贝。有一些标准库类，包括string，都定义了“移动构造函数”。移动构造函数通常是将资源从给定对象‘移动’而不是拷贝到正在创建的对象。
第二个机制是一个名为move的标准库函数，它定义在utility头文件中。当reallocate在新内存构造string时，必须调用move表示希望使用string的移动构造函数。如果漏掉了move调用，将会使用string的拷贝构造函数。其次，通常不为move提供一个using声明, 原因在第十七章2③解释。当我们使用move时，直接调用std::move而不是move.
StrVec类定义：

//类vector类内存分配策略的简化实现
class StrVec
{
public:
    StrVec():elements(nullptr), first_free(nullptr), cap(nullptr) {}//allocator成员默认初始化
    StrVec(const StrVec&);//拷贝构造函数
    StrVec &operator=(const StrVec&);//拷贝赋值运算符
    ~StrVec();//析构函数
    void push_back(const string&);//拷贝元素
    size_t size() const//数组元素个数
    {
        return first_free-elements;
    }

    size_t capacity() const//数组容量
    {
        return cap-elements;
    }

    string *begin() const {return elements;}
    string *end() const {return first_free;}

private:
    static allocator<string> alloc;//分配元素
    //被添加元素的函数所使用
    void chk_n_alloc()//确保有空间足够容纳新元素
    {
        if(size()==capacity())
            reallocate();
    }
    pair<string*, string*> alloc_n_copy(const string*, const string*);
    void free();//销毁元素并释放内存
    void reallocate();//获得更多元素并拷贝已有元素
    string *elements;//指向数组首元素的指针
    string *first_free;//指向数组第一个空闲元素的指针
    string *cap;//指向数组内存尾后的指针
};

void StrVec::push_back(const string &s)
{
    chk_n_alloc();//确保空间
    //在first_free指向的元素中构造s的副本
    alloc.construct(first_free++, s);//只有一个参数s,会使用其string拷贝构造函数拷贝元素
}

//拷贝n个元素
pair<string*, string*> StrVec::alloc_n_copy(const string *b, const string *e)
{
    //分配空间保存给定范围中的元素
    auto data=alloc.allocate(e-b);//计算空间
    //初始化并返回一个pair, 该pair由data和uninitialized_copy的返回值组成(尾后元素的指针)
    return {data, uninitialized_copy(b, e, data)};
}

//首先destroy元素(析构)，然后释放StrVec自己分配的内存空间
//for循环从构造的尾元素开始，逆序销毁元素
void StrVec::free()
{
    //不能传递给deallocate一个空指针，如果elements为0，函数什么也不做
    if(elements)
    {
        for(auto p=first_free;p!=elements;)
            alloc.destroy(--p);
    }
    alloc.deallocate(elements, cap-elements);
}

//拷贝构造函数
StrVec::StrVec(const StrVec &s)
{
    auto newdata= alloc_n_copy(s.begin(), s.end());
    elements=newdata.first;
    first_free=cap=newdata.second;
}

//析构函数
StrVec::~StrVec()
{
    free();
}

//拷贝赋值运算符
StrVec &StrVec::operator=(const StrVec &rhs)
{
    //调用alloc_n_copy分配内存
    auto data= alloc_n_copy(rhs.begin(), rhs.end());
    free();//释放旧空间
    elements=data.first;
    first_free=cap=data.second;
    return *this;
}

//重新分配空间
void StrVec::reallocate()
{
    //将分配当前大小两倍的内存空间
    auto newcapacity=size()?2*size():1;
    //分配新内存
    auto newdata=alloc.allocate(newcapacity);
    //将数据从旧内存移动到新内存
    auto dest=newdata;//起始指针，下一个空闲位置
    auto elem=elements;//起始指针，旧数组下一个元素
    for(size_t i=0;i!=size();++i)//移动元素
        alloc.construct(dest++, std::move(*elem++));//move的返回结果，会令construct使用string的移动构造函数
    free();//释放旧内存空间
    //更新数据结构
    elements=newdata;
    first_free=dest;
    cap=elements+newcapacity;
}

6. 对象移动

新标准一个最主要特性是可以移动而非拷贝对象的能力。在某些情况，对象被拷贝后就被立马销毁了，在此情况，移动而非拷贝元素会大幅提升性能。
使用移动而非拷贝的另一个原因源于IO类或unique_ptr，这些类包含不能共享的资源。因此这些类的对象不能拷贝，但可移动。
旧C++标准中，没有直接的方法移动对象，容器所保存的类必须是可拷贝的。但在新标准，容器可保存不可拷贝的类型，只要他们能被移动即可。

①右值引用

为了支持移动操作，新标准引入了一种新的引用类型---右值引用。即，绑定到右值的引用，使用&&而不是&来获得右值引用。右值引用有一个重要的性质，只能绑定到一个将要销毁的对象。因此，我们可以自由的将一个右值引用的资源‘移动’到另一个对象。
左值和右值是表达式的属性，一般而言，一个左值表达式表示的是一个对象的身份，而一个右值表达式表示的是对象的值。
类似任何引用，一个右值引用就是某个对象的另一个名字。对于左值引用，不能将其绑定到要求转换的表达式、字面常量或是返回右值的表达式。右值引用有着完全相反的绑定特性：可以将一个右值引用绑定到这类表达式上，但不能将一个右值引用直接绑定到一个左值上。

    int i=42;
    int &r=i;//✔
    int &&rr=i;//✖，不能将一个右值引用绑定到一个左值上
    int &r2=i*42;//✖，i*42是一个右值
    const int &r3=i*42;//✔，可以将一个const引用绑定到一个右值上
    int &&rr2=i*42;//✔，将rr2绑定到乘法结果上

返回左值引用的函数，连同赋值、下标、解引用和前置递增/递减运算符，都返回左值表达式，可以将左值引用绑定到这类表达式。
返回非引用类型的函数，连通算术、关系、位及后置递增/递减运算符，都生成右值。不能将左值引用绑定到这类表达式上。但可以将一个const的左值引用或一个右值引用绑定到这类表达式上。
左值持久；右值短暂
左值有持久的状态，而右值要么是字面常量，要么是在表达式求值过程中创建的临时对象。
由于右值只能绑定到临时对象可知：所引用的对象将要被销毁；该对象没有其他用户。
这两个特性意味着：使用右值引用的代码可以自由的接管所引用的对象的资源
变量是左值：
变量可以看做只有一个运算对象而没有运算符的表达式。类似其他表达式，变量表达式也有左值/右值属性。变量表达式(持久)都是左值，所以不能将一个右值引用绑定到一个右值引用类型的变量上

    int &&rr1=42;//✔，字面值是右值
    int &&rr2=rr1;//✖，表达式rr1是左值

标准库move函数：
虽然不能将一个右值引用直接绑定到一个左值上，但我们可以显示的将一个左值转换为对应的右值引用类型。还可以通过名为move的新标准库函数获得绑定到左值上的右值引用(函数匹配精确匹配就会调用移动赋值运算符)，此函数定义在头文件utility中。
move告诉编译器，我们有一个左值，但希望像一个右值一样处理它。调用move意味着承诺：除了对rr1赋值或销毁它外，将不再使用它。
使用std::move，避免潜在的名字冲突

    int &&rr1=42;//✔，字面值是右值
    int &&rr2=std::move(rr1);//✔

②移动构造函数和移动赋值运算符

类似string已经标准库中的某些类，若自己的类也同时支持移动和拷贝，则有助于提升效益。为了支持移动操作，需要定义移动构造函数和移动赋值运算符。这两个成员类似于对应的拷贝操作，但它们从给定对象窃取资源而不是拷贝资源。
类似拷贝构造函数，移动构造函数的第一个参数是该类类型的一个引用。不同于拷贝构造函数的是，这个引用参数在移动构造函数中是一个右值引用。与拷贝构造函数一样，任何额外的参数必须有默认实参。
除了完成资源移动，移动构造函数还必须确保移后源对象销毁它是无害的。一旦完成资源移动，源对象必须不再指向被移动的资源，这些资源的所有权已经归属新创建的对象。

//类vector类内存分配策略的简化实现
class StrVec
{
public:
    StrVec():elements(nullptr), first_free(nullptr), cap(nullptr) {}//allocator成员默认初始化
    StrVec(const StrVec&);//拷贝构造函数
    StrVec &operator=(const StrVec&);//拷贝赋值运算符
    StrVec(StrVec &&s) noexcept;//移动操作不抛出任何异常, 移动构造函数
    ~StrVec();//析构函数
    void push_back(const string&);//拷贝元素
    size_t size() const//数组元素个数
    {
        return first_free-elements;
    }

    size_t capacity() const//数组容量
    {
        return cap-elements;
    }

    string *begin() const {return elements;}
    string *end() const {return first_free;}
    
private:
    static allocator<string> alloc;//分配元素
    //被添加元素的函数所使用
    void chk_n_alloc()//确保有空间足够容纳新元素
    {
        if(size()==capacity())
            reallocate();
    }
    pair<string*, string*> alloc_n_copy(const string*, const string*);
    void free();//销毁元素并释放内存
    void reallocate();//获得更多元素并拷贝已有元素
    string *elements;//指向数组首元素的指针
    string *first_free;//指向数组第一个空闲元素的指针
    string *cap;//指向数组内存尾后的指针
};

/**
 *  与拷贝构造函数不同，移动构造函数不分配任何新内存：
 *  它接管给定的StrVec中的内存。在接管内存后，将给定对象中
 *  指针值为nullptr, 这样就完成了从给定对象的移动操作，此对象继续存在。
 *  最终，移后源对象会被销毁，意味着在其上运行析构函数。若我们忘记了
 *  改变s.first_free，则销毁移后源对象就会释放掉我们刚刚移动的内存。
 */
StrVec::StrVec(StrVec &&s) noexcept//移动操作不抛出任何异常
:elements(s.elements), first_free(s.first_free), cap(s.cap)//成员初始化器，接管s中的资源
{
    //令s进入这样的状态---对其运行析构函数是安全的
    s.elements=s.first_free=s.cap= nullptr;
}

移动操作、标准库容器和异常：由于移动操作‘窃取’资源，通常不分配任何资源。因此移动操作通常不会抛出任何异常。当编写一个不抛出异常的移动操作时，应该将此事通知标准库。除非标准库知道我们的移动构造函数不会抛出异常，否则他会认为移动类对象时可能会抛出异常，并且为了处理这种可能性而做一些额外工作。
一种通知标准库的方法是在我们的构造函数中指明noexcept(新标准库引入).我们在函数的参数列表后指定noexcept.在一个构造函数中，noexcept出现在参数列表和初始化列表开始的冒号之间。
必须在类头文件的声明中和定义中(定义在类外)都指定noexcept.
弄清楚为什么需要noexcept能帮助我们深入理解标准库是如何与我们自定义的类型交互的。需要指出一个移动操作不抛出异常，这是因为两个相互关联的事实：首先，虽然移动操作通常不抛出异常，但是抛出异常也是允许的；其次，标准库容器能对异常发生时其自身的行为提供保障。例如， vector保证，如果我们调用push_back时发生异常，vector自身不会发生改变。
对一个vector调用push_back可能要求为vector重新分配内存空间。当重新分配vector内存时，vector将元素从旧空间移动到新内存中。
正如上面那样，移动一个对象通常会改变他的值。如果重新分配的过程中使用了移动构造函数，且在移动了部分而不是全部元素后抛出了一个异常，就会产生问题。旧空间中的移动源元素已经被改变了，而新空间中未构造的元素可能尚不存在。在此情况下vector不能满足自身保持不变的条件。
为了避免这种潜在问题，除非vector知道元素类型的移动构造函数不会抛出异常，否则在重新分配内存的过程中，就必须使用拷贝构造函数而不是移动构造函数。如果希望在vector重新分配内存这类情况对自定义类型对象进行移动而不是拷贝，就必须显式的告诉标准库我们的移动构造函数可以安全使用。通过将移动构造函数(移动赋值运算符)标记为noexcept来做到这一点。
移动赋值运算符：
移动赋值运算符执行与析构函数和移动构造函数相同的工作。与移动构造函数一样，若移动赋值运算符不抛出任何异常，应该将其标记为noexcept。类似拷贝赋值运算符，移动赋值运算符必须正确处理自身赋值

//类vector类内存分配策略的简化实现
class StrVec
{
public:
    StrVec():elements(nullptr), first_free(nullptr), cap(nullptr) {}//allocator成员默认初始化
    StrVec(const StrVec&);//拷贝构造函数
    StrVec &operator=(const StrVec&);//拷贝赋值运算符
    StrVec &operator=(const StrVec&&) noexcept;//移动赋值运算符
    StrVec(StrVec &&s) noexcept;//移动操作不抛出任何异常, 移动构造函数
    ~StrVec();//析构函数
    void push_back(const string&);//拷贝元素
    size_t size() const//数组元素个数
    {
        return first_free-elements;
    }

    size_t capacity() const//数组容量
    {
        return cap-elements;
    }

    string *begin() const {return elements;}
    string *end() const {return first_free;}

private:
    static allocator<string> alloc;//分配元素
    //被添加元素的函数所使用
    void chk_n_alloc()//确保有空间足够容纳新元素
    {
        if(size()==capacity())
            reallocate();
    }
    pair<string*, string*> alloc_n_copy(const string*, const string*);
    void free();//销毁元素并释放内存
    void reallocate();//获得更多元素并拷贝已有元素
    string *elements;//指向数组首元素的指针
    string *first_free;//指向数组第一个空闲元素的指针
    string *cap;//指向数组内存尾后的指针
};

//首先destroy元素(析构)，然后释放StrVec自己分配的内存空间
//for循环从构造的尾元素开始，逆序销毁元素
void StrVec::free()
{
    //不能传递给deallocate一个空指针，如果elements为0，函数什么也不做
    if(elements)
    {
        for(auto p=first_free;p!=elements;)
            alloc.destroy(--p);
    }
    alloc.deallocate(elements, cap-elements);
}

/**
 * 若this和rhs地址相同，则不需做任何事。
 * 
 * 检查自赋值有些奇怪，毕竟，移动赋值运算符需要右侧运算对象的
 * 一个右值(短暂的)。检查的原因是：此右值可能是move调用的返回
 * 结果。与其他任何赋值运算符一样，不能在使用右侧运算对象的资源前就释放左侧运算
 * 对象的资源(可能是相同的资源)
 */
StrVec &StrVec::operator=(const StrVec &&rhs) noexcept
{
    //直接检测自赋值
    if(this!=&rhs)
    {
        free();//释放已有元素
        elements=rhs.elements;//从rhs接管资源
        first_free=rhs.first_free;
        cap=rhs.cap;
        //将rhs处于可析构状态
        rhs.elements=rhs.first_free=rhs.cap= nullptr;
    }
    return *this;
}

移后源对象必须可析构：
从一个对象移动数据并不会销毁此对象，但是有时移动操作完成后，源对象会被销毁。因此，当我们编写一个移动操作时，必须确保移后源对象进入一个可析构状态。StrVec的移动操作满足这一要求，是通过将移后源对象设置为nullptr来实现的
移动操作还必须保证对象仍然是有效的。对象的有效就是指可以安全的为其赋予新值或者可以安全的使用而不依赖其当前值。不依赖于移后源对象中的数据。
合成的移动操作：
编译器也会合成移动构造函数和移动赋值运算符，但是合成移动的条件与合成拷贝的条件大不相同。
编译器不会为某些类合成移动操作。特别是，一个类定义了自己的拷贝构造函数、拷贝赋值运算符或者析构函数，编译器不会为他合成移动构造函数和移动赋值运算符了。若一个类没有移动操作，通过正常的函数匹配，类会使用对应的拷贝操作代替移动操作。
只有当一个类没有定义任何自己版本的拷贝控制成员，且类的每个非static数据成员都可以移动时，编译器才会为他合成移动构造函数或移动赋值运算符。编译器可以移动内置类型成员。若一个成员是类类型，且该类有对应的移动操作，编译器也能移动这个成员。

struct X
{
    int i;//内置类型可移动
    string s;//string定义了自己的移动操作
};
struct  hasX
{
    X mem;//X有合成的移动操作
};

X x, x2=std::move(x);//使用合成移动构造函数
hasX hx, hx2=std::move(hx);//使用合成移动构造函数

与拷贝操作不同，移动操作永远不会隐式定义为删除的函数。若，显式的要求编译器生成=default的移动操作，且编译器不能移动所有成员，则编译器会将移动操作定义为删除函数。除了一个重要例外，什么时候将合成的移动操作定义为删除的函数遵循与定义删除的合成拷贝操作类似原则：
[1] 与拷贝构造函数不同，移动构造函数被定义为删除的函数的条件是：有类成员定义了自己的拷贝构造函数且未定义移动构造函数，或者是有类成员未定义自己的拷贝构造函数且编译器不能为其合成移动构造函数。移动赋值运算符情况类似。
[2] 若有类成员的移动构造函数或移动赋值运算符被定义为删除的或不可访问的，则类的移动构造函数或移动赋值运算符被定义为删除的。
[3] 类似拷贝构造函数，若类的析构函数被定义为删除的或不可访问的，则类的移动构造函数被定义为删除的。
[4] 类似拷贝赋值运算符，若有类成员是const的或是引用，则类的移动赋值运算符被定义为删除的。
移动操作和合成的拷贝控制成员间还有一个关系：一个类是否定义了自己的移动操作对拷贝操作如何合成有影响。若类定义了一个移动构造函数和/或一个移动赋值运算符，则该类的合成拷贝构造函数和拷贝赋值运算符会被定义为删除的，若还想要拷贝操作，则必须显式定义拷贝控制操作。
移动右值，拷贝左值...：若一个类既有移动构造函数，也有拷贝构造函数，编译器使用普通的函数匹配规则来确定使用哪个构造函数。赋值操作情况类似。
例如，在我们StrVec类中，拷贝构造函数接受一个const StrVec的引用，因此它可以用于任何可以转换为StrVec的类型。而移动构造函数接受一个StrVec&&, 因此只能用于实参是(非static)右值的情形。

    StrVec v1, v2;
    v1=v2;//v2是左值, 传递给赋值运算符；使用拷贝赋值
    StrVec getVec(istream &);//getVec返回一个右值
    v2= getVec(cin);//getVec(cin)是一个右值，传递给赋值运算符，使用移动赋值
    //getVec可绑定到两个赋值运算符，但是右值更精确

...但如果没有移动构造函数，右值也被拷贝：若一个类有一个拷贝构造函数但未定义移动构造函数，编译器不会合成移动构造函数，该类的对象会被拷贝，即使我们试图通过调用move来移动他们。
拷贝并交换赋值运算符和移动操作：
在下面这个版本中，我们为类添加了一个移动构造函数，它接管了给定实参的值。构造函数体将给定的HasPtr的指针置为0, 从而确保销毁移后源对象是安全的。观察赋值运算符，此运算符有一个非引用参数，意味着此参数要进行拷贝初始化。依赖于实参的类型，拷贝初始化要么使用拷贝构造函数，要么使用移动构造函数(左值被拷贝，右值被移动)。因此，单一的赋值运算符就实现了拷贝赋值运算符和移动赋值运算符两种功能。

//行为像值的类
class HasPtr
{
    friend void swap(HasPtr&, HasPtr&);

public:

    //添加的移动构造函数
    HasPtr(HasPtr &&p) noexcept:ps(p.ps), i(p.i){p.ps=0;}
    //赋值运算符既是移动赋值运算符，也是拷贝赋值运算符
    HasPtr& operator=(HasPtr);

    HasPtr(const string &s=string()):ps(new string(s)), i(0) {}//逻辑上默认构造函数
    HasPtr(const HasPtr &p):ps(new string(*p.ps)), i(p.i) {}//string是类值的，所以其拷贝构造函数new string()也是值行为

    ~HasPtr()
    {
        delete ps;
    }
private:
    string *ps;
    int i;
};

inline void swap(HasPtr &lhs, HasPtr &rhs)
{
    using std::swap;
    swap(lhs.ps, rhs.ps);//交换指针，而不是string数据
    swap(lhs.i, rhs.i);//交换int成员
}

/**
 * 在此版本的赋值运算符，参数不是引用(也是为了下面的自赋值)，因此右侧对象以传值方式传给
 * 了赋值运算符。因此，rhs是右侧运算对象的一个副本(类值的拷贝构造函数)。
 * 且string也是副本
 */
/**
 * 这个技术自动处理了自赋值情况天然安全。
 * 它通过改变左侧对象前，拷贝右侧对象保证了自身赋值的正确
 */
HasPtr& HasPtr::operator=(HasPtr rhs)
{
    //交换左侧运算对象和局部变量rhs的内容，rhs指向本对象曾经使用的内存
    swap(*this, rhs);//HasPtr的swap
    return *this;//rhs被销毁(执行析构函数)，从而delete了rhs中的指针
}

    HasPtr hp, hp2;
    hp=hp2;//hp2是一个左值；hp2通过拷贝构造函数来拷贝
    hp=std::move(hp2);//移动构造函数移动hp2
    //不管是使用拷贝构造函数还是移动构造函数，赋值运算符函数体都swap两个
    //运算对象的状态.交换HasPtr,会交换两个对象的指针(及int)成员。
    //在swap之后，rhs中的指针将指向原来左侧运算对象所有的string.
    //当rhs离开作用域时，这个string将被销毁
	//rhs仅是一个副本罢了

更新三/五法则

所有五个拷贝控制成员应该看做一个整体：一般来说，如果一个类定义了任何一个拷贝操作，它就应该定义所有五个操作。

移动迭代器：StrVec的reallocate成员使用了一个for循环来调用construct从旧内存将元素拷贝到新内存中。作为一种替换方法，若我们能调用uninitialized_copy来构造新分配的内存，将比循环更简单。但是这个函数对元素进行拷贝操作。标准库并没有类似的函数将对象移动到未构造的内存中。
新标准库定义了一种移动迭代器适配器。一个移动迭代器通过改变给定迭代器的解引用运算符的行为来适配此迭代器。一般来说，一个迭代器的解引用运算符返回一个指向元素的左值。与其他迭代器不同，移动迭代器的解引用运算符生成一个右值引用。
通过调用标准库的make_move_iterator函数将一个普通迭代器转换为一个移动迭代器。此函数接受一个迭代器参数，返回一个移动迭代器。
原迭代器的所有其他操作在移动迭代器中都照常工作，所以可以将移动迭代器传递给uninitialized_copy

//类vector类内存分配策略的简化实现
class StrVec
{
public:
    StrVec():elements(nullptr), first_free(nullptr), cap(nullptr) {}//allocator成员默认初始化
    StrVec(const StrVec&);//拷贝构造函数
    StrVec &operator=(const StrVec&);//拷贝赋值运算符
    ~StrVec();//析构函数
    void push_back(const string&);//拷贝元素
    size_t size() const//数组元素个数
    {
        return first_free-elements;
    }

    size_t capacity() const//数组容量
    {
        return cap-elements;
    }

    string *begin() const {return elements;}
    string *end() const {return first_free;}

private:
    static allocator<string> alloc;//分配元素
    //被添加元素的函数所使用
    void chk_n_alloc()//确保有空间足够容纳新元素
    {
        if(size()==capacity())
            reallocate();
    }
    pair<string*, string*> alloc_n_copy(const string*, const string*);
    void free();//销毁元素并释放内存
    void reallocate();//获得更多元素并拷贝已有元素
    string *elements;//指向数组首元素的指针
    string *first_free;//指向数组第一个空闲元素的指针
    string *cap;//指向数组内存尾后的指针
};

void StrVec::push_back(const string &s)
{
    chk_n_alloc();//确保空间
    //在first_free指向的元素中构造s的副本
    alloc.construct(first_free++, s);//只有一个参数s,会使用其string拷贝构造函数拷贝元素
}

//拷贝n个元素
pair<string*, string*> StrVec::alloc_n_copy(const string *b, const string *e)
{
    //分配空间保存给定范围中的元素
    auto data=alloc.allocate(e-b);//计算空间
    //初始化并返回一个pair, 该pair由data和uninitialized_copy的返回值组成(尾后元素的指针)
    return {data, uninitialized_copy(b, e, data)};
}

//首先destroy元素(析构)，然后释放StrVec自己分配的内存空间
//for循环从构造的尾元素开始，逆序销毁元素
void StrVec::free()
{
    //不能传递给deallocate一个空指针，如果elements为0，函数什么也不做
    if(elements)
    {
        for(auto p=first_free;p!=elements;)
            alloc.destroy(--p);
    }
    alloc.deallocate(elements, cap-elements);
}

//拷贝构造函数
StrVec::StrVec(const StrVec &s)
{
    auto newdata= alloc_n_copy(s.begin(), s.end());
    elements=newdata.first;
    first_free=cap=newdata.second;
}

//析构函数
StrVec::~StrVec()
{
    free();
}

//拷贝赋值运算符
StrVec &StrVec::operator=(const StrVec &rhs)
{
    //调用alloc_n_copy分配内存
    auto data= alloc_n_copy(rhs.begin(), rhs.end());
    free();//释放旧空间
    elements=data.first;
    first_free=cap=data.second;
    return *this;
}

//重新分配空间
void StrVec::reallocate()
{
    //将分配当前大小两倍的内存空间
    auto newcapacity=size()?2*size():1;
    //分配新内存
    auto newdata=alloc.allocate(newcapacity);
//    //将数据从旧内存移动到新内存
//    auto dest=newdata;//起始指针，下一个空闲位置
//    auto elem=elements;//起始指针，旧数组下一个元素
//    for(size_t i=0;i!=size();++i)//移动元素
//        alloc.construct(dest++, std::move(*elem++));//move的返回结果，会令construct使用string的移动构造函数
//移动元素
/**
 * uninitialized_copy对输入序列中的每个元素调用construct来将元素“拷贝”到目的位置
 * 此算法使用迭代器的解引用运算符从输入序列中提取元素。由于我们传递给它的是移动迭代器，
 * 因此解引用运算符生成的是一个右值引用，意味着construct将使用移动构造函数来构造元素
 */
    auto last= uninitialized_copy(make_move_iterator(begin()),
                                  make_move_iterator(end()),
                                  newdata);
    free();//释放旧内存空间
//    //更新数据结构
//    elements=newdata;
//    first_free=dest;
//    cap=elements+newcapacity;
    elements=newdata;
    first_free=last;
    cap=elements+newcapacity;
}

不要随意使用移动操作

由于一个移后源对象具有不确定状态，对其调用std::move时危险的。当调用move时，必须确认移后源对象没有其他用户。

③右值引用和成员函数

除了构造函数和赋值运算符外，若一个成员函数同时提供拷贝和移动版本，也能提升效率。这种允许移动的成员函数通常使用与拷贝/移动构造函数和赋值运算符相同的参数模式---一个版本接受一个指向const的左值引用，第二个版本接受一个指向非const(要对其修改)的右值引用。
例如定义了push_back的标准库提供两个版本：

void push_back(const X&)//拷贝，绑定任意类型的X
void push_back(X&&)//移动, 只能绑定到类型X的可修改的右值

一般来说，我们不需要为函数定义接受一个const X&&或是一个(普通的)X&参数的版本。当我们想从实参‘窃取’数据(可修改)，通常传递一个右值引用。为了达到这一目的，实参不能是const的。类似的从一个对象进行拷贝的操作不用改变对象，所以无需定义普通版本的X&参数。
右值和左值引用成员函数：
通常，我们在一个对象上调用成员函数，而不管该对象是一个左值还是一个右值。

//此例中。我在一个string右值上调用find成员。该string右值通过连接两个string得到
string s1="a valye", s2="another";
auto n=(s1+s2).find('a');

//右值使用, 对右值赋值
s1+s2="wow!";
/**
 * 在旧标准中，无法阻止上述使用方式。为了维持向后的兼容性
 * 新标准仍允许向右赋值。但是我们可能希望在自己的类中阻止这种
 * 用法。我们希望强制左侧运算对象(this指向的对象)是一个左值
 */

指出this的左值/右值属性的方式与定义const成员函数相同，在参数列表后放置一个引用限定符.

class Foo
{
public:
    Foo &operator=(const Foo&) &;//只能向可修改的左值赋值
};
Foo &Foo::operator=(const Foo &rhs) &
{
    //其他所需操作
    return *this;
}

引用限定符可以是&或&&, 分别指出this可以指向一个左值或右值。类似const限定符，引用限定符只能用于（非static）成员函数, 且必须同时出现在函数的声明和定义中。
对于&限定的函数只能用于左值；对于&&限定的函数，只能用于右值

//前提：已经限制左值赋值
Foo &retFoo();//返回一个引用；retFoo调用时一个左值
Foo retVal();//返回一个值；retVal调用是一个右值
Foo i, j;//i,j是左值
i=j;//✔，i是左值
retFoo()=j;//✔，retFoo()返回一个左值
retVal()=j;//✖。retVal()返回一个右值
i=retVal();//✔

一个函数可以同时用const和引用限定。在此情况，引用限定必须跟在const限定符之后。

class Foo
{
public:
    Foo anotherMem() const &;
};

重载和引用函数：
就像一个成员函数可以根据是否有const来区分重载版本一样，引用限定符也可以区分重载版本。而且，我们可以综合引用限定符和const来区分一个成员函数的重载版本。

/**
 * 当我们对一个右值执行sorted时，他可以安全的直接对data成员进行排序
 * 对象是一个右值，意味着没有其他用户，因此我们可以改变对象
 * 
 * 当对一个const右值或一个左值执行sorted时，我们不能改变对象，因此需要在
 * 排序前拷贝data
 */
class Foo
{
public:
    Foo sorted() &&;//可用于可改变的右值
    Foo sorted() const &;//可用于任何类型的Foo

private:
    vector<int> data;
};

//本对象为右值，因此可以原址排序
Foo Foo::sorted() &&
{
    sort(data.begin(), data.end());
    return *this;
}
//本对象是const或是一个左值，哪种情况都不能原址排序
Foo Foo::sorted() const &
{
    Foo ret(*this);//拷贝一个副本, 普通函数匹配到默认拷贝构造函数
    sort(ret.data.begin(), ret.data.end());//排序副本
    return ret;//返回副本
}

int main(int argc, char *argv[])
{
    //编译器会根据调用sorted的对象的左值/右值属性来确定使用哪个sorted版本
    retVal().sorted();//retVal()是一个右值，调用Foo sorted() &&;
    retFoo().sorted();//retFoo()是一个左值，调用Foo sorted() const &;
}

当我们定义const成员函数时，可以定义两个版本，唯一差别是有无const限定。引用限定的函数不一样，若我们定义两个或以上具有相同名字和相同参数列表的成员函数，必须对所有函数加上引用限定符，或者所有都不加

class Foo
{
public:
    Foo sorted() &&;//可用于可改变的右值
    Foo sorted() const ;//✖，必须加上引用限定符
    
    //此函数用来比较int值
    using Comp=bool(const int&, const int&);
    Foo sorted(Comp*);//✔，不同参数列表
    Foo sorted(Comp*) const;//✔，两个版本都无引用限定符

private:
    vector<int> data;
};