序列式容器 之 vector详解_vector的内存管理

目录

一.vector的迭代器

二.vector的数据结构

三.vector的构造与内存管理

3.1 vector的构造

3.2 vector的内存管理

3.3 vector的元素操作

---

        vector容器是c++模板库中十分重要且有用的容器，它的存储结构属于线性表，不过究其根本，vector容器的存储地址是在堆区开辟的，以下本文将简单介绍vector容器的使用方法以及内部实现原理。

一.vector的迭代器

        由于vector维护的是一个连续的线性空间（通过SGI提供的配置器alloc申请的连续内存），所以vector的迭代器（迭代器说白了就相当于指针的作用，由于容器是一种特殊的数据结构，需要迭代器这种特殊的指针进行维护，从而实现像普通指针那样对容器内存的访问，如，++操作指向当前内存的下一个内存，或者通过“*”对指针指向的内容的读取，等等）使用普通的指针就可以实现对vector内存的维护，因此，vector的迭代器属于Random Access Iterators。但是为了统一容器的迭代器的格式，于是对普通指针进行了简单封装：

template <class T, class Alloc = alloc>
class vector{
public:
    typedef T           value_type;
    typedef value_type* iterator;  //vector的迭代器就是普通指针
};

二.vector的数据结构

        vector的数据是申请在堆区的，所以需要用指针进行维护：

iterator start;         //表示目前使用的空间的头
iterator finish;        //表示目前使用的空间的尾
iterator end_of_storage;//表示目前可用的空间的尾

        其中，为了降低空间配置时的速度成本，vector实际配置的大小可能比客户需求得更大一些，一会讲到。

三.vector的构造与内存管理

3.1 vector的构造

        vector的构造其实就是类的构造函数，其中，vector的构造函数重载了多种类型，但是基本的使用方式都是一样的，都是先传入要构造空间大小，其次传入要填充的初值。

//vector的其中一个构造函数
vector(size_type n, const T& value)
{
    fill_initialize(n, value);//看起来vector只是对fill_initialize()函数的简单封装
}

        其中，fill_initialize()函数：首先，调用allocate_and_fill()函数先配置大小为n的连续空间再全部用value进行填充，再返回该连续空间的首地址给start成员变量；然后，再设置finish = start + n；最后设置end_of_storage = finish，因此初始化vector的可用空间大小和实际使用的空间大小相同。

void fill_initialize(size_type n, const T& value)
{
    start = allocate_and_fill(n, value);
    finish = start + n;
    end_of_storage = finish;
}

3.2 vector的内存管理

        当我们以push_back()函数填入vector尾端时，该函数检查是否有备用空间，如果有就直接在备用空间中构造元素；如果没有备用空间了，就调用insert_aux()函数。

void push_back(const T& x)
{
    if(finish != end_of_storage)//如果还有备用空间
    {
        construct(finish, x);
        ++finish;
    }
    else                        //没有备用空间
        insert_aux(end(), x);
}

        对于insert_aux()函数，并不是所有部分都是push_back()函数所能用得到的，其中该函数主要是重新创建一个两倍于原来空间的新空间，并且将之前的所有元素都移到新空间中，再将原来的空间释放掉，本文将简单介绍push_back()函数所能用得到的部分：

/............/
const size_type old_size = size();//返回目前vector容器已经使用的空间大小
//如果原大小为0，则配置1个元素大小；反之配置原来两倍的空间大小
const size_type len = old_size != 0 ? s* old_size : 1;
 
iterator new_start = data_allocator::allocate(len);//利用空间配置器在堆区重新申请一个大小为len的连续线性空间
iterator new_finish = new_start;
try{
    //将原vector的内容拷贝到新vector
    new_finish = uninitialized_copy(start, position, new_start);
    //为新元素设定初值x
    consturct(new_finish, x);
    ++new_finish;
    /............/
}
/............/

3.3 vector的元素操作

        vector的元素操作主要有用于从vector尾部删除元素的pop_back()函数，也有用于从迭代器first指向的元素之后，last指向的元素之前的所有元素进行清除的erase(iterator first, iterator last)函数以及删除整个vector中所有元素的clear()函数。

        以上三个函数源码比较简单易懂，再次我将整理以下我对于比较复杂的insert(iterator position, size_type n, const T& x)函数的理解：

        insert函数要对备用元素地址（insert申请的但未填充具体数值的地址）的大小进行计算，判断备用元素个数是否大于等于要插入元素个数？

        1.如果时，先拷贝之前的finish的值到新变量old_finish中；然后再进行判断，插入点position之后，finish（之前说过）之前的元素是否大于新增元素个数？

if(size_type(end_of_storage - finish) >= n)
{
    T x_copy = x;
    const size_type elems_after = finish - position;//插入点到目前使用空间尾部的元素个数
    iterator old_finish = finish;
    /.../
}

        a.如果是，则将finish-n到finish之间的已填充的元素拷贝复制到finish之后的已分配但未填充的部分，finish = finish+n；然后再将position到old_finish-n之间的元素复制到old_finish元素之前；最后，再将position到position+n之间由新元素x覆盖：

if(elems_after > n)
{
    uninitialized_copy(finish - n, finish, finish);
    finish += n;
    copy_backward(position, old_finish-n, old_finish);
    fill(position, position + n, x_copy);
}

        b.如果否，则将finish之后，end_of_storage之前填充n - elems_after个元素x，finish += n - elems_after；然后再将postion到old_finish之间的将要被x覆盖的元素拷贝复制到finish之后，finish += elems_after；然后再将position到old_finish之间用元素x覆盖：

uninitialized_fill_n(finish, n - elems_after, x_copy);
finish += n - elems_after;
uninitialized_copy(position, old_finish, finish);
fill(position, old_finish, x_copy);

        2.如果备用空间不足，则先重新分配至少两倍于之前大小的内存空间，并用new_start指向这个空间的起始地址，再另new_finish等于new_start；然后进行拷贝赋值之前老地址start到position之间的元素到新地址new_start中，再将用new_finish指向赋值过来以后这些元素的后一个地址；再将new_finish到new_finish+n这段地址中，用n个x填充，再将new_finish指向new_finish+n这个地址；最后再将之前老的数据position到finish之间的元素拷贝复制到new_finsh之后，再用newf_finish指向拷贝复制过来以后最后一个元素的后一个地址。

const size_type old_size = size();
const size_type len = old_size + max(old_size, n);
iterator new_start = data_allocator::allocate(len);
iterator new_finish = new_start;
_STL_TRY {
    new_finish = uninitialized_copy(start, position, new_start);
    new_finish = uninitialized_fill_n(new_finish, n, x);
    new_finish = uninitialized_copy(position, finish, new_finish);
}

        最后，释放之前start到finish之间的空间，然后让start指向new_start指向的内存，finish指向new_finish指向的内存。

destroy(start, finish);//相当于类的析构
deallocate();//释放之前start到end_of_storage这段内存
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;