【笔记】《C++Primer》—— 第9章：顺序容器

想想我还是回来先把这书读完吧，C++太重要了。

这一章介绍了标准库中的几个典型的容器，非常非常常用的部分，值得好好看，由于很常用所有很多地方就没有详细记录了，只写下了我决定重要的部分，也就是因此这篇的篇幅就不是很长了。

9.1 顺序容器概述

• 顺序容器的储存顺序不依赖于元素的值，而是与元素加入的位置相关
• 标准库提供了很多种顺序容器，都是对下面两点的不同方向的折衷
  • 对容器内增减元素的代价
  • 非顺序访问元素的代价

• 其中forward_list(前向链表)和array(内置数组的替代版)是C11的新特性
• 新标准库的容器性能非常好，都是精心优化的，我们无需自己实现容器来处理自己的数据
• 而且我们可以尽量使用标准库容器来替代之前使用的更加原始的数据结构如内置数组，因为array更安全，效率也相当高
• 大多数情况下我们都可以用vector来进行数据处理，需要在中间插入数据时用list，只需要在某个阶段进行中间插入，则可以先用list再转存到vector
• 当不清楚改用什么容器时，先用迭代器代替下标操作，避免随机访问且增加灵活性

9.2 容器库概览

• 容器都放在与类同名的头文件中
• 容器均是模板类，即需要以 容器类型<元素类型> 来初始化，其中array类还需要 array<元素类型,元素数量>
• 容器初始化常常需要元素有默认构造函数，如果没有的话需要在尖括号里提供一个
• 容器有很多通用的接口，注意只要标准库里容器的接口相同就代表其效果和用法是相同的，注意尽管有相同的接口但有些容器并不支持某些接口，这应由容器本身的特性来记忆，并辅以智能补全来应用
• 用begin和end可以得到容器的头尾迭代器，注意begin指向第一个元素，end指向最后一个元素后面的位置。这让我们可以用begin==end来确定容器是否为空，当不等时容器至少有一个元素
• 常用的遍历容器方法：while(begin!=end) ++begin;
• 有一系列反向迭代器和常量迭代器(C11引入)，如rbegin(尾元素),rend(首元素之前),cbegin,cend。反向迭代器的各种操作也是相反的，对反向迭代器使用++是指向上一个元素
• 容器可以进行列表初始化，用花括号赋值
• 直接进行容器的拷贝构造要求两容器的类型和元素类型需要匹配，但如果用迭代器来构造则只要元素可以转换匹配即可，迭代器指向第一个元素和最后一个元素的后一个位置
• 内置数组可以用来初始化array，用array方便进行拷贝对象赋值等操作
• assign(分配)函数可以将目标元素替换到当前容器中，会直接将当前整个容器改为目标内容
• swap函数交换容器中的指定元素，除了array外swap不对元素进行拷贝删除插入等，因此很快
• 容器之间可以用运算符比较，规则遵照直觉，对于自定义的容器则需要元素也实现的对应的比较运算符才行

9.3 顺序容器操作

• push_back和emplace_back都可以向容器尾加入元素，区别是push_back是用拷贝构造实现的，emplace_back是直接使用参数(因此参数需与元素的构造函数匹配)进行了内部构造，emplace_back效率稍微高一点
• insert可以向目标迭代器之前插入元素，但要注意对vector，string尾外，deque首尾外加元素效率低下
• 相类似的也有push_front，但是只有deque可用
• insert函数在新标准中返回值为刚插入的部分的第一个元素的迭代器，以便连续插入
• 注意任何时候都要保证不要对空容器进行访问，操作结果是未定义的
• 访问容器元素可以解引用迭代器，用下标或用at函数，其中at函数比直接用下标安全很多，速度差别不大
• erase函数用于删去容器中的元素，目标是迭代器所指的元素或两个迭代器之间的左闭范围，返回值是被删元素之后元素的迭代器，以便连续删除
• 也可用pop_back，pop_front来弹出头尾元素
• forward_list(前向列表)的操作函数都是xxx_after形式，因为其单向链表的特性使得只能操作目标迭代器之后的元素
• 用resize来改变容器大小，显然array不支持。变大会自动填充元素，变小会删去后部分的元素
• 容器操作可能会使迭代器失效，重点是脑内要理解目标容器的实现方式和数组组成原理，目标迭代器所指元素是否经历重新分配是重点，保险起见进行容器操作后最好都重新进行引用，指针，迭代器操作
• 不要缓存end迭代器，通常标准库中的end操作都很快，end迭代器非常容易失效，基于这两点最好每次需要都要求一个新的end迭代器

9.4 vector对象是如何增长的

• vector是连续储存的，通过成倍地扩充当前容量来实现无限储存
• vector的扩张速度通常比list和deque快
• capacity是vector的容量变量(区分于元素量size)，可以用reserve指定下一次分配时所需分配的容量，用shrink_to_fit来将capacity减少只size的大小(不一定被实现)
• 空的vector的size是0，capacity也是0
• vector只有迫不得已(填满了容量)才会申请新空间

9.5 额外的string操作

• 构造string时可以用C风格的字符串char*或另一个的string，同时可以指定所需的迭代器和元素数量。要注意用char*直接构造时需要保证数组以空字符(\0)结尾
• substr函数可以返回目标字符串中的指定范围部分
• 同样的，assing，insert，erase也都有字符串版本的
• append函数相当于+=，对string末尾追加内容
• replace函数是erase和insert的简写形式，替换一部分内容
• find函数可以搜索指定字符串，搜索成功时返回字符串第一次出现时的第一个匹配位置的下标，搜索失败时返回称为string::npos的string::size_type的-1，npos是一个unsigned成员，因此-1代表任何string的最大可能大小，因此用int或其他类型来保存返回值并不合适
• find_first_of函数返回对给定字符串中任意一个匹配字符的第一个匹配位置
• 相应的也有find_last_of，find_first_not_of等等
• 上述的查找函数都可以用下标指定搜索的开始位置以分段搜索
• 类似的还有rfind系列函数，从右向左地寻找匹配，返回最右的匹配位置下标，注意匹配仍然是正常顺序的字符串
• string还有compare函数可以进行更精细的比较操作，规则和运算符一样
• to_string函数可以将各式的数值类型转换为string。而类似的有stoi(string to int)，stod(string to double)等一系列string转数值的函数

9.6 容器适配器

• 标准库有三个容器适配器stack(栈),queue(队列),priority_queue(优先队列)。适配器接受一种已有的容器类型让他看起来像是另一种类型
• stack和quene基于deque实现，priority_quene基于vector实现
• 适配器都在与类同名的头文件中
• 每个适配器都有自己独有的操作，任何掩盖低层容器的操作
• 注意栈需要先top得到栈顶元素后才pop

• quene同理，书中写错了