【C++基础】2.标准库-创新互联

• C++语言不直接处理输入输出，而是通过定义在标准库中的类型来处理IO，这些类型支持从设备读写数据，设备可以是文件、控制台窗口等。还有一些类型允许内存IO，即从string读写数据
• 标准库定义了3仲不同的IO处理操作，分别定义在3个独立的头文件中，iostream定义了用于读写流的基本类型，用于处理控制台IO，fstream定义了读写命名文件的类型，sstream定义了读写内存string对象的类型
• fstream和stringstream都是继承自类iostream，输入类都继承自istream，输出类都继承自ostream，因此在istream对象上执行的操作，也可在ifstream和istringstream对象上执行
• 不能对IO对象进行拷贝或赋值，因此也不能将形参或返回类型设置为流类型，进行IO操作的函数通常以引用方式传递和返回流，读写一个IO对象会改变其状态，因此传递和返回的引用不能是const的
• IO操作的一个问题是可能发生错误，有些错误是可恢复的，而有些错误是不可恢复的，因此代码应该在使用一个流之前检查它是否处于良好状态，确定一个流对象状态的最简单方法是将它当作一个条件来使用while(cin >>word)，while循环检查>>表达式返回的流的状态，如果输入操作成功，流保持有效状态，则条件为真
• 每个输出流都管理一个缓冲区，用来保存程序读写的数据，如果执行os<< "hello";，文本串可能会立即打印，也可能被保存在缓冲区中，导致缓冲刷新（数据真正写到输出设备中）的原因有：① 程序正常结束；② 缓冲区满；③ 使用endl（添加换行）或flush（不添加）或ends（添加空字符）操作符显式刷新缓冲区；④ 使用unitbuf操作符使流在每次写操作后都进行一次flush操作；⑤ 一个输出流可能被关联到另一个流，当读写被关联的流时，关联到的流缓冲区会被刷新，默认情况下cin和cerr都关联到cout
• 如果程序崩溃，输出缓冲区是不会被刷新的
• 定义一个空文件流对象，可以调用成员函数open()将它与文件关联起来，如果调用失败则不能使用该对象，此时和cin一样返回false，对一个已经打开的文件流调用open()会失败，并导致该对象不能被使用，为了将文件流关联到另一个文件，必须先用成员函数close()关闭已经关联的文件，当一个fstream对象离开其作用域时，与之关联的文件会自动关闭（对象销毁时，close()自动调用）

9.1 顺序容器概述

• 标准库中有多种顺序容器，所有顺序容器都提供了快速顺序访问元素的能力，但是这些容器在以下两方面都有不同的性能折中：① 向容器添加或从容器中删除元素的代价；② 非顺序访问容器中元素的代价
• 顺序容器类型如下：

• vector：可变大小数组。支持快速随机访问。在尾部之外的位置插入或删除元素很慢
• deque：双端队列。支持快速随机访问。在头尾位置插入和删除速度很快
• list：双向链表。只支持双向顺序访问。在list中任何位置进行插入和删除操作速度都很快
• forward_list：单向链表。只支持单向顺序访问。在链表中任何位置进行插入和删除操作都很快
• array：固定大小数组。支持快速随机访问。不能添加或删除元素。与内置数组相比，array是一种更安全、更易用的数组类型
• string：与vector类似，但专门用于保存字符

• 一般来说，每个容器都定义在一个头文件中，文件名与类型名相同，即deque定义在头文件deque中。容器均定义为模板类
• 所有容器都拥有的操作：

• 类型别名：①iterator/const_iterator：此容器类型的迭代器类型；②size_type：无符号整数类型，可保存此容器类型大可能大小；③difference_type：带符号整数类型，可保存两个迭代器之间的距离；④vaule_type：元素类型；⑤reference/const_reference：元素的左值类型
• 构造函数：①C c;：默认构造函数，构造空容器；②C c1(c2);：拷贝构造函数；③C c(b,e);将迭代器b和e范围内的元素拷贝到c（array不支持）；④C c{x,y,z};：列表初始化
• 赋值与swap：①c1=c2;；②c={x,y,z};；③c1.swap(c2);；（swap通常比拷贝快得多）④swap(c1,c2);（最好统一使用非成员版本的swap，适用于泛型编程）
• 大小：①c.size()：c中元素数目（不支持forward_list）；②c.max_size()：c中可保存的大元素数目；③c.empty()
• 添加删除元素（array不支持，不同容器中这些操作的接口都不同）：①c.insert(args)；②c.emplace(inits)；③c.erase(args)；④c.clear()
• 关系运算符：①==/!=：所有容器都支持；②</<=/>/>=：无序关联容器不支持
• 获取迭代器：c.begin(),c.end()/c.cbegin(),c.cend()
• 反向容器的额外成员（不支持forward_list）：①reverse_iterator/const_reverse_iterator；②c.rbegin(),c.rend()/c.crbegin(),c.crend()

