【STL】vector

向量（$vector$）是 $C$++ 标准模板库（$STL$）中封装的顺序容器（$SequenceContainer$），是一个能够存放任意类型的动态数组，能够增加和压缩数据。

前言 —— 序列式容器（sequence containers）

1. 容器的概观

一句话总结：容器，置物之所也。（存放数据 —— 数据结构）

研究数据的特定排序方式，以利于查找或排序或其他特殊目的，这一专门学科我们称为数据结构（$DataStructures$）。几乎可以说，任何特定的数据结构都是为了实现某种特定的算法。

$STL$ 容器即是将运用最广的一些数据结构实现出来：

$array$（数组）、$list$（链表）、$tree$（树）、$stack$（堆栈）、$queue$（队列）、$hashtable$（哈希表）、$set$（集合）、$map$（映射）$\cdot \cdot \cdot \cdot \cdot \cdot$ 等等。

2. 容器的分类

根据 $“$ 数据在容器中的排列 $”$ 特性，将这些数据结构分为序列式（$sequence$）和关联式（$associative$）两种：

各种容器之间存在内含（$containment$）关系。例如：

1. $heap$ 内含一个 $vector$

2. $priority\_queue$ 内含一个 $heap$

3. $stack$ 和 $queue$ 都含一个 $deque$

4. $set/map/multiset/multimap$ 都内含一个 $RB-tree$

5. $unordered\_x$ 都内含一个 $hashtable$

3. 序列式容器（sequence containers）

所谓序列式容器，其中的元素都可序（$ordered$），但未必有序（$sorted$）。

$C$++ $STL$ 中主要提供了以下序列式容器：

1. $array$（定长数组）

2. $vector$（变长数组）

3. $list$（双向链表）

4. $forward\_list$（单向链表）

5. $deque$（双端队列）

6. $stack$（栈）

7. $queue$（队列）

8. $priority\_queue$（优先队列）

其中，$stack$ 和 $queue$ 由于只是将 $deque$ 改头换面而成，技术上被归类为一种配接器（$adapter$），即其改变了容器的接口，被称为容器配接器（$containeradapter$）。

$array$ 和 $forward\_list$ 都是 $C$++ $11$ 才引入的新容器。

一、vector 的介绍

$vector$ 其实就是顺序表。在实际应用中非常的重要且非常的好用。因此我们要熟悉其常用的接口，会使用，再到了解其底层，知其然且知其所以然。一些不常用的或者忘记的内容可以直接去查 $C$++ 官方文档：$vector$ 的文档介绍。

二、vector 的使用（常用接口）

下面只列举了 $vector$ 最常用的几个接口，更多详细信息可以自行查官方文档：$vector$。

可以看出 $vector$ 真正采用模板：
$$template<classT,classAlloc=allocator<T>>classvector;$$

1. 常见构造

void test1()
{
	//1.无参构造
	vector<int> v1;
	
	//2.带参构造
	vector<int> v2(10);
	
	//3.构造+初始化（10个1）
	vector<int> v3(10, 1);
	
	//4.迭代器构造
	vector<int> v4(v2.begin() + 2, v2.end() - 3);
	
	//5.拷贝构造
	vector<int> v5(v3);

	cout << "v1：";
	for (auto i : v1) cout << i;
	cout << endl << "v2：";
	
	for (auto i : v2) cout << i;
	cout << endl << "v3：";
	
	for (auto i : v3) cout << i;
	cout << endl << "v4：";
	
	for (auto i : v4) cout << i;
	cout << endl << "v5：";
	
	for (auto i : v5) cout << i;
	cout << endl;
}

2. iterator 的使用

