【STL简单源码剖析】vector的实现

收灯庭院迟迟月

落索秋千翦翦风

---

目录

 vector 简单概述

vector 代码摘要

vector 的迭代器

vector 成员变量

vector 构造析构

获取当前元素个数  

获取当前容器容量 

operator[]的运算符重载

vector 空间预留

push_back() 的实现

迭代器失效的简单讲解 

pop_back() 的实现

 insert() 的实现

 erase() 的实现

vector 拷贝构造

vector 赋值构造

vector 迭代器构造

vector 字符构造 

vector 链式构造 

契子✨

---

 vector 简单概述

vector 的資料安排以及操作方式，与 array 非常像似。兩者的唯一差別在於空間的運用彈性

---

array 是靜態空間，一旦配置了就不能改變；要換個大（或小） 一點的房子，可以，一切細瑣得由客端自己來：首先配置一塊新空間，然後將元素從舊址一一搬往新址，然後再把原來的空間釋還給系統

---

vector 是動態空間， 隨著元素的加入，它的內部機制會自行擴充空間以容納新元素。因此，vector 的運用對於記憶體的樽節與運用彈性有很大的幫助，我們再也不必因為害怕空間不足而一開始就要求一個大塊頭 array 了，我們可以安心使用 vector，吃多少用多少

我们不仅要会用 vector 的接口使用，还需要了解底层的代码逻辑，学习更新优秀的代码思维 ~

本篇文件将会带大家学习 vector 的简单实现，提前说明一下并不会涉及内存池的相关操作 ~

---

vector 代码摘要

templateclass vector{public:typedef T* iterator;typedef const T* const_iterator;//迭代器iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}//构造vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}//析构~vector(){if (_start){delete[] _start;_start = _finish = _end_of_storage;}}size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}private:iterator _start;iterator _finish;iterator _end_of_storage;};

vector 的迭代器

vector 的底层是一个连续性的空间，所以不管其元素类型如何

其原生指针都可以作为 vector 的迭代器而满足所有条件，因为 vector 迭代器所需要的操作：

operator* operator-> operator++ operator-- operator+ operator- operator+= operator-=

原生指针天生就具备，所以 vector 支持随时存取，而原生指针正有着这样的能力

简单来说就像我们之前实现 string 库一样，我们可以使用模板来实现原生指针

typedef T* iterator;typedef const T* const_iterator;

就是以上的代码，不管是怎样的类型我们的迭代器都可以使用 ~

vector 成员变量

vector 采用的结构非常简单：线性且连续的空间，它以两个迭代器 start 和 finish 分别指向配置得来的连续空间中目前已被使用的范围（size），并以迭代器 end_of_storage 指向连续空间的末尾（capacity）

templateclass vector{public:typedef T* iterator;typedef const T* const_iterator;    // ... private:iterator _start;            //表示目前使用空间的头iterator _finish;           //表示目前使用空间的尾iterator _end_of_storage;   //表示目前可用空间的尾};

为了降低空间配置时的速度成本，vector 实际配置的大小可能比客端需求量更大一些，以备将来可能的扩充。这便是容量（capacity）的概念。换一句话说一个 vector 的容量永远大于或等于其大小。一旦容量等于大小，便是满载，下次再有新增元素，整个 vector 就得另觅居所。 使用 start finish end_of_storage 三个迭代器，便可轻易提供首尾位置、 大小、容量、空容器判断、运算符[ ] 的使用、最前端元素值、最后端元素值… 等功能

 

vector 构造析构

构造

vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}

析构

                ~vector(){if (_start){delete[] _start;_start = _finish = _end_of_storage;}}

 

获取当前元素个数  

这里迭代器指向的空间的地址，所以我们用 元素末尾的迭代器 - 元素起始的迭代器 会得到相差的字节数，我们将其转化为整型就是当前元素个数了

size() 成员函数加个 const，这样 const 和非 const 对象都就可以调用了

size_t size() const{return _finish - _start;}

 

获取当前容器容量 

 

size_t capacity() const{return _end_of_storage - _start;}

operator[]的运算符重载

T& operator[](size_t pos) {assert(pos   
vector 空间预留
 
void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];size_t lod_size = size();if (_start){for (int i = 0; i  
我们知道扩容操作的本质并不是从末尾追加空间，而是找一块合适的空间并将原内容拷贝过去，再释放原空间
  
不光是内容要变，我们迭代器的指向也要变，而我们设置  lod_size 正是为了确立 _finish 的指向
 
表明 _finish 在原空间的第几号位置，在新空间同样如此
  
push_back() 的实现
   
push_back() 就是我们常见的尾插接口，当我们以 push_back() 将新元素插入到 vector 尾端，应该先检查是否还有足够的空间？如果有就直接在足够空间上建立元素，并调整迭代器_finish ，使 vector 变大。如果没有足够空间了，就扩充空间
  
（重新配置、搬移资料、释放原空间）
  
void push_back(const T& x){if (size() == capacity()){size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);}*_finish = x;++_finish;}
 
 我们来浅浅测试一下：
 
void Test_vector(){vector str;str.push_back(1);str.push_back(2);str.push_back(3);str.push_back(4);str.push_back(5);for (int i = 0; i