c++ - 第9节 - vector类

目录

1.标准库中的vector类

1.1.vector类

1.2.vector类的常用接口说明

1.3.vector类练习题

2.vector类的模拟实现

2.1.vector类源代码解析

2.2.vector类的模拟实现

---

1.标准库中的vector类

1.1.vector类

vector类的文档介绍：https://cplusplus.com/reference/vector/vector/

注：

1. vector是表示可变大小数组的序列容器。

2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。

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

4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。

5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。

6. 与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和forward_lists统一的迭代器和引用更好

7.如下图所示是vector类的声明，vector其实也是一个模板，是顺序表的模板，模板第一个参数是一个类（一般传的是需要存储数据的类型名，可以是int这种普通类型，也可以是string这种类），模板第二个参数也是一个类，是一个空间配置器（内存池），第二个参数给了缺省值，这个缺省值其实就是官方库给的vector，如果不想使用官方库的vector那么也可以自己写一个vector传过来

​

1.2.vector类的常用接口说明

使用string前的说明：

1.使用vector类需要包含vector的头文件，代码为：#include

2.vector类是在std里面的，因此使用vector类需要using namespace std将std展开（如果不展开每次使用vector类需要std::vector）

1. vector类对象的常见构造

函数名称	功能说明
vector()	无参构造
vector(size_type n, const value_type& val = value_type())	构造并初始化n个val
vector (const vector& x)	拷贝构造
vector (InputIterator first, InputIterator last)	使用迭代器进行初始化构造

注：

1.vector类可以存储任意类型的数据，可以是int、double这种常见类型数据，也可以存储string类这种数据，如下图所示

​

上面的v3.push_back("李白")代码，表面上是用一个字符串来构造string类，实际上vector空间一般是提前开好的，相当于是将字符串赋值给string类的对象，类似下图所示的代码，可以直接将字符串赋值给string类的对象是因为单参数的构造函数支持隐式类型的转换

	string s;
	s = "hello word";

2.vector(size_type n, const value_type& val = value_type())这种形式构造函数的功能是构造并初始化n个val，其中第一个参数是size_type类型的，如下图一所示，size_type其实就是无符号整型；第二个参数const value_type&，其中value_type其实就是vector模板中的模板第一个参数T，如下图二所示，参数T其实就是vecor中要放的数据类型。

​

​

vector(size_type n, const value_type& val = value_type())这种形式构造函数使用方式如下，这里是使用10个数值5对整型的vector对象v4进行初始化

vector<int> v4(10, 5);

3.vector (InputIterator first, InputIterator last)这种形式构造函数的功能是使用迭代器进行初始化构造，使用方式如下图一所示，是使用这一段迭代器区间来进行初始化。

注意：这种形式的构造函数其实是一个模板函数，如下图二所示，模板参数是InputIterator，因此其可以接收任意类的迭代器，不一定非要是vector的迭代器，也可以使用string类的迭代器对vector进行初始化，如下图三所示。这里要注意不管是什么类型的迭代器，对应的迭代器解引用都要对上vector里面的数据类型

​

​​

2.vector类对象的访问及遍历操作

方法	解释
对象名[ ]	像数组一样访问
迭代器	使用迭代器配合begin、end函数，来访问对象的字符串任意字符
范围for	使用范围for的语法进行遍历，本质上就是转换成了迭代器

注：

1.可以对象名[ ]访问vector对象的任意数据是因为vector里面对运算符[ ]进行了运算符重载，如下图一所示，那么遇见s[i]编译器就会翻译成s.operator[ ](i)，其中参数reference其实就是value_type&，而value_type是vector模板中的模板第一个参数T（参数T其实就是vecor中要放的数据类型）

对象名[ ]的使用方式如下图所示

2.vector类里面也有vector类的迭代器，vector类的迭代器和string类迭代器相同，可以认为是指针，vector类的迭代器使用方式如下图所示

vector类begin和end函数的声明如下图所示，如果是普通对象则返回普通的迭代器，用户可使用普通迭代器进行读写操作，如果是const修饰的对象则返回const修饰的迭代器，用户只能使用const修饰的迭代器进行读操作

 

c++为了规范化，增加了cbegin和cend函数，如果是const修饰的对象，可以调用cbegin和cend函数，返回const修饰的迭代器，cbegin和cend函数声明如下图所示

3.范围for的访问方式如下图所示

3.vector类对象的容量操作

函数名称	功能说明
size	获取数据个数
capacity	获取容量大小
empty	判断是否为空
resize	改变vector的size
reserve	改变(增加)vector的capacity
shrink_to_fit	减少vector的capacity

1.size函数的功能是获取数据个数，size函数的声明如下图所示，size函数返回有效数据元素的个数

 除了size还有一个函数是max.size，string类的max.size函数返回的是整形的最大值，而vector类的max.size函数返回的是整型的最大值除以单个数据单元的大小（如果vector存储是int类型的数据，也就是T是int，则返回的是整型最大值除以4），如下图所示

2.capacity函数的功能是获取容量大小，capacity函数的声明如下图所示

3.vector类的扩容机制演示如下图所示，如果是vs编译器（vs编译器使用PJ版本的STL），每次增容增容后的容量大概为增容前容量的1.5倍，也就是1.5倍的增容，不同的编译器增容倍数可能不同（Linux g++使用的是SGI版本的STL，其是2倍增容）

