STL源码剖析读书笔记之vector

STL源码剖析读书笔记之vector

1.vector概述

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

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

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

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

2.关于vector的定义

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

1 vector<int> v1;
2 vector<sting> v2;

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

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

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

 1 template <class T,class Alloc=alloc>
 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 <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main(int argc, char* argv[])
 6 {
 7     std::vector<int> v1;
 8     
 9     cout<<"v1.size()="<<v1.size()<<"   "<<"v1.capacity()="<<v1.capacity()<<endl;
10     v1.push_back(1);
11     cout<<"v1.size()="<<v1.size()<<"   "<<"v1.capacity()="<<v1.capacity()<<endl;
12     v1.push_back(2);
13     cout<<"v1.size()="<<v1.size()<<"   "<<"v1.capacity()="<<v1.capacity()<<endl;
14     v1.push_back(3);
15     cout<<"v1.size()="<<v1.size()<<"   "<<"v1.capacity()="<<v1.capacity()<<endl;
16     v1.push_back(4);
17     cout<<"v1.size()="<<v1.size()<<"   "<<"v1.capacity()="<<v1.capacity()<<endl;
18     v1.push_back(5);
19     cout<<"v1.size()="<<v1.size()<<"   "<<"v1.capacity()="<<v1.capacity()<<endl;
20     return 0;
21 }

截图如下:

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

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

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

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

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