04.C++ 函数模板

本节分为四个部分：

  1. 理解函数模板
  2. 理解类模板
  3. 实现 C++ STL 向量容器 vector
  4. 理解容器控件配置器 allocator

1. 理解函数模板

1. 定义

函数模板不是一个实在的函数，编译器不能为其生成可执行代码。定义函数模板后只是一个对函数功能框架的描述，当它具体执行时，将根据传递的实际参数决定其功能。

2. 用法

面向对象的继承和多态机制有效提高了程序的可重用性和可扩充性。在程序的可重用性方面，程序员还希望得到更多支持。举一个最简单的例子，为了交换两个整型变量的值，需要写下面的 Swap 函数：

1
2
3
4
5
6
void Swap(int& x, int& y) 
{
	int temp = x;
	x = y;
	y = temp;
}

为了交换两个 double 型变量的值，还需要编写下面的 Swap 函数：

1
2
3
4
5
6
void Swap (double & xr double & y)
{
    double tmp = x;
    x = y;
    y = tmp;
}

如果还要交换两个 char 型变量的值，交换两个 CStudent 类对象的值……都需要再编写 Swap 函数。而这些 Swap 函数除了处理的数据类型不同外，形式上都是一样的。

能否只写一遍 Swap 函数，就能用来交换各种类型的变量的值呢？继承和多态显然无法解决这个问题。因此，“模板”的概念就应运而生了。

程序设计语言中的模板就是用来批量生成功能和形式都几乎相同的代码的。有了模板，编译器就能在需要的时候，根据模板自动生成程序的代码。从同一个模板自动生成的代码，形式几乎是一样的。

模板函数、模板的特例化和非模板函数的重载关系：候选的函数中，优先在精确匹配中选择，优先选择普通函数，特例性更强的模版函数次之，然后是模版函数的特化版本，最后才是泛化版本。

模板代码是不能声明在.h，实现在.cpp，模板代码调用之前，一定要看到模板定义的地方，这样的话，模板才能够正常的实例化，产生能够被编译器编译的代码。模板代码都是放在头文件中，然后在源文件中直接进行 #include

3. 原理

C++ 语言支持模板。有了模板，可以只写一个 Swap 模板，编译器会根据 Swap 模板自动生成多个 Sawp 函数，用以交换不同类型变量的值。

在 C++ 中，模板分为函数模板和类模板两种。

  • 函数模板是用于生成函数；
  • 类模板则是用于生成类的。

函数模板的写法如下：

1
2
3
4
5
template <class 类型参数1, class类型参数2, ...>
返回值类型  模板名(形参表)
{
    函数体
}

其中的 class 关键字也可以用 typename 关键字替换，例如：

1
template <typename 类型参数1, typename 类型参数2, ...>

函数模板看上去就像一个函数。前面提到的 Swap 模板的写法如下：

1
2
3
4
5
6
7
template <typename T>
T Swap(T& x, T& y)
{
	T tmp = x; 
	x = y; 
	y = tmp;
}

T 是类型参数，代表类型。编译器由模板自动生成函数时，会用具体的类型名对模板中所有的类型参数进行替换，其他部分则原封不动地保留。同一个类型参数只能替换为同一种类型。编译器在编译到调用函数模板的语句时，会根据实参的类型判断该如何替换模板中的类型参数。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;

template <typename T>
T Swap(T& x, T& y)
{
	T tmp = x;
	x = y;
	y = tmp;
}

int main()
{
	int n = 1, m = 2;
	// 编译器自动生成 void Swap (int &, int &)函数
	Swap(n, m);

	double f = 1.2, g = 3.4;
	// 编译器自动生成 void Swap (double &, double &)函数
	Swap(f, g);

	return 0;
}

编译器在编译到 Swap(n, m); 时找不到函数 Swap 的定义，但是发现实参 n、m 都是 int 类型的，用 int 类型替换 Swap 模板中的 T 能得到下面的函数：

1
2
3
4
5
6
void Swap (int & x, int & y)
{
    int tmp = x;
    x = y;
    y = tmp;
}