注意：string类因为里面存储的是一个个字符，string类的capacity数值对应的是字节个数，所以申请空间系统会进行内存对齐；下面演示的是vector类，里面存储的是int类型的数据，capacity数值对应的是int类型的个数，每一个int类型是四个字节，那么最后申请的空间是4*capacity个字节，结果是对齐好的，因此不用专门进行内存对齐

单次增容增多少的问题分析：

单次增容越多，插入N个值，增容次数越少，效率就越高，但是单次增容越多，可能浪费的空间就越多。因此到底一次增容多少其实是一个平衡的选择

4.与string类类似，vector的reserve函数的功能是改变vector的容量capacity，vector的resize函数的功能是改变vector的有效数据size大小（capacity也会跟着改变），也就是开了空间并进行初始化，两个函数的声明如下图所示

resize函数的使用如下图所示，resize函数的第二个参数是指定初始化的值

注意：reserve函数和resize函数只能用来增容（增加capacity的值），不会去缩容（其中resize函数可以控制有效字符size变小，但容量capacity不变）

string和vector等都有一个特点，删除数据，一般是不会主动缩容的（STL没有规定，只是一般都有这个特点）

5.shrink_to_fit函数的功能是减少vector的capacity（缩容），使capacity和size大小相同。函数声明如下图所示

 注意：shrink_to_fit函数要慎用、少用，因为操作系统的内存不允许一部分一部分的还内存，所以使用该函数进行缩容，其实是再开辟一块size个数据大小的新空间，将size个有效数据拷贝过来，然后释放之前的旧空间，这样性能很低。其意义是还一些大内存空间给操作系统，但是要付出一些性能上的代价

4.vector类对象的修改操作

函数名称	功能说明
push_back	尾插
pop_back	尾删
find	查找。（注意这个是算法模块实现，不是vector的成员接口）
insert	在position之前插入val
erase	删除position位置的数据
swap	交换两个vector的数据空间
clear	清空有效数据

注：

1.push_back函数的功能是尾插数据，函数声明如下图所示，其中参数是const value_type&类型，value_type前面讲过是vector模板中的模板第一个参数T

2.pop_back函数的功能是尾删数据，函数声明如下图所示

3.insert函数的功能是在position之前插入数据，insert函数声明如下图所示，看以看出vector类里面的insert函数和string里面的insert函数有一些区别，string里面的insert函数支持使用下标来定位数据，而vector类里面的insert函数只支持迭代器

vector类里面的insert函数使用方式如下图一二所示

 

与string类一样，vector类里面的insert函数也需要挪动后面的数据然后进行插入，效率比较低，所以尽量少用

注意：insert函数是在任意位置插入数据，如果要尾插iterator position可以定位到尾的后一个位置，但是如果定位的位置再往后就越界了，系统会报错，如下图所示

4.erase函数的功能是删除position位置的数据，erase函数声明如下图所示，可以看出，vector类里面的erase函数和insert函数相同，也是只能使用迭代器来定位，erase函数第一种用法是删除某一个位置处的值，第二种用法是删除一段区间。

erase函数的使用方式如下图所示

与string类一样，vector类里面的erase函数也需要挪动后面的数据然后进行删除，效率比较低，所以尽量少用

5.swap函数的功能是交换两个vector的数据空间，其函数声明如下图所示，本质上vector类的swap函数是直接交换指向的内存空间地址（将内存空间地址进行交换），比库里面的swap函数效率高

 6.clear函数的功能是清空有效数据，也就是将size置成0，其函数声明如下图所示

7.vector类里面没有find成员函数，如果在vector类里面需要找一个数据，可以使用算法algorithm头文件里面的find模板函数，其函数声明如下图一所示，algorithm里面的find函数支持传一段迭代器区间来找某个数据，其实现方式如下图二所示

注意：这里面传过去的迭代区间一定是左闭右开的，也就是说真正的区间是从first开始到last-1结束

从上图algorithm里面的find函数实现可以看出，如果没有找到目标数据则返回的是last

algorithm里面的find函数使用方式如下图所示

上个图所示由于pos变量的类型很长，可以使用auto来自动推导

注意：

（1）使用algorithm里面的find函数需要#include包含algorithm头文件

（2）这里把find模板函数写到算法algorithm头文件里面是为了支持复用，这里不仅vector类可以使用，list等其它类同样可以使用

8.算法algorithm头文件里面有一个sort函数，他的功能是进行排序，其函数的声明如下图一所示，其传入的参数是一段迭代器区间，迭代器区间是左闭右开的，也就是说这个区间是从first开始到last-1结束。

如果不传第三个参数那么默认是升序的(默认<仿函数)，如果要排降序那么需要>仿函数（仿函数后面会讲），简单的说就是将第三个参数写成greater()即可，如下图二所示

注意：

（1）使用仿函数需要#include包含functional头文件

（2）greater()其实是一个对象，是使用greater类定义出来的匿名对象，如下图三所示，二者功能相同

string和vector的区别：

（1）vector不支持append函数和operator+=函数，这样没办法很方便的去插入一段字符串，操作上有区别

（2）string要符合c形式的字符串，因此最后有/0，可以很好的和c语言库里面的字符串操作str系列函数进行配合使用

（3）string支持流插入的输出，vector不支持

（3）很多接口功能上的区别（比如二者的比较函数对字符串的比较方式是不一样的）

虽然从底层看string和vector都是管理char类型的数组，但是操作和接口等方面还是有很多区别的，实际中要存char类型的数据，最好是用string类

