STL之vector的push_back过程详解

最近，被面试官的一道题问倒，很失落，明明看过《STL源码分析》，为啥这种问题还没答好，只能说自己看的时候没有仔细去思考。这道题就是标题的问题，面试完我重新看了一遍《STL源码分析》中关于这块的内容，这里记录下自己看完的一点理解。

在STL中，一般对容器的内存分配和构造是分开的2个过程，STL有专门的空间配置器负责分配内存，而构造则是通过placement new在已申请的内存上进行的，vector也不除外，下面是vector的push_back函数源码：

template <class T, class Alloc = alloc>
void vector::push_back(const T& x)
{
    if (finish != end_of_storage)
    {
        construct(finish, x);
        ++finish;
    }
    else
    {
        insert_aux(finish, x);
    }
}

其中，construct是STL的全局函数，是所有容器共用的，它的具体实现如下：

template<class T1, class T2>
inline void construct(T1* p, const T2& value)
{
    new(p) T1(value);    //placement new, 调用T1::T1(value);
}

而insert_aux是vector自己的成员函数，具体实现如下：

template <class T, class Alloc = alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x)
{
    //还有备用空间
    if (finish != end_of_storage)
    {
        //在备用空间起始处构造一个元素，并以vector最后一个值为其初值
        construct(finish, *(finish - 1));
        //调整水位
        ++finish;
        //拷贝一个元素
        T copy_x = x;
        //把vector插入位置position之后的元素往后移一位
        copy_backward(position, finish - 2, finish - 1);
        //给position指向的地方赋值，赋值内容为前面拷贝的元素
        *position = copy_x;
    }
    //已无备用空间
    else
    {
        const size_type old_size = size();
        //如果原来的vector为空，则申请一个元素的空间，否则申请可以容纳原来2倍元素的空间
        const size_type len = old_size == 0 ? 1 : 2 * old_size;
        //全局函数，申请空间
        iterator new_start = data_allocator::allocate(len);
        iterator new_finish = new_start;

        try
        {
            //将原来vector的position之前的内容拷贝到新的vector前面
            new_finish = uninitialized_copy(start, position, new_start);
            //调用构造函数为新插入的元素赋值
            construct(new_finish, x);
            //调整水位
            ++new_finish;
            //将原来vector的postion之后的内容拷贝到新的vector后面
            new_finish = uninitialized_copy(position, finish, new_finish);
        }
        catch (...)
        {
            //析构
            destroy(new_start, new_finish);
            //释放刚刚申请的内存
            data_allocator::deallocate(new_start, len);
            throw;
        }

        //析构原vecotr
        destroy(begin(), end());
        //释放原vector的空间
        deallocate();
        
        //调整迭代器指向新的vector
        start = new_start;
        finish = new_finish;
        end_of_storage = new_start +len;
    }
}

上面空间配置函数allocate的最底层实现比较复杂，但是只要记住2点即可，（1）如果申请的空间大于128字节，就直接调用malloc申请，（2）如果申请的空间小于等于128字节，就从STL维护的16条free list里面寻找合适的一块内存使用（这16条free list各自管理大小分别为8，16，24，32，40，48，56，64，72，80，88，96，104，112，120，128字节的小额内存块，之所谓维护这些list既是为了防止频繁调用malloc，也是为了避免太多小额区块造成内存的碎片）。

介绍了这么多，回到最初的问题，如果我们一开始定义了一个空的vector，然后现在要往里面push_back一个个对象，这个过程具体是怎样的，请看下面这段代码的注释，这些都是我重新看了一遍书的理解：

//定义一个类A
class A{
    int x;
    double y;
};

//定义一个空的vector，vector中可以存放的是类A的对象
vector<A> vec;

//定义类A的对象a，对象b，对象c和对象d
A a;
A b;
A c;
A d;

/*
注意：根据上面对push_back的源码分析可知，
因为一开始vec是空的，所以会走insert_aux函数的无可用空间的分支，
调用allocate申请一块能够容纳《一》个A类对象的内存，
并调用拷贝构造函数把a赋值给vec的finish迭代器指向的内存，
说白了就是vec中存放的a和上面定义的a对象已经不是一个东西了。
*/
vec.push_back(a);

/*
注意：根据上面对push_back的源码分析可知，
现在vec也没有多余的可用空间，所以会再次走insert_aux函数的无可用空间的分支，
调用allocate申请一块能够容纳《两》个A类对象的内存，
把原来的vec的唯一一个元素a移动到新的vec上去，
并调用拷贝构造函数把b赋值给新的vec的finish迭代器指向的内存，这时a和b存放在相邻内存中。
*/
vec.push_back(b);

/*
注意：根据上面对push_back的源码分析可知，
现在vec也没有多余的可用空间，所以会再次走insert_aux函数的无可用空间的分支，
调用allocate申请一块能够容纳《四》个A类对象的内存，
把原来的vec的两个元素a和b移动到新的vec上去，
并调用拷贝构造函数把c赋值给新的vec的finish迭代器指向的内存，
这时a和b和c存放在相邻内存中，而且这块内存还能再容纳一个类A对象。
*/
vec.push_back(c);

/*注意：根据上面对push_back的源码分析可知，
现在vec还有一个可用空间，所以这次会走construct函数的分支，
通过placement new在已有的内存上调用拷贝构造函数把d赋值给finish迭代器指向的内存，
这时a和b和c和d存放在相邻内存中，但这块内存又再次没有剩余空间了。
*/
vec.push_back(d);

就写到这里吧，继续面壁思过了。