• 赋值相关运算会导致指向左边容器内部的迭代器、引用、指针失效。而swap操作将容器内容交换不会导致失效（容器类型为array和string除外）
• 用一个对象来初始化容器时，或将一个对象插入到容器中时，实际上放入到容器中的是对象值的一个拷贝，而不是对象本身

9.2 顺序容器专有操作

• 初始化（array不可用）：①C seq(n);：seq包含n个元素，对这些元素进行值初始化，此构造函数是explicit的（string不可用）；②C seq(n,t);：seq包含n个初始化为t的元素
• 赋值（array不适用）：①seq.assign(b,e);：将seq中元素替换为迭代器b和e范围内的元素，b和e不能指向seq本身；②seq.assign(il);：将seq中的元素替换为初始化列表il中的元素；③seq.assign(n,t);：将seq中的元素替换为n个值为t的元素
• 添加元素（array不可用）：①c.push_back(t)/c.emplace_back(args)：在c的尾部创建一个值为t或由args创建的元素，返回void（forward_list不可用）；②c.push_front(t)/c.emplace_front(args)：在c的头部创建一个元素，返回void（vector和string不可用）；③c.insert(p,t)/c.emplace(p,args)：在迭代器p指向的元素之前创建一个元素，返回指向新添加的元素的迭代器；④c.insert(p,n,t)/c.insert(p,b,e)/c.insert(p,il)
• 访问元素（返回的均为引用）：①c.back()（forward_list不可用）；②c.front()；③c[n]/c.at(n)（只能用于string、vector、deque、array）
• 删除元素：①c.pop_back()：删除c中尾元素（forward_list不可用）；②c.pop_front()：删除c中首元素（vector和string不可用）；③c.erase(p)：删除迭代器p所指向元素，返回被删元素之后元素的迭代器；④c.erase(b,e)：删除迭代器b和e范围内的元素，返回最后一个被删元素之后元素的迭代器；⑤c.clear()：删除c中所有元素，返回void
• 改变容器大小：①c.resize(n)：调整c的大小为n个元素，添加的新元素进行值初始化，若n小于原长度，则多出的元素被丢弃；②c.resize(n,t)：添加的新元素初始化为值t

• 向一个vector、string、deque插入元素会使所有指向容器的迭代器、引用、指针失效
• 容器中访问元素的成员函数返回的都是引用，如果容器是一个const对象，则返回值是const引用
• 下标运算符并不检查下标是否存在合法范围内，使用越界的下标是一种严重的设计错误，使用at()成员函数时如果下标越界，会抛出out_of_range异常
• 删除deque中除首尾位置之外的任何元素都会使所有迭代器、引用、指针失效。指向vector或string中删除点之后位置的迭代器、引用、指针都会失效
• forward_list为单向链表，在单向链表中，没有简单的方法来获取一个元素的前驱，forward_list并未定义常规的插入删除操作，而是定义了名为insert_after、emplace_after、erase_after的操作，并且定义了首前迭代器before_begin，该迭代器允许在链表首元素之前添加或删除元素
• 如果resize缩小容器，则指向被删除元素的迭代器、引用、指针都会失效。对vector、string、deque进行resize可能导致迭代器、引用、指针失效
• 如果在一个循环中插入或删除deque、string、vector中的元素，不要缓存end返回的迭代器，每次循环都会重新计算end
• 当容器中元素是连续存储，且容器大小可变时，向容器中添加元素必须分配新的内存空间来保存已有元素和新元素，vector和string的实现通常会分配比新的空间需求更大的内存空间
• vector和string类型提供了一些成员函数，实现对容器大小的管理操作：①c.capacity()：不重新分配内存空间的话，c可以保存多少元素；②c.reserve(n)：分配至少能容纳n个元素的内存空间；③c.shrink_to_fit()：将能保存的元素空间缩大小减为当前的元素个数

9.3 额外的string操作