1.3.vector类练习题

练习题一：

题目描述：

题目链接：136. 只出现一次的数字 - 力扣（LeetCode）

代码：

练习题二：

题目描述：

题目链接：118. 杨辉三角 - 力扣（LeetCode）

代码： 

注：

1.c语言解法题目给的函数如下图一所示，形参numRows是行数，returnSize是输出型参数要返回行数，returnColumnSizes也是输出型参数，获取一个一维数组，数组数据依次表示每一行的数据个数。

动态的二维数组从c语言的角度需要开两层，首先动态开辟一个指针数组（如果开辟的是int的数组，那么返回值类型是int*，如果开辟的是int*的数组，那么返回值类型是int**），malloc这个动态指针数组的返回值应该用int**接收。然后再依次malloc开数组返回值给到指针数组的每一个元素，形式如下图二所示

2.动态的二维数组从c++的角度就是vector的vector，创建一个vector对象，这个vector对象里面的每一个数据是vectot类型的对象，创建方式为vector>，这种创建方式创建出来的动态二维数组可能是规则或者不规则的二维数组（每一行的数据个数可能不一样），形式如下图所示

这个动态的二维数组vector>的遍历方式如下图所示，vv.size()是二维数组的行数，vv[i]是每一行的那个管理int的vector，vv[i].size表示每一行的数据个数。

vv[i]的本质是vv.operator[](i)，返回的是vector类型的数据，vector类型的数据又可以继续去结合第二个[j]，这次调用其实就是vv[i].operator[j]，那么整体vv[i][j]的本质就是(vv.operator[](i)).operator[j]

这样通过两次operator[]的调用，像访问二维数组一样访问数据。访问第i行第j个数据，本质上是先访问第i个vector对象，再访问这个对象的第j个int数据

注：c++方式的动态的二维数组不管是开辟、访问、管理都比c语言方式的动态的二维数组方便很多，并且出了作用域c++方式的动态的二维数组会自动调用析构函数，因为都是自定义类型，两层vector都会自动析构。如果是c语言方式的动态的二维数组，那么需要写一个for循环将内层每一个数组释放了，然后再将外层整体的这个数组进行释放

3.这道题应该使用resize开空间而不是reserve，代码vv.resize(numRows)是开numRows个vector类型数据的空间并初始化，没有给第二个参数那就是使用默认的初始化值，vector类型数据默认的初始化值为vector默认构造的对象，vector默认构造的对象其实就是对象里面没存数据

练习题三：

题目描述：

题目链接：17. 电话号码的字母组合 - 力扣（LeetCode）

代码：

---

2.vector类的模拟实现

2.1.vector类源代码解析

以前我们实现类，成员变量是使用T* _a 、 size_t _size 、size_t _capacity，但是从上面的源代码中可以见并不是这样的。从上面一图可以看出iterator其实就是value_type*，而value_type其实是T，因此iterator就是T*，T是里面存储数据的类型。

从上图三可以看到begin函数返回的是start，结合我们之前所学可以确定start是指向空间的第一个数据位置；end函数返回的是finish，结合我们之前所学可以确定finish是指向空间的最后一个有效数据后一个数据的位置；

从上图四可以看到capacity函数返回的是size_type(end_of_storage - begin())，结合我们之前所学可以确定end_of_storage指向的就是这块空间结束位置的后一个位置。

也就是说 start相当于_a 、finish相当于_a+_size 、 end_of_storage相当于_a+_capacity，形象表示如下图所示

上图是vector构造函数的源码，第一行默认无参构造函数是将start、finish、end_of_storage这几个成员变量初始化为0，这几个变量的类型都是T*类型的，也就是指针，所以其实应该初始化为空指针，c++里面的空指针是nullptr，这里因为源代码写的比较早，因此写的是0

2.2.vector类的模拟实现

test.cpp文件：

#include 
#include 
#include 
#include 
#include 
using namespace std;
 
#include "vector.h"
 
namespace std
{
	void test_vector1()
	{
		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
 
		vector<double> v2;
		v2.push_back(1.1);
		v2.push_back(2.2);
		v2.push_back(3.3);
 
		vector v3;
		v3.push_back("李白");
		v3.push_back("杜甫");
		v3.push_back("苏轼");
		v3.push_back("白居易");
 
		vector<int> v4(10, 5);
 
		vector v5(++v3.begin(), --v3.end());
		
		string s = "hello world";
		vector<char> v6(s.begin(), s.end());
	}
 
	void test_vector2()
	{
		// 遍历
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
 
		// 1、下表+[]
		for (size_t i = 0; i < v.size(); ++i)
		{
			v[i] += 1;
			cout << v[i] << " ";
		}
		cout << endl;
 
		// 2.迭代器
		vector<int>::iterator it = v.begin();
		while (it != v.end())
		{
			*it -= 1;
			cout << *it << " ";
			++it;
		}
		cout << endl;
 
		// 3.范围for
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}
 
	void test_vector3()
	{
		size_t sz;
		std::vector<int> foo;
		foo.reserve(100);
		//foo.resize(100);
		sz = foo.capacity();
		std::cout << "making foo grow:\n";
		for (int i = 0; i < 100; ++i) {
			foo.push_back(i);
			if (sz != foo.capacity()) {
				sz = foo.capacity();
				std::cout << "capacity changed: " << sz << '\n';
			}
		}
 
		// string vector等都有一个特点，删除数据，一般是不会主动缩容
		foo.resize(10);
		cout << foo.size() << endl;
		cout << foo.capacity() << endl;
 
		// 慎用、少用
		foo.shrink_to_fit();
		cout << foo.size() << endl;
		cout << foo.capacity() << endl;
	}
 