该函数可以匹配 Swap(n, m); 这条语句。于是编译器就自动用 int 替换 Swap 模板中的 T，生成上面的 Swap 函数，将该 Swap 函数的源代码加入程序中一起编译，并且将 Swap(n, m); 编译成对自动生成的 Swap 函数的调用。

同理，编译器在编译到 Swap(f, g); 时会用 double 替换 Swap 模板中的 T，自动生成以下 Swap 函数：

1
2
3
4
5
6
void Swap(double & x, double & y)
{
    double tmp = x;
    x = y;
    y = tmp;
}

然后再将 Swap(f, g); 编译成对该 Swap 函数的调用。

编译器由模板自动生成函数的过程叫模板的实例化。由模板实例化而得到的函数称为模板函数。在某些编译器中，模板只有在被实例化时，编译器才会检查其语法正确性。如果程序中写了一个模板却没有用到，那么编译器不会报告这个模板中的语法错误。

编译器对模板进行实例化时，并非只能通过模板调用语句的实参来实例化模板中的类型参数，模板调用语句可以明确指明要把类型参数实例化为哪种类型。可以用：

1
模板名<实际类型参数1, 实际类型参数2, ...>

2. 理解类模板

1. 定义

为了多快好省地定义出一批相似的类,可以定义「类模板」，然后由类模板生成不同的类。

类模板的定义形式如下：

1
2
3
4
5
template <class 类型参数1，class 类型参数2，...> //类型参数表
class 类模板名
{
   成员函数和成员变量
};

用类模板定义对象的写法：

1
类模板名<真实类型参数表> 对象名(构造函数实参表);
  • 类模板用于实现类所需数据的类型参数化
  • 类模板在表示如数组、表、图等数据结构显得特别重要
  • 这些数据结构的表示和算法不受所包含的元素类型的影响

2. 类模板实现顺序栈

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
#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

template <class T>
class SeqStack
{
public:
	// 公共方法
		// 构造函数初始化
		// 构造和析构函数名不加<T> 其他出现模板的地方都加上类型参数列表
	SeqStack(int size = 10)
		: PStack(new T[size])
		, Top(0)
		, Size(size) {
		// 初始化生成的指令更少，效率更高。
		// 仅调用默认构造函数（如果存在类成员）。赋值需要调用默认构造函数和赋值运算符
	};

	// 拷贝构造
	// 初始化列表的方式初始化 size 和 top
	SeqStack(const SeqStack<T>& stack)
		: Top(stack.Top)
		, Size(stack.Size) {
		// 重新设置栈
		PStack = new T[stack.Size];
		int i = 0;
		for (i = 0; i < Top; i++)
		{
			PStack[i] = stack.PStack[i];
		}
	}

	// 析构函数 释放内存
	~SeqStack()
	{
		if (PStack)
		{
			delete[] PStack;
			PStack = nullptr;
		}
	}

	// 复制重载
	SeqStack<T>& operator=(const SeqStack<T>& stack)
	{
		// 判断是否相等
		if (this == &stack)
		{
			return *this;
		}
		// 清空
		delete[] PStack;

		// 重新赋值
		Top = stack.Top;
		Size = stack.Size;
		PStack = new T[stack.Size];
		int i = 0;
		for (i = 0; i < Top; i++)
		{
			PStack[i] = stack.PStack[i];
		}

		return *this;
	}

	// 共有方法
	// 1. push 方法
	void push(const T& val)
	{
		if (full())
		{
			resize();
		}
		PStack[Top] = val;
		Top++;
	}

	// 2. pop 方法
	void pop()
	{
		if (empty())
		{
			return;
		}
		Top--;
	}

	// 3. top 方法
	T top() const
	{
		if (empty())
		{
			throw "Stack is empty!";
		}
		return PStack[Top - 1];
	}

	// 4. full 方法
	bool full() const {
		return Top == Size;
	}

	// 5. empty 方法
	bool empty() const {
		return Top == 0;
	}

	// 私有方法和数据
private:
	// 扩容方法
	void resize()
	{
		T* p = new T[Size * 2];
		// 将值赋值过去
		int i = 0;
		for (i = 0; i < Top; i++)
		{
			p[i] = PStack[i];
		}
		// 扩大
		Size *= 2;
		// 清空
		delete PStack;
		// 重新赋值
		PStack = p;
	}

