【C++】vector使用详解及重要部分底层实现

分手后的思念是犯贱 2024-04-22 22:17 47阅读 0赞

![09073f48e95f40c0a847eb128259d83a.gif][]

> 本篇文章会对vector的语法使用进行详解。同时，还会对重要难点部分的底层实现进行讲解。其中有vector的**迭代器失效**和**深拷贝**问题。希望本篇文章的内容会对你有所帮助。

> **目录**
> 
> 一、vector 简单概述
> 
> 1、1 C语言中数组的不便
> 
> 1、2 C++中的动态数组容器vector 
> 
> 二、vector的常用语法举例
> 
> 2、1 vector的声明和定义
> 
> 2、1 尾插 push\_back
> 
> 2、2 尾删 pop\_back
> 
> 2、3 设置容量大小 reserve
> 
> 2、4 赋值 =
> 
> 2、5 在pos位置插入
> 
> 2、6 任意位置删除
> 
> 2、7 访问vector中的元素
> 
> 2、8 数组中的头和尾元素front（）、back（）
> 
>  三、部分重要底层实现及常见问题
> 
> 3、1 拷贝构造的底层实现
> 
> 3、2 insert的底层实现及迭代器失效
> 
> 3、3 erase的底层实现及迭代器失效
> 
> 3、4 vector中深拷贝的问题
> 
> --------------------
> 
> **?♂️ 作者：@Ggggggtm ?♂️**
> 
> **? 专栏：C++ ?**
> 
> **? 标题：vector讲解?**
> 
>  **❣️ 寄语：与其忙着诉苦，不如低头赶路，奋路前行，终将遇到一番好风景 ❣️**
> 
> ![8fe6bd5fd71f4da287b110ee158d51af.png][]

## 一、vector 简单概述 ##

### 1、1 C语言中数组的不便 ###

> 在C语言中，我们所要存放一组类型相同的数据，我们可以选择数组。C语言中的**数组是静态**的，一旦声明后，其大小就是固定的，无法动态调整。这就导致使用起来并不方便。当然，我们也用**malloc、calloc来动态申请空间**。当我们不再使用此数组时，我们也要时刻**注意是否已经释放我们所动态开辟的空间**。

### 1、2 C++中的动态数组容器vector ###

> 针对C语言中静态数组的不便，C++中引出了动态数组容器vector，vector有以下几个不同和优点：
> 
> 1.  可以根据需要自动调整大小，可以动态地添加或删除元素。
> 2.  就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
> 3.  C++中的vector自动处理内存管理，无需手动指定大小或释放内存。
> 4.  C++中的vector提供了边界检查功能，能够确保在访问元素时不会发生越界错误。
> 5.  C++中的vector提供了丰富的函数和操作，如添加元素、删除元素、排序、查找等。这些功能能够更方便地操作和处理数组元素。

>  本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是 一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。

> 只有概念并不能很好的使用vector，我们接下来看一下vector语法的讲解。

## 二、vector的常用语法举例 ##

>     #include <vector>
>     #include <iostream>
>     using namespace std;
>     int main()
>     {
>     	vector<int> v;
>     	vector<int> v1(10);
>     	vector<int> v2(10, 1);
>     	vector<int> v3(v2);
>     
>     
>     	v.push_back(10);
>     	v.push_back(20);
>     
>     	v.pop_back();
>     
>     	v.reserve(10);
>     
>     	v = v1;
>     
>     	v.insert(v.begin() + 2, 3);
>     
>     	v.erase(v.begin() + 2);
>     
>     	int sz = v.size();
>     	for (int i = 0; i < sz; i++)
>     	{
>     		cout << v[i] << " ";
>     	}
>     	cout << endl;
>     
>     	vector<int>::iterator it = v.begin();
>     	while (it != v.end())
>     	{
>     		cout << *it << " ";
>     		it++;
>     	}
>     	cout << endl;
>     
>     	for (auto it : v)
>     	{
>     		cout << it << " ";
>     	}
>     	cout << endl;
>     
>     	v.clear();
>         
>         v.front();
>         v.back();
>     	return 0;
>     }
> 
> 我们就上面的例子展开对vector的用法进行详解。

### 2、1 vector的声明和定义 ###