	void test_vector4()
	{
		// 遍历
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
 
		v.insert(v.begin(), -1);
		v.insert(v.begin(), -2);
		v.insert(v.begin(), -3);
 
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
 
		v.insert(v.begin() + 7, 300);
		//v.insert(v.begin()+8, 300);
 
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
		v.erase(v.begin());
		v.erase(v.begin());
 
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}
 
 
	void test_vector5()
	{
		// 遍历
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
 
		//vector::iterator pos = find(v.begin(), v.end(), 3);
		auto pos = find(v.begin(), v.end(), 3);
		if (pos != v.end())
		{
			cout << "找到了" << endl;
			v.erase(pos);
		}
		else
		{
			cout << "没有找到" << endl;
		}
 
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
 
		v.push_back(0);
		v.push_back(9);
		v.push_back(3);
		v.push_back(1);
 
		// 默认是升序
		//sort(v.begin(), v.end());   // <
 
		// 排降序，仿函数
		// 关于仿函数，大家先记住这个用法，具体我们后面讲队列再详细讲
		// sort(v.begin(), v.end(), greater());  // >
 
		//greater g;
		//sort(v.begin(), v.end(), g);  // >
 
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}
 
	void test_vector6()
	{
		std::vector<int> v;
		//v.reserve(10);
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		cout << v.size() << ":" << v.capacity() << endl;
		auto pos = find(v.begin(), v.end(), 2);
		if (pos != v.end())
		{
			v.insert(pos, 20);
		}
 
		cout << *pos << endl;
		*pos = 10;
		cout << *pos << endl;
	}
 
	void test_vector7()
	{
		std::vector<int> v;
		v.reserve(100);
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		cout << v.size() << ":" << v.capacity() << endl;
		auto pos = find(v.begin(), v.end(), 2);
		if (pos != v.end())
		{
			v.erase(pos);
		}
 
		cout << v.size() << ":" << v.capacity() << endl;
 
		cout << *pos << endl;
		*pos = 10;
		cout << *pos << endl << endl;
 
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}
 
	void test_vector8()
	{
		std::vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(2);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(4);
		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;
	}
}
 
int main()
{
	bit::test_vector7();
 
	return 0;
}

vector.h文件：

#pragma once
#include 
 
