数组？NO 系Vector啊！

╰半橙微兮° 2024-04-24 23:19 3阅读 0赞

#### 文章目录 ####

*  前言
 *  一、vector的介绍
 *  二、vector的使用
 *   *  2.1 vector求容量的用法
     *  2.2 vector的增删查改用法
     *   *  2.2.1 尾插
         *  2.2.2 尾删
         *  2.2.3 头插
         *  2.2.4 任意位置删除
     *  2.3 vector的iterator是什么以及失效问题
 *  三、vector的模拟实现
 *   *  3.1 成员变量
     *  3.2 成员函数
     *   *  3.2.1 构造函数
         *  3.2.2 拷贝构造
         *  3.2.3 析构函数
         *  3.2.4 operator=
         *  3.2.5 size
         *  3.2.6 capacity
         *  3.2.7 迭代器相关
         *  3.2.8 reserve
         *  3.2.9 resize
         *  3.2.10 operator\[ \]
         *  3.2.11 insert
         *  3.2.12 erase
         *  3.2.13 pop\_back
 *  总结

--------------------

## 前言 ##

哈喽大家好，这里是夏目学长的C++学习笔记，本次主要讲解一下C++的`STL`当中的`vector`  
如果大家正在学习vector或者需要对`STL`更加精进的同学，那么本篇博客非常适合你的学习，因为这里夏目将会不仅仅会写vector的各种功能和还会手搓`vector`的各种基本功能，帮助大家的学习。

--------------------

## 一、vector的介绍 ##

首先如果要学习STL的话肯定要去下面这个网站去读取第一手文档的，这是我们之后学习很重要的手段。

点击这里前去网站：[C++学习网站][C]

![在这里插入图片描述][c0e2524b3916460cbe10a37a4eee47bb.png]

**这里就需要我们去翻译文本来进行学习，这里节约大家的时间，我就直接归纳总结了。**

1.  vector是表示**可变大小数组的序列容器。**
2.  就像数组一样，vector也采用的**连续存储空间来存储元素**。也就是意味着可以**采用下标对vector的元素  
    进行访问，和数组一样高效。** 但是又不像数组，**它的大小是可以动态改变的，而且它的大小会被容器自  
    动处理。**
3.  本质讲，vector使用 **动态分配数组来存储它的元素。** 当新元素插入时候，这个数组需要被重新分配大小  
    为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是  
    一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大  
    小。
4.  vector分配空间策略：**vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存  
    储空间更大**。 不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是  
    对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
5.  因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式**动态增  
    长。**
6.  与其它动态序列容器相比（deque, list and forward\_list）， vector在访问元素的时候更加高效，在末  
    尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward\_list  
    统一的迭代器和引用更好.

**这里我要给大家挖一个坑，因为动态增长这里Linux环境和VS环境的增长倍数是不一样的。这个比较细节，曾经出过面试题。**

## 二、vector的使用 ##

我相信，你读取了上边六条vector的介绍肯定对于vector的了解肯定还是不是很深入，**所以我打算从上层应用的角度讲起**，然后**先学会使用vector，然后再去讲解vector的底层**，也就是手挫vector的各种功能写成代码的形式。

所以下面一起聊聊vector的使用，**讲到vector其实可以近似理解它就是强化版本的数组，但是数组是静态的，而vector是动态的，vector可以动态增长，增长的倍数在Linux下是标准的2倍，在VS环境下是1.5倍（后面专门验证）**，数组和vector都可以通过下标的方法进行索引访问，并且他们分配的物理或者逻辑空间是连续的。

1.  capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。  
    这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义  
    的。vs是PJ版本STL，g++是SGI版本STL。
2.  reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问  
    题。
3.  resize在开空间的同时还会进行初始化，影响size。

说了这么多的vector和数组的对比，那既然学习vector了，那么vector肯定要比数组要厉害，所以厉害在哪里？所以，就引出了vector的功能，**增删查改**。

这里举出vector 类型的例子帮助大家去理解。

### 2.1 vector求容量的用法 ###

![在这里插入图片描述][51a3f999e7154056af991883e797bfc4.png]  
这些都是vector的求容量的用法，这里给出代码，看到代码基本就会使用，我也会添加注释讲解。