	T* PStack;
	int Top;
	int Size;
};

int main()
{
	SeqStack<int> stack;
	for (int i = 0; i < 8; ++i) {
		stack.push(i);
	}

	while (!stack.empty())
	{
		cout << stack.top() << " ";
		stack.pop();
	}
	return 0;
}

3. 实现 C++ STL 向量容器 vector

image.png

vector 的本质是一个数组，在vector 中需要有三个指针：

  • First：指向数组的起始位置
  • Last：指向已经存放的最后一个元素的下一个位置
  • End：指向数组长度的末尾元素的下一个位置。

vector 方法：

  • 数组的容量：End-First
  • 数组中存放的元素个数：Last-First
  • 数组是否为空：First == Last
  • 数组是否已满：Last == End
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
#include <iostream>
using namespace std;

template <class T>
class vector
{
public:
	// 构造函数
	vector(int size = 10)
		: First(new T[size])
		, Last(First)
		, End(First + size)
	{
		// 使用初始化列表方式
	}
	// 拷贝构造函数
	vector(const vector<T>& rhs)
	{
		// 获取容器长度
		int size = rhs.End - rhs.First;
		// 创建新容器
		First = new T[size];
		// 获取数据长度
		int len = rhs.Last - rhs.First;
		// 遍历赋值
		int i = 0;
		for (i = 0; i < len; i++)
		{
			First[i] = rhs.First[i];
		}
		// 重置 Last 和 End
		Last = First + len;
		End = First + size;
	}
	// 析构函数
	~vector()
	{
		delete[] First;
		First = End = Last = nullptr;
	}
	// 赋值重载
	vector<T>& operator=(const vector<T>& rhs)
	{
		// 判断
		if (this == &rhs)
		{
			return *this;
		}

		// 清除
		delete[] First;

		// 重新计算并赋值
		// 获取容器长度
		int size = rhs.End - rhs.First;
		// 创建新容器
		First = new T[size];
		// 获取数据长度
		int len = rhs.Last - rhs.First;
		// 遍历赋值
		int i = 0;
		for (i = 0; i < len; i++)
		{
			First[i] = rhs.First[i];
		}
		// 重置 Last 和 End
		Last = First + len;
		End = First + size;

		return *this;
	}

	// 共有方法
	// push_back 方法：容器添加内容
	void push_back(const T& val)
	{
		if (full())
		{
			extend();
		}
		// 先给之以后，下次 push 则会递增内存
		*Last++ = val;
	}
	// pop_back 方法：容器删除内容
	void pop_back()
	{
		if (empty())
		{
			return;
		}
		--Last;
	}
	// back 方法：输出删除内容
	T back() const
	{
		return *(Last - 1);
	}
	// full 方法：容器是否已满
	bool full() const
	{
		return Last == End;
	}
	// empty 方法：容器是否为空
	bool empty() const
	{
		return Last == First;
	}
	// size 方法：获取内容厂区
	int size() const
	{
		return Last - First;
	}

// 私有方法
private:
	// vector 容器扩容
	void extend()
	{
		int size = End - First;
		T* ptmp = new T[size * 2];

		// 遍历并转移
		int i = 0;
		for (i = 0; i < size; i++)
		{
			ptmp[i] = First[i];
		}
		// 删除原先的
		delete[] First;

		// 重新覆盖
		First = ptmp;
		Last = First + size;
		End = First + 2 * size;
	}

// 私有数据
private:
	T* First;
	T* Last;
	T* End;
};

class Test
{
public:
	Test() 
	{ 
		cout << "Test()" << endl; 
	}
	Test& operator=(const Test& t) 
	{ 
		cout << "operator=" << endl; 
		return *this; 
	}
	~Test() 
	{ 
		cout << "~Test()" << endl; 
	}
	Test(const Test&) 
	{ 
		cout << "Test(const Test&)" << endl; 
	}
};

int main()
{
	Test t1;
	Test t2;

	cout << "vector<Test> vec" << endl;

	vector<Test> vec;
	cout << "vector<Test> vec; push_back" << endl;

	vec.push_back(t1);
	vec.push_back(t2);

	cout << "vector<Test> vec; pop_back" << std::endl;
	vec.pop_back();

	return 0;
}