> 当我们想用vector时，我们首先要引入头文件:**\#include<vector>**。当我们可展开命名空间std，也可选择不展开命名空间std。具体例子如下：
> 
>     #include <vector>
>     #include <iostream>
>     using namespace std;
>     
>     int main() 
>     {
>         //std::vector<int> v;
>     	vector<int> v;
>     	vector<int> v1(10);
>     	vector<int> v2(10, 1);
>     	vector<int> v3(v2);
>         return 0;
>     }
> 
> 注意，上述中的变量**v为空数组，空间大小为0**。v1是开辟了一个大小为**10个int的数组，这10个元素默认为0**。v2是开辟了一个大小为**10个int的数组，这10个元素初始化为1**。v3是用v2中的元素来进行初始化的，也就是v3中的元素与v2中的元素相同。我们可看如下结果：
> 
> ![b7602099e42846428f7f810e673026b6.png][]

### 2、1 尾插 push\_back ###

> 有了vector，我们想要往里添加元素，我们可使用push\_back进行尾部插入元素。具体例子如下：
> 
>     #include<iostream>
>     #include<vector>
>     using namespace std;
>     int main()
>     {
>     	vector<int> v;
>     	vector<int> v1(10);
>     	vector<int> v2(10, 1);
>     
>     
>     	v.push_back(10);
>     	v.push_back(20);
>     	v.push_back(30);
>         return 0;
>     }
> 
> 运行结果如下：
> 
> ![d3df9521aa8441e189bccf2ba8b6dd24.png][]
> 
> 我们发现，v数组不是空间大小为0吗，怎么还能插入元素呢？这个是因为vector是一个动态数组，**底层就是一个动态的顺序表**。**当空间容量不够时，会自动进行扩容**。

### 2、2 尾删 pop\_back ###

> pop\_back可对尾部元素进行删除。当然，尾删的前提是数组不为空。否则会程序会被终止。具体例子如下：‘
> 
>     #include<iostream>
>     #include<vector>
>     using namespace std;
>     int main()
>     {
>     	vector<int> v;
>     	//v.pop_back();
>     	vector<int> v1(10);
>     	vector<int> v2(10, 1);
>     
>     
>     	v.push_back(10);
>     	v.push_back(20);
>     	v.push_back(30);
>     
>     	v.pop_back();
>         return 0;
>     }
> 
> 我们先看看在空vector进行删除的结果：
> 
> ![7d72d4db07f04e06a794bb3b9b00e3a2.png][]
> 
> 我们再看看实际的尾删效果:
> 
> ![7a0473082ecd487eb415516a226b3673.png][]

### 2、3 设置容量大小 reserve ###

> 当我们知道要存储的元素个数是多少时，我们可直接通过reserve来设置vector的容量大小。有人就说了，vector空间不够了可以自己进行扩容，为啥还要用reserve来设定容量大小呢？注意，**扩容是有损耗的。频繁的扩容会大大的降低程序的运行效率**。我们来看reserve的实际效果。
> 
>     #include<iostream>
>     #include<vector>
>     using namespace std;
>     int main()
>     {
>     	vector<int> v;
>     
>     	v.push_back(10);
>     	v.push_back(20);
>     	v.push_back(30);
>     
>     	v.pop_back();
>     
>     	
>     	v.reserve(10);
>         return 0;
>     }
> 
> 运行结果如下：
> 
> ![876af5e4a0fe4f82b3257f83e0dc4d53.png][]
> 
> 我们之前看到尾删后的容量（capacity）大小为3，当我们reserve（）后，容量大小变为了10。size为当前vector中的实际有多少个元素。capacity为当前vector实际能够存储多少个元素。两者是不同的。

### 2、4 赋值 = ###

> 当然，我们也可直接对不同的vector进行赋值操作。具体例子如下：
> 
>     #include<iostream>
>     #include<vector>
>     using namespace std;
>     int main()
>     {
>     	vector<int> v;
>     	vector<int> v1(10);
>     
>     	v.push_back(10);
>     	v.push_back(20);
>     	v.push_back(30);
>     
>     	v.pop_back();
>     
>     	
>     	v.reserve(10);
>     
>     	
>     	v = v1;
>         return 0;
>     }
> 
> 运行结果如下：
> 
> ![0d82dda08f8b4ad2852845ac180ed80a.png][]
> 
> 赋值完后，v与v1完全相同。

### 2、5 在pos位置插入 ###