#include<iostream>
    #include<vector>
    
    using namespace std;
    int main()
    {
        
    //	test_vector1();
    	vector<int> v;
    	cout << v.size() << endl;
    	cout << v.max_size() << endl;
    	cout << v.capacity() << endl; 
    	return 0;
    }

![在这里插入图片描述][729a7d3f493b40638c2ae1c4d491aaa9.png]  
**size顾名思义就是求vector的已经添加了多少个元素了，capacity就是求vector的总容量是多少**，max\_size()说白了就是纯纯没用的库函数，所以不学也罢。

### 2.2 vector的增删查改用法 ###

#### 2.2.1 尾插 ####

vector的尾插，查阅文档就是`std::vector::push_back(const T& x);`

![在这里插入图片描述][b57b9deaee6f4be6b7b0313087c503fe.png]  
顾名思义就是在vector容器里面的末尾插入一个数据。  
代码例子：

#include<iostream>
    #include<vector>
    
    using namespace std;
    
    void test_vector1()
    {
        
    	vector<int> v;
    	v.push_back(1);
    	v.push_back(2);
    	for(int i = 0 ; i < 2 ; ++ i)
    		cout << v[i] << " ";
    	cout << endl;
    }
    int main()
    {
        
    	test_vector1();
    	return 0;
    }

例子结果：  
![在这里插入图片描述][d357ee8599ac4d97853d1052fcdc1d79.png]  
声明： 后面的代码我自动只写类似于`test_vectorx();`的代码了，**这样更加方便，不会冗余。**

#### 2.2.2 尾删 ####

vector的尾删，查阅文档就是`std::vector::pop_back();`  
![在这里插入图片描述][2829f8524bc94043bb580b3c7e937fb9.png]

代码例子：

void test_vector2()
    {
        
    	vector<int> v;
    	v.push_back(1);
    	v.push_back(2);
    	v.pop_back();
    	for(int i = 0 ; i < v.size() ; ++ i)
    		cout << v[i] << " ";
    	cout << endl;
    }

例子结果：  
![在这里插入图片描述][77dbac7eb8664bfb8ea22c5d87aeedbf.png]

#### 2.2.3 头插 ####

vector的头插，查阅文档就是`iterator insert(iterator pos, const T& x = T());` 或者就是  
`void insert(iteraotr pos, size_t n, const T& x)`  
再或者就是需要用到迭代器了，这个我会专门在下面讲。

![在这里插入图片描述][08a2df86970644559ea1368ac4e797d9.png]

代码例子：

void test_vector3() 
    {
        
    	vector<int> v;
    	v.push_back(1);
    	v.push_back(2);
    	
    	v.insert(v.begin(),0);//第一种写法
    	v.insert(v.begin(),2);
    	v.insert(v.begin(),10,1);//第二种写法
    	for(int i = 0 ; i < v.size() ; ++ i)
    		cout << v[i] << " ";
    	cout << endl;
    }

**测试结果是：1 1 1 1 1 1 1 1 1 1 2 0 1 2**

#### 2.2.4 任意位置删除 ####

vector的头插，查阅文档就是`iterator erase(iterator pos);` 或者就是  
`iterator erase(iterator first,iterator last);`  
![在这里插入图片描述][bcb6188834274dffb1385500bfbfe65e.png]  
代码例子：

void test_vector4() 
    {
        
    	vector<int> v;
    	v.push_back(1);
    	v.push_back(2);
    	
    	v.insert(v.begin(),0);
    	v.insert(v.begin(),1);
    	v.insert(v.begin(),2);
    	v.insert(v.begin(),3);
    	
    	for(int i = 0 ; i < v.size() ; ++ i)
    		cout << v[i] << " ";
    	cout << endl;
    	
    	v.erase(v.begin());
    	v.erase(v.begin() + 2);
    	
    	for(int i = 0 ; i < v.size() ; ++ i)
    		cout << v[i] << " ";
    	cout << endl;
    }

测试结果是：

删除前：3 2 1 0 1 2  
删除后：2 1 1 2

### 2.3 vector的iterator是什么以及失效问题 ###

![在这里插入图片描述][fb4b70621707485091eb6afb717f0703.png]

查阅了给出网站的文档我知道了，iterator其实就是vector的迭代器，我是这样理解的，迭代器其实就是类似指针的东西，但是他不是指针，我们在以后的学习还是会继续学习他的，所以这里就来讲解一下iterator的用法。