image.png

问题：在我们实现的 vector 构造函数中，使用 new T[size] ：它做了两件事情：

（1）开辟内存空间
（2）调用 T 类型的默认构造函数构造对象

其中第二步是一种浪费，因为我还没在vector 添加元素，提前构造一遍对象 然后在析构时候是否纯属多余。

同时：在实现 pop_back(） 时，存在内存泄漏

1
2
3
4
5
6
void pop_back() // 从容器末尾删除元素
{
  if (empty())
    return;
  --Last;
}

 仅仅将 Last 指针 –，并没有释放 Test 申请的资源。需要调用对象的析构函数

4. 理解容器控件配置器 allocator

通过 Win msvc 编译器的实现：

image.png

1
2
3
4
5
6
7
8
9
10
// CLASS TEMPLATE vector
template<class _Ty, class _Alloc = allocator<_Ty>>
	class vector
		: public _Vector_alloc<_Vec_base_types<_Ty, _Alloc>>
	{	// varying size array of values
private:
	using _Mybase = _Vector_alloc<_Vec_base_types<_Ty, _Alloc>>;
	using _Alty = typename _Mybase::_Alty;
	using _Alty_traits = typename _Mybase::_Alty_traits;
......

系统的实现，除了数据类型外，还有一个allocator,它将开辟空间和构造对象分离开。

而这，也就是空间配置器做的工作；

1. 容器的空间配置器

空间配置器主要有四个功能：

  1. 内存开辟 allocate（底层调用malloc）；
  2. 内存释放 deallocate（底层调用free）；
  3. 对象构造 construct（调用构造函数）；
  4. 对象析构 destroy（调用析构函数）；
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
// 定义容器的空间适配器和 C++ 标准库的 allocator 实现一样
template <typename T>
struct Allocator
{
	// 负责内存的开辟
	T* allocate(size_t size)
	{
		return (T*)malloc(sizeof(T) * size);
	}
	// 负责内存的释放
	void deallocate(void* p)
	{
		free(p);
	}
	// 负责对象构造
	void construct(T* p, const T& val)
	{
		new (p) T(val);
	}
	// 负责对象析构
	void destory(T* p)
	{
		// ~T() 代表了 T 类型的析构函数
 		p->~T();
	}
};

重新实现 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
#include <iostream>
using namespace std;

// 定义容器的空间配置器，和C++标准库的allocator实现一样
template<typename T>
class Allocator
{
public:
	// 负责内存开辟
	T* allocate(size_t size) 
	{
		return (T*)malloc(sizeof(T) * size);
	}
	// 负责内存释放
	void deallocate(void* p) 
	{
		free(p);
	}
	// 负责对象构造
	void construct(T* p, const T& val) 
	{
		new (p)T(val); // 定位new
	}
	// 负责对象析构
	void destroy(T* p) 
	{
		p->~T(); // ~T()代表了T类型的析构函数
	}
};

// 通过 allocator 适配器重写 vector
template<typename T, typename Alloc = Allocator<T>>
class vector
{
	// 公共构造、拷贝、重载、析构、方法函数
public:
	// 构造函数
	// 需要把内存开辟和对象构造分开处理
	vector(int size = 10)
		: First(_allocator.allocate(size))
		, Last(First)
		, End(First + size)
	{
		// 通过初始化列表的方式，初始化数据
	}

	// 拷贝函数
	vector(const vector<T>& rhs)
	{
		// 定义 大小
		int size = rhs.End - rhs.First;
		// 空间适配器开辟空间
		First = _allocator.allocate(size);
		// 获取长度
		int len = rhs.Last - rhs.First;

		// 拷贝数据
		int i = 0;
		for (i = 0; i < len; i++)
		{
			// 空间适配器的构造方法赋值
			_allocator.construct(First + i, rhs.First[i]);
		}
		// 重新配置 Last 和 End
		Last = First + len;
		End = First + size;
	}
	// 析构函数
	~vector()
	{
		cout << "~vector" << endl;
		// 析构容器有效的元素，然后释放 First 指针指向的堆内存
		T* p = First;
		for (p = First; p != Last; p++)
		{
			// cout << "p =" << p << endl;
			//  把 First 指针指向的数组的有效元素进行析构操作
			_allocator.destroy(p);
		}
		// 释放堆上的数组内存
		_allocator.deallocate(First);
		// 重置 指针
		First = Last = End = nullptr;
	}


	// 赋值重载
	vector<T>& operator=(const vector<T>& rhs)
	{
		// 1. 判断
		if (this == &rhs)
		{
			return *this;
		}
		// 2. 清空
		// 析构容器有效的元素，然后释放 First 指针指向的堆内存
		T* p = First;
		for (p = First; p != End; p++)
		{
			//  把 First 指针指向的数组的有效元素进行析构操作
			_allocator.destroy(p);
		}
		// 释放堆上的数组内存
		_allocator.deallocate(First);

		// 3. 重新计算
		// 定义 大小
		int size = rhs.End - rhs.First;
		// 空间适配器开辟空间
		First = _allocator.allocate(size);
		// 获取长度
		int len = rhs.Last - rhs.First;

		// 拷贝数据
		int i = 0;
		for (i = 0; i < len; i++)
		{
			// 空间适配器的构造方法赋值
			_allocator.construct(First + i, rhs.First[i]);
		}
		// 重新配置 Last 和 End
		Last = First + len;
		End = First + size;

		return *this;
	}

	// 公共方法
	// 1. push_back 方法
	void push_back(const T& val)
	{
		// 判断
		if (full())
		{
			expand();
		}
		// 通过适配器添加内容
		_allocator.construct(Last, val);
		Last++;
	}
	// 2. pop_back 方法
	void pop_back()
	{
		if (empty())
		{
			return;
		}
		// 不仅要把 Last 指针--，还需要析构删除的元素
		--Last;
		_allocator.destroy(Last);
	}
	// 3. back 方法
	T back() const 
	{
		return *(Last - 1);
	}
	// 4. full 方法
	bool full() const { return Last == End; }
	// 5. empty 方法
	bool empty() const { return First == Last; }
	// 6. size 方法
	int size() const { return Last - First; }

// 私有属性和方法
private:
	// 指向数组起始的位置
	T* First;
	// 指向数组中有效元素的后继位置
	T* Last;
	// 指向数组空间的后继位置
	T* End;
	// 定义容器的空间配置器对象
	Alloc _allocator;

	// 扩容方法
	void expand()
	{
		// 获取大小
		int size = End - First;
		// 配置 2 倍适配器空间
		T* ptmp = _allocator.allocate(size * 2);
		// 赋值
		int i = 0;
		for (i = 0; i < size; i++)
		{
			_allocator.construct(ptmp + i, First[i]);
		}

		// 清空
		// 析构容器有效的元素，然后释放 First 指针指向的堆内存
		T* p = First;
		for (p = First; p != End; p++)
		{
			//  把 First 指针指向的数组的有效元素进行析构操作
			_allocator.destroy(p);
		}
		// 释放堆上的数组内存
		_allocator.deallocate(First);

		// 重新赋值
		First = ptmp;
		Last = First + size;
		End = First + size * 2;
	}
};


class Test
{
public:
	Test()
	{
		cout << "Test()" << endl;
	}
	Test& operator=(const Test& t)
	{
		cout << "operator=" << endl;
		return *this;
	}
	~Test() 
	{ 
		cout << "~Test()" << endl; 
	}
	Test(const Test&)
	{ 
		cout << "Test(const Test&)" << endl; 
	}
};

int main()
{
	Test t1, t2;
	cout << "1." << endl;
	cout << "vector<Test> vec" << endl;

	vector<Test> vec;
	cout << "vector<Test> vec; push_back" << endl;

	vec.push_back(t1);
	vec.push_back(t2);

	cout << "vector<Test> vec; pop_back" << endl;
	vec.pop_back();
	cout << "end" << endl;


	return 0;
}

image.png

现在的效果就和 msvc 实现的 vector 相同了

2. 运算符重载与迭代器实现

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
// 迭代器一般是现成容器的嵌套类型
template<class T>
class iterator
{
public:
	// 构造函数
	iterator(T* p = nullptr)
		: _ptr(p)
	{
		// 初始化列表方式
	}
	// 拷贝构造函数
	iterator(const iterator& iter)
		: _ptr(iter._ptr)
	{
		// ...
	}

	// 重载函数合集
	// 1. 前置 ++
	iterator& operator++()
	{
		_ptr++;
		return *this;
	}
	// 2. 后置 ++
	iterator operator++(int) {
		iterator tmp(*this);
		_ptr++;
		return tmp;
	}
	// 3. 解引用
	T& operator*()
	{
		return *_ptr;
	}
	// 4. !=
	bool operator!=(const iterator& iter) const
	{
		return _ptr != iter._ptr;
	}

private:
	T* _ptr;
};


//迭代器方法
iterator begin() { return iterator(First); }
iterator end() { return iterator(Last); }

//运算符重载[]
T& operator[](int index) {
	if (index < 0 || index >= size()) {
		throw "OutofRangeException";
	}

	return First[index];
}

3. 最终 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
#include <iostream>
using namespace std;


// 定义容器的空间配置器，和C++标准库的allocator实现一样
template<typename T>
class Allocator
{
public:
	// 负责内存开辟
	T* allocate(size_t size) 
	{
		return (T*)malloc(sizeof(T) * size);
	}
	// 负责内存释放
	void deallocate(void* p) 
	{
		free(p);
	}
	// 负责对象构造
	void construct(T* p, const T& val) 
	{
		new (p)T(val); // 定位new
	}
	// 负责对象析构
	void destroy(T* p) 
	{
		p->~T(); // ~T()代表了T类型的析构函数
	}
};

// 通过 allocator 适配器重写 vector
template<typename T, typename Alloc = Allocator<T>>
class vector
{
	// 公共构造、拷贝、重载、析构、方法函数
public:
	// 构造函数
	// 需要把内存开辟和对象构造分开处理
	vector(int size = 10)
		: First(_allocator.allocate(size))
		, Last(First)
		, End(First + size)
	{
		// 通过初始化列表的方式，初始化数据
	}

	// 拷贝函数
	vector(const vector<T>& rhs)
	{
		// 定义 大小
		int size = rhs.End - rhs.First;
		// 空间适配器开辟空间
		First = _allocator.allocate(size);
		// 获取长度
		int len = rhs.Last - rhs.First;

		// 拷贝数据
		int i = 0;
		for (i = 0; i < len; i++)
		{
			// 空间适配器的构造方法赋值
			_allocator.construct(First + i, rhs.First[i]);
		}
		// 重新配置 Last 和 End
		Last = First + len;
		End = First + size;
	}
	// 析构函数
	~vector()
	{
		cout << "~vector" << endl;
		// 析构容器有效的元素，然后释放 First 指针指向的堆内存
		T* p = First;
		for (p = First; p != Last; p++)
		{
			// cout << "p =" << p << endl;
			//  把 First 指针指向的数组的有效元素进行析构操作
			_allocator.destroy(p);
		}
		// 释放堆上的数组内存
		_allocator.deallocate(First);
		// 重置 指针
		First = Last = End = nullptr;
	}


	// 赋值重载
	vector<T>& operator=(const vector<T>& rhs)
	{
		// 1. 判断
		if (this == &rhs)
		{
			return *this;
		}
		// 2. 清空
		// 析构容器有效的元素，然后释放 First 指针指向的堆内存
		T* p = First;
		for (p = First; p != End; p++)
		{
			//  把 First 指针指向的数组的有效元素进行析构操作
			_allocator.destroy(p);
		}
		// 释放堆上的数组内存
		_allocator.deallocate(First);

		// 3. 重新计算
		// 定义 大小
		int size = rhs.End - rhs.First;
		// 空间适配器开辟空间
		First = _allocator.allocate(size);
		// 获取长度
		int len = rhs.Last - rhs.First;

		// 拷贝数据
		int i = 0;
		for (i = 0; i < len; i++)
		{
			// 空间适配器的构造方法赋值
			_allocator.construct(First + i, rhs.First[i]);
		}
		// 重新配置 Last 和 End
		Last = First + len;
		End = First + size;

		return *this;
	}
	//运算符重载[]
	T& operator[](int index) 
	{
		// 判断索引位置
		if (index < 0 || index >= size()) {
			throw "OutofRangeException";
		}
		// 返回索引值
		return First[index];
	}

	// 公共方法
	// 1. push_back 方法
	void push_back(const T& val)
	{
		// 判断
		if (full())
		{
			expand();
		}
		// 通过适配器添加内容
		_allocator.construct(Last, val);
		Last++;
	}
	// 2. pop_back 方法
	void pop_back()
	{
		if (empty())
		{
			return;
		}
		// 不仅要把 Last 指针--，还需要析构删除的元素
		--Last;
		_allocator.destroy(Last);
	}
	// 3. back 方法
	T back() const 
	{
		return *(Last - 1);
	}
	// 4. full 方法
	bool full() const { return Last == End; }
	// 5. empty 方法
	bool empty() const { return First == Last; }
	// 6. size 方法
	int size() const { return Last - First; }

	// 迭代器一般是现成容器的嵌套类型
	class iterator
	{
	public:
		// 构造函数
		iterator(T* p = nullptr)
			: _ptr(p)
		{
			// 初始化列表方式
		}
		// 拷贝构造函数
		iterator(const iterator& iter)
			: _ptr(iter._ptr)
		{
			// ...
		}

		// 重载函数合集
		// 1. 前置 ++
		iterator& operator++()
		{
			_ptr++;
			return *this;
		}
		// 2. 后置 ++
		iterator operator++(int) {
			iterator tmp(*this);
			_ptr++;
			return tmp;
		}
		// 3. 解引用
		T& operator*()
		{
			return *_ptr;
		}
		// 4. !=
		bool operator!=(const iterator& iter) const
		{
			return _ptr != iter._ptr;
		}

	private:
		T* _ptr;
	};
	//迭代器方法
	iterator begin() { return iterator(First); }
	iterator end() { return iterator(Last); }


// 私有属性和方法
private:
	// 指向数组起始的位置
	T* First;
	// 指向数组中有效元素的后继位置
	T* Last;
	// 指向数组空间的后继位置
	T* End;
	// 定义容器的空间配置器对象
	Alloc _allocator;

	// 扩容方法
	void expand()
	{
		// 获取大小
		int size = End - First;
		// 配置 2 倍适配器空间
		T* ptmp = _allocator.allocate(size * 2);
		// 赋值
		int i = 0;
		for (i = 0; i < size; i++)
		{
			_allocator.construct(ptmp + i, First[i]);
		}

		// 清空
		// 析构容器有效的元素，然后释放 First 指针指向的堆内存
		T* p = First;
		for (p = First; p != End; p++)
		{
			//  把 First 指针指向的数组的有效元素进行析构操作
			_allocator.destroy(p);
		}
		// 释放堆上的数组内存
		_allocator.deallocate(First);

		// 重新赋值
		First = ptmp;
		Last = First + size;
		End = First + size * 2;
	}
};

class Test
{
public:
	Test()
	{
		cout << "Test()" << endl;
	}
	Test& operator=(const Test& t)
	{
		cout << "operator=" << endl;
		return *this;
	}
	~Test() 
	{ 
		cout << "~Test()" << endl; 
	}
	Test(const Test&)
	{ 
		cout << "Test(const Test&)" << endl; 
	}
};

int main()
{
	Test t1, t2;
	cout << "vector<Test> vec" << endl;

	vector<Test> vec;
	cout << "vector<Test> vec; push_back" << endl;

	vec.push_back(t1);
	vec.push_back(t2);

	cout << "vector<Test> vec; pop_back" << endl;
	vec.pop_back();
	cout << "end" << endl;

	cout << "-------------------------------" << endl;
	vector<Test>::iterator it = vec.begin();
	for (; it != vec.end(); ++it) {
		cout << "it = " << &(*it) << endl;
		std::cout << "iterator" << " " << endl;;
	}

	return 0;
}
#C++
04.C++ 函数模板
http://example.com/2023/08/08/02.C++ 基础部分/04.C++ 函数模板/
Author
Yakumo
Posted on
August 8, 2023
Licensed under