深度剖析C++ STL vector容器的底层构造

学习了这么久的vector，想必读者对vector的底层原理一定充满好奇，为了满足读者的求知欲，本节将带领读者深入vector的学习，探寻其底层实现的奥秘。

vector被称为动态数组，普通数组的promax版，得益于动态扩展这一特性使得它与普通数组走上了截然不同的命运。下面我将提供其底层源码的一部分，有理有据地深入了解vector。

template<typename _Tp, typename _Alloc>struct _Vector_base {
    struct _Vector_impl : public _Alloc {
        pointer _M_start;     //指向第一个元素
        pointer _M_finish;   //指向最后一个元素的下一个位置    
        pointer _M_end_of_storage; //指向内存块最后一个位置的下一个位置

        _Vector_impl()
            : _M_start(0), _M_finish(0), _M_end_of_storage(0) 
        { }
        
        _Vector_impl(_Alloc const& __a)
            : _Alloc(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0) 
        { }
    };public:
    _Vector_impl _M_impl;

源码比较复杂，我们只需要关心单行注释这三个变量就好了，他们是vector的核心变量。

有色部分（A-G）表示一个vector容器，可见该容器预存共7个单位空间，已经有5个单位空间被使用了（深绿色部分），还有2个单位空间没有被使用（浅绿色部分）。

此时注意三个指针的位置，大多数情况下，_M_start负责查找，比如从头开始遍历元素；_M_finish负责元素增删，比如push_back()、pop_back()；_M_end_of_storage管内存尾，负责统计容器容量。

当然，你也可以写一个模板去实现diy的vector，通过这三个指针的千变万化来满足个性化需求。

那么vector是如何“动态”的呢？

当元素总量超过当前容量时，vector会申请一个更大内存，然后将原数据复制到新数组，然后销毁旧数组，是不是有点像冒泡排序的swap算法，我愿称其为移花接木。一次动态扩展的行为，由于地址发生变化，所以会影响其他成员变量，比如维护的指针或迭代器，所以我们需要及时更新这类变量，避免未定义行为。