【C++】STL——vector（万字详解）

🎇C++学习历程：入门

---

• 博客主页：一起去看日落吗
• 持续分享博主的C++学习历程
• 博主的能力有限，出现错误希望大家不吝赐教
• 分享给大家一句我很喜欢的话： 也许你现在做的事情，暂时看不到成果，但不要忘记，树🌿成长之前也要扎根，也要在漫长的时光🌞中沉淀养分。静下来想一想，哪有这么多的天赋异禀，那些让你羡慕的优秀的人也都曾默默地翻山越岭🐾。

---

🎶 🎵

---

🎶 1.vector 的介绍及使用

🎵 1.1 vector的介绍

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，我们也是按照这个方法去学习

🎵 1.2 vector的使用

vector学习时一定要学会查看文档：vector的文档介绍，vector在实际中非常的重要，在实际中我们熟悉常见的接口就可以，下面列出了哪些接口是要重点掌握的。

💨 1.2.1 vector的定义

• 这里的迭代器还是一个函数模板，也就是说这里的迭代器不一定是 vector 的迭代器

---

💨1.2.2 vector iterator 的使用

---

💨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。

测试vector扩容机制：

#include
#include
using namespace std;

void test_vector1()
{
	vector<int> v;   

	//开空间,改变容量,如果确定知道需要多少空间,reserve可以缓解vector增容所带来的代价
	v.reserve(10);
	/* err,错误访问,在之前string里就说明了operator[]会去检查下标是否小于size,[]只能去对size范围内的数据使用
	for(size_t i = 0; i < 10; ++i)
	{
		v[i] = i;	
	}
	*/
	//ok,正确访问
	for(size_t i = 0; i < 10; ++i)
	{
		v.push_back(i);	
	}
	
	//开空间+默认初始化,resize会影响size
	v.resize(20);	
	//开空间+指定初始化
	v.resize(20, 1);
}
int main()
{
	test_vector1();
	return 0;
}

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

---

💨 1.2.4 vector 增删查改

---

💨1.2.5 vector 使用演示

#define _CRT_SECURE_NO_WARNINGS

#include 
using namespace std;
#include 


//    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;
}



//  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::reverse_iterator rit = v.rbegin();
	auto rit = v.rbegin();
	while (rit != v.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;

	PrintVector(v);
}


//  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';
		}
	}
}


//  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
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

---

💨1.2.6 vector 迭代器失效问题（重点）

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

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

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

#include 
using namespace std;
#include 
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;
}
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

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

#include 
#include 
using namespace std;

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

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

#include 
#include 
#include 
using namespace std;

// 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
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

---

// 2. erase删除任意位置代码后，linux下迭代器并没有失效
// 因为空间还是原来的空间，后序元素往前搬移了，it的位置还是有效的
#inlcude <iostream>
#include 
#include 
using namespace std;

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

// 3: erase删除的迭代器如果是最后一个元素，删除之后it已经超过end
// 此时迭代器是无效的，++it导致程序崩溃
#inlcude <iostream>
#include 
#include 
using namespace std;

int main()
{
	vector<int> v{1,2,3,4,5};
	// vector 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

• 使用第一组数据时，程序可以运行

---

• 使用第二组数据时，程序最终会崩溃

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

---

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

#include 
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;
	}
}
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

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

---

💨1.2.7 vector 在OJ中的使用

链接：只出现一次的数字

• 解题思路：使用异或操作符 ^ —— 相同为 0，相异为 1

• 代码演示：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        //1、operator[]
        /*for(size_t i = 0; i < nums.size(); ++i)
        {
            ret ^= nums[i];
        }*/
        //2、迭代器
        /*vector::iterator it = nums.begin();
        while(it != nums.end())
        {
            ret ^= *it;
            ++it;
        }*/
        //3、范围for
        for(auto e : nums)
        {
            ret ^= e;
        }
        return ret;
    }
};

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

---

链接：杨辉三角

• 解题思路：需要先生成一个杨辉三角，每行的第一个和最后一个是 1，其余设置为 0，如果是 0，则需要计算。这里可以发现规律：1 = 1 + (1 - 1)，这里以第一个要计算的值为例，且这里的数字代表的下标 —— 第 3 行以 1 为下标位置的值是等于第 2 行以 1 为下标的值加上第 2 行以 1 - 1 为下标的值

• 代码演示：