void test2()
{
	vector<int> v;
	for (int i = 0; i < 10; i++) v.push_back(i);
	
	//正向迭代器
	vector<int>::iterator it = v.begin();
	cout << "iterator：        ";
	while (it != v.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;

	vector<int>::const_iterator cit = v.begin();
	cout << "const_iterator：  ";
	while (cit != v.end())
	{
		cout << *cit << " ";
		cit++;
	}
	cout << endl;

	//反向迭代器
	vector<int>::reverse_iterator rit = v.rbegin();
	cout << "reverse_iterator：";
	while (rit != v.rend())
	{
		cout << *rit << " ";
		rit++;
	}
	cout << endl;
}

3. 容量操作

void print(const vector<int>& v)
{
	cout << "size：" << v.size() << endl;
	cout << "v：";
	for (int i = 0; i < v.size(); i++) cout << v[i] << " ";
	v.empty() == true ? cout << endl << "empty true" : cout << endl << "empty false";
	cout << endl << endl;
}

void test3()
{
	vector<int> v;
	for (int i = 0; i < 10; i++) v.push_back(i);
	print(v);

	v.resize(5);	
	print(v);

	v.resize(8, 10);
	print(v);
	
	v.resize(12);	
	print(v);

	v.resize(0);	
	print(v);
}

void test4()
{
	vector<int> v;
	int size = v.capacity();
	cout << "making v grow：" << endl;
	for (int i = 0; i < 100; i++)
	{
		v.push_back(i);
		if (size != v.capacity())
		{
			size = v.capacity();
			cout << "capacity changed：" << size << endl;
		}
	}
}

$vs$ 下使用的 $STL$ 基本是按照 $1.5$ 倍方式扩容：

直接使用 $reserve$ 预留空间来避免 $/$ 减少扩容：

void test5()
{
	vector<int> v;
	//使用reserve预留空间，减少扩容
	v.reserve(100);
	int size = v.capacity();
	cout << "making vector grow：" << endl;
	for (int i = 0; i < 100; i++)
	{
		v.push_back(i);
		if (size != v.capacity())
		{
			size = v.capacity();
			cout << "capacity changed：" << size << endl;
		}
	}
}

$reserve$ 既不会缩容，也不会改变大小：

void test6()
{
	vector<int> v(10, 1);
	cout << "size：    " << v.size() << endl;
	cout << "capacity：" << v.capacity() << endl << endl;

	//会增容且不改变大小
	v.reserve(20);
	cout << "size：    " << v.size() << endl;
	cout << "capacity：" << v.capacity() << endl << endl;

	//不会缩容且不改变大小
	v.reserve(5);
	cout << "size：    " << v.size() << endl;
	cout << "capacity：" << v.capacity() << endl << endl;
}

总结：

1. $capacity$ 的代码在 $vs$ 和 $g$++ 下分别运行会发现：$vs$ 下 $capacity$ 是按 $1.5$ 倍增长的，$g$++ 是按 $2$ 倍增长的。

注意：$vs$ 是 $PJ$ 版本 $STL$，$g$++ 是 $SGI$ 版本 $STL$（具体增长多少是根据具体的需求定义的，思维不要固化）。

2. $reserve$ 只负责开辟空间，如果确定知道需要用多少空间，$reserve$ 可以缓解 $vector$ 增容的代价缺陷问题。

3. $resize$ 在开空间的同时还会进行初始化，影响 $size$。

4. 增删查改

使用 $push\_back()$ 和 $pop\_back()$ 插入删除：

void test7()
{
	vector<int> v;

	//尾插
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);

	for (int i = 0; i < v.size(); i++) cout << v[i] << " ";
	cout << endl;

	//尾删
	v.pop_back();
	v.pop_back();

	for (int i = 0; i < v.size(); i++) cout << v[i] << " ";
	cout << endl;
}

使用 $insert()$ 和 $erase()$ 在指定位置插入删除（只能使用迭代器）：

void test8()
{
	//C++11新语法：使用列表方式初始化
	vector<int> v{ 1,2,3,4,5 };
	for (auto i : v) cout << i << " "; cout << endl << endl;

	// 在指定位置前插入值为val的元素，比如：3之前插入30,如果没有则不插入
	// 注意：vector没有提供find方法，如果要查找只能使用STL提供的全局find
	
	// 1.先使用find查找3所在位置
	vector<int>::iterator pos = find(v.begin(), v.end(), 3);
	
	// 如果没有找到会返回 v.end()
	if (pos != v.end())
	{
		// 2.在pos位置之前插入10
		v.insert(pos, 10);					
	}
	for (auto i : v) cout << i << " "; cout << endl << endl;
	
	// 在0位置（头删）删除元素
	v.erase(v.begin());
	for (auto i : v) cout << i << " "; cout << endl << endl;

	//删除所有元素
	v.erase(v.begin(), v.end());
	v.empty() == true ? cout << "empty true" << endl : cout << "empty false" << endl;
}

注意：$C$++ $11$ 之后支持列表初始化：vector<int> v{ 1,2,3,4,5 };，非常方便。

三、vector 迭代器失效问题（重点）

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

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