namespace bit
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;
		vector()
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstoage(nullptr)
		{}
 
		template <class InputIterator>
		vector(InputIterator first, InputIterator last)
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstoage(nullptr)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
 
		vector(size_t n, const T& val = T())
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstoage(nullptr)
		{
			reserve(n);
			for (size_t i = 0; i < n; ++i)
			{
				push_back(val);
			}
		}
 
		vector(int n, const T& val = T())
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstoage(nullptr)
		{
			reserve(n);
			for (int i = 0; i < n; ++i)
			{
				push_back(val);
			}
		}
 
		void swap(vector& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstoage, v._endofstoage);
		}
 
		//vector(const vector& v);
		vector(const vector& v)
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstoage(nullptr)
		{
			vector tmp(v.begin(), v.end());
			swap(tmp);
		}
 
		//vector& operator=(vector v)
		vector& operator=(vector v)
		{
			swap(v);
			return *this;
		}
 
		~vector()
		{
			if (_start)
			{
				delete[] _start;
				_start = _finish = _endofstoage = nullptr;
			}
		}
 
		iterator begin()
		{
			return _start;
		}
 
		iterator end()
		{
			return _finish;
		}
 
		const_iterator begin() const
		{
			return _start;
		}
 
		const_iterator end() const
		{
			return _finish;
		}
 
		size_t size() const
		{
			return _finish - _start;
		}
 
		size_t capacity() const
		{
			return _endofstoage - _start;
		}
 
		void reserve(size_t n)
		{
			size_t sz = size();
			if (n > capacity())
			{
				T* tmp = new T[n];
				if (_start)
				{
					//memcpy(tmp, _start, size()*sizeof(T));
					for (size_t i = 0; i < size(); ++i)
					{
						tmp[i] = _start[i];
					}
 
					delete[] _start;
				}
 
				_start = tmp;
			}
 
			_finish = _start + sz;
			_endofstoage = _start + n;
		}
 
		//void resize(size_t n, const T& val = T())
		void resize(size_t n, T val = T())
		{
			if (n > capacity())
			{
				reserve(n);
			}
 
			if (n > size())
			{
				while (_finish < _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
			else
			{
				_finish = _start + n;
			}
		}
 
		void push_back(const T& x)
		{
			/*if (_finish == _endofstoage)
			{
				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newCapacity);
			}
			*_finish = x;
			++_finish;*/
 
			insert(end(), x);
		}
 
		void pop_back()
		{
			/*if (_finish > _start)
			{
				--_finish;
			}*/
			erase(end() - 1);
		}
 
		T& operator[](size_t pos)
		{
			assert(pos < size());
 
			return _start[pos];
		}
 
		const T& operator[](size_t pos) const
		{
			assert(pos < size());
 
			return _start[pos];
		}
 
		iterator insert(iterator pos, const T& x)
		{
			// 检查参数
			assert(pos >= _start && pos <= _finish);
 
			// 扩容
			// 扩容以后pos就失效了,需要更新一下
			if (_finish == _endofstoage)
			{
				size_t n = pos - _start;
 
				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newCapacity);
 
				pos = _start + n;
			}
 
			// 挪动数据
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				--end;
			}
 
			*pos = x;
			++_finish;
 
			return pos;
		}
 
		iterator erase(iterator pos)
		{
			assert(pos >= _start && pos < _finish);
			iterator it = pos + 1;
			while (it != _finish)
			{
				*(it - 1) = *it;
				++it;
			}
 
			--_finish;
 
			return pos;
		}
 
		void clear()
		{
			_finish = _start;
		}
 
	private:
		iterator _start;
		iterator _finish;
		iterator _endofstoage;
	};
 
 
	void test_vector1()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
 
		vector<int>::iterator it = v.begin();
		while (it != v.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
 
		v.pop_back();
		v.pop_back();
		v.pop_back();
 
		for (size_t i = 0; i < v.size(); ++i)
		{
			cout << v[i] << " ";
		}
		cout << endl;
 
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
 
		// C++中内置类型也可以认为有构造函数 析构函数
		// 这样才能更好支持模板
		// void resize(size_t n, T val = T())
		int i = 0;
		int j = int();
		int k = int(1);
	}
 
	void test_vector2()
	{
		/*vector v;
		v.resize(10, -1);
		for (auto e : v)
		{
		cout << e << " ";
		}
		cout << endl;*/
 
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		//v.push_back(5);
 
		v.insert(v.begin(), 0);
 
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}
 
 
	void test_vector3()
	{
		// 在所有的偶数的前面插入2
		vector<int> v;
		//v.reserve(10);
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
		v.push_back(6);
 
		vector<int>::iterator it = v.begin();
		while (it != v.end())
		{
			if (*it % 2 == 0)
			{
				it = v.insert(it, 20);
				++it;
			}
 
			++it;
		}
 
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}
 
	void test_vector4()
	{
		vector<int> v;
		//v.reserve(10);
		v.push_back(1);
		v.push_back(2);
		v.push_back(2);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(4);
		v.push_back(5);
		cout << v.size() << ":" << v.capacity() << endl;
		auto pos = find(v.begin(), v.end(), 4);
		if (pos != v.end())
		{
			v.erase(pos);
		}
 
		cout << *pos << endl;
		*pos = 10;
		cout << *pos << endl << endl;
 
		cout << v.size() << ":" << v.capacity() << endl;
 
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}
 
	void test_vector5()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
 
		vector<int> v1(v.begin(), v.end());
		std::string s("hello");
		vector<int> v2(s.begin(), s.end());
 
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;
 
		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;
 
		vector<int> v3(v);
		for (auto e : v3)
		{
			cout << e << " ";
		}
		cout << endl;
 
		v1 = v2;
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;
	}
 
	void test_vector6()
	{
		vector<int> v1(10, 2);
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;
 
		vector<char> v2(10, 'x');
		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;
	}
 
	class Solution {
	public:
		vectorint>> generate(int numRows) {
			vectorint>> vv;
			vv.resize(numRows);
			for (size_t i = 0; i < vv.size(); ++i)
			{
				// 杨辉三角，每行个数依次递增
				vv[i].resize(i + 1, 0);
 
				// 第一个和最后一个初始化成1
				vv[i][0] = 1;
				vv[i][vv[i].size() - 1] = 1;
			}
 
			for (size_t i = 0; i < vv.size(); ++i)
			{
				for (size_t j = 0; j < vv[i].size(); ++j)
				{
					if (vv[i][j] == 0)
					{
						// 中间位置等于上一行j-1 和 j个相加
						vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];
					}
				}
			}
 
			for (size_t i = 0; i < vv.size(); ++i)
			{
				for (size_t j = 0; j < vv[i].size(); ++j)
				{
					cout << vv[i][j] << " ";
				}
				cout << endl;
			}
			cout << endl;
 
			return vv;
		}
	};
 
	void test_vector7()
	{
		vectorint>> ret = Solution().generate(5);
 
		for (size_t i = 0; i < ret.size(); ++i)
		{
			for (size_t j = 0; j < ret[i].size(); ++j)
			{
				cout << ret[i][j] << " ";
			}
			cout << endl;
		}
		cout << endl;
	}
}

注：

1.vector函数里面有一个使用迭代器区间进行构造的构造函数，该构造函数官方声明如下图所示，这里可以看出类模板里面是可以定义函数模板的。

该构造函数我们的实现如下图所示，我们复用push_back函数来实现。

使用该构造函数如下图所示，因为是模板函数，所以不仅可以使用vector类型的迭代器区间进行构造，也可以使用其他类型例如string类型的迭代器区间进行构造

vector函数里面有一个使用n个val值进行构造的构造函数，该构造函数官方声明如下图所示

该构造函数的实现代码如下图一所示，使用下图二所示的代码进行测试，结果编译器会报非法的间接寻址错误，如下图三所示

 

我们双点错误输出里的错误行发现错误定位在了使用迭代器区间进行构造的构造函数里面push_back(*first)代码上，如下图所示我们写n个val值进行构造的构造函数代码错误却报在了另一个已经实现的构造函数上，说明这里vector v1(10,2)代码没有匹配到n个val值进行构造的构造函数而是匹配到了迭代器区间进行构造的构造函数

我们再使用vector v2(10,'x')代码来测试，发现vector v2(10,'x')能匹配到n个val值进行构造的构造函数

