STL之vector扩容机制

前言

    大家好，我是萝卜。上期结尾说到vector的push_back操作一般情况下时间复杂度为O(1)，是否存在特殊情况。那么本期就讲讲vector在容器空间不足时进行push_back操作会发生什么。

    vector作为STL的常用容器之一，其特性和数组类似，拥有一段连续的内存空间。vector申请的是一段连续的内存，当插入新的元素内存不够时，通常会再重新申请更大的一块内存，将原来的元素拷贝过去，释放旧空间。因为内存空间是连续的，所以在进行插入和删除操作时，会造成内存块的拷贝，时间复杂度为O(n)。

相关函数

在讲解vector扩容机制前，先了解四个函数：

size()、capacity()、resize()、reserve()。

• size()：

size()函数返回当前vector所容纳元素的数目，即使用的空间大小。

• capacity()

capacity()函数返回当前vector在重新进行内存分配以前所能容纳的元素数量，即返回的是总的容量大小，capacity()-size()后就是未使用的空间大小。

使用者可以通过reserve()来改变capacity()，resize()改变size()。

• resize()

resize，即重置容器空间。当设置值小于当前容器空间时，会将目前容器中超出设置值的空间释放掉；当设置值大于当前容器空间时，会在当前空间的基础上增加容量。

举个例子，vector当前容量为10，若使用resize(20)设置容量为20，则需要再扩容增加10个；若使用resize(5)设置容量为5，则将6-10的空间进行释放。

源码如下：

void resize(size_type __new_size){
    if (__new_size > size()){ 
        _M_default_append(__new_size - size());
    }
    else if (__new_size < size()){
        _M_erase_at_end(this->_M_impl._M_start + __new_size);
    }
}

• reserve()

reserve，即预留容器空间。当设置值大于当前容器空间时，会增加当前容器空间的大小，源码如下：

void reserve(size_type __n){
    if (__n > max_size()){
        __throw_length_error(__N("vector::reserve"));
    }
    if (capacity() < __n){
        _M_reallocate(__n);
    }
}

扩容机制

不同编译器在vector的扩容策略上显然不太一致，在vector的size()(当前容器所用空间)等于capacity()(当前容器总空间)时会发生扩容。

不同的的编译器实现方式不同,vs编译器每次是以1.5倍且向下取整的策略进行扩容，gcc编译器则是每次以2.0倍的策略进行扩容。

扩容因子的比较

扩容的大小叫做扩容因子，扩容因子由编译器决定，VS的扩容因子为1.5，G++中，扩容因子为2。

• 扩容因子大，每次需要分配的新内存空间越多，分配空间耗时。空闲空间较多，内存利用率低。

• 扩容因子小，需要再分配的可能性更高，扩容耗时。空闲空间较少，内存利用率较。

一般认为扩容因子1.5优于2.0，原因是以1.5作为扩容因子可以实现复用释放的内存空间。

以2为扩容因子时，空闲的空间始终要小于需要分配的空间

以1.5为扩容因子时，随着分配空间增大，之前释放的空闲空间能够满足当次扩容所需的空间，实现内存的复用

扩容后数据地址变化

在扩容时，系统会选择一端更大的内存，将数据从原来的内存拷贝过来，同时释放原有的内存。这时数据存在的地址就发生了改变。我们可以通过&vector[0]的方式来查看数据首地址。

注意：对于vector，&vector和&vector[0]是不一样的; 而对于数组，&array与&array[0]是一样的。