> 我们发现尾插并不能很好的满足我们对插入的实现。insert就可以选择位置进行插入。当然，我们插入的位置必须是合法的位置。否则程序就会终止。我们看如下例子：
> 
>     #include<iostream>
>     #include<vector>
>     using namespace std;
>     int main()
>     {
>     	vector<int> v;
>     	vector<int> v1(10);
>     
>     	v.push_back(10);
>     	v.push_back(20);
>     	v.push_back(30);
>     
>     	v.pop_back();
>     
>     	
>     	v.reserve(10);
>     
>     	
>     	v = v1;
>     
>     	
>     	v.insert(v.begin() + 2, 3);
>         return 0;
>     }
> 
> 运行结果如下:
> 
> ![cdbb8f77ddb54f32ade716dd2f65bb0d.png][]
> 
> 我们是在开始位置往后偏移两个元素的位置进行插入结果也正是如此。细心的同学也会发现，在插入的同时实现的扩容。 具体的扩容大小

### 2、6 任意位置删除 ###

> 尾删也并不能满足我们所需的删除功能。erase可进行任意位置删除。具体例子如下：
> 
>     #include<iostream>
>     #include<vector>
>     using namespace std;
>     int main()
>     {
>     	vector<int> v;
>     	vector<int> v1(10);
>     
>     	v.push_back(10);
>     	v.push_back(20);
>     	v.push_back(30);
>     
>     	v.pop_back();
>     
>     	
>     	v.reserve(10);
>     
>     	
>     	v = v1;
>     
>     	
>     	v.insert(v.begin() + 2, 3);
>     
>     	v.erase(v.begin() + 2);
>         return 0;
>     }
> 
> 运行结果如下：
> 
> ![0f0c02d05de14992a5ff60635fb3f4a4.png][]
> 
> 我们就是在之前所插入的位置进行了删除。

### 2、7 访问vector中的元素 ###

> 访问vector中的元素有两种：通过 \[\] + 下标索引 、迭代器。具体例子如下：
> 
>     #include<iostream>
>     #include<vector>
>     using namespace std;
>     int main()
>     {
>     	vector<int> v(10,2);
>         int sz = v.size();
>     	for (int i = 0; i < sz; i++)
>     	{
>     		cout << v[i] << " ";
>     	}
>     	cout << endl;
>     
>     	vector<int>::iterator it = v.begin();
>     	while (it != v.end())
>     	{
>     		cout << *it << " ";
>     		it++;
>     	}
>     	cout << endl;
>     
>     	for (auto it : v)
>     	{
>     		cout << it << " ";
>     	}
>     	cout << endl;
>         return 0;
>     }
> 
>  **size（）可返回vector中的元素个数**。运行结果如下：
> 
> ![32b405e456654298a03bab2f20952cfd.png][]
> 
> 都能够很好的打印出vector中的元素。

### 2、8 数组中的头和尾元素front（）、back（） ###

> front（）、back（）函数可返回数组中的第一个元素和最后一个元素。当然，我们也可通过下标直接访问。所以这两个函数也并不常用。

## 三、部分重要底层实现及常见问题 ##

> vector的底层是由三个指针是私有成员变量。来记录数组的不同位置、大小、容量。实际如下：
> 
>     template<class T>
>     
>     	class vector
>     	{
>     	public:
>     		typedef T* iterator;private:
>         private:
>     		iterator start;
>     		iterator finish;
>     		iterator end_of_storage;
>     	};
> 
> 注意，底层使用类模板来试实现的。很好的解决了vector可以存储不同类型的数据问题。

### 3、1 拷贝构造的底层实现 ###

> 拷贝构造底层实现的方式有很多，但思路是大同小异的，具体如下：
> 
>     vector(const vector<T>& v)
>     			:start(nullptr)
>     			,finish(nullptr)
>     			,end_of_storage(nullptr)
>     		{
>     			iterator tmp = new T[v.size()];
>     			//memcpy(tmp, v.start, sizeof(T) * v.size());
>     			//T为自定义类型时，自定义类型自动调用赋值重载，完成深拷贝
>     			for (size_t i = 0; i < v.size(); i++)
>     			{
>     				tmp[i] = v.start[i];
>     			}
>     
>     			start = tmp;
>     			finish = start + v.size();
>     			end_of_storage = start + v.size();
>     		}
>     
>     		//vector(const vector<T>& v)
>     		//	:start(nullptr)
>     		//	, finish(nullptr)
>     		//	, end_of_storage(nullptr)
>     		//{
>     		//	reserve(v.size());
>     		//	for (auto it : v)
>     		//	{
>     		//		push_back(it);
>     		//	}
>     		//}
>     
>     		template <class InputIterator>
>     		vector(InputIterator first, InputIterator last)
>     				:start(nullptr)
>     				, finish(nullptr)
>     				, end_of_storage(nullptr)
>     		{
>     			while (first != last)
>     			{
>     				push_back(*first);
>     				first++;
>     			}
>     		}
>     
>     		void swap(vector<T>& v)
>     		{
>     			std::swap(start, v.start);
>     			std::swap(finish, v.finish);
>     			std::swap(end_of_storage, v.end_of_storage);
>     		}
>     		vector(const vector<T>& v)
>     			:start(nullptr)
>     			, finish(nullptr)
>     			, end_of_storage(nullptr)
>     		{
>     			vector<T> tmp(v.begin(), v.end());
>     			swap(tmp);
>     		}