为什么vector v1(10,2)代码匹配到的是迭代器区间进行构造的构造函数而vector v2(10,'x')代码匹配到的是n个val值进行构造的构造函数呢？

分析：vector v1(10,2)的形参类型是int和int，vector v2(10,'x')的形参类型是int和char，编译器在函数匹配的时候会去找最匹配的。

int和int类型的参数与size_t和const T&类型的参数需要隐式类型转换，与InputIterator first和InputIterator last类型的参数相匹配，此时模板参数InputIterator识别成了int，因此vector v1(10,2)调用的是迭代器区间进行构造的构造函数

int和char类型的参数与size_t和const T&类型的参数需要隐式类型转换，与InputIterator first和InputIterator last类型的参数不匹配，因为模板参数InputIterator无法同时识别成int和char相矛盾，因此vector v2(10,'x')调用的是n个val值进行构造的构造函数

上面报了非法解引用的错误，是因为vector v1(10,2)调用的是迭代器区间进行构造的构造函数，InputIterator识别成了int，迭代器区间进行构造的构造函数里面有*first，相当于对int类型进行解引用，所以是非法解引用的错误

解决方法：我们前面实现的n个val值进行构造的构造函数参数为size_t和const T&类型，我们再重载一个参数为int和const T&类型的n个val值进行构造的构造函数即可，如下图一所示，我们观察标准库里的解决方式，如下图二所示，也是使用函数重载来解决

2.拷贝构造函数和赋值运算符重载函数的现代写法实现如下图所示

使用类创建对象时，类名就是类型，使用类模板创建对象时，类名是类模板名<类型>，因此类模板名<类型>才是类型，但是有些时候类模板名也可以表示类型，如下如所示，构造和运算符重载这里可以直接使用模板名表示类型，这么写可以但是不标准，不推荐这么写

3.reserve函数如果像下图一所示的方式实现其实是有问题的。如下图二所示，第一次调用push_back函数，构造函数构造的_start成员变量是空指针，push_back函数里面算出来new_capacity为4，reserve函数判断n为4是大于capacity为0的，进入if语句，memcpy函数里面_start此时是空指针，会报错。因此需要检查一下是否需要将旧空间的数据拷贝到新空间，如果旧空间没有数据，那就不拷贝了，如下图三所示

但是上图代码还是有问题，第一次push_back开4个数据大小的空间，_start成员变量指向4个数据空间第一个数据的位置，运行到代码_finish=_start+size()， size函数如下图所示，是用_finish-_start，_finish此前没有更新此时是构造时的空指针，那么_finish=_start+size()=_start+_finish-_start=空指针。后面开空间reserve也会出问题，运行到_finish=_start+size()，_start已经指向新开空间的位置了，_finish指向的还是旧空间最后一个有效数据后一个位置，此时是用size函数还是会报错

同理代码_endofstoage=_start+capacity()得到的_endofstoage也是空指针，后面再开空间走到这也会出问题

所以我们应该在start更新之前算好有效数据的个数sz，用来计算后面的_finish，后面的_endofstoage直接是用reserve形参n即可，如下图所示

4.resize函数的官方声明如下图一所示，其中value_type就是vector里面存的数据类型T。仿照下面的我们的声明可以是void resize(size_t n,const T& val=T())，如下图二所示，有些编译器这句代码有可能编不过，因为T()是一个临时对象，编译器认为不能对这个临时对象引用，如果这个代码不行，那我们严格按照官方声明的形式去写，代码为void resize(size_t n,T val=T())，如下图三所示，不去引用了（不引用const也可以不要了）

这里T val=T()给了缺省参数，第二个参数不给那么就使用临时T对象（创建一个临时T对象，T对象默认构造函数对这个临时T对象进行构造，然后再将默认T对象拷贝构造给val对象，前面的操作编译器优化成直接调用val对象的默认构造函数），这样val对象就是默认构造函数构造出来的对象，然后resize出来的所有数据都使用val对象赋值进行初始化

如过vector里面存的是int类型，也就是T为int，上面函数声明void resize(size_t n,T val=T())，T val=T()调用T也就是int的默认构造函数，内置类型有构造函数吗？

在c语言里面没有构造函数的概念，所以c语言里面内置类型没有构造函数，c++里面内置类型是有构造函数的，如果不传参进行构造使用的就是默认构造函数，默认构造函数如果是int类型就会构造成0，如果是double类型就会构造成0.0，如果是int*类型就会构造成空指针，其他类型类似。因此我们定义变量也可以像如下方式进行初始化工作。

c++中内置类型也可以认为有构造函数、析构函数，这样才能更好的支持模板

resize函数的代码实现如下图所示

5. insert函数的官方声明如下图所示，其中第二个和第三个声明只需要复用第一个声明的函数就可以了，所以我们只实现第一个声明的函数

insert函数代码实现如下图所示

上面实现的代码其实是有问题的，要在迭代器pos处插入数据，扩容部分执行之后开辟了新的内存，旧的内存已经释放了，reserve函数更新了_start、_finish、_endofstoage指向了新的空间而没有更新迭代器pos，此时pos还指向旧空间，这就造成了迭代器失效，也可以说是野指针，后面end=_finish-1然后进入while循环，end指向新空间最后一个有效数据的位置，pos指向旧空间的一处位置，因此循环次数不定，并且会越界访问。

上面的代码扩容以后迭代器pos就失效了，所以扩容的时候应该更新一下迭代器pos，如下图所示