1. 会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back 等。

vector<int> v{ 1,2,3,4,5,6 };
for (auto i : v) cout << i << " ";
cout << endl;

int x; cin >> x;
auto p = find(v.begin(), v.end(), x);
if (p != v.end())
{
	//insert以后pos就失效了，不要直接访问
	//v.insert(p, 10);
	//*p *= 10;
	//要访问就要更新这个失效迭代器的值
	p = v.insert(p, 10);	//insert要返回新pos
	*(p+1) *= 11;
}
for (auto i : v) cout << i << " ";
cout << endl;

因此，如 $insert$ 操作在标准库中的实现是返回一个迭代器指向插入位置的元素，就是为了避免迭代器失效的问题，所以以后如果要访问 $pos$ 位置元素，要更新一下再访问：pos = insert(pos,val);。

2. 指定位置元素的删除操作 $——$ erase

vector<int> v{ 1,2,3,4 };

auto pos = find(v.begin(), v.end(), 3);

// 删除pos位置的数据，导致pos迭代器失效。
v.erase(pos);

cout << *pos << endl; // 此处会导致非法访问

$erase$ 删除 $pos$ 位置元素后，$pos$ 位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果 $pos$ 刚好是最后一个元素，删完之后 $pos$ 刚好是 $end$ 的位置，而 $end$ 位置是没有元素的，那么 $pos$ 就失效了。因此删除 $vector$ 中任意位置上元素时，$vs$ 就认为该位置迭代器失效了。

以下代码的功能是删除 $vector$ 中所有的偶数，请问那个代码是正确的，为什么？

//要求删除所有的偶数
void test1()
{
	vector<int> v{ 1,2,3,4 };
	
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
			v.erase(it);
		++it;
	}
	
	for(auto i : v) cout << i << " "; 
	cout << endl;
}

$test1$ 报错：

//要求删除所有的偶数
void test2()
{
	vector<int> v{ 1,2,3,4 };
	
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
			it = v.erase(it);
		else
			++it;
	}
	
	for(auto i : v) cout << i << " "; 
	cout << endl;
}

$test2$ 正常运行：

因此，$erase$ 在标准库中的实现是返回一个迭代器指向删除位置的下一个元素，就是为了避免迭代器失效的问题，所以如果以后要访问 $pos$ 位置元素，要更新一下再访问：pos = erase(pos);。

注意：$Linux$ 下，$g$++ 编译器对迭代器失效的检测并不是非常严格，处理也没有 $vs$ 下极端。