### 3、2 insert的底层实现及迭代器失效 ###

> 在实现insert时，我们需要注意的是**扩容后，释放掉原来的空间，原来的pos就变成了野指针**！需要记录相对位置，更新pos。具体代码如下：
> 
>     iterator insert(iterator pos,const T& x)
>     		{
>     			assert(pos >= start);
>     			assert(pos <= finish);
>     			if (start == end_of_storage)
>     			{
>     				//注意，扩容后原来的pos就变为野指针，需要记录相对位置更新pos
>     				size_t len = pos - start;
>     				reserve(capacity() == 0 ? 4 : capacity() * 2);
>     				pos = start + len;
>     			}
>     
>     			iterator end = finish - 1;
>     			while (end >= pos)
>     			{
>     				*(end+1) = *end;
>     				end--;
>     			}
>     			*pos = x;
>     			finish++;
>     
>     			return pos;
>     		}

>     void test()
>     	{
>     		vector<int> v;
>     		v.push_back(1);
>     		v.push_back(2);
>     		v.push_back(3);
>     		v.push_back(4);
>     		//v.push_back(5);
>     
>     		for (auto e : v)
>     		{
>     			cout << e << " ";
>     		}
>     		cout << endl;
>     
>     		vector<int>::iterator p = find(v.begin(), v.end(), 3);
>     		if (p != v.end())
>     		{
>     			// 在p位置插入数据以后，不要访问p，因为p可能失效了。
>     			v.insert(p, 30);
>     
>     			//cout << *p << endl;
>     			//v.insert(p, 40);
>     		}
>     
>     		for (auto e : v)
>     		{
>     			cout << e << " ";
>     		}
>     		cout << endl;
>     
>     		v.insert(v.begin(), 1);
>     	}
> 
> 我们在用迭代器时，可能会出现很多意想不到的错误。上述代码中的变量 p 为例子，我们能**一直在变量 p 位置插入数据吗？答案是不能！！！**为什么呢？因为当我们扩容后，原指针 p 所指向的空间就会被释放，p 就变成了野指针！所以，在p位置插入数据以后，不要访问p，因为p可能失效了。这就是所谓的**迭代器失效**。

### 3、3 erase的底层实现及迭代器失效 ###

> erase的底层实现较为简单，直接更改finish指针即可。我们直接看代码：
> 
>     iterator erase(iterator pos)
>     		{
>     			assert(pos >= start);
>     			assert(pos < finish);
>     
>     			iterator cur = pos + 1;
>     			while (cur < finish)
>     			{
>     				*(cur - 1) = *cur;
>     				cur++;
>     			}
>     
>     			finish--;
>     			return pos;
>     		}