上面的代码还是有一些问题，执行下图所示主函数里面的代码，迭代器it是从begin位置开始往后遍历，当需要insert插入的时候，如果insert里面进行了扩容开辟了新的空间，reserve函数更新了_start、_finish、_endofstoage指向了新的空间而没有更新迭代器it，因为实参迭代器it传给insert函数的形参pos，这里是值传递，前面我们更新了pos但是pos改变不会影响it，此时it还指向旧空间，和前面一样，迭代器失效了

那我们给insert函数的形参pos前面加个引用，这样pos更新it也会更新，如下图一所示，可以看见这样编译器会报错，如果传过来的是一个具有常性的迭代器，iterator& pos是无法接收的（权限放大），如下图二所示，v.begin是传值返回的，返回的值是一份临时拷贝具有常性。而iterator& pos前面不能加const，因为insert函数体中开辟新空间要更新pos。源代码中的insert函数的声明里面也没有使用引用 。

就算我们reserve开辟好足够的空间，迭代器it不会失效，it指向数据2位置时要插入数据20，那么将2及其后面的数据往后移动一个数据大小，将20插入到it指向的这块空间，it指向数据20需要继续插入20，这样就变成了一直在这个位置插入数据20，如下图所示，和我们的预想不一样,这种场景下，其实也可以称作是迭代器失效

上面这个场景insert以后虽然没有扩容，it没有成为野指针，但是it指向位置意义变了，导致我们这个程序重复插入20

可以把迭代器的失效分为两大类：

（1）迭代器指向已经释放的空间，导致迭代器失效（类似野指针）

（2）迭代器指向位置意义变了，导致迭代器失效

为了解决上面迭代器指向已经释放的空间，导致迭代器失效，官方库里面的解决方法是使用insert函数返回值来解决，将更新后的pos进行返回，外面的it每次进行一次接收来进行更新，如下图所示

为了解决迭代器指向位置意义变了，导致迭代器失效，如果是偶数，那么insert插入后it指针需要指向往后移动两个数据大小的位置（跳过新插入的20和原本的偶数），如果是奇数，那么it指针需要指向往后移动一个数据大小的位置（跳过这个奇数），如下图所示

6.比较对于insert函数，两类迭代器失效在vs和g++不同编译器下的处理情况，如下图所示。

如果是类似野指针的情况，vs编译器的情况检查的较严格（直接报断言错误），g++编译器没有报错（编译器对越界访问不一定会进行检查，vs编译器也只是在这个情况下检查出来了）

如果是迭代器指向位置意义变了的情况，两个编译器都没有报错，但是真实插入数据的逻辑和我们的逻辑不同

总结：在使用insert函数时，有可能出现迭代器失效的情况，两类迭代器失效，无论是哪种迭代器失效，编译器都可能不报错（只有类似野指针的情况vs编译器会报错），但是真实插入数据的逻辑与我们的不同，因此我们使用insert时一定要小心

7.erase函数的官方声明如下图所示，其中第二个声明只需要复用第一个声明的函数就可以了，所以我们只实现第一个声明的函数。erase函数返回的是一个迭代器，返回

下图所示是erase函数返回值介绍，erase函数返回的是pos迭代器，因为大多数编译器erase函数里面没有开或者缩空间，所以pos迭代器不需要更新，返回的pos迭代器和形参pos迭代器完全相同。如果某些编译器erase函数缩容了，那么pos迭代器在函数里面就进行了更新，返回的是更新后的pos迭代器

常见的缩容方案：当size()

缩容的行为前面讲过其本质是一种以时间换空间的行为（创建小空间然后进行拷贝），大多数编译器删除数据都不考虑缩容的方案，因为实际比较关注时间效率，不关注空间效率，现在硬件设备空间都比较大，空间存储也比较便宜

我们实现的erase函数的实现代码如下图一所示，使用我们实现的erase函数代码如下图二三所示，从下图三可以看出，如果删除最后一个数据，erase删除--_finish，此时迭代器pos指向的位置没有变，再用迭代器去访问还是能访问到4这个数据，也可以将其改为10，这里迭代器指向位置意义变了，导致迭代器失效，因为没有缩容迭代器pos指向的还是有效的空间，因此编译器不会报错。

8.下图所示是分别使用vs编译器和g++编译器执行erase函数代码的情况，可以看出vs编译器和g++编译器标准库里的erase函数都没有缩容操作，并且

vs编译器：vs编译器标准库会对迭代器指向位置意义变了导致的迭代器失效这种情况做检查，如果失效了在访问的时候就会检查出来报断言错误（vs编译器标准库对于insert函数的迭代器指向位置意义变了导致的迭代器失效这种情况不做检查，vs编译器标准库对于erase函数的迭代器指向位置意义变了导致的迭代器失效这种情况做检查报断言错误）

g++编译器：g++编译器对迭代器指向位置意义变了导致的迭代器失效这种情况不做检查（g++编译器对于insert和erase函数的迭代器指向位置意义变了导致的迭代器失效这种情况处理方式相同，都不做检查，更加统一）

g++编译器对迭代器指向位置意义变了导致的迭代器失效这种情况不做检查，并不代表没有问题我们可以不管，如下图所示，实现删除所有偶数的功能，实际输出的结果和我们的逻辑预想的可能相同，可能不同，甚至输出结果可能会报段错误（越界），这是由于迭代器意义变了造成迭代器失效导致的。

