读完两遍《STL源码剖析》后，我发现了一些辛秘

前排提醒

• 本文是阿秀以前给某位号主投稿文章改编而来，当时自己文笔还较弱，现重新改写一下发表出来，希望与大家共同进步！
• 阅读本文需要具备一些C++基础，不是完全面向小白的文章。
• 因能力有限，如果总结的不到位，欢迎各位大佬在留言区批评指正。

前言

对于每一位学习 C++ 的小伙伴来说，STL 不可谓不重要，特别是那些为我们造好的底层轮子比如容器、算法等更是一件利器。

比如在一些 OJ 平台，用 STL 下的算法刷题简直不要太爽，谁试谁知道。

不止如此，在一些大厂面试过程中，C++有两个区分度比较高的知识点：虚函数相关和 STL 。

不管是骡子是马，问一下这两个知识点就知道几斤几两了。

今天阿秀就带大家梳理一下 STL 中的常见容器下的一些小知识吧，都是我过去两年在学习C++过程中慢慢总结出来的。

在此过程中去验证一下，那些真理，特别喜欢侯捷老师的一句名言：源码面前，了无秘密。

好了，发车！

STL 下的容器主要分为两类：序列式容器以及关联式容器。

序列式容器顾名思义就是物理上彼此相邻的一种关系，比如数组、栈、队列或者你和你的同桌，这种一个挨着一个的关系；而关联式容器的重点在关联二字上，至少是两个东西之间存在着某种联系才可以叫做关联，否则就不能被称之为关联式容器了，比如 hashtable 中的key和 value，是一对一或者一对多的关系。

序列式容器

vector

不知道在读的小伙伴在刷算法题的时候最喜欢哪个容器，我个人最喜欢的、用的最顺手的容器绝对是vector。

它是一种类似于数组的数据结构，它与数组 array 非常类似，两者的唯一差别就是对于空间运用的灵活性，vector 更加灵活多变，而 array 比较固定，具体来说：

• array 占用的是静态空间。也就是说一旦配置了它的空间就不可以改变大小，如果遇到空间不足的情况还要自行创建更大的空间，并手动将以前的数据拷贝到新的空间中，再把原来的空间释放才行。

• vector 则使用更加灵活的动态空间来进行配置。它始终维护一块连续的线性空间，在空间不足时，vector可以自动扩展空间容纳新元素，做到按需供给。其在扩充空间的过程中仍然需要经历：重新配置空间，移动数据，释放原空间等操作。

​ 《STL源码剖析》一书中侯捷老师说 vector 扩容倍数为2倍，如下图所示：

但网上也有说 1.5 倍的，后来我自己动手实践一番后得出结论：动态扩容原则跟操作系统相关，没有一个统一的结论，也就是说在不同环境下 vector 的扩容系数是不一样的，不可盖棺定论为 2 倍。

实践代码如下：

int main()
{
    vector<int> data(2, 1);
    cout << "size: " << data.size() << " capacity " << data.capacity() << endl;
    data.push_back(1);
    cout << "size: " << data.size() << " capacity " << data.capacity() << endl;
    data.push_back(1);
    cout << "size: " << data.size() << " capacity " << data.capacity() << endl;
    data.push_back(1);
    cout << "size: " << data.size() << " capacity " << data.capacity() << endl;
    data.push_back(1);
    cout << "size: " << data.size() << " capacity " << data.capacity() << endl;
    data.push_