// 1. 扩容之后，迭代器已经失效了，程序虽然可以运行，但是运行结果已经不对了
int main()
{
	vector<int> v{1,2,3,4,5};
	for(size_t i = 0; i < v.size(); ++i)
		cout << v[i] << " ";
	cout << endl;
	auto it = v.begin();
	cout << "扩容之前，vector的容量为: " << v.capacity() << endl;
	// 通过reserve将底层空间设置为100，目的是为了让vector的迭代器失效
	v.reserve(100);
	cout << "扩容之后，vector的容量为: " << v.capacity() << endl;
	// 经过上述reserve之后，it迭代器肯定会失效，在vs下程序就直接崩溃了，但是linux
	下不会
	// 虽然可能运行，但是输出的结果是不对的
	while(it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	return 0;
}

程序输出：
1 2 3 4 5
扩容之前，vector的容量为: 5
扩容之后，vector的容量为: 100
0 2 3 4 5 409 1 2 3 4 5

// 2. erase删除任意位置代码后，linux下迭代器并没有失效
// 因为空间还是原来的空间，后序元素往前搬移了，it的位置还是有效的
#include <vector>
#include <algorithm>
int main()
{
	vector<int> v{1,2,3,4,5};
	vector<int>::iterator it = find(v.begin(), v.end(), 3);
	v.erase(it);
	cout << *it << endl;
	while(it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	return 0;
}

程序可以正常运行，并打印：
4
4 5

// 3: erase删除的迭代器如果是最后一个元素，删除之后it已经超过end
// 此时迭代器是无效的，++it导致程序崩溃
int main()
{
	vector<int> v{1,2,3,4,5};
	// vector<int> v{1,2,3,4,5,6};
	auto it = v.begin();
	while(it != v.end())
	{
		if(*it % 2 == 0)
		v.erase(it);
		++it;
	}
	for(auto e : v)
		cout << e << " ";
	cout << endl;
	return 0;
}

========================================================
// 使用第一组数据时，程序可以运行
[sly@VM-0-3-centos 20220114]$ g++ testVector.cpp -std=c++11
[sly@VM-0-3-centos 20220114]$ ./a.out
1 3 5
=========================================================
// 使用第二组数据时，程序最终会崩溃
[sly@VM-0-3-centos 20220114]$ vim testVector.cpp
[sly@VM-0-3-centos 20220114]$ g++ testVector.cpp -std=c++11
[sly@VM-0-3-centos 20220114]$ ./a.out
Segmentation fault

从上述三个例子中可以看到：$SGISTL$ 中，迭代器失效后，代码并不一定会崩溃，但是运行结果肯定不对，如果 $it$ 不在 $begin$ 和 $end$ 范围内，肯定会崩溃的。

与 $vector$ 类似，$string$ 在插入 $+$ 扩容操作 $+$ $erase$ 之后，迭代器也会失效

string s("hello");
auto it = s.begin();
// 放开之后代码会崩溃，因为resize到20会string会进行扩容
// 扩容之后，it指向之前旧空间已经被释放了，该迭代器就失效了
// 后序打印时，再访问it指向的空间程序就会崩溃
//s.resize(20, '!');
while (it != s.end())
{
	cout << *it;
	++it;
}
cout << endl;
it = s.begin();
while (it != s.end())
{
	it = s.erase(it);
	// 按照下面方式写，运行时程序会崩溃，因为erase(it)之后
	// it位置的迭代器就失效了
	// s.erase(it);
	++it;
}

虽然 $string$ 也会有迭代器失效的问题，但是我们一般使用 $string$ 都是通过下标访问，不经常用迭代器。

迭代器失效解决办法：在使用前，对迭代器重新赋值即可。

四、vector 的深度剖析

在 《$STL$源码剖析》 这本书中，根据 $SGISTL$ 源代码 <stl_vector.h> 分析出 $vector$ 的实现如下：

$vector$ 所采用的数据结构非常简单：线性连续空间。

它以两个迭代器 $start$ 和 $finish$ 分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器 $end\_of\_storage$ 指向整块连续空间（含备用空间）的尾端：

template <class T, class Alloc = alloc>
class vector
{
public:
	typedef T 			value_type;
	typedef value_type*	iterator;
...
protected:
	iterator start;				//表示目前使用空间的头
	iterator finish;			//表示目前使用空间的尾
	iterator end_of_storage;	//表示目前可用空间的尾
...
};

运用 $start$，$finish$，$end\_of\_storage$ 三个迭代器，便可轻松提供首尾标识begin()+end()、大小size()、容量capacity()、空容器判断empty()、注标运算子[] ··· 等机能：

template <class T, class Alloc = alloc>
class vector
{
...
public:
	typedef T 			value_type;
	typedef value_type*	iterator;
	typedef value_type& reference;
	typedef size_t 		size_type;

	iterator begin() { return start; }
	iterator end() { return finish; }

	size_type size() const { return end() - begin(); }
	size_type capacity() const { return end_of_storage - begin(); }

	bool empty() const { return begin() == end(); }
	reference operator [] (size_type n) { return *(begin() + n); }
...
};

1. 内置类型构造函数

对于模板类型变量给缺省值的时候为了考虑类类型变量，因此缺省值会直接给默认构造函数（匿名对象），如 $resize$ 函数：void resize (size_t n, T val = T());

此时，对于类类型可以有默认构造函数，那么 $T$ 也有可能是内置类型，这个时候编译器会自动优化：

/*内置类型*/

int i(1);						//构造函数
int j = int();					//默认构造->匿名对象->拷贝构造
int k = int(2);					//构造函数->匿名对象->拷贝构造
cout << i << " " << j << " " << k << endl;

char ic('a');					//构造函数
char jc = char();				//默认构造->匿名对象->拷贝构造
char kc = char('b');			//构造函数->匿名对象->拷贝构造
cout << ic << " " << jc << " " << kc << endl;

double id(1.1);					//构造函数
double jd = double();			//默认构造->匿名对象->拷贝构造
double kd = double(2.2);		//构造函数->匿名对象->拷贝构造
cout << id << " " << jd << " " << kd << endl;

/*自定义类型*/

string is("hello");				//构造函数
string js = string();			//默认构造->匿名对象->拷贝构造
string ks = string("world");	//构造函数->匿名对象->拷贝构造
cout << is << " " << js << " " << ks << endl;

可见，为了适配模板类型函数给缺省值时要调用构造函数初始化，对于内置类型，编译器自动优化（相当于给内置类型一个构造函数）。

2. 使用 memcpy 拷贝问题

当我们自己实现一个 $vector$ 的成员函数 $reserve$ 时，会用到 $memcpy$ 将原来需要扩容的空间直接拷贝给重新动态开辟的一块空间 $tmp$：

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t old_size = size();

		T* tmp = new T[n];
		memcpy(tmp, _start, sizeof(T) * old_size);

		delete[] _start;
		_start = tmp;
		_finish = tmp + old_size;
		_end_of_storage = tmp + n;
	}
}

