面试之快速学习STL- vector

1. vector底层实现机制刨析：

简述：使用三个迭代器表示的：



这也就解释了，为什么 vector 容器在进行扩容后，与其相关的指针、引用以及迭代器可能会失效的原因。

insert

整体向后移

erase

整体向前移

size 变化会重新reserve

2. emplace_back()和push_back()的区别

emplace_back() 和 push_back() 的区别，就在于底层实现的机制不同。push_back() 向容器尾部添加元素时，首先会创建这个元素，然后再将这个元素拷贝或者移动到容器中（如果是拷贝的话，事后会自行销毁先前创建的这个元素）；而 emplace_back() 在实现时，则是直接在容器尾部创建这个元素，省去了拷贝或移动元素的过程。

3. 避免不必要的扩容：

那既然扩容会影响程序的运行效率，那我们如何来避免呢？
在插入元素之前，我们可以预估vector里面要存储多少个元素，我们提前将这个空间给它开辟好就可以了！！！
比如说，我们需要向vector中插入100个元素，在执行push_back之前，我们进行reserver预留空间，只要空间大小给的足够，在整个插入的过程中就不需要进行任何的扩容！

4. 减小不必要的容量

1 . shrink_to_fit()
2 . Swap
如果想用 swap() 成员方法去除当前 vector 容器多余的容量时，可以套用如下的语法格式：
vector(x).swap(x);

1. #include <iostream>
2. #include <vector>
3. using namespace std;
4. 
5. int main()
6. {
7.     vector<int>myvector;
8.     //手动为 myvector 扩容
9.     myvector.reserve(1000);
10.     cout << "1、当前 myvector 拥有 " << myvector.size() << " 个元素，容量为 " << myvector.capacity() << endl;
11.     //利用 myvector 容器存储 10 个元素
12.     for (int i = 1; i <= 10; i++) {
13.         myvector.push_back(i);
14.     }
15.     //将 myvector 容量缩减至 10
16.     vector<int>(myvector).swap(myvector);
17.     cout << "2、当前 myvector 拥有 " << myvector.size() << " 个元素，容量为 " << myvector.capacity() << endl;
18.     return 0;
19. }

输出：

1、当前 myvector 拥有 0 个元素，容量为 1000
2、当前 myvector 拥有 10 个元素，容量为 10

显然，第 16 行代码成功将 myvector 容器的容量 1000 修改为 10，此行代码的执行流程可细分为以下 3 步：

1. 先执行 vector(myvector)，此表达式会调用 vector 模板类中的拷贝构造函数，从而创建出一个临时的 vector 容器（后续称其为 tempvector）。
   值得一提的是，tempvector 临时容器并不为空，因为我们将 myvector 作为参数传递给了复制构造函数，该函数会将 myvector 容器中的所有元素拷贝一份，并存储到 tempvector 临时容器中。
   注意，vector 模板类中的拷贝构造函数只会为拷贝的元素分配存储空间。换句话说，tempvector 临时容器中没有空闲的存储空间，其容量等于存储元素的个数。
2. 然后借助 swap() 成员方法对 tempvector 临时容器和 myvector 容器进行调换，此过程不仅会交换 2 个容器存储的元素，还会交换它们的容量。换句话说经过 swap() 操作，myvetor 容器具有了 tempvector 临时容器存储的所有元素和容量，同时 tempvector 也具有了原 myvector 容器存储的所有元素和容量。
3. 当整条语句执行结束时，临时的 tempvector 容器会被销毁，其占据的存储空间都会被释放。注意，这里释放的其实是原 myvector 容器占用的存储空间。
   经过以上 3 个步骤，就成功的将 myvector 容器的容量由 100 缩减至 10。

当 swap() 成员方法用于清空 vector 容器时，可以套用如下的语法格式：
vector().swap(x);

4. vector < bool >

具体来讲，不推荐使用 vector 的原因有以下 2 个：

1. 严格意义上讲，vector<bool> 并不是一个 STL 容器；
2. vector<bool> 底层存储的并不是 bool 类型值。

值得一提的是，对于是否为 STL 容器，C++ 标准库中有明确的判断条件，其中一个条件是：如果 cont 是包含对象 T 的 STL 容器，且该容器中重载了 [ ] 运算符（即支持 operator[]），则以下代码必须能够被编译：

T *p = &cont[0];

此行代码的含义是，借助 operator[ ] 获取一个 cont 容器中存储的 T 对象，同时将这个对象的地址赋予给一个 T 类型的指针。
这就意味着，如果 vector 是一个 STL 容器，则下面这段代码是可以通过编译的：

//创建一个 vector 容器

vectorcont{0,1};

//试图将指针 p 指向 cont 容器中第一个元素

bool *p = &cont[0];

但不幸的是，此段代码不能通过编译。原因在于 vector 底层采用了独特的存储机制。

实际上，为了节省空间，vector 底层在存储各个 bool 类型值时，每个 bool 值都只使用一个比特位（二进制位）来存储。也就是说在 vector 底层，一个字节可以存储 8 个 bool 类型值。在这种存储机制的影响下，operator[ ] 势必就需要返回一个指向单个比特位的引用，但显然这样的引用是不存在的，等号左右两边出现冲突！

么，如果在实际场景中需要使用 vector< bool > 这样的存储结构，该怎么办呢？很简单，可以选择使用 deque< bool > 或者 bitset 来替代 vector。

要知道，deque 容器几乎具有 vecotr 容器全部的功能（拥有的成员方法也仅差 reserve() 和 capacity()），而且更重要的是，deque 容器可以正常存储 bool 类型元素。

还可以考虑用 bitset 代替 vector，其本质是一个模板类，可以看做是一种类似数组的存储结构。和后者一样，bitset 只能用来存储 bool 类型值，且底层存储机制也采用的是用一个比特位来存储一个 bool 值。