1.vector的介绍及使用

1.1 vector的介绍

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

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

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

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

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

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

使用 STL 的三个境界：能用，明理，能扩展 ，那么下面学习 vector，我们也是按照这个方法去学习

当然也可以借助文档来学习 http://www.cplusplus.com/reference/vector/vector/

1.2 vector的使用

vector 学习时一定要学会查看文档，vector在实际中非常的重要，在实际中我们熟悉常

见的接口就可以，下面列出了 哪些接口是要重点掌握的 。

1.2.1 vector的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
using namespace std;
#include <vector>
 
////////////////////////////////////////////////////////////////////
//    vector的构造
////////////////////////////////////////////////////////////////////
int TestVector1()
{
	// constructors used in the same order as described above:
	vector<int> first;                                // empty vector of ints
	vector<int> second(4, 100);                       // four ints with value 100
	vector<int> third(second.begin(), second.end());  // iterating through second
	vector<int> fourth(third);                       // a copy of third
 
	// 下面涉及迭代器初始化的部分，我们学习完迭代器再来看这部分
	// the iterator constructor can also be used to construct from arrays:
	int myints[] = { 16,2,77,29 };
	vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));
 
	cout << "The contents of fifth are:";
	for (vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)
		cout << ' ' << *it;
	cout << '\n';
 
	return 0;
}

1.2.2 vector iterator的使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
////////////////////////////////////////////////////////////////////////
//  vector的迭代器
////////////////////////////////////////////////////////////////////////
void PrintVector(const vector<int>& v)
{
	// const对象使用const迭代器进行遍历打印
	vector<int>::const_iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}
 