• 构造string的其他方法：除通用的构造函数外，string还支持另外三个构造函数：①string s(cp,n)：s是cp指向数组中前n个字符的拷贝，此数组至少包含n个字符；②string s(s2,pos2)：s是s2从下标pos2开始的字符的拷贝；③string s(s2,pos2,len2)：s是s2从下标pos2开始len2个字符的拷贝；④s.substr(pos,n)：子字符串操作，返回一个string，包含s中从pos开始的n个字符的拷贝
• 修改string的其他操作：①s,insert(pos,args)；②s.erase(pos,len)；③s.assign(args)；④s.append(args)；⑤a.replace(range,args)。其中args可以是下列形式之一：str/str,pos,len/cp,len/cp/n,c/b,e/初始化列表
• string搜索操作：每个搜索操作都返回一个string::size_type值，表示匹配发生位置的下标，如果搜索失败，则返回一个名为string::npos的static成员，二者均为unsign类型：①s.find(args)/s.rfind(args)：查找s中args第一次/最后一次出现的位置；②s.find_first_of(args)/s.find_last_of(args)：在s中查找arg中任何一个字符第一次/最后一次出现的位置；③s.find_first_not_of(args)/s.find_last_not_of(args)：在s中查找第一个/最后一个不在args中的字符。其中args是以下形式之一：c,pos/s2,pos/cp,pos/cp,pos,n
• 除了关系运算符外，标准库string类型还提供了一组compare函数，与C标准库的strcmp函数类型，根据s是等于、大于、小于参数指定的字符串，返回0、正数、负数，s.compare(args)的参数形式有：s2/pos1,n1,s2/pos1,n1,s2,pos2,n2/cp/pos1,n1,cp/pos1,n1,cp,n2
• 字符串中常常包含表示数值的字符，新标准引入了多个函数，可以实现数值数据与string之间的转换：①to_string(val)：将数值类型转为string；②stoi(s,p,b)/stol(s,p,b)/stoul(s,p,b)/stoll(s,p,b)/stoull(s,p,b)：将s转为整型，b表示转换用的基数，默认为10，p是size_t指针，用来保存s中第一个非数值字符的下标，默认为0，即不保存下标；③stof(s,p)/stod(s,p)/stold(s,p)：将s转为浮点型

9.4 容器适配器

• 除了顺序容器外，标准库还定义了三个顺序容器适配器：stack、queue、priority_queue，本质上一个容器适配器是一种机制，能使某种事物的行为看起来像另外一种事物，如stack适配器接受一个顺序容器，使其操作起来像一个stack一样
• 每个适配器都定义两个构造函数：默认构造函数创建一个空对象，接受一个容器的构造函数拷贝该容器来初始化适配器，如stackstk(seq);，默认情况下stack和queue是基于deque实现的，可以在创建一个适配器时将一个命名的顺序容器作为第二个类型参数，来重载默认容器类型stack>str_stk;
• 所有适配器都要求容器具有添加、删除、访问尾元素元素的能力，因此适配器不能构造在array和forward_list上。stack可以用除上述两种外的任意容器类型来构造，queue不能基于vector构造，priority_queue不能基于list构造。可通过适配器的container_type类型访问底层容器类型
• 栈操作：①s.pop()；②s.push(item)/s.emplace(args)：③s.top()
• 队列操作：①q.pop()；②q.front()；③q.back()（只能用于queue）；④q.top()（只能用于priority_queue）；⑤q.push(item)/q.emplace(args)

10.1 泛型算法概述

• 标准库并没有给容器定义大量的操作，而是提供了一组算法，这些算法大多数都独立于任何容器，称这些算法为泛型的，可用于不同类型的容器和不同类型的元素
• 大多数算法都定义在头文件中，还有一组数值泛型算法定义在头文件中。一般情况下，这些算法并不直接操作容器，而是遍历由两个迭代器指定的一个元素范围来进行操作，如auto result=find(vec.cbegin(),vec.cend(),val);，如果发现匹配元素，则返回指向该元素的迭代器，否则返回尾后迭代器
• 标准库提供了超过100个算法，大多数算法遍历输入范围的方式相似，但它们使用范围中元素的方式不同，理解算法最基本的方法就是了解它们是否：读取元素、改变元素、重排元素顺序
• 只读算法：find()函数和count()函数都是只读算法，定义在头文件中的accumulate()函数也是只读算法，equal(r1.cbegin(),r1.cend(),r2.cbegin())函数用于比较两个序列是否保存相同的值，该函数接受三个迭代器，前两个表示第一个序列的范围，第三个表示第二个序列的首元素，这种只接受一个单一迭代器来表示第二个序列的算法，都假定第二个序列至少与第一个序列一样长
• 写容器元素的算法：①fill(vec.begin(),vec.end(),10)向给定序列中写入数据；②fill_n(vec.begin(),n,0)：必须保证vec至少包含n个元素/fill_n(back_inserter(vec),n,0)：使用插入迭代器back_inserter会调用push_back来添加元素；③copy(bigin(a1),end(a1),a2)：把a1的内容拷贝给a2；④replace(ilst.cbegin(),ilst.cend(),0,10)：将序列中所有0替换为10/replace_copy(ilst.cbegin(),ilst.cend(),back_inserter(ivec),0,10)：ilst不变，ilst中0替换为10后拷贝到ivec中
• 重排容器元素的算法：①sort()：排序；②unique()：去除相邻重复项；以下步骤消除vector中的重复单词

