C++学习之路-类模板之泛型动态数组的实现

动态数组的需求

• 可以向数组中添加元素，且无限制添加。这也就意味着该数组可以动态扩容

array.append(value0)
array.append(value1)
...
array.append(value2)
1
2
3
4

• 可以通过get方法取出数组中某个索引处的元素

array.get(index)
1

• 可以删除数组中某个索引处的元素

array.remove(index)
1

• 可以向数组中任意位置插入元素

array.insert(index,value)
1

• 终极功能：数组不在局限于某一种数据类型，而是泛型。

Array<int> array;
[1, 2, 3, 4]
Array<char> array;
["a", "b", "c", "d"]
Array<Point> array;
[(1,2), (3,4), (5,6), (7,8)]
1
2
3
4
5
6

int型动态数组的实现过程

首先需要，声明一个动态数组类，成员变量包含：指向数组首元素的指针变量、当前数组的长度、初始化数组的容量。

class DynamicArray
{
private:
	int *m_data;	//指向数组的首元素
	int m_size;		//当前数组中元素的个数
	int m_capacity;	//当前数组的容量，也就是最大长度
public:
	DynamicArray(int);
	~DynamicArray();
	void append(int);	//向数组中添加元素，添加在当前数组元素的下一位
	int get(int);   //获取指定index处的值
	int size();     //返回当前数组的长度，也就是元素的格式
};
1
2
3
4
5
6
7
8
9
10
11
12
13

• 首先是构造函数的实现：初始化数组的容量，并且申请堆空间存储数组内容，同时将堆空间的首地址赋值给指向数组首地址的指针。
• 析构函数需要释放刚创建的堆空间

DynamicArray::DynamicArray(int capacity = 0)
{
	//如果实例数组对象时，传入的小于0或者等于0的数，那数组默认的长度就是4
	m_capacity = (capacity > 0) ? capacity : 10;
	// 申请堆空间，存储当前容量数组,m_data指向数组的首地址，也就是这段堆空间的首地址
	m_data = new int[m_capacity];
}

