首页 > 其他 > 详细

stl源码剖析-序列式容器 之 vector

时间:2019-10-19 19:39:49      阅读:51      评论:0      收藏:0      [点我收藏+]

  vector的数据安排以及操作方式,与array(c++自身提供的序列式容器)非常相似。两者唯一的差别在于空间的运用的灵活性。array是静态空间,一旦配置了将不能随意更改其大小,若要更改需要重新配置一块新的空间,如何将元素从旧址中一一搬迁,再释放原来的系统。而vector是动态空间,随着元素的加入,它的内部机制会自行扩充空间已容纳新元素。(实际vector每次动态分配的空间大小是有限的,超过了这个临界值同样是要像array一样进行元素搬迁,下面将会进行详细介绍)vector 是最常用的 C++ 容器,其动态扩容的特性是普通数组无法具备的,大大增加了编程的灵活性。

vector迭代器

  vector维护的是一个连续线性空间,所以不论其元素型别为何,普通指针都可以作为vector的迭代器而满足所有必要条件,因为vector迭代器所需要的操作,如operator*、operator->、operater++、operater--、operator-、operator+、operator+=、operator-=,普通指针天生就具备。vecotr支持随机存取,而普通指针正有这样的能力,所以,vecotr提供的是Random Access Iterators。

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

 

vector数据结构

iterator start;//指向vector目前使用空间头,即vector.begin()

iterator finish;//指向vector目前使用空间尾,即vector.end()

iterator end_of_storage;//指向vector目前可用空间尾

  为了降低空间配置时的开销成本,vector每次配置的大小会比需求量更大,剩余的空间用于将来扩充的需要,这就是容量(capacity)的观念。也就是说,一个vector的容量永远大于或等于其大小,一大容量等于其大小,就是满载,下次再有元素新增,将要像array进行元素搬迁一样,另外开辟一个空间移动已有元素,另外开辟空间的大小一般情况下是现有空间大小的两倍。

  运用 start,finish,end_of_stroage三个迭代器,可以轻易地提供首尾标示、大小、容量、空容器判断...等等机能

template<class T, class Alloc = alloc>  
  class vector{
  ...
  public:
      iterator begin() {return start;}
      iterator end() {return finish;}
      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();}
      reference operator[](size_type n){return *(begin()+n);}
      
      reference front(){return *begin();}
      reference back(){return *(end()-1);}
  ...
  }

技术分享图片

 

 

vector的构造与内存管理

  以下是vector配置空间过程的部分代码:

//vector提供的许多constructor
vector() : start(0), finish(0), end_of_storage(0) {}
    vector(size_type n, const T& value) {
        fill_initialize(n, value);
    }
    vector(int n, const T& value) {
        fill_initialize(n, value);
    }
    vector(long n, const T& value) {
        fill_initialize(n, value);
    }
    explicit vector(size_type n) {
        fill_initialize(n, T());
    }
....
 //填充并予以初始化
void fill_initialize(size_type n, const T& value) {
        start = allocate_and_fill(n, value);
        finish = start + n;
        end_of_storage = finish;
    }
 ....
//配置而后填充
iterator allocate_and_fill(size_type n, const T& x) {
        iterator result = data_allocator::allocate(n);
        __STL_TRY 
        {
            uninitialized_fill_n(result, n, x);
            return result;
        }
        __STL_UNWIND(data_allocator::deallocate(result, n));
    }
//uninitialized_fill_n会根据第一参数的型别来决定算法使用fill_n()或者反复调用construct()来完成任务

   当我们以push_back()将新元素插入vector尾端时,该函数先检查是否还有备用空间,如果有就直接在备用空间上构造元素,并调整迭代器finish,使vector变大。不过没有备用空间,就扩充空间(重新配置、移动数据、释放原空间):

void push_back(const T& x) {
        if (finish != end_of_storage) {  //还有备用空间
            construct(finish, x);  //全局函数
            ++finish;
        } else  //无备用空间
            insert_aux(end(), x);  //成员函数,后续会分析
}
....
template <class T, class 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;
        //全局函数,从后面finish-1往前复制[position,finish-2]的值
        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;  //为当前空间两倍大小
        iterator new_start = data_allocator::allocate(len);
        iterator new_finish = new_start;
        __STL_TRY
        {
            //复制[start,position)复制到new_start,new_finish为new_start+(position-start)
            new_finish = uninitialized_copy(start, position, new_start);
            construct(new_finish, x); 
            ++new_finish; //调整水位
            //复制[position,finish)复制到new_finish
            new_finish = uninitialized_copy(position, finish, new_finish);
        }
        catch(...) {
            destroy(new_start, new_finish); 
            data_allocator::deallocate(new_start, len);
            throw;
        }
        destroy(begin(), end()); //调用旧空间元素的析构函数
        deallocate(); //释放旧空间
        start = new_start;
        finish = new_finish;
        end_of_storage = new_start + len;
 }
}

  所谓动态增加大小,并不是在原空间之后接续空间(因为无法包装原空间之后尚有可配置的空间),而是以原大小的两倍另外配置一块较大的空间,然后将原来内容拷贝过来,然后才开始在原内容之后构造新元素,并释放原空间。因此对vector的任何操作,一旦引起空间重新配置,指向原vector的所有迭代器就都失效了。

 

vector的元素操作:pop_back,erase,clear,insert

  pop_back():

void pop_back() {
        --finish;
        destroy(finish);    //finish->~T 这里仅仅是调用指针finish所指对象的析构函数,不能释放内存
    }

  erase():

iterator erase(iterator first, iterator last) {
        iterator i = copy(last, finish, first);  
        destroy(i, finish);    
        finish = finish - (last - first); 
        return first;
    }

iterator erase(iterator position) {
        
        if (position + 1 != end())
            copy(position + 1, finish, position);  //全局函数

        --finish;
        destroy(finish);
        return position;
    }

技术分享图片

 

 

  

  clear():

 void clear() { erase(begin(), end()); }

  insert():

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;
                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);
                //新增元素填入新空间
                new_finish = uninitialized_fill_n(new_finish, n, x);
                //旧vector插入点之后的元素复制到新空间
                new_finish = uninitialized_copy(position, finish, new_finish);
            }
            catch(...) {
                //如果发生异常,实现commit和rollback操作
                destroy(new_start, new_finish);
                data_allocator::deallocate(new_start, len);
                throw;
            }
            //以下清除并释放旧的vector
            destroy(start, finish);
            deallocate();
            //以下调整水位
            start = new_start;
            finish = new_finish;
            end_of_storage = new_start + len;
        }
    }
}

  插入完成后,新节点将位于哨兵迭代器所指节点的前方,这是stl对于插入操作的标准规范,下图展示来插入操作:

技术分享图片

 

 

技术分享图片

 

 技术分享图片

 

 

 

 

stl源码剖析-序列式容器 之 vector

原文:https://www.cnblogs.com/LEEYATWAH/p/11704647.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!