sort(v.begin(),v.end());	//排序
auto end_unique = unique(v.begin(),v.end());	//unique函数实现无重复排列，返回指向不重复区域的尾后迭代器
v.erase(end_unique,v.end());	//删除重复单词

10.2 定制操作

• 很多算法都会比较输入序列中的元素，默认情况下，这类算法使用元素类型的<或=运算符来比较。标准库还为这些算法提供了额外的版本，使得能够用自己定义的操作来代替默认运算符
• 谓词是一个可调用的表达式，其返回结果是一个能用作条件的值，标准库算法所使用的谓词分为一元谓词（接受一个参数）和二元谓词（接受两个参数）。接受谓词参数的算法对输入序列中的元素调用谓词，元素类型必须能转换为谓词的参数类型
• 接受一个二元谓词参数的sort()函数用谓词代替<来比较元素，如sort(words.begin(),words.end(),isShorter)，若想要保证稳定排序，可使用stable_sort()函数
• 可以向一个算法传递任何类别的可调用对象，对于一个对象或表达式，如果可以对其使用调用运算符，则称它为可调用的。可调用对象包括：函数、函数指针、重载了函数调用运算符的类、lambda表达式
• 一个lambda表达式表示一个可调用的代码单元，可以将其理解为一个未命名的内联函数，与函数类似，一个lambda具有一个返回类型、一个参数列表、一个函数体。但与函数不同，lambda可能定义在函数内部
• 一个lambda表达式具有以下形式：

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

其中，捕获列表是一个lambda所在函数中定义的局部变量的列表，通常为空，参数列表、返回类型、函数体与普通函数一样，但是lambda必须使用尾置返回来指定返回类型。lambda可以忽略参数列表和返回类型，但必须包含捕获列表和函数体：auto f = []{return 10;};，忽略参数列表即参数列表为空，忽略返回类型则从函数体代码中推断返回类型，若函数体中包含单一return之外的内容且未指定返回类型，则返回void

• lambda不能有默认参数，实参数目永远与形参数目相等，空捕获列表说明此lambda不使用它所在函数中的任何局部变量，lambda使用示例如下：