DynamicArray::~DynamicArray()
{
	if (m_data == NULL) return;
	delete[] m_data;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

• 实现向数组中添加元素。添加完元素之后，m_size要++，因为数量加1了。
• 如果当前元素的个数达到数组容量容量，就要扩容，这是动态数组的核心技术。
• 扩容的步骤就是：申请一个更大的堆空间、将旧空间的内容拷贝至新的存储空间、回收之前数组的堆空间。

void DynamicArray::append(int value)
{
	// 扩容:如果此次添加元素时，数组中的元素已经达到了数组容量，那么就需要扩容之后，才能将value添加进去
	if (m_size == m_capacity)
	{
		/*  扩容步骤：
		1、申请一个更大的堆空间
		2、将旧空间的内容拷贝至新的存储空间
		3、回收之前数组的堆空间
		*/

		// 申请一个更大的堆空间
		int *new_data = new int(m_capacity + m_capacity/2);

		// 将旧空间的内容拷贝至新的存储空间
		for (int i = 0; i < m_size; i++)
		{
			new_data[i] = m_data[i];
		}

		// 回收之前数组的堆空间
		delete[] m_data;
		m_data = new_data; //m_data 指向新空间的首地址：数组指针更新
		m_capacity = m_capacity + m_capacity / 2; //数组容量更新

	}

	m_data[m_size++] = value; //将要添加的值，添加在当前数组的最后一位
}
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

• 实现根据索引获取相应值

int DynamicArray::get(int index)
{
	//先判断索引是否越界
	if (index < 0 || index >= m_size)
	{
		throw "数组越界"; //抛出异常throw
	}

	return m_data[index];
}
1
2
3
4
5
6
7
8
9
10

• 实现可以随时查看数组的长度

int DynamicArray::size()
{
	return m_size;
}
1
2
3
4

此时，我们在main函数中验证一下，数组的动态扩容是否实现了：

int main()
{
	DynamicArray array(5); //先申请一个长度为5的数组
	array.append(1);
	array.append(2);
	array.append(3);
	array.append(4);
	array.append(5);  //到此，数组就已经满了

	cout << array.get(4) << endl; // 5

	array.append(6);  //继续添加
	cout << array.get(5) << endl;  //打印正常： 6

	getchar();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

说明，动态数组已经扩容成功，可以自适应的扩充数组的容量。

有一个小问题啊，我们通常根据索引获取数组元素的时候，都是采用：

array[5]
1

而不是：

array.get(5)
1

但由于array是我们定义的数组对象，因此需要重载符号"[ ]"

int operator[](int index)
{
	return m_data[index];
}
1
2
3
4

因此，我们在获取数组元素的时候，就不用get方法了，直接下标即可

array.append(6);  //继续添加
cout << array[5] << endl;  //打印正常： 6
1
2

类模板实现泛型动态数组

泛型动态数组，也就意味着数组的类型是多样的。数组不在局限于某一种数据类型，而是泛型。

Array<int> array;
[1, 2, 3, 4]
Array<char> array;
["a", "b", "c", "d"]
Array<Point> array;
[(1,2), (3,4), (5,6), (7,8)]
1
2
3
4
5
6

因此，我们使用类模板实现这个功能。

• 首先，类模板的定义格式与函数模板类似，需要在类的前面声明这是一个模板类。

泛型不是泛的类，而是泛类中某个成员的类型。比如，泛型类中的指向数组的指针类型。因此就需要注意，一些函数的入口参数和返回值，是否是泛型。

template <class Item>
class DynamicArray
{
private:
	Item *m_data;	//指向数组的首元素
	int m_size;		//当前数组中元素的个数
	int m_capacity;	//当前数组的容量，也就是最大长度
public:
	DynamicArray(int);
	~DynamicArray();
	void append(Item);	//向数组中添加元素，添加的元素是泛型
	Item get(int);   //获取指定index处的值，该值也是泛型
	int size();     //返回当前数组的长度，也就是元素的格式

	Item operator[](int index) //返回的值也是泛型
	{
		return m_data[index];
	}

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

将成员函数实现和声明分离之后，在每一个实现处，都有规范的写法：

template<class Item>
函数返回值 类名<Item>::函数名(参数)
1
2

需要注意的是，没有类模板的时候，类名后面是不需要加< Item>的，一旦有了泛型之后，类名就和泛型绑定了，在每一个函数都要加。

• append函数实现，需要改动的地方就是申请堆空间时，申请的是泛型类型的，而不是规定某一种类型（比如int）

template<class Item>
void DynamicArray<Item>::append(Item value)
{
	// 扩容:如果此次添加元素时，数组中的元素已经达到了数组容量，那么就需要扩容之后，才能将value添加进去
	if (m_size == m_capacity)
	{
		/*  扩容步骤：
		1、申请一个更大的堆空间
		2、将旧空间的内容拷贝至新的存储空间
		3、回收之前数组的堆空间
		*/

		// 申请一个更大的堆空间
		Item *new_data = new Item(m_capacity + m_capacity / 2);

		// 将旧空间的内容拷贝至新的存储空间
		for (int i = 0; i < m_size; i++)
		{
			new_data[i] = m_data[i];
		}

		// 回收之前数组的堆空间
		delete[] m_data;
		m_data = new_data;
		m_capacity = m_capacity + m_capacity / 2;

	}

	m_data[m_size++] = value; //将要添加的值，添加在当前数组的最后一位
}
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

• get函数的实现，返回值变为泛型，因为是获取数组中的元素（不一定是int型），是泛型的。

template<class Item>
Item DynamicArray<Item>::get(int index)
{
	//先判断索引是否越界
	if (index < 0 || index >= m_size)
	{
		throw "数组越界";
	}

	return m_data[index];
}
1
2
3
4
5
6
7
8
9
10
11

• 即使函数的参数，内部，返回值都用不到泛型，也要按照类模板的规定书写。

template<class Item>
int DynamicArray<Item>::size()
{
	return m_size;
}
1
2
3
4
5

• 构造函数和析构函数的书写。改动的地方就是申请堆空间时，申请的是泛型类型。

template<class Item>
DynamicArray<Item>::DynamicArray(int capacity)
{
	//如果实例数组对象时，传入的小于0或者等于0的数，那数组默认的长度就是4
	m_capacity = (capacity > 0) ? capacity : 10;

	// 申请堆空间，存储当前容量数组,m_data指向数组的首地址，也就是这段堆空间的首地址
	m_data = new Item[m_capacity]; //初始化堆空间时，初始的是泛型数据类型
}

template<class Item>
DynamicArray<Item>::~DynamicArray()
{
	if (m_data == NULL) return;
	delete[] m_data;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

至此，采用类模板实现的动态数组就基本完成了。

打印数组的实现

有些编程语言，例如Python可以直接打印数组，C++也可以实现这一点

打印数组，也就是打印对象，那就得需要运算符重载，重载<<运算符。

template<class Item>
ostream &operator<<(ostream &cout, const DynamicArray<Item> &array)
{
	cout << "[";
	for (int i = 0; i < array.size(); i++)
	{
		if (i != 0) //第一个元素前面不打印逗号，剩下的前面都打印逗号
		{
			cout << ", ";
		}
		cout << array[i];
		//if (i != array.m_size - 1) //最后一个的后面不打印逗号，其他元素都打印
		//{
		//	cout << ", ";
		//}
	}

	return cout << "]";
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

由于array是const类型的，所以array调用的所有函数都得是const成员函数，因此必须要额外将原本的成员函数变为const成员函数。

template<class Item>
int DynamicArray<Item>::size() const
{
	return m_size;
}
1
2
3
4
5

Item operator[](int index) const
{
	return m_data[index];
}
1
2
3
4

另一种做法不需要这样，那就是将函数变为友元函数，然后调用直接调用可以实现相同功能的成员变量即可。

友元函数：必须在括号前和重载符号后添加“<>”，这是语法糖，记住即可。

friend ostream &operator<<<>(ostream &cout, const DynamicArray<Item> &array);
1

array.size() 变为 array.m_size
array[i] 变为 array.m_data[i]

template<class Item>
ostream &operator<<<>(ostream &cout, const DynamicArray<Item> &array)
{
	cout << "[";
	for (int i = 0; i < array.m_size; i++)
	{
		if (i != 0)
		{
			cout << ", ";
		}
		cout << array.m_data[i];
	}

	return cout << "]";
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

两种方式，更倾向于后者，因为后者减少调用函数，减少开辟栈空间。

main函数打印char类型的数组。一旦有了类模板，声明对象的时候，类必须明确是那种类型，不可省略。

int main()
{
	DynamicArray<char> array(5);
	array.append('1');
	array.append('2');
	array.append('3');
	array.append('4');
	array.append('c');
	cout << array << endl;

	getchar();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

打印成功：