阅读 77

【决战西二旗】|理解STL vector原理

Vector概述

STL中的Vector是最为常用的顺序容器之一,与C/C++中的数组Array很相似,最重要的区别在于对连续内存空间运用的灵活性。

数组真叫人为难

我们在使用数组Array时要指定数组的大小,而后由系统来分配连续的内存空间,Array是静态空间必须指定大小且指定之后自动无法扩缩容,因此为了避免元素装不下,一般都把数组设置的比预期要大,但是往往导致空间的浪费。

另外往往很多时候需装载元素的数量无法预期,这样设置怎样的大小就取决于使用者了。如果最初数组设计比较小,那么就面临着开辟新的更大空间、将旧空间元素复制到新空间、释放旧空间三个大步骤,这一切都是需要使用者自己来维护实现的。

使用数组太大浪费空间、太小浪费效率,真的很希望有个助手帮我们做了这些事情,专业的人做专业的事情,让我们只关心业务逻辑即可,那该多好!

它来了,踏着七彩祥云

就这样盼望着 盼望着 东风来了 春天的脚步近了,不不, vector的脚步近了….

vector底层与Array一样都是连续的内存空间,区别在于vector的空间是动态的,随着更多元素的加入可以自动实现空间扩展,并且vector针对这种扩展做了优化,并不是one by one的扩展,那样实在是低效,而是按照某种倍率来扩展,这样就有效了减少因为扩容带来的复制效率降低问题。

简单来说就是当需要放置1个元素时,vector空间已满,此时vector并不会只向系统申请1个元素的空间,而是按照目前已占用的空间的倍率来申请。

假如原来占用A字节,那么再次申请时可能是2A字节,由于此时向尾部地址扩展不一定有连续未分配的内存,大多时候还是会涉及开辟新的更大空间、将旧空间元素复制到新空间、释放旧空间三个大步骤。

所以和数组相比底层的操作都是一样的,不要把Vector神话,都是普通的结构只不过被封装了一层而已。

从本质上看,vector就是在普通Array和使用者中间加了一层,从而把使用者从对数组的直接管理权接手过来,让使用者有个管家一样,在毫无影响使用的前提下更加省心和高效。

透过现象看本质

  • 空间分配

看中对vector的定义(节选部分成员变量)

//alloc是SGI STL的空间配置器
template <class T,class Alloc=alloc>
class vector
{
public:
    typedef T   value_type;
    typedef value_type*  pointer;
    typedef value_type*  iterator;
    typedef value_type&  reference;
    typedef size_t   size_type;
    typedef ptrdiff_t   difference_type;

protected:
    //simple_alloc是SGI STL的空间配置器
    typedef simple_alloc<value_type,Alloc> data_allocator;
    //表示目前使用空间的头
    iterator start; 
    //表示目前使用空间的尾
    iterator finish; 
    //表示目前可用空间的尾
    iterator end_of_storage;
}复制代码

从定义看vector 是一种前闭后开的容器,在vector里头有一些变量记录着一些信息,分别是三个迭代器:

  1. start:表示目前使用空间的头
  2. finish:目前使用空间的尾
  3. end_of_storage:目前可用空间的尾

vector的空间示意图:

vector中有三个和容量空间相关的成员函数:size、capacity、empty。

其中size代表已存储的元素数量,capacity表示可以容纳的最大元素数量,empty判断是否无元素存储,这些判断也都是依据迭代器来实现的,定义如下:

size_type size() const {return size_type(end()-begin());}
size_type capacity() const{return size_type(end_of_storage-begin());}
bool empty() const{return begin()==end();}复制代码

  • 迭代器

vector由于在底层和数组没有区别,都是地址连续的内存空间,因此普通指针具备vector迭代器的重要功能,诸如:
*、->、++、--、+、-、+=、-=
这些迭代器操作,都可以由指针来实现。

//迭代器举例
iterator begin()
{
    return start;
}
iterator end()
{
    return finish;
}

reference front()
{
    return *begin();
}
reference back()
{
    return *(end() - 1);
}复制代码

  • push_back

在使用push_back()将元素插入vector尾端时的基本流程:

  1. 仍有空间 直接在剩余空间上构造元素,并调整迭代器finish指向
  2. 已无空间 扩充空间(重新分配、移动数据、释放旧空间)
  3. 扩充空间时调用另外一个成员函数insert_aux来实现,其中我们可以看到更多的细节。

代码定义如下:

void push_back(const T& x)//添加元素
{
    //是否超出最大可容纳空间
    if(finish !=end_of_storage){
        /*全局函数,construct()接收一个指针p和一个初值value,
        该函数的用途就是将
        初值value设定到指针锁指的空间上。
        */
        construct(finish,x);
        ++finish;
    }
    else{
        insert_aux(end(),x);  //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 x_copy = x;
        copy_backward(position, finish - 2, finish -1);
        *position = x_copy;
    }
    else {  //已无备用空间
        const size_type old_size = size();
        const size_type len = old_size != 0 ? 2 * old_size : 1;
        //以上配置原则:如果原大小为0,则配置1(个元素大小);
        //如果原大小不为0, 则配置原大小的两倍,
        //前半段用来放置原数据,后半段准备用来放置新数据

        iterator new_start = data_allocator::allocate(len); //实际配置
        iterator new_finish = new_start;
        try {
            //将原vector的内容拷贝到新vector
            new_finish = uninitialized_copy(start, position, new_start);
            //将新元素设定初值x
            construct(new_finish, x);
            //调整水位
            ++new_finish;
            //将安插点的原内容也拷贝进来(提示:本函数也可能被insert(p,x)调用)
            new_finish = uninitialized_copy(position, finish, new_finish);
        }
        catch(...) {
            //"commit or rollback" semantics
            destroy(new_start, new_finish);
            data_allocator::deallocate(new_start, len);
            throw;
        }

        //析构并释放原vector
        destroy(begin(), end());
        deallocate();

        //调整迭代器,指向新vector
        start = new_start;
        finish = new_finish;
        end_of_storage = new_start + len;
    }
}复制代码

  • insert

insert成员函数也是实现元素添加的主要函数,因此也涉及了与push_back类似的扩容过程,但是比push_back更复杂一些,在插入元素时需要根据插入点、备用空间大小、待插入元素数量等角度进行分类对待,详细过程看下代码定义:

//从position开始,插入n个元素,元素初值为x
template <class T, class Alloc>
void vector<T, Alloc>::insert(iterator position, size_type n, const T& x)
{
    if ( n != 0){   //当n!=0才进行以下所有操作
        if(size_type(end_of_storage - finish) >= n) {
            //备用空间大于等于“新增元素个数”
            T x_copy = x;
            //以下计算插入点之后的现有元素个数
            const size_type elems_after = finish - position;
            iterator old_finish = finish;
            if (elems_after > n) {
                //“插入点之后的现有元素个数”大于“新增元素个数”
                uninitialized_copy(finish - n, finish, finish);
                finish += n;    //将vector尾端标记后移
                copy_backward(position, old_finish - n, old_finish);    //逆向拷贝
                fill(position, position + n, x_copy);
            }
            else {
                //“插入点之后的现有元素个数”小于等于“新增元素个数”
                uninitialized_fill_n(finish, n - elems_after, x_copy);
                finish += n-elems_after;
                uninitialized_copy(position, old_finish, finish);
                finish += elems_after;
                fill(position, old_finish, x_copy);
            }
        }
        else {
            //备用空间小于“新增元素个数”(那就必须配置额外内存)
            //首先决定新长度:旧长度的两倍,或旧长度+新增元素个数
            const size_type old_size = size();
            const size_type len = old_size + max(old_size, n);
            //以下配置新的vector空间
            iterator new_start = data_allocator::allocate(len);
            iterator new_finish = new_start;
            __STL_TRY {
                //以下首先将旧vector的插入点之前的元素复制到新空间
                new_finish = uninitialized_copy(start, position, new_start);
                //以下再将新增元素(初值皆为n)填入新空间
                new_finish = uninitialized_fill_n(new_finish, n, x);
                //以下再将旧vector的插入点之后的元素复制到新空间
                new_finish = uninitialized_copy(position, finish, new_finish);
            }

        #ifdef __STL_USE_EXCEPTIONS
            catch(...) {
                //如有异常发生,实现”commit or rollback"semantics
                destroy(new_start, new_finish);
                data_allocator::deallocate(new_start, len);
                throw;
            }
        #endif /* __STL_USE_EXCEPTIONS */
        //以下清楚并释放旧的vector
        destroy(start, finish);
        deallocate();
        //以下调整水位标记
        start = new_start;
        finish = new_finish;
        end_of_storage = new_start + len;
        }
    }
}复制代码

插入点、备用空间大小、待插入元素数量等角度进行分类:

1-1 插入点之后元素个数大于新增元素个数:

A. 将finish之前的n个元素移到finish之后
B. finish变更为finish + n得到newfinish
C. 将position之后到oldfinish - n之间的元素后移到oldfinish位置
D. 从position开始填充n个x

1-2 插入点之后元素小于新增元素个数

A. 将差值补到finish之后
B. finish变更为finish + n - elems_after得到newfinish
C. 将position到oldfinish的元素拷贝到newfinish之后
D. 在position到oldfinish之间插入x

                                摘自 stl源码剖析
                               摘自 stl源码剖析

2. 备用空间小于新增元素个数

A. 申请空间,old_size + max(old_size, n)
B. 复制填充:
c. 将原vector插入点之前的元素拷贝到新空间
D. 将新增元素填入新空间
E. 将原vector插入点之后的元素拷贝到新空间

                                                  摘自 stl源码剖析

这个过程还是比较有意思的,其中涉及到了几个泛型拷贝:

uninitialized_copy和copy_backward等,可以再自己细致地画一下图理解这个过程,在此不再赘述。

参考资料


关注下面的标签,发现更多相似文章
评论