void TestVector2()
{
	// 使用push_back插入4个数据
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
 
	// 使用迭代器进行遍历打印
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
 
	// 使用迭代器进行修改
	it = v.begin();
	while (it != v.end())
	{
		*it *= 2;
		++it;
	}
 
	// 使用反向迭代器进行遍历再打印
	// vector<int>::reverse_iterator rit = v.rbegin();
	auto rit = v.rbegin();
	while (rit != v.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;
 
	PrintVector(v);
}

1.2.3 vector 空间增长问题

capacity 的代码在 vs 和 g++ 下分别运行会发现， vs 下 capacity 是按 1.5 倍增长的， g++ 是按 2 倍增长的 。 这个问题经常会考察，不要固化的认为，vector 增容都是 2 倍，具体增长多少是根据具体的需求定义 的。vs 是 PJ 版本 STL ， g++ 是 SGI 版本 STL 。

reserve 只负责开辟空间，如果确定知道需要用多少空间， reserve 可以缓解 vector 增容的代价缺陷问 题。 resize在开空间的同时还会进行初始化，影响 size 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 测试vector的默认扩容机制
void TestVectorExpand()
{
	size_t sz;
	vector<int> v;
	sz = v.capacity();
	cout << "making v grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}
//vs：运行结果：vs下使用的STL基本是按照1.5倍方式扩容
//making foo grow :
//capacity changed : 1
//capacity changed : 2
//capacity changed : 3
//capacity changed : 4
//capacity changed : 6
//capacity changed : 9
//capacity changed : 13
//capacity changed : 19
//capacity changed : 28
//capacity changed : 42
//capacity changed : 63
//capacity changed : 94
//capacity changed : 141
//g++运行结果：linux下使用的STL基本是按照2倍方式扩容
//making foo grow :
//capacity changed : 1
//capacity changed : 2
//capacity changed : 4
//capacity changed : 8
//capacity changed : 16
//capacity changed : 32
//capacity changed : 64
//capacity changed : 128
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 如果已经确定vector中要存储元素大概个数，可以提前将空间设置足够
// 就可以避免边插入边扩容导致效率低下的问题了
void TestVectorExpandOP()
{
	vector<int> v;
	size_t sz = v.capacity();
	v.reserve(100); // 提前将容量设置好，可以避免一遍插入一遍扩容
	cout << "making bar grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}

接口演示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
////////////////////////////////////////////////////////////////////////
//  vector的resize 和 reserve
////////////////////////////////////////////////////////////////////////
// reisze(size_t n, const T& data = T())
// 将有效元素个数设置为n个，如果时增多时，增多的元素使用data进行填充
// 注意：resize在增多元素个数时可能会扩容
void TestVector3()
{
	vector<int> v;
 
	// set some initial content:
	for (int i = 1; i < 10; i++)
		v.push_back(i);
 
	v.resize(5);
	v.resize(8, 100);
	v.resize(12);
 
	cout << "v contains:";
	for (size_t i = 0; i < v.size(); i++)
		cout << ' ' << v[i];
	cout << '\n';
}
 
// 测试vector的默认扩容机制
// vs：按照1.5倍方式扩容
// linux：按照2倍方式扩容
void TestVectorExpand()
{
	size_t sz;
	vector<int> v;
	sz = v.capacity();
	cout << "making v grow:\n";
	for (int i = 0; i < 100; ++i) 
	{
		v.push_back(i);
		if (sz != v.capacity()) 
		{
			sz = v.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}
 
// 往vecotr中插入元素时，如果大概已经知道要存放多少个元素
// 可以通过reserve方法提前将容量设置好，避免边插入边扩容效率低
void TestVectorExpandOP()
{
	vector<int> v;
	size_t sz = v.capacity();
	v.reserve(100);   // 提前将容量设置好，可以避免一遍插入一遍扩容
	cout << "making bar grow:\n";
	for (int i = 0; i < 100; ++i) 
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}

1.2.4 vector 增删查改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
////////////////////////////////////////////////////////////////////////
//  vector的增删改查
////////////////////////////////////////////////////////////////////////
// 尾插和尾删：push_back/pop_back
void TestVector4()
{
	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()) 
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
 
	v.pop_back();
	v.pop_back();
 
	it = v.begin();
	while (it != v.end()) 
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}
 
// 任意位置插入：insert和erase，以及查找find
// 注意find不是vector自身提供的方法，是STL提供的算法
void TestVector5()
{
	// 使用列表方式初始化，C++11新语法
	vector<int> v{ 1, 2, 3, 4 };
 
	// 在指定位置前插入值为val的元素，比如：3之前插入30,如果没有则不插入
	// 1. 先使用find查找3所在位置
	// 注意：vector没有提供find方法，如果要查找只能使用STL提供的全局find
	auto pos = find(v.begin(), v.end(), 3);
	if (pos != v.end())
	{
		// 2. 在pos位置之前插入30
		v.insert(pos, 30);
	}
 
	vector<int>::iterator it = v.begin();
	while (it != v.end()) 
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
 
	pos = find(v.begin(), v.end(), 3);
	// 删除pos位置的数据
	v.erase(pos);
 
	it = v.begin();
	while (it != v.end()) {
		cout << *it << " ";
		++it;
	}
	cout << endl;
}
 
// operator[]+index 和 C++11中vector的新式for+auto的遍历
// vector使用这两种遍历方式是比较便捷的。
void TestVector6()
{
	vector<int> v{ 1, 2, 3, 4 };
 
	// 通过[]读写第0个位置。
	v[0] = 10;
	cout << v[0] << endl;
 
	// 1. 使用for+[]小标方式遍历
	for (size_t i = 0; i < v.size(); ++i)
		cout << v[i] << " ";
	cout << endl;
 
	vector<int> swapv;
	swapv.swap(v);
 
	cout << "v data:";
	for (size_t i = 0; i < v.size(); ++i)
		cout << v[i] << " ";
	cout << endl;
 
	// 2. 使用迭代器遍历
	cout << "swapv data:";
	auto it = swapv.begin();
	while (it != swapv.end())
	{
		cout << *it << " ";
		++it;
	}
 
	// 3. 使用范围for遍历
	for (auto x : v)
		cout << x << " ";
	cout << endl;
}

1.2.5 vector 迭代器失效问题。（重点）

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
using namespace std;
#include <vector>
int main()
{
	vector<int> v{ 1,2,3,4,5,6 };
 
	auto it = v.begin();
 
	// 将有效元素个数增加到100个，多出的位置使用8填充，操作期间底层会扩容
	// v.resize(100, 8);
 
	// reserve的作用就是改变扩容大小但不改变有效元素个数，操作期间可能会引起底层容量改变
	// v.reserve(100);
 
	// 插入元素期间，可能会引起扩容，而导致原空间被释放
	// v.insert(v.begin(), 0);
	// v.push_back(8);
 
	// 给vector重新赋值，可能会引起底层容量改变
	v.assign(100, 8);
 
	/*
	出错原因：以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉，
   而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的
   空间，而引起代码运行时崩溃。
	解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给it重新
   赋值即可。
	*/
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	return 0;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
#include <vector>
int main()
{
	int a[] = { 1, 2, 3, 4 };
	vector<int> v(a, a + sizeof(a) / sizeof(int));
	// 使用find查找3所在位置的iterator
	vector<int>::iterator pos = find(v.begin(), v.end(), 3);
	// 删除pos位置的数据，导致pos迭代器失效。
	v.erase(pos);
	cout << *pos << endl; // 此处会导致非法访问
	return 0;
}

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
using namespace std;
#include <vector>
int main()
{
	int a[] = { 1, 2, 3, 4 };
	vector<int> v(a, a + sizeof(a) / sizeof(int));
	// 使用find查找3所在位置的iterator
	vector<int>::iterator pos = find(v.begin(), v.end(), 3);
	// 删除pos位置的数据，导致pos迭代器失效。
	v.erase(pos);
	cout << *pos << endl; // 此处会导致非法访问
	return 0;
}
 
#include <iostream>
using namespace std;
#include <vector>
int main()
{
	vector<int> v{ 1, 2, 3, 4 };
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
			v.erase(it);
		++it;
	}
 
	return 0;
}
int main()
{
	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;
	}
	return 0;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream>
using namespace std;
#include <vector>
int main()
{
	vector<int> v{ 1, 2, 3, 4 };
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
			v.erase(it);
		++it;
	}
 
	return 0;
}
int main()
{
	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;
	}
	return 0;
}
 
 
// 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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <string>
void TestString()
{
	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;
	}
}

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

2.vector深度剖析及模拟实现

2.1 std::vector的核心框架接口的模拟实现xyl::vector

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
#pragma once
#include <assert.h>
 
namespace xyl
{
	template <class T>
	
	class vector                                                                                                                                                                                                                     
	{
	public:
		typedef T* iterator;
			typedef const T* const_iterator;
 
 
		vector()
			:_start(nullptr)
			, _finish ( nullptr)
			, _endOfStorage (nullptr)
		{
			
		}
 
		vector(int n, const T& value = T())
             :_start(nullptr)
             , _finish ( nullptr)
             , _endOfStorage (nullptr)
		{
			resize(n, value);
		}
 
		template<class InputIterator>
		vector(InputIterator first, InputIterator last)
            :_start(nullptr)
            , _finish ( nullptr)
            , _endOfStorage (nullptr)
		{
			
			size_t  sz = last-first;
			T* tmp = new T[sz];
			for (size_t i = 0;i < sz;i++)
			{
				tmp[i] = first[i];
			}
			//memcpy(tmp, first, sizeof(T) * (sz));
			_start = tmp;
			_finish = _start + sz;
			_endOfStorage = _finish;
		}
		vector( vector<T>& v)
			:_start(nullptr)
			, _finish(nullptr)
			, _endOfStorage(nullptr)
		{
			size_t sz= v.size();
			size_t cp = v.capacity();
			_start = new T[cp];
			for (size_t i = 0;i < sz;i++)
			{
				_start[i] = v._start[i];
			}
			//memcpy(tmp, v._start, sizeof(T) * (sz));
			
			_finish = _start + sz;
			_endOfStorage = _start+ cp;
			
		}
 
		vector<T>& operator= (vector<T> v)
		{
			/*size_t sz = v.size();
			size_t cp = v.capacity();
			T* tmp = new T[cp];
			memcpy(tmp, v._start, sizeof(T) * (sz));
			_start = tmp;
			_finish = _start + sz;
			_endOfStorage = _start + cp;*/
			swap(v);
 
			return *this;
		}
 
		void reserve(size_t n)
		{
			if (n >= capacity())
			{
				size_t sz = size();
				T* tmp = new T[n];
				if (_start)
				{
					for (size_t i=0;i < sz;i++)
					{
						tmp[i] = _start[i];
					}
					//memcpy(tmp, _start, sizeof(T)*sz);
					delete[]_start;
				}
				_start = tmp;
				_finish = _start + sz;
				_endOfStorage = _start + n;
			}
		}
		void resize(size_t n, const T& value = T())
		{
		
		/*	for (size_t i = 0;i < n;i++)
			{
				push_back(value);
			}*/
			if (n < size())
			{
				_finish = _start + n;			
			}
			else
			{
				reserve(n);
				while (_finish != _start + n)
				{
					*_finish = value;
					_finish++;
				}
			}
		
		}
		void push_back(const T& x)
		{
			if (_finish == _endOfStorage)
			{
				size_t newcapacity =capacity()== 0 ? 4 : capacity() * 2;
				reserve(newcapacity);
			}
			*_finish = x;
			_finish++;
			
		}
		void pop_back()
		{
			assert(size());
			//_finish -= 1;
			erase(end()-1);
		}
 
		void swap(vector<T>& v)
		{
			
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endOfStorage, v._endOfStorage);
		}
		iterator insert(iterator pos, const T& x)
		{
			assert(pos >= _start && pos <= _finish);
			if (_finish==_endOfStorage)
			{
				size_t len = pos-_start;
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newcapacity);
				pos = _start + len;
			}
			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 p1 = pos;
			iterator end = _finish - 1;
			while (p1<end )
			{
				*p1 = *(p1+1);
			     p1++;
			}
			_finish--;
			return pos;
		}
 
		size_t capacity()
		{
			return _endOfStorage - _start;
		}
 
		size_t size()
		{
			return _finish - _start;
		}
 
		iterator begin()
		{
			return _start;
		}
 
		iterator end()
		{
			return _finish;
		}
 
		const_iterator begin() const
		{
			return _start;
		}
 
		const_iterator end() const
		{
			return _finish;
		}
		const_iterator cbegin()
		{
			return _start;
		}
 
		const_iterator cend() const
		{
			return _finish;
		}
		T& operator[](size_t pos)
		{
			return _start[pos];
		}
 
		const T& operator[](size_t pos)const
		{
			return _start[pos];
		}
		~vector()
		{
			if (_start)
			{
				delete[]_start;
				_start = _finish = _endOfStorage = nullptr;
			}
		
		}
 
	private:
		iterator _start; // 指向数据块的开始
 
		iterator _finish; // 指向有效数据的尾
 
		iterator _endOfStorage;// 指向存储容量的尾
	};
}
```                                                                                                                                                                                                               {public:typedef T* iterator;typedef const T* const_iterator;vector():_start(nullptr), _finish ( nullptr), _endOfStorage (nullptr){}vector(int n, const T& value = T())             :_start(nullptr)             , _finish ( nullptr)             , _endOfStorage (nullptr){resize(n, value);}template<class InputIterator>vector(InputIterator first, InputIterator last)            :_start(nullptr)            , _finish ( nullptr)            , _endOfStorage (nullptr){size_t  sz = last-first;T* tmp = new T[sz];for (size_t i = 0;i < sz;i++){tmp[i] = first[i];}_start = tmp;_finish = _start + sz;_endOfStorage = _finish;}vector( vector<T>& v):_start(nullptr), _finish(nullptr), _endOfStorage(nullptr){size_t sz= v.size();size_t cp = v.capacity();_start = new T[cp];for (size_t i = 0;i < sz;i++){_start[i] = v._start[i];}_finish = _start + sz;_endOfStorage = _start+ cp;}vector<T>& operator= (vector<T> v){swap(v);return *this;}void reserve(size_t n){if (n >= capacity()){size_t sz = size();T* tmp = new T[n];if (_start){for (size_t i=0;i < sz;i++){tmp[i] = _start[i];}delete[]_start;}_start = tmp;_finish = _start + sz;_endOfStorage = _start + n;}}void resize(size_t n, const T& value = T()){if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish != _start + n){*_finish = value;_finish++;}}}void push_back(const T& x){if (_finish == _endOfStorage){size_t newcapacity =capacity()== 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish = x;_finish++;}void pop_back(){assert(size());erase(end()-1);}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}iterator insert(iterator pos, const T& x){assert(pos >= _start && pos <= _finish);if (_finish==_endOfStorage){size_t len = pos-_start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);pos = _start + len;}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 p1 = pos;iterator end = _finish - 1;while (p1<end ){*p1 = *(p1+1);     p1++;}_finish--;return pos;}size_t capacity(){return _endOfStorage - _start;}size_t size(){return _finish - _start;}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}const_iterator cbegin(){return _start;}const_iterator cend() const{return _finish;}T& operator[](size_t pos){return _start[pos];}const T& operator[](size_t pos)const{return _start[pos];}~vector(){if (_start){delete[]_start;_start = _finish = _endOfStorage = nullptr;}}private:iterator _start; iterator _finish; iterator _endOfStorage;};}

测试部分

```c++
#include <iostream>
//#include<vector>
#include "vector.h"
 