**顾名思义：begin其实就是元素首地址，end就是元素的末地址的下一个地址，rbegin其实就是end，rend就是begin，目前来说这些都是最长用的也是最有用的，剩下的自己去读取文档学习。**

然后再讲解一个很重要的知识点就是迭代器失效问题：

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了  
封装，比如：vector的迭代器就是原生态指针T\* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的  
空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，  
程序可能会崩溃)。

对于vector可能会导致其迭代器失效的操作有：

1.  会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、  
    push\_back等。
2.  指定位置元素的删除操作–erase
3.  注意：Linux下，g++编译器对迭代器失效的检测并不是非常严格，处理也没有vs下极端。
4.  与vector类似，string在插入+扩容操作+erase之后，迭代器也会失效

**对于迭代器失效的第一条：**  
我认为，其实就是it这个指针原本指向老空间没错，但是经过增加元素，导致了vector的扩容，就会使得vector开辟新的一段空间并且把老的空间的内容拷贝进去，而我们的it迭代器，还指向旧空间，因此，就会导致it的失效。  
**迭代器失效解决办法：在使用前，对迭代器重新赋值即可**

**对于迭代器失效的第二条：**

void test_vector5()
    {
        
    	vector<int> v;
    	v.push_back(1);
    	v.push_back(2);
    	v.push_back(3);
    	v.push_back(4);
    	vector<int>::iterator pos = find(v.begin(),v.end(),3);
    	v.erase(pos);
    	cout << *pos << endl;
    }

erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代  
器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是  
没有元素的，那么pos就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效  
了。  
所以迭代器失效的最重要的方法就是:  
**迭代器失效解决办法：在使用前，对迭代器重新赋值即可**  
**迭代器失效解决办法：在使用前，对迭代器重新赋值即可**  
**迭代器失效解决办法：在使用前，对迭代器重新赋值即可**  
重要的事情说三遍。

## 三、vector的模拟实现 ##

### 3.1 成员变量 ###

namespace Vct
    {
        
    	template<class T>
    	class vector
    	{
        
    	public:
    		typedef T* iterator;
    		typedef T* const_iterator;
    	private:
    		iterator _start;
    		iterator _finish;
    		iterator _endofstorage;
    	}
    }

### 3.2 成员函数 ###

#### 3.2.1 构造函数 ####

vector()
    	:_start(NULL)
    	,_finish(NULL)
    	,_endofstorage(NULL)
    {
        }
    		
    vector(size_t n, const T& x = T())
    	:_start(NULL)
    	,_finish(NULL)
    	,_endofstorage(NULL)
    {
        
    	resize(n,x);
    }
    		
    vector(int n, const T& x = T())
    	:_start(NULL)
    	,_finish(NULL)
    	,_endofstorage(NULL)
    {
        
    	resize(n,x);
    }	
    //迭代器区间初始化 [first,last)  
    template<class InputIterator>
    vector(InputIterator first, InputIterator last)
    {
        
    	while (first != last)
    	{
        
    		push_back(*first);
    		first++;
    	}
    }

#### 3.2.2 拷贝构造 ####

//方案一
    vector(const vector<T>& V)
    	:_start(nullptr)
    	, _finish(nullptr)
    	, _endofstorage(nullptr)
    {
        
    	iterator tmp = new T[V.capacity()];
    	//memcpy(tmp, V._start, sizeof(T) * V.size());
    	for (size_t i = 0; i < V.size(); i++)
    	{
        
    		tmp[i] = V._start[i];
    	}
    	_start = tmp;
    	_finish = _start + V.size();
    	_endofstorage= _start + V.capacity();
    }
    
    //方案二
    vector(const vector<T>& V)
    	:_start(nullptr)
    	, _finish(nullptr)
    	, _endofstorage(nullptr)
    {
        
    	reserve(V.capacity());
    	for (auto e : V)
    	{
        
    		push_back(e);
    	}
    }

#### 3.2.3 析构函数 ####

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

#### 3.2.4 operator= ####

void swap(vector<T> v)
    {
        
    	std::swap(v._start, _start);
    	std::swap(v._finish, _finish);
    	std::swap(v._end_of_storage, _endofstorage);
    }
    
    vector<T>& operator=(vector<T> v)//调用拷贝构造函数
    {
        
    	swap(v);
    	return *this;
    }

#### 3.2.5 size ####

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