这时就造成了这么一个问题 —— $memcpy$ 是浅拷贝，如果拷贝前的空间有指针指向其他的空间（需要深拷贝），如：$string$ 类型，在拷贝完后原来指针所指向的空间会直接释放掉，因此拷贝到的指针指向的空间就被释放掉了。

namespace bite	//bite代表自己实现的vector的reserve版本（使用memcpy拷贝）
{
	int main()
	{
		vector<string> v;
		v.push_back("1111");
		v.push_back("2222");
		v.push_back("3333");
		return 0;
	}
}

问题分析：

1. $memcpy$ 是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存
   空间中（浅拷贝）。

2. 如果拷贝的是内置类型的元素，$memcpy$ 既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时（需要深拷贝），就会出错，因为 $memcpy$ 的拷贝实际是浅拷贝。

结论：如果对象中涉及到资源管理时，千万不能使用 $memcpy$ 进行对象之间的拷贝，因为 $memcpy$ 是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。

3. 动态二维数组理解

vector<T> 是模板类型，因此 $T$ 不仅可以是内置类型，也可以是自定义类型，如：string、vector $\cdot \cdot \cdot$ 等。当 $T$ 这个类型为 vector<T> v 的时候，vector<vector<T>> vv 就代表了 $vv$ 里面每一个元素存放的都是一个 vector<T> v（地址），即可以理解为二维数组。

vector<vector<int>> vv(n) 构造一个 $vv$ 动态二维数组，$vv$ 中总共有 $n$ 个元素，每个元素都是 $vector$ 类型的，每行没有包含任何元素，如果 $n$ 为 $5$ 时如下所示：

$vv$ 中元素填充完成之后，如下图所示：

二维数组的遍历（$3$ 种方式）：

1. $operator[]$ 遍历：

vector<vector<int>> vv1(5, vector<int>(5, 1));	//匿名对象赋值
for (int i = 0; i < vv1.size(); i++)
{
	for (int j = 0; j < vv1[i].size(); j++)
	{
		cout << vv1[i][j] << " ";
		//cout << vv1.operator[](i).operator[](j) << " ";
	}
	cout << endl;
}
cout << endl;

2. 迭代器遍历：

vector<vector<int>> vv2(5, vector<int>(5, 2));	//匿名对象赋值
for (auto it = vv2.begin(); it != vv2.end(); ++it)
{
	for (auto _it = it->begin(); _it != it->end(); ++_it)
	{
		cout << *_it << " ";
	}
	cout << endl;
}
cout << endl;

3. 范围 $for$ 遍历：

vector<vector<int>> vv3(5, vector<int>(5, 3));	//匿名对象赋值
for (auto& v : vv3)
{
	for (auto& i : v)
	{
		cout << i << " ";
	}
	cout << endl;
}
cout << endl;

运行结果如下：

五、vector 的模拟实现

因为 $vector$ 隶属于 $C$++ $STL$ 容器，即标准模板库。因此，由于模板不能分开写到两个文件里，所以之前对于类的声明和定义分离写到两个文件中是不可取的。从今往后，只要带模板的类，都只能写到一个文件中，但是声明和定义可以分离：声明写到类里面（类外要重新写模板参数），定义写到类外面，或者把所有东西都写到类里面（类内部默认为内联 $inline$）。

因此，总共分为两个文件：$vector.h$ 用来存放 $vector$ 的定义和实现；$test.cpp$ 用来测试。

注意：这里两个文件中的 $vector$ 都是自己定义的，为了和 $std::vector$ 作区分，我们要单独创建一个命名空间，这里我用的是 $namespaceybc$ 。

