【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 代码摘要

	template
	class 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 的迭代器而满足所有条件，因为 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）

	template
	class 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 呢？
我们知道扩容操作的本质并不是从末尾追加空间，而是找一块合适的空间并将原内容拷贝过去，再释放原空间
 
 
不光是内容要变，我们迭代器的指向也要变，而我们设置  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