#### 3.2.6 capacity ####

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

#### 3.2.7 迭代器相关 ####

iterator begin()
    {
        
    	return _start;
    }
    
    iterator end()
    {
        
    	return _finish;
    }
    
    const_iterator begin() const
    {
        
    	return _start;
    }
    
    const_iterator end() const
    {
        
    	return _finish;
    }

#### 3.2.8 reserve ####

void reserve(size_t new_capacity)
    {
        
    	if (new_capacity > capacity())
    	{
        
    		iterator tmp = new T[new_capacity];
    		if (_start)//如果原来的_start申请过空间，要先将源空间中的内容拷贝过来
    		{
        
    			memcpy(tmp, _start, sizeof(T)*size());
    			delete[] _start;
    		}
    
    		size_t vsize = size();
    
    		_start = tmp;
    		_finish = tmp + vsize;//记得更新_finish
    		_endofstorage  = _start + new_capacity;
    	}
    }

#### 3.2.9 resize ####

void resize(size_t n, const T& val = T())//缺省参数给的是一个匿名对象
    {
        
    	if (n > size())
    	{
        
    		//检查容量，扩容
    		if (n > capacity())
    		{
        
    			reserve(n);
    		}
    
    		//开始填数
    		iterator it = end();
    		while (it < _start + n)
    		{
        
    			*it = val;
    			it++;
    		}
    
    	}
    
    	_finish = _start + n;
    }

#### 3.2.10 operator\[ \] ####

T& operator[](size_t pos)//读写版本
    {
        
    	assert(pos < size());
    	return _start[pos];
    }
    
    const T& operator[](size_t pos) const//只读版本
    {
        
    	assert(pos < size());
    	return _start[pos];
    }

#### 3.2.11 insert ####

iterator insert(iterator pos, const T& val)
    {
        
    	assert(pos >= _start && pos <= _finish);
    	size_t rpos = pos - _start;//保存一下pos的相对位置
    	//检查容量
    	if (_finish + 1 >= _end_of_storage)
    	{
        
    		size_t new_capacity = capacity();
    		reserve(new_capacity == 0 ? 4 : old_capacity * 2);
    	}
    	pos = _start + rpos;//更新pos
    	//插入数据
    	iterator end = _finish - 1;
    	while (end >= pos)
    	{
        
    		*(end + 1) = *end;
    		end--;
    	}
    	*pos = val;
    	_finish++;
    	return pos;
    }

#### 3.2.12 erase ####

iterator erase(iterator pos)
    {
        
    	assert(pos >= _start && pos <= _finish);
    	iterator cur = pos + 1;
    	while (cur != _finish)
    	{
        
    		*(cur - 1) = *cur;
    		cur++;
    	}
    	_finish--;
    	return pos;
    }

#### 3.2.13 pop\_back ####

//直接复用
    void pop_back()
    {
        
    	erase(--end());
    }

--------------------

## 总结 ##

写了一个晚自习终于把C++的vector的博客给写完了，写了很多东西，如果觉得写的不错的可以给夏目一个三连支持一下谢谢。

[C]: https://legacy.cplusplus.com/reference/vector/vector/
[c0e2524b3916460cbe10a37a4eee47bb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/a1d051cbc6f64b3fb92bab01260ecdb6.png
[51a3f999e7154056af991883e797bfc4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/f5af5f828d2645fe9dfd1139e767f913.png
[729a7d3f493b40638c2ae1c4d491aaa9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/978a2d32309d4cdcb1f5241e5ebb3535.png
[b57b9deaee6f4be6b7b0313087c503fe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/6105ff4635c54ca2bd00c457591f6731.png
[d357ee8599ac4d97853d1052fcdc1d79.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/0e0c1bf098e44b899864d78b573bc6b0.png
[2829f8524bc94043bb580b3c7e937fb9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/050e795672464d1a8ad21e8fed1da353.png
[77dbac7eb8664bfb8ea22c5d87aeedbf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/7e0210796f1f49849d9b373011775f81.png
[08a2df86970644559ea1368ac4e797d9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/a8ca3d0a0bb84589b8e61870290ed00a.png
[bcb6188834274dffb1385500bfbfe65e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/7fa9d5b45d814b10afb205ae9602059c.png
[fb4b70621707485091eb6afb717f0703.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/ff02af9b40274260b9dec59bbd5e7c9e.png