C++面试八股文：std::vector了解吗？

某日二师兄参加XXX科技公司的C++工程师开发岗位第23面：

面试官：vector了解吗？

二师兄：嗯，用过。

面试官：那你知道vector底层是如何实现的吗？

二师兄：vector底层使用动态数组来存储元素对象，同时使用size和capacity记录当前元素的数量和当前动态数组的容量。如果持续的push_back(emplace_back)元素，当size大于capacity时，需要开辟一块更大的动态数组，并把旧动态数组上的元素搬移到当前动态数组，然后销毁旧的动态数组。

面试官：你知道新开辟的动态数组的容量是就数组的多少倍比较合适？

二师兄：这个值在不同的编译器上不是固定的。MSVC 是1.5，而GCC是2。

面试官：有没有什么好的办法提升vector连续插入效率？

二师兄：有的，如果知道数据的大概量，我们可以使用reserve方法直接为vector扩容这个量级。这样在后续的数据插入时就不会因为频繁的capacity被用尽而导致的多次的数据搬移，从而提升vector插入效率。

面试官：push_back和emplace_back有什么区别？

二师兄：两者都可以在容器尾部插入元素。在GCC中，如果插入的元素是右值，两者都会move元素到容器。如果是左值，两者都会copy元素到容器。唯一不同的一点是，当C++版本高于C++17时，emplace_back返回当前插入的值的引用，而push_back返回void。

面试官：erase和remove有什么区别？

二师兄：erase属于成员函数，erase删除了元素，remove属于算法库函数，而remove只会把元素移动到尾部。

面试官：哪些情况下迭代器会失效？

二师兄：迭代器失效主要有两种情况引起：1.插入数据。由于插入数据可能导致数据搬移（size > capacity）,所以迭代器失效。2.删除数据。当使用erase删除数据时，被删除数据后面的数据依次向前移一位。这会导致被删除数据之后的迭代器失效。

面试官：如何快速的清空vector容器并释放vector容器所占用的内存？

二师兄：有两种方法：第一种，使用clear方法清空所有元素。然后使用shrink_to_fit方法把capacity和size（0）对齐，达到释放内存的作用：

#include <iostream>
#include <vector>
int main(int argc, char const *argv[])
{
    std::vector<int> vi;
    vi.reserve(1024);
    for (int i = 0; i < 1024; i++) vi.push_back(i);
    std::cout << vi.size() << " " << vi.capacity() << std::endl;    //1024 1024
    vi.clear(); 
    std::cout << vi.size() << " " << vi.capacity() << std::endl;    //0 1024
    vi.shrink_to_fit(); 
    std::cout << vi.size() << " " << vi.capacity() << std::endl;    //0 0
}

二师兄：第二种，使用swap方法；

#include <iostream>
#include <vector>
int main(int argc, char const *argv[])
{
    std::vector<int> vi;
    vi.reserve(1024);
    for (int i = 0; i < 1024; i++) vi.push_back(i);
    std::cout << vi.size() << " " << vi.capacity() << std::endl;    //1024 1024
    std::vector<int>().swap(vi); //使用临时量（size =0, capacity=0）和vi交换，临时量会立即析构
    std::cout << vi.size() << " " << vi.capacity() << std::endl;    //0 0
}

面试官：你知道vector<bool>是如何实现的吗？

二师兄：vector<bool>的实现和其他实现容器的实现不一致。每个元素被当作一个位而不是一个字节存储。这导致我们不能直接访问该元素，也无法对每个元素取地址（8个元素可能在同一个字节中存储）。所以不建议使用vector<bool>，必要时可以使用std::bitset替代。

面试官：好的，回去等通知吧。