class Solution {
public:
    //vector>就是一个二维数组
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> vv;
        vv.resize(numRows);
        //生成
        for(size_t i = 0; i < vv.size(); ++i)
        {
        	//每行有多少个,并初始化为0
            vv[i].resize(i + 1, 0);
            //每一行的第一个和最后一个赋值为1
            /*vv[i].front() = 1;
            vv[i].back() = 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)//需要处理
                {
                    vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
                }
            }
        }
        return vv;
    }
};

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

---

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

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

//
//  main.cpp
//  模拟实现vector
//
//  Created by 卜绎皓 on 2022/10/20.
//

#include
#include
#include
#include
#include
using namespace std;

#pragma once

namespace byh
{
    template<class T>
    class vector
    {
    public:
        // Vector的迭代器是一个原生指针
        typedef T* iterator;
        typedef const T* const_iterator;
        
        // 迭代器相关
        iterator begin()
        {
            return _start;
        }
        const_iterator begin() const
        {
            return _start;
        }
        iterator end()
        {
            return _finish;
        }
        const_iterator end() const
        {
            return _finish;
        }
        
        // 构造和销毁
        vector()
            : _start(nullptr)
            , _finish(nullptr)
            , _endofstorage(nullptr)
        {}
        //类模板的成员函数还可以再定义模板参数,这样写的好处是first/last可以是list等其它容器的迭代器,只要它解引用后的类型与T匹配
        template<class InputIterator>
        vector(InputIterator first, InputIterator last)
            : _start(nullptr)
            , _finish(nullptr)
            , _endofstorage(nullptr)
        {
            //reserve(?)这个构造函数里传的是一段迭代器区间,只有对象才知道你有多少个容量
            while(first != last)
            {
                push_back(*first);
                ++first;
            }
        }
        //v2(v1)
        //1、传统写法
        /*vector(const vector& v)
        {
            _start = new T[v.capacity()];
            memcpy(_start, v._start, sizeof(T) * v.size());
            _finish = _start + v.size();
            _endofstorage = _start + v.capacity();
        }*/
        //2、传统写法————复用当前的一些接口,本质还是自己开空间,这里相对于现代写法更推荐第二种传统写法,因为它这里提前把空间开好了,并利用
        /*vector(const vector& v)
            : _start(nullptr)
            , _finish(nullptr)
            , _endofstorage(nullptr)
        {
            reserve(v.capacity());//一次性开好空间
            for(const auto& e : v)//引用的作用是为了防止T是string等
            {
                push_back(e);
            }
        }*/
        //3、现代写法,sring那我们是取_str来构造一个临时对象再交换,但是这里怎么取所有的数据来构造并交换呢,没有法子
        //这里有个法子：vector的构造函数里还提供了一个显示的迭代器(它可以传其它容器或原生指针做迭代器,但是原生指针必须要求指向的空间是连续的)
        //所以这里还需要构造一个函数,这里的现代写法对比上面的传统写法并没有讨到便宜()
        vector(const vector<T>& v)
            : _start(nullptr)
            , _finish(nullptr)
            , _endofstorage(nullptr)
        {
            //现代写法里提前开空间没有意义,因为现代写法的空间是tmp去搞的,tmp没办法自己开,因为它不知道有多少个数据,那有人说用last－first,不敢减,因为比如list是不支持减的,它不是一段连续的空间
            vector<T> tmp(v.begin(), v.end());
            swap(tmp);
        }
        void swap(vector<T>& v)
        {
            std::swap(_start, v._start);
            std::swap(_finish, v._finish);
            std::swap(_endofstorage, v._endofstorage);
        }
        //v1 = v4;
        //1、传统写法————不推荐(如果你能掌握现代写法,任何容器的深拷贝都推荐现代写法,尤其是赋值操作)
        /*vector& operator=(const vector& v)
        {
            if(this != &v)
            {
                delete[]_start;
                _start = _finish = _endofstorage = nullptr;
    
                reserve(v.capacity());
                for(const auto& e : v)
                {
                    push_back(e);
                }
            }
            return *this;
        }*/
        //2、现代写法,v就是去深拷贝的v4
        vector<T>& operator=(vector<T> v)
        {
            //v是v1想要的,所以v1和v交换
            swap(v);
            return *this;
        }
        ~vector()
        {
            delete[] _start;
            _start = _finish = _endofstorage = nullptr;
        }
        size_t size() const
        {
            return _finish - _start;
        }
        size_t capacity() const
        {
            return _endofstorage - _start;
        }
        T& operator[](size_t i)
        {
            assert(i < size());
            return _start[i];
        }
        const T& operator[](size_t i) const
        {
            assert(i < size());
            return _start[i];
        }
        void reserve(size_t n)
        {
            if(n > capacity())
            {
                //备份一份
                size_t sz = size();
                T* tmp = new T[n];
                if(_start)
                {
                    //对于string,memcpy会引发更深层次的浅拷贝问题,具体如下说明
                    //memcpy(tmp, _start, sizeof(T) * size());
                    for(size_t i = 0; i < size(); ++i)
                    {
                        //如果T是string,它会调用string的operator=完成深拷贝
                        tmp[i] = _start[i];
                    }
                    delete[] _start;
                }
                _start = tmp;
                _finish = _start + sz;
                //_finish = _start + size();err,size去计算时,_finish还是旧空间的_finish,而_start却是新空间的_start了,所以_finish-_start就是一个负值,再加_start就是0
                _endofstorage = _start + n;
            }
        }
        //如果没有给值,就用默认值,如果T是int,那就是int的匿名对象。T是string,那就是stirng的匿名对象。它会调用对应的默认构造函数————int是0,double是0.0,指针就是空指针
        //所以一般写一个类型,一定要提供一个不用参数就可以调的函数
        void resize(size_t n, const T& val = T())
        {
            if(n <= size())
            {
                _finish = _start + n;
            }
            else
            {
                if(n > capacity())
                {
                    reserve(n);
                }
                while(_finish < _start + n)
                {
                    *_finish = val;
                    ++_finish;
                }
            }
        }
        void push_back(const T& x)
        {
            /*if(_finish == _endofstorage)
            {
                size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
                reserve(newcapacity);
            }
            //这里不用像源码中一样使用定位new,因为使用定位new的原因是finish指向的空间没有初始化,所以使用定位new把对象构造上去。但是我们这里的对象是new出来的,所以这里直接赋值即可
            *_finish = x;
            ++_finish;*/
            insert(end(), x);
        }
        void pop_back()
        {
            /*
            //一般情况下--finish就行了,但是特殊情况vector为空时就不好
            //所以一般需要assert
            assert(!empty());
            --_finish;*/
            erase(--end());
        }
        iterator insert(iterator pos, const T& x)
        {
            //可以=_finish,因为它相当于尾插
            assert(pos >= _start && pos <= _finish);
            if(_finish == _endofstorage)
            {
                size_t len = pos - _start;
                size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
                //reserve里会更新那三个成员变量,insert返回新插入的那个元素的地址,所以这里的pos需要先备份一下旧空间里与_start之间的长度,然后再在新空间里重新赋值
                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 it = pos + 1;
            while(it != _finish)
            {
                *(it - 1) = *it;
                ++it;
            }
            --_finish;
            return pos;
        }
    private:
        iterator _start;
        iterator _finish;
        iterator _endofstorage;
    };

    void print(const vector<int>& v)
    {
        vector<int>::const_iterator it = v.begin();
        while(it != v.end())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;
        
        for(auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;

        for(size_t i = 0; i < v.size(); ++i)
        {
            cout << v[i] << " ";
        }
        cout << endl;
    }
    void test_vector1()
    {
        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;
        
        for(auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;

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

        print(v);
    }
    void test_vector2()
    {
        vector<int> v;
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);
    
        for(auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;
    
        v.resize(2);
        for(auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;
        
        v.resize(4);
        for(auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;
        
        v.resize(10, 5);
        for(auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;
    }
    void test_vector3()
    {
        vector<string> v;
        
        string s("hello");
        v.push_back(s);
        
        v.push_back(string("hello"));

        v.push_back("hello");
        v.push_back("hello");
        v.push_back("hello");
        v.push_back("hello");
    
        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);
    
        vector<int>::iterator pos = find(v.begin(), v.end(), 2);
        if(pos != v.end())
        {
            pos = v.insert(pos, 20);
        }
        cout << *pos << endl;
        *pos = 100;
        ++pos;
        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<int>::iterator pos = find(v.begin(), v.end(), 2);
        if(pos != v.end())
        {
            v.erase(pos);
        }
        //这段代码在VS下是会崩溃的,但是在Linux下没有崩,所以这块我们就按Linux下实现
        cout << *pos << endl;
        *pos = 100;
    }
    void test_vector6()
    {
        vector<int> v;
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);
        //删除v中所有偶数
        vector<int>::iterator 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;
    }
    void test_vector7()
    {
        vector<int> v1;
        v1.push_back(1);
        v1.push_back(2);
        v1.push_back(3);
        v1.push_back(4);
    
        vector<int> v2(v1);
        for(auto e : v2)
        {
            cout << e << " ";
        }
        cout << endl;

        //为什么现代写法里的构造函数的实现还需要再定义模板,而不使用T*或iterator
        //因为如果是T*的话就写死了,你是其它容器的迭代器就不行了
        string s("abcde");
        vector<int> v3(v1.begin(), v1.end());
        vector<int> v4(s.begin(), s.end());
    
        //赋值
        v1 = v4;
        for(auto e : v1)
        {
            cout << e << " ";
        }
        cout << endl;
    }
}




int main()
{
    byh::test_vector1();
    cout << "-----------------------next-----------------------" << endl;
    byh::test_vector2();
    cout << "-----------------------next-----------------------" << endl;
    byh::test_vector3();
    cout << "-----------------------next-----------------------" << endl;
    byh::test_vector4();
    cout << "-----------------------next-----------------------" << endl;
    byh::test_vector5();
    cout << "-----------------------next-----------------------" << endl;
    byh::test_vector6();
    cout << "-----------------------next-----------------------" << endl;
    byh::test_vector7();
    return 0;
}

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
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479

---

🎵 2.2 使用memcpy拷贝问题

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

vector<string> v;
		
v.push_back(1111);
		
v.push_back(2222);

v.push_back(3333);

return 0;

1
2
3
4
5
6
7
8
9
10

• 问题分析：

1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
2. 如果拷贝的是自定义类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。

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

---

🎵 2.3 动态二维数组理解

//以杨辉三角的前n行为例:假设n为5
void test5(size_t n) 
{
	//使用vector定义二维数组vv,vv中的每个元素都是vector
	vector<vector<int>> vv(n);
 
	//将二维数组每一行中的vecotr中的元素全部设置为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];
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

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

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

---