1. $vector.h$

#pragma once
#include<iostream>
#include<vector>
#include<list>
#include<string>
#include<assert.h>

using namespace std;

namespace ybc
{
	template<class T>

	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;

		/*vector()
		{}*/

		// C++11 前置生成默认构造
		vector() = default;

		//类模板的成员函数，还可以继续是函数模板
		template<class InputIterator>	//任意类型的迭代器初始化
		vector(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				this->push_back(*first);
				++first;
			}
		}

		vector(int n, const T& val = T())
		{
			reserve(n);
			for (size_t i = 0; i < n; i++)
			{
				push_back(val);
			}
		}

		vector(const vector<T>& v)
		{
			reserve(v.size());
			for (auto& i : v)
			{
				push_back(i);
				//this->push_back(i);
			}
		}

		void clear()
		{
			_finish = _start;
		}

		/*//传统写法
		vector<T>& operator = (const vector<T>& v)
		{
			if (this != &v)
			{
				clear();
				reserve(v.size());
				for (auto& i : v)
				{
					push_back(i);
					//this->push_back(i);
				}
			}
			return *this;
		}*/

		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<T>& operator = (vector<T> v)
		{
			swap(v);	//拷贝构造传参直接交换（编译器甚至会优化）
			return *this;
		}

		~vector()
		{
			if (_start != nullptr)
			{
				delete[] _start;
				_start = _finish = _end_of_storage = 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 _end_of_storage - _start;
		}

		bool empty() const
		{
			return _start == _finish;
		}

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t old_size = size();

				T* tmp = new T[n];
				//memcpy(tmp, _start, sizeof(T) * old_size); //浅拷贝
				for (size_t i = 0; i < old_size; i++)
				{
					tmp[i] = _start[i];	//类类型会调用赋值重载（深拷贝）
				}
				delete[] _start;

				_start = tmp;
				_finish = tmp + old_size;
				_end_of_storage = tmp + n;
			}
		}

		//主要是用来初始化
		void resize(size_t n, const T& val = T())	//调用默认构造构造一个匿名对象给缺省值（不确定T的类型）
		{											//编译器会优化：内置类型也有构造函数的概念
			if (n < size())
			{
				_finish = _start + n;
			}
			else
			{
				reserve(n);
				while (_finish < _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
		}

		void push_back(const T& x)
		{
			//扩容
			if (_finish == _end_of_storage)
			{
				reserve(capacity() == 0 ? 4 : capacity() * 2);
			}
			*_finish = x;
			++_finish;
		}

		void pop_back()
		{
			assert(!empty());
			--_finish;
		}

		iterator insert(iterator pos, const T& x)
		{
			assert(pos >= _start && pos <= _finish);
			//扩容
			if (_finish == _end_of_storage)
			{
				//迭代器失效
				size_t len = pos - _start;
				reserve(capacity() == 0 ? 4 : capacity() * 2);
				pos = _start + len;
			}
			iterator end = _finish;
			while (end > pos)
			{
				*end = *(end - 1);
				--end;
			}
			*pos = x;
			++_finish;
			return pos;
		}

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

		T& operator [] (size_t i)
		{
			assert(i < size());
			return _start[i];
		}

		const T& operator [] (size_t i) const
		{
			assert(i < size());
			return _start[i];
		}

	private:
		iterator _start = nullptr;
		iterator _finish = nullptr;
		iterator _end_of_storage = nullptr;
	};
}

2. $test.cpp$

#include"vector.h"

namespace ybc
{
	template<class T>
	void print_vector(const vector<T>& v)
	{
		//规定：没有实例化的类模板里面取东西，编译器不能区分这里的const_iterator是类型还是静态成员变量
		//typename vector<T>::const_iterator it = v.begin()

		//1.迭代器遍历
		for (auto it = v.begin(); it != v.end(); it++)
		{
			cout << *it << " ";
		}
		cout << endl;

		//2.范围for遍历
		for (const auto& i : v)
		{
			cout << i << " ";
		}
		cout << endl;
	}

	void test1()
	{
		vector<int> v;
		//下标遍历
		for (int i = 0; i < 10; ++i)
		{
			v.push_back(i);
			cout << v[i] << " ";
		}
		cout << endl;

		print_vector(v);
		cout << endl;

		vector<double> vd;
		//下标遍历
		for (int i = 0; i < 10; ++i)
		{
			vd.push_back(i * 1.1);
			cout << vd[i] << " ";
		}
		cout << endl;

		print_vector(vd);
	}

