1. 容器 vector

1> vector 底层结构

vector 实际上是一个动态增长的数组，其内部通过一个指针指向一块连续的线性空间，若新增元素，内部会自动申请一片更大的空间以容纳新元素，然后释放旧的空间。

一个 vector 容器中包含三个部分：

• 迭代器：用于遍历容器内部的元素；
• 构造函数：满足容器不同的初始化方式；
• 属性获取：比如 begin()， end()等；

对于 vector 其内部包含三个迭代器：

template <class T, class Alloc = alloc>
class Vector {
protected:
    iterator start; // 当前使⽤空间的头
    iterator finish; // 当前使⽤空间的尾
    iterator end_of_storage; // 当前可⽤空间的尾
};

因为 vector 需要表示用户操作的当前数据的起始地址，结束地址，还需要其真正的最大的地址，所以共需要 3 个迭代器分别指向：数据的头（start），数据的尾（finish），数组的尾（end_of_storage）

2> vector 扩容机制

当有新的元素插入时, 若目前容量够用则直接插入, 若容量不够, 则容量扩充至两倍.
扩充的过程是重新申请一块连续空间, 将原有的数据拷贝到新空间中, 再释放原有空间, 完成了一次扩充.
需要注意的是，每次扩充是重新开辟的空间，所以扩充后，原有的迭代器将会失效。

vector 提供的常用接口：

/* 容量 */
empty(): 检测是否为空
reserve():    预留存储
capacity(): 返回内部容量
/* 编辑 */
clear(): 清空内容
erase(): 删除元素
push_back(): 添加元素到末尾
emplace_back(): 在末尾构造元素

1.1 vector 的 push_back() 内部的流程？

当调用 push_back() 插入新元素的时候，首先会检查是否有备用空间，如果有就直接在备用空间上构造元素，并调整内部迭代器 finish向后移动一位；

1.2 vector 的 erase() 内部的流程?

erase() 方法用于清除指定位置的元素，其删除过程如下：
第一步，将 迭代器 finish 后面的元素向前拷贝，然后返回拷贝完成的尾部迭代器

1.3 追问：vector的 size() 与 capacity()区别是什么？

size() 得到的是容器内部已有元素的数量； capacity()得到的是容器的最大容量.

1.4 追问：清除 vector 的元素是使用什么方法？

clear() 删除所有的元素， 调用后 size() 返回 0

1.5 追问: 频繁对vector调用 push_back() 性能影响?

向 vector 的尾部添加元素，很有可能引起整个对象 存储空间的重新分配，重新分配更大的内存，再将原数据拷贝到新空间中，再释放原有内存，这个过程是耗时耗力的，频繁对 vector 调用 push_back() 会导致性能的下降.

在 C++11 之后， vector 容器中添加了新的⽅法： emplace_back() ，和 push_back() ⼀样的是都是在容器末尾添加⼀个新的元素进去，不同的是 emplace_back() 在效率上相比较于 push_back() 有了⼀定的提升

emplace_back() 函数在原理上较 push_back() 有了⼀定的改进，包括在内存优化方面和运行效率方面。内存优化主要体现在使用了就地构造（直接在容器内构造对象，不用拷贝⼀个复制品再使用）+ 强制类型转换的⽅法来实现，在运行效率方面，由于省去了拷贝构造过程， 因此也有⼀定的提升

1.6 追问：使用 STL 迭代器删除元素？

对于序列容器 vector，deque来说，使⽤ erase(itertor) 后，后边的每个元素的迭代器都会失效，但是后边每个元素都会往前移动⼀个位置，但是 erase 会返回下⼀个有效的迭代器；

所以循环 erase 一般写法如下：

std::vector<int> c{0, 1, 2, 3, 4, 5};
for(auto it = c.begin(); it != c.end();) {
    if(*it % 2 == 0) {
        it = c.erase(it);
    } else {
        ++it;
    }
}

1.7 追问： vector 为什么是两倍扩容？

使用k=2增长因子的问题在于，每次扩展的新尺寸必然刚好大于之前分配的总和，也就是说，之前分配的内存空间不可能被使用。这样对内存不友好。最好把增长因子设为(1,2)

1.8 追问：vector 动态扩容开销较大，有没有可以提高效率的方式进行扩容？

由于动态增长会引起重新分配内存空间、拷贝原空间、释放原空间，这些过程会降低程序效率。因此，可以使用reserve(n)预先分配一块较大的指定大小的内存空间，这样当指定大小的内存空间未使用完时，是不会重新分配内存空间的，这样便提升了效率。只有当n>capacity()时，调用reserve(n)才会改变vector容量。

1.9 追问: 有了解list吗? list与vector的区别是什么?

STL list 是⼀个双向链表，普通指针已经不能满足 list 迭代器的需求， 因为 list 的存储空间是不连续的。list 的迭代器必需具备前移和后退功能，所以 list 的数据结构中只要⼀个指向 node 节点的指针就可以了

与 vector 相比，list 的好处就是每次插⼊或删除⼀个元素，就配置或释放⼀个空间，⽽且原有的迭代器也不会失效。

1.10 容器内部删除一个元素是怎么删除？

1)  顺序容器

erase迭代器不仅使所指向被删除的迭代器失效，而且使被删元素之后的所有迭代器失效(list除外)，所以不能使用erase(it++)的方式，但是erase的返回值是下一个有效迭代器；

it = c.erase(it);

2)  关联容器

erase迭代器只是被删除元素的迭代器失效，但是返回值是void，所以要采用erase(it++)的方式删除迭代器；

c.erase(it++)