STL源码剖析读书笔记之vector

1.vector概述

vector是一种序列式容器,我的理解是vector就像数组。但是数组有一个很大的问题就是当我们分配

一个一定大小的数组的时候,起初也许我们不会觉得数组容量太小不合需求，但是随着数据量的增加，

数组尺寸大小不再满足需求,此时我们需要手动的去扩展其大小。然而vector就帮我们完全实现了一个可

自适应增长的数组功能。那么这样看来vector其实也就是一种可自适应增长的动态数组的类的实现。

 

2.关于vector的定义

其实用过vector的人都知道 vector的定义大都像这个样子:

1 vector
     
       v1;2 vector
      
        v2;
      
     

很显然vector是一种与类型无关的类模板，支持各种类型的vector，这也很好的体现了C++的泛型思想，正

是这种类型无关性，使得STL在各种平台上广为使用。

 

这里我只是贴出STL源码剖析书中一小部分vector定义

1 template 
     
       2 class vector 3 { 4 public: 5    typedef   T     value_type; 6    typedef valuetype* pointer; 7    typedef valuetype* iterator;   8    typedef valuetype& reference; 9    typedef size_t    size_type;10 ......11 protected:12      iterator start;13      iterator finish;14      iterator end_of_storage;15 ....16 pubic:17      iterator begin{
   return start;}18      iterator end(){
   return finish;}19      size_type size() const {
   return size_type(end()-begin());}20      size_type capacity() const {
   return size_type(end_of_storage-begin());}21      reference front {
   return *begin()}22  }
     

上面有几个关键点:

vector维护了三个迭代器:start,finish和end_of_storage由typedef valuetype* iterator可知迭代器说白

了就是指针。那么vector维护的三个迭代器(指针)的意思是什么呢。start指向vector的第一个元素。finish

指向vector已经使用的空间的最后一个元素的下一个元素。end_of_storage指向vector总共可用空间的最后

一个元素的下一个元素所以操作vector与操作指针完全类似，只是在vector中把这些操作封装成相应的方法

直接供读者使用罢了。

 

3.vector内存分配原理

不是之前我们说vector是一种自增长的动态数组吗？那么其子增长的原理是什么。

其实很简单:

1.当vector为空时,我们插入一个元素到vector中,这时候vector将内存容量变为1,然后将新的元素插入其中

2.当vector容量为1的时候,此时vector中刚好有一个元素,若要插入一个2,这时候将重新new一个内存为2的新空

间，将之前内存中的1拷贝到新内存并释放1旧内存，同时将新的元素2插入其中

3.重复步骤2，只要就内存容量已满就重新分配新内存，新内存的大小是旧内存的二倍，再讲旧内存中的数据赋

值到新内存,同时释放新内存。同时插入新元素在新的内存空间。

 

我们可以用下面的程序验证这一点:

1 #include 
     
       2 #include 
      
        3 using namespace std; 4  5 int main(int argc, char* argv[]) 6 { 7     std::vector
       
         v1; 8      9     cout<<"v1.size()="<
        
         <<"   "<<"v1.capacity()="<
         
          <
         
        
       
      
     

截图如下:

 

此外，有几个问题需要注意:

1.为什么vector容量满了之后要重新开辟新的内存,因为vector要求连续的内存空间

2.如果重新开启新内存太频繁应该会造成较大的程序开销,怎么办.我们可以一开给reserve一个大的capacity.

3.重新开启新内存是否会造成原来的迭代器失效 ?是的,所以我们最好知道何时会开辟新的capacity，进而防止这种迭代器失效。

4.对于vector删除或者插入造成的迭代器失效已经在之前的博文中有介绍。