	void test2()
	{
		std::vector<int> v{ 1,2,3,4,5,6 };
		for (auto i : v) cout << i << " ";
		cout << endl;

		int x; cin >> x;
		auto p = find(v.begin(), v.end(), x);
		if (p != v.end())
		{
			//insert以后pos就失效了，不要直接访问
			//v.insert(p, 10);
			//*p *= 10;
			//要访问就要更新这个失效迭代器的值
			p = v.insert(p, 10);	//insert要返回新pos
			*(p + 1) *= 11;
		}
		for (auto i : v) cout << i << " ";
		cout << endl;
	}

	void test3()
	{
		vector<int> v;

		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);

		for (auto i : v) cout << i << " "; cout << endl;

		//要求删除所有的偶数
		for (auto it = v.begin(); it != v.end();)
		{
			if (*it % 2 == 0)
				it = v.erase(it);
			else
				++it;
		}
		for (auto i : v) cout << i << " "; cout << endl;

	}

	void test4()
	{
		/*内置类型*/

		int i(1);		//构造函数
		int j = int();	//默认构造->匿名对象->拷贝构造
		int k = int(2);	//构造函数->匿名对象->拷贝构造

		cout << "int：   " << i << " " << j << " " << k << endl;

		char ic('a');		//构造函数
		char jc = char();	//默认构造->匿名对象->拷贝构造
		char kc = char('b');//构造函数->匿名对象->拷贝构造

		cout << "char：  " << ic << " " << jc << " " << kc << endl;

		double id(1.1);			//构造函数
		double jd = double();	//默认构造->匿名对象->拷贝构造
		double kd = double(2.2);//构造函数->匿名对象->拷贝构造

		cout << "double：" << id << " " << jd << " " << kd << endl;

		/*自定义类型*/

		string is("hello");			//构造函数
		string js = string();		//默认构造->匿名对象->拷贝构造
		string ks = string("world");//构造函数->匿名对象->拷贝构造

		cout << "string：" << is << " " << js << " " << ks << endl;
	}

	void test5()
	{
		vector<int> v;

		v.resize(10, 2);
		v.reserve(20);

		cout << "size：    " << v.size() << endl;
		cout << "capacity：" << v.capacity() << endl;
		cout << endl;

		for (auto i : v) cout << i << " "; cout << endl;
	}

	template<class Containers>
	void print(const Containers& v)
	{
		for (const auto& i : v)
		{
			cout << i << " ";
		}
		cout << endl;
	}

	void test6()
	{
		//默认构造
		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(5);
		cout << "v1："; print(v1);

		//拷贝构造
		vector<int> v2 = v1;
		cout << "v2："; print(v1);

		//赋值重载
		vector<int> v3;
		v3 = v1;
		cout << "v3："; print(v1);

		//迭代器构造
		vector<int> v4(v1.begin(), v1.end());
		cout << "v4："; print(v4);

		list<int> l{ 1,2,3,4 };
		vector<int> v5(l.begin(), l.end());
		cout << "v5："; print(v5);

		//n个val初始化
		vector<string> v6(10, "hi");
		cout << "v6："; print(v6);

		vector<int> v7(10, 1);	//会调用参数最匹配的构造函数：这里10和1默认为int类型
		cout << "v7："; print(v7);

		//memcpy拷贝问题
		vector<string> v8;
		v8.push_back("111111");
		v8.push_back("222222");
		v8.push_back("333333");
		v8.push_back("444444");
		v8.push_back("555555");
		cout << "v8："; print(v8);

		v8.push_back("666666");
		v8.push_back("777777");
		cout << "v8："; print(v8);
	}
}

int main()
{
	//ybc::test1();

	//ybc::test2();

	//ybc::test3();

	//ybc::test4();

	//ybc::test5();

	ybc::test6();

	return 0;
}

总结

$vector$ 是 $STL$ 封装好的一块能够动态开辟连续空间的模板类。随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。因此，$vector$ 的运用对于内存的合理利用与运用的灵活性有很大的帮助，我们再也不必因为害怕空间不足而一开始就要求使用定长数组，或者遭受自己动态开辟释放空间的麻烦，我们可以安心使用 $vector$，用多少开辟多少。