using namespace std;
void test_vector1()
{
	xyl::vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(5);
	v1.push_back(6);
	v1.push_back(7);
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
	xyl::vector<int> v2(5,100);
	for (auto e : v2)
	{
		cout << e << " ";
	}
	cout << endl;
	xyl::vector<int> v3(v1.begin(), v1.end());
	for (auto e : v3)
	{
		cout << e << " ";
	}
	xyl::vector<int> v4(v3);
	cout << endl;
	for (auto e : v4)
	{
		cout << e << " ";
	}
	xyl::vector<int> v5;
	cout << endl;
	v5 = v4;
	for (auto e : v5)
	{
		cout << e << " ";
	}
	cout << endl;
	for (int i = 0;i < v5.size();i++)
	{
		cout << v5[i]<< " ";
	}
}
void test_vector2()
{
	xyl::vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(5);
	v1.push_back(4);
	v1.push_back(100);
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
	v1.pop_back();
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
	xyl::vector<int> v2;
	v1.swap(v2);
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
	for (auto e : v2)
	{
		cout << e << " ";
	}
	cout << endl;
	xyl::vector<int> v3;
	v3.push_back(1);
	v3.push_back(4);
	v3.push_back(3);
	v3.push_back(4);
	v3.push_back(500);
	v3.push_back(4);
	v3.push_back(100);
	v3.insert(v3.begin()+2, 5);
	for (auto e : v3)
	{
		cout << e << " ";
	}
	cout << endl;
	v3.erase(v3.begin() + 2);
	for (auto e : v3)
	{
		cout << e << " ";
	}
}
void test_vector3()
{
	xyl::vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(5);
	v1.push_back(4);
	v1.push_back(100);
 
	for (auto e : v1)
	{
		cout << e << " ";
	}
 
	cout << endl;
 
	v1.erase(v1.end());
 
	for (auto e : v1)
	{
		cout << e << " ";
	}
}
void test_vector4()
{
	xyl::vector<int> v1;
	v1.resize(10);
 
	for (auto e : v1)
	{
		cout << e << " ";
	}
}
void test_vector5()
{
	xyl::vector<string> v1;
	v1.push_back("1111111111");
	v1.push_back("2222222222");
	v1.push_back("3333333333");
	v1.push_back("4444444444");
	for (auto e : v1)
	{
		cout << e << ' ';
	}
 
	cout << endl;
 
	xyl::vector<string> v2(v1);
 
	for (auto e : v2)
	{
		cout << e << ' ';
	}
 
	cout << endl;
 
	xyl::vector<string> v3(v1.begin(),v1.end());
 
	for (auto e : v3)
	{
		cout << e << ' ';
	}
}
int main()
{
	test_vector5();
	return 0;
}

2.2 使用memcpy拷贝问题

假设模拟实现的 vector 中的 reserve 接口中，使用 memcpy 进行的拷贝，以下代码会发生什么问题？

1
2
3
4
5
6
7
8
int main()
{
	xyl::vector<bite::string> v;
	v.push_back("1111");
	v.push_back("2222");
	v.push_back("3333");
	return 0;
}

问题分析：

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

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

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

2.3****动态二维数组理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 以杨辉三角的前n行为例：假设n为5
void test2vector(size_t n)
{
	// 使用vector定义二维数组vv，vv中的每个元素都是vector<int>
	bit::vector<bit::vector<int>> vv(n);
 
	// 将二维数组每一行中的vecotr<int>中的元素全部设置为1
	for (size_t i = 0; i < n; ++i)
		vv[i].resize(i + 1, 1);
	// 给杨辉三角出第一列和对角线的所有元素赋值
	for (int i = 2; i < n; ++i)
	{
		for (int j = 1; j < i; ++j)
		{
			vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
		}
	}
}

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

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

使用标准库中 vector 构建动态二维数组时与上图实际是一致的