场景1：原始数据为1 2 3 4 5，开始it指向1不是偶数it++，it指向2是偶数后面数据往前移，数据为1 3 4 5此时it指向3然后it++，it指向4是偶数后面数据往前移，数据为1 3 5此时it指向5然后it++，v.end()指向5后面的位置it也指向5后面的位置结束循环，打印为1 3 5

场景2：原始数据为1 2 3 4，开始it指向1不是偶数it++，it指向2是偶数后面数据往前移，数据为1 3 4此时it指向3然后it++，it指向4是偶数_finish--，数据为1 3此时it指向3后面位置然后it++，此时v.end()指向3后面位置it指向3后面的后面位置，it和v.end()错过循环不会停止，运行到后面会越界

场景3：原始数据为10 2 3 4 5，开始it指向10是偶数后面数据往前移，数据为2 3 4 5此时it指向2然后it++，it指向3不是偶数it++，it指向4是偶数后面数据往前移，数据为2 3 5此时it指向5然后it++，v.end()指向5后面的位置it也指向5后面的位置结束循环，打印为2 3 5

场景4：原始数据为10 2 3 4，开始it指向10是偶数后面数据往前移，数据为2 3 4此时it指向2然后it++，it指向3不是偶数it++，it指向4是偶数_finish--，数据为2 3此时it指向3后面位置然后it++，此时v.end()指向3后面位置it指向3后面的后面位置，it和v.end()错过循环不会停止，运行到后面会越界

上面都是迭代器意义变了造成迭代器失效导致的错误，解决方式是如果it指向的位置是2的倍数erase删除之后it已经指向下一个数据，所以不再it++，如果it指向的位置不是2的倍数，it++指向下一个数据，如下图所示

erase函数的失效都是迭代器指向位置意义变了导致的失效（如果是最后一个数据前面的数据删除，那么实际迭代器指向位置的逻辑和我们逻辑不同，如果是尾删那么迭代器指向位置不在有效数据访问范围内）。一般erase函数不会使用缩容的方案，那么erase函数的迭代器失效也不存在野指针的失效。

总结：使用erase函数erase(pos)之后，迭代器pos的意义变了导致迭代器失效，但是不同平台下对于访问失效迭代器pos的反应是不一样的，我们用的时候一定要小心，统一以失效角度去看待

9.对于insert和erase函数造成的迭代器失效问题，Linux下g++平台检查很佛系，基本依靠操作系统自身野指针越界检查机制。windows下vs系列检查更严格，使用了一些强制检查机制，即使是意义变了也可能会检查出来

10.string类的insert和erase函数也存在迭代器失效的问题，但是string类的insert和erase函数声明如下，两个函数迭代器的版本用的很少，用的基本都是下标版本

11.如下图一所示使用杨辉三角的代码测试一下我们实现的vector类，运行结果出错并且程序崩溃了，如下图二所示

代码中我们在Solution类的generate成员函数里面先将结果vv打印了一遍，结果正确，在test_vector7()函数中将结果传给ret变量进行打印，结果出错并且程序崩溃。我们可以推测出结果出错并且程序崩溃的原因是test_vector7()函数中代码vector> ret = Solution().generate(5)。该代码调用Solution类的generate成员函数，将成员函数的返回值返回给ret，这里是传值返回，generate成员函数返回vv，vv进行一个临时拷贝，然后将临时拷贝的值再拷贝给ret变量，连续的拷贝构造编译器会进行优化，直接将vv拷贝给ret变量，这里的结果出错和程序崩溃应该就是因为拷贝构造函数出了问题

进一步分析，如下图一所示，代码vector> ret = Solution().generate(5)调用了拷贝构造函数，拷贝构造函数调用了使用迭代器区间进行构造的构造函数，使用迭代器区间进行构造的构造函数进行了尾插调用了push_back函数，push_back函数复用insert函数，insert函数在代码实现中如果存储已经有4个数据了，如下图二所示，那么需要reserve函数进行扩容，reserve函数里面扩容开好了空间使用memcpy将原数据内容拷贝过来，这里memcpy是进行浅拷贝，那么新空间和旧空间四个vector类型的数据同时指向四个空间，如下图三所示，随后delete[] _start释放旧空间，delete函数在释放旧空间的同时会调用析构函数将四个vector类型的数据指向的空间也释放掉，那么新空间前四个vector类型的数据指向的空间是已经被释放的空间，打印出来的数值是随机数，然后继续push_back新空间第五个vector类型的数据指向的空间插入新数据，第五个vector类型的数据指向的空间没有被释放，可以打印出来正确值。

最后程序运行结束，编译器调用析构函数对vector>类型的ret数据进行释放（此时ret指向的是新空间），而vector>类型的ret数据指向的新空间一部分空间已经被释放掉了，这部分空间进而二次释放系统崩溃

上面的这个问题就是更深层次的深浅拷贝问题，在vector中，当T是涉及需要深拷贝的类型时，如：string、vector等等，我们扩容使用memcpy拷贝数据是存在浅拷贝问题的。

解决方法是reserve函数里面不再使用memcpy函数，而是使用赋值来完成。如果是内置类型直接赋值，如果是自定义类型调用对应的赋值运算符重载函数，这样需要深拷贝的类型调用对应的赋值运算符重载函数，其赋值运算符重载函数实现的就是深拷贝功能，改进后的reserve函数代码实现如下图一所示，改进后运行结果如下图二所示