刷题、找工作，不会STL怎么行？vector篇（上）

作者 | 梁唐

大家好，我是梁唐。

今天来和大家聊聊C++当中一个非常重要的STL库，叫做vector。

为什么要讲这个？因为这个库非常重要，学会了它对于刷题、笔试非常有帮助，熟悉使用可以大大简化代码量。有同学会说，为什么一定要用C++刷题，其他语言不行么？

其实也行，但C++最专业，其他语言难免遇到各种问题。

vector

vector本身是向量的意思，在计算机系统当中，一般vector都表示一个数组形式的向量。

在C++ STL当中也非常类似，只不过我们也可以有不同的理解，比如可以理解成一个可变长度的数组。众所周知，数组的长度都是固定的，链表的长度是可以随意增长的。当我们不知道有多少元素需要存储的时候，使用可变长度的数据结构就会非常舒服。

但使用链表的话访问起来非常不方便，我们没办法快速访问链表当中的某一个位置。而数组可以访问很快，但长度固定，一旦长度超过就会越界报错。

vector就可以看成是将链表和数组优点彼此结合的产物。

原理

对于程序员来说，学习一个工具或者是一个系统的原理，最好的方式就是去读它的源码。源码当中藏着一切原理和细节，源码能读懂，一切都没问题了。

当然，源码可能很长，也可能很难懂，尤其是对于初学者来说。不过也不用太担心，一般来说比较优秀的源码都会有非常非常完善的注释，如果你英语好的话，结合注释一起理解，难度并不大。

话不多说，我们就一起来看看vector这个类的源码。

我们的目的是理解vector核心的运行机制，所以我们抓大放小，先从最根本的类结构看起。

template<class _Ty,
    class _Ax>
    class vector
        : public _Vector_val<_Ty, _Ax>
    {   // varying size array of values
public:
    /********/
protected:
    pointer _Myfirst;   // pointer to beginning of array
    pointer _Mylast;    // pointer to current end of sequence
    pointer _Myend; // pointer to end of array
    };

一开始是一些类的定义，比如这里用到了模板类。如果你不明白什么是C++中的模板类，也没关系，可以先放一放，之后再去补。

关键点在于protected当中的三个值，也就是Myfirst、Mylast和Myend。这三个值是理解vector原理的关键，为了更好理解， 我找来一张图，大家一看就明白了。

Myfirst和Myend很好理解，表明的是这个vector的存储范围，如果把它理解成链表的话，一个是头结点，另外一个是尾结点。

那么这个Mylast又是什么呢？Mylast记录的是已有数据的最后位置，也就是说虽然我们能存储Myend - Myfirst这么多的元素，但是我当前可能没有使用那么多，仅仅使用了其中的一部分。已使用这部分的末尾位置就是Mylast。

理解了这个，我们再来看相关的两个术语。

一个叫做size一个叫做capacity，size大家都知道就是尺寸、大小的意思，capacity的意思是容量。对比到上面这张图，我们可以知道一个vector的size应该是Mylast - Myfirst，也就是已经存入的元素数量。capacity自然就是Myend - Myfirst，也就是这个vector能够存储的最大容量。

理解了这个存储原理之后，还没有结束，我们进一步可以思考一个问题。

vector是可变长度的，我们在使用的时候其实是不知道它满了没有的。如果它已经满了，Mylast等于Myend了，这个时候我们再继续插入元素会发生什么呢？

很简单，它会重新申请一块新的更大的内存，然后将当前存储的所有元素都拷贝过去，之后再对老的数据进行销毁。这样的操作也有个术语叫做扩容，每一次扩容，都会申请比之前大50%空间的内存。

同样我们不难想到，扩容的操作需要申请内存、销毁内存，还需要拷贝大量元素，这是非常耗时的。所以为了性能考虑，我们在使用vector的时候应该尽量避免扩容的操作出现。

探讨

虽然粗浅，但vector的基本原理到这里就算是讲完了，剩下也有很多细节值得研究，但主要的内容就这么多。

表面的原理就这些，但深层次的内容其实还有很多，需要我们自己挖掘。比如说，为什么每次扩容的时候，容量扩大50%，这个50%的数字是怎么来的？

如果你想到这个问题，说明你的思维很缜密，捕捉到了细节里的魔鬼。C++ vector全世界开发者都在使用的容器，它的原理必然是无比缜密的，当中的任何一个值任何一个设计方法都不可能是凭空来的，一定是经过前人思考和实验的。

前文说了，每次扩容都会重新申请一块更大的内存，这个在我们看来是理所应当的，但这个更大究竟是多大就很难描述了。如果新申请的内存过大，可能会造成浪费。我存储了10个元素，却开辟了1000个元素的空间，显然就太浪费了。如果过小，也有问题，因为很快就满了，又需要重新申请。

50%的扩容率是工程师经过反复权衡和实验之后得到的一个折中值，既不会过大造成浪费，也不会过小，导致频繁申请内存影响性能。所以当我们使用vector的时候，不要无脑使用，不妨也可以想一想在我们的场景中存储的元素规模最大可能是多少，提前布局，尽量避免vector的扩容出现影响性能。你想到了，别人没想到，自然你的代码性能更好，bug更少。

如果你还学过其他一些编程语言的话，又会发现新的问题。

因为现在流行的所有其他语言，几乎都有可变长度数组这样一个概念，那么问题来了，对于这些语言来说，它们的可变长度数组又是怎么实现的？比如Python的list，比如java的ArrayList，再比如Go的slice。

如果能够再去细化了解其他语言的list的实现原理，又会有新的收获。比如会发现Java的ArrayList采取的是和vector一样的扩容机制，而Go和Python则在扩容率上有一些细微的区别，整个大体的原理依然是一致的。如果再去追究，为什么会有这样的区别？一层层地刨根问题，又会学到新的原理，拥有新的积累。这样反反复复，还愁技术实力不强吗？

扯远了，关于vector的基本原理就说到这里，下期再和大家聊聊vector的一些具体用法。

感谢大家的阅读。