//将words按长度稳定排序
stable_sort(words.begin(),words.end(),[](const string &a,const string &b){return a.size()return a.size()>=sz;});
//从wc迭代器开始打印单词，每个单词后接一个空格
for_each(wc,words.end(),[](const string &s){cout<

• 当定义一个lambda时，编译器生成一个与lambda对应的新的类类型
• 类似于参数传递，变量的捕获方式也可以是值捕获（[a]）或引用捕获[&a]，采用值捕获的前提是变量可以拷贝，被值捕获的变量是在lambda创建时拷贝，而非调用时，因此随后对其的修改不会影响到lambda内对应的值，当以引用方式捕获一个变量时，必须保证在lambda执行时变量是存在的
• 除了显式列出希望使用的来自所在函数的变量之外，还可以让编译器根据lambda体中的代码来推断要使用哪些变量，此时应在捕获列表中写一个[&]或[=]，&告诉编译器采用引用捕获方式，=采用值捕获方式。当混用隐式捕获和显式捕获时，捕获列表中第一个元素必须是&或=
• 默认情况下，对于一个值被拷贝的变量，lambda不会改变其值，如果希望能改变一个被捕获的变量的值，必须在参数列表首加上关键字mutable：auto f=[v]()mutable{return ++v;};，一个引用捕获的变量是否可以修改依赖于该引用指向的是一个const类型还是非const类型
• 对于捕获列表为空的lambda，通常可以用函数来代替，对捕获局部变量的lambda，需要使用标准库中的bind()函数，该函数定义在头文件中，可以将bind函数看作一个通用的函数适配器，接受一个可调用对象，生成一个新的可调用对象auto newCallable = bind(callable,arg_list);，当调用newCallable时，会调用callable，并传给它arg_list中的参数，arg_list是一个逗号分隔的参数列表，其中形如_n的参数代表占位符，绑定引用参数时要使用ref()或cref()函数：bind(print,ref(os),_1,' ')

10.3 再探迭代器

• 除了每个容器自己的迭代器之外，标准库在头文件中还定义了额外几种迭代器，包括：插入迭代器、流迭代器、反向迭代器、移动迭代器
• 插入迭代器是一种迭代器适配器，它接受一个容器，生成一个迭代器，能实现向给定容器添加元素。插入器有三种类型：①back_inserter(c)创建一个使用c.push_back(t)的迭代器；②front_inserter(c)创建一个使用c.push_front(c)的迭代器；③inserter(c,iter)创建一个使用c.insert(iter,t)的迭代器。使用插入器时，只需要iter=t;即可在iter指定的位置处插入值t
• 流迭代器可以用泛型算法从流对象读取数据及写入数据，istream_iterator读取输入流，ostream_iterator向一个输出流写数据

istream_iteratorin(is);	//in从输入流is读取类型为T的值
istream_iteratorend;	//读取类型为T的尾后迭代器
ostream_iteratorout(os);	//out将类型为T的值写到输出流os中
ostream_iteratorout(os,d);	//out将类型为T的值写到输出流os中，且每个值后都输出一个d，d为C风格的字符串

• 反向迭代器就是在容器中从尾元素向首元素反向移动的迭代器，++it会移动到前一个元素，–it会移动到下一个元素，除了forward_list之外，其他容器都支持反向迭代器，可以通过调用rbegin(),rend(),crbegin(),crend()成员函数来获得反向迭代器，反向迭代器调用base()成员函数可以得到正向迭代器，但是指向的元素不同（正向迭代器指向后一个元素）

10.4 泛型算法结构

• 任何算法的最基本特性是它要求其迭代器提供哪些操作，算法所要求的迭代器操作可分为5个迭代器类别：

1. 输入迭代器：只读，不写，单遍扫描，只能递增；
2. 输出迭代器：只写，不读，单遍扫描，只能递增；
3. 前向迭代器：可读写，多遍扫描，只能递增；
4. 双向迭代器：可读写，多遍扫描，可递增递减；
5. 随机访问迭代器：可读写，多遍扫描，支持全部迭代器运算

• 迭代器也定义了一组公共操作，一些操作所有迭代器都支持，另外一些只有特定迭代器才支持，除了输出迭代器之外，一个高层的迭代器支持低层迭代器的所有操作，各迭代器需要支持的操作包括：

1. 输入迭代器：① 用于比较两个迭代器的相等==和不相等运算符!=；② 迭代器的前置和后置递增运算++；③ 用于读取元素的解引用运算符*（只会出现在赋值运算符的右侧）；④ 用于解引用迭代器并提取成员的箭头运算符->
2. 输出迭代器：与1类似，解引用运算符只能出现在赋值运算符的左侧
3. 前向迭代器：1和2会破环迭代器原本结构，只能单遍扫描，前向迭代器可以保存当前状态，多次读写同一个元素
4. 双向迭代器：还支持前置和后置的递减运算符--
5. 随机访问迭代器：还支持 ① 用于比较两个迭代器相对位置的关系运算符<,<=,>,>=；② 迭代器和一个整数值的加减运算+,+=,-,-=；③ 用于两个迭代器的减法运算-；④ 下标运算符iter[n],*iter[n]（两者等价）

• 大多数算法的形参模式是下列4仲形式之一：其中dest参数是一个表示算法可以写入的目的位置的迭代器，常被用于绑定到一个插入迭代器或是一个ostream_iterator

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

• 算法命名规范：① 一些算法使用重载形式传递一个谓词，来代替<或==；② 接受一个元素值的算法通常会有一个不同名的后缀加上_if的版本，该版本接受一个谓词代替元素值，如find和find_if；③ 默认情况下，重排元素的算法将重排后的元素写回给定的输入序列中，通常提供额外的拷贝版本，加上后缀_copy，如reverse和reverse_copy
• 与其他容器不同，链表类型list和forward_list定义了几个成员函数形式的算法，特别定义了独有的sort(),merge(),remove(),reverse(),unique()算法，通用版本的sort要求随机访问迭代器，因此不能用于链表类型

auto m_it = m.cbegin();
while(m_it != m.cend()){cout<< m_it->first<< ":"<< m_it->second<< endl;
	++m_it;
}