> erase并没有扩容，为啥会出现迭代器失效呢？我们先看个例子：
> 
>     void test_vector4()
>     {
>     	// 正常运行
>     	vector<int> v;
>     	v.push_back(1);
>     	v.push_back(2);
>     	v.push_back(3);
>     	v.push_back(4);
>     	v.push_back(5);
>     
>     	// 要求删除所有的偶数
>     	auto it = v.begin();
>     	while (it != v.end())
>     	{
>     		if (*it % 2 == 0)
>     		{
>     			v.erase(it);
>     		}
>     
>     		++it;
>     	}
>     
>     	for (auto e : v)
>     	{
>     		cout << e << " ";
>     	}
>     	cout << endl;
>     }
>     
>     void test_vector4()
>     {
>     	// 崩溃
>     	vector<int> v;
>     	v.push_back(1);
>     	v.push_back(2);
>     	v.push_back(3);
>     	v.push_back(4);
>     
>     	// 要求删除所有的偶数
>     	auto it = v.begin();
>     	while (it != v.end())
>     	{
>     		if (*it % 2 == 0)
>     		{
>     			v.erase(it);
>     		}
>     		++it;
>     	}
>     
>     	for (auto e : v)
>     	{
>     		cout << e << " ";
>     	}
>     	cout << endl;
>     }
>     
>     void test_vector4()
>     {
>     	// 结果不对
>     	vector<int> v;
>     	v.push_back(1);
>     	v.push_back(2);
>     	v.push_back(4);
>     	v.push_back(3);
>     	v.push_back(4);
>     	v.push_back(5);
>     
>     	// 要求删除所有的偶数
>     	auto it = v.begin();
>     	while (it != v.end())
>     	{
>     		if (*it % 2 == 0)
>     		{
>     			v.erase(it);
>     		}
>     			
>     		++it;
>     	}
>     
>     	for (auto e : v)
>     	{
>     		cout << e << " ";
>     	}
>     	cout << endl;
>     }
> 
> 上述准确来说，第一个运行结果正确的为侥幸。为什么呢？注意，erase删除后，后面的元素就会向前移动。并且会返回当前所指向的位置，所以不用再 it++ 了。正确的代码如下：
> 
>     //正确的方式
>     	void test_vector4()
>     	{
>     		vector<int> v;
>     		v.push_back(1);
>     		v.push_back(2);
>     		v.push_back(4);
>     		v.push_back(3);
>     		v.push_back(4);
>     		v.push_back(5);
>     
>     		// 要求删除所有的偶数
>     		auto it = v.begin();
>     		while (it != v.end())
>     		{
>     			if (*it % 2 == 0)
>     			{
>     				it = v.erase(it);
>     			}
>     			else
>     			{
>     				++it;
>     
>     			}
>     		}
>     
>     		for (auto e : v)
>     		{
>     			cout << e << " ";
>     		}
>     		cout << endl;
>     	}
> 
> 总的来说，我们进行插入和删除后，就尽可能的不要再次去访问原指针了。很有可能已经失效了，会出现意想不到的效果。

### 3、4 vector中深拷贝的问题 ###

> vector中，**不管是赋值重载还是拷贝构造，都是需要进行深拷贝的**。但是**vector中元素也必须进行深拷贝**。为什么呢？当vector中的元素为int、char等内置类型无所谓，如果是自定义类型，那问题就出来了。
> 
> 当vector中的元素为自定义类型，对元素进行先拷贝，元素还是指向的同一块空间。
> 
> vector中存储的为string：
> 
> ![c3b0cc12559c43bab01e47adecce8285.png][]
> 
> \_str中存储的是string的地址，如果使用浅拷贝，在插入扩容时，就把原来的地址拷贝过来。
> 
> ![9a939cbde31a45f4848f4eb639f7a65a.png][]
> 
> 再释放掉原来的地址，就会导致新拷贝的地址变成野指针。具体如下：
> 
> ![5ce19b4a107f452db234908f475f6f36.png][]

[09073f48e95f40c0a847eb128259d83a.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/9bf82fa13e52424898d3ba873e7ce6fb.gif
[8fe6bd5fd71f4da287b110ee158d51af.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/cfc4c881c033448b9595a998644a072a.png
[b7602099e42846428f7f810e673026b6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/4a7036a1f034499997e41812c2ff228a.png
[d3df9521aa8441e189bccf2ba8b6dd24.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/20e681ae84a841ad8e5ac10f39e10921.png
[7d72d4db07f04e06a794bb3b9b00e3a2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/14267e43c54d4b86bf0d5484150abc6e.png
[7a0473082ecd487eb415516a226b3673.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/f0450ad64c5344ba892af3c91e3e4f21.png
[876af5e4a0fe4f82b3257f83e0dc4d53.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/0d72b994a71d4e9a98a89ab5822d8f5a.png
[0d82dda08f8b4ad2852845ac180ed80a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/2ff8953528f642b0b4e3d189dbefb855.png
[cdbb8f77ddb54f32ade716dd2f65bb0d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/b8b885de5abe4d1f8275cab39a49e4a4.png
[0f0c02d05de14992a5ff60635fb3f4a4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/e8f084bfb46f49688dced0f4fee67abd.png
[32b405e456654298a03bab2f20952cfd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/c771c7105e414992b0cf153b4ef123d1.png
[c3b0cc12559c43bab01e47adecce8285.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/735b246ca06344fdb5a5b8354fb8a5c4.png
[9a939cbde31a45f4848f4eb639f7a65a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/d5474348feda4aaa84d8b20760d4b5b7.png
[5ce19b4a107f452db234908f475f6f36.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/c58fad8227fb4906b1c8d1bf1b6e5dc6.png