C++基础第9章：序列与关联容器（2）——序列容器

• 1.概述
• 2.array容器
• 3.vector容器
• 4.list和forward_list容器
• • 4.1.list容器
  • 4.2.forward_list容器
• 5.deque(double-end queue)容器——双端容器
• 6. basic_string容器——实现字符串相关接口

1. array：不支持增加和删除
2. vector：在内存中连续存储
3. list：基于链表，在内存中不是连续存储
4. deque：vector和list的折中，分为很多段，每一段都是连续存储的，不同段之间使用链表来链接
5. basic_string：提供了对字符串的专门支持

1. 与内建数组功能基本相同：那么为什么还要引入array呢？为了实现数组复制的操作。由于array不支持扩展长度，所以定义的时候必须也指定大小。

#include 
#include 

int main()
{
	std::array a;
	std::array b = a;  // 数组复制

2. 构造：和内建数组一样，如果使用std::array a = {1, 2}，那么前两个是1，2，剩下的用0初始化。如果不进行初始化，那么内部值初始化为乱值，即随机初始化。
3. 成员类型value_type：std::array::value_type // 就是int；siz _type：大小的类型，实际就是size_t。
4. 元素访问：

• at方法相对[]方法对索引超过数组大小可以让程序崩溃，并且给出提示；而[]方法可能会崩溃（无提示），也可能访问非法内存，所以没有at方法好。
• front/back返回数组第一个/最后一个元素。
• data返回数组成员类型的指针，指向数组中的第一个元素，跟内建数组的数组名差不多的功能。同时这个接口也是为了和接受内建数组类型的函数接口兼容，比如如下代码：

void fun(int* ptr)
{}

int main()
{
	std::array a = {1, 2, 3};
	fun(a.data());   // a.data()得到int*类型，指向a的第一个元素
}

注意：并不是所有的容器都有data接口，后面可以看到vector也有data接口，实际上只有容器中的元素在内存中连续存储的时候才会有data接口，这个很好理解，和数组一样，这样提供了data接口就可以使用指针连续访问了。而如果不是连续保存的，那么返回data也没有意义，后面无法用它进行访问其他元素。

5. 容量相关（平凡实现）

• empty：实际上编译期就确定了，是否为空
• size：也是编译期确定，大小
• max_size：也是编译器确定，跟size一样。为啥还这样呢？这是为了统一接口，比如vector中这些量就不一样了，所以就是为了接口统一。

6. 填充与交换：填充很简单，就是把一个array全部填充成某个值。交换是交换两个array的数值。但是注意，这两个操作的成本是非常高的，因为它内部就是一个数组；而vecotr交换操作成本就很低，因为它内部是一个指针指向一个数组。

7. 迭代器
   

1. 和array相似的接口：构造、成员类型、元素访问和array都一样。
2. 容量访问不再是平凡实现：和实际运行期间有关，而不是编译期确定的。

• capacity：容量
• reserve：实现分配好容量，防止填充的时候因为容量不够重新开内存然后拷贝再插入。
• shrink_to_fit：构造完vector之后，知道不会再往里面填充数据了，所以就可以把buffer的一部分内存释放掉了。

3. 填充与交换：填充还是比较慢。但是交换就很快了，因为vector中维护的是一个buffer指针，所以交换的时候只需要把指针交换，然后把cap/size也交换一下就可以了，存储在buffer中的数据不需要交换，因此性能高。
4. 附加元素接口：push_back和emplace_back在内建数据类型上差别不打，但是在一些复杂数据类型，比如自定义对象、string等会有性能上的差别。

• push_back：先构造对象，然后把构造的对象移动或者复制到buffer中。
• implace_back：直接在buffer中构造对象，因此性能更高。

5. 元素插入接口：
   insert：在某个位置插入，然后把这个位置后面的元素全部向后移动，这就需要移动后面的所有元素，所以比较慢。
   emplace：差别和push_back/emplace_back一样？？疑问：我以为是在某个位置替换元素，具体使用的时候再查一下是什么意思吧
6. 删除元素：

• pop_back：把最后的元素删掉就行
• erase：把某个元素删除，然后后面的元素全部前移
• clear：把整个vector清空

7. 写操作可能导致迭代器失效： 比如for循环使用迭代器来遍历vector（之前举过这个例子），但是在for循环中执行了push_back操作，此时end迭代器其实就失效了。如果push_back超过了vector的容量，此时会拷贝buffer中数据到另一个位置，此时begin迭代器也会失效。

1. list双向链表：一个位置存储3个元素，其中最重要的是当前位置存储的数据，然后存储一个前面元素的指针和一个后面元素的指针。
2. 插入、删除成本低，随机访问成本高

• 插入删除就是打开链表中间某个位置，然后把前后指针改一下即可。
• 随机访问成本比较高。比如vector是连续内存存储的，所以使用a[2]这种操作直接把buffer指针偏移2即可访问。而list则需要遍历元素，只有到了当前元素，才知道下一个元素在哪，到了下一个元素的位置，才知道下下个元素在哪，所以随机访问需要从头一直往后访问。因此list并没有提供[]这种随机访问的接口。

3. pop_front/splice接口：pop_front消耗很低，这个和链表结构也是相关的。splice就是把一个list插入到另一个list的某个位置，也是由于链表结构，消耗低。
4. 写操作一般不会改变迭代器的有效性

1. 引入目的：成本较低的线性表实现，因为list每个位置需要存储3个元素，成本太高。
2. 迭代器只能递增，因此无rbegin/rend
3. 不支持size：list是支持size属性的，原因是它内部还存储了一个size变量来统计链表的大小。但是forward_list为了降低成本，把size也去掉了。
4. 不支持pop_back/push_back：也是因为没有记录最后一个元素的指针？？注意：这里没有特别清楚，还要看数据结构的内容。

1. deque是vector和list的折中：注意下图的前边和后边是白色，代表分配了内存但是并没有存储元素。但看最后一个长条的话，可以发现它就是vector的典型实现。
   但是上图只是一个布局示意图，真正在实现的时候，可能如下图所示，也就是在一个数组中存储了指针，这些指针指向各个小的数组。
   

2. push_back/push_front较快：以push_back为例（push_front类似），看上图：

• 如果最后的vector没满，那么直接在最后出入元素即可，性能和普通vector一样。
• 如果最后的那个vector满了，那么需要再新开辟一个vector，然后在里面插入数据；然后还需要维护一下左边的链表，把最后一个指针指向新开辟的小的vector。这里可以发现，这样并不会复制原来的那些小的vector，因此它的性能比vector要高。

3. 随机访问元素速度较快，提供了[]接口：如上图内存布局所示，假设访问的元素位置是10，那么先把前面空的3个元素加上得到13，然后除以6取整得到在那个小的vector里，除以6取余得到在这个小的vector里的索引，这样就可以访问了。由于这个过程只设计数值计算，没有过多的内存访问操作，所以它的性能相对较高。但是相比vector还是没法比的。
4. 在序列中间插入/删除比较慢：一旦插入或者删除，那么它后面的所有小的vector里面的内容都需要移动，所以是非常慢的。

1. std::string就是basic_string
2. 提供了字符与字符串转换的接口

• 数值转string
  
• string转数值