C++模板实现动态顺序表(更深层次的深浅拷贝)与基于顺序表的简单栈的实现

时间:2021-10-03 21:40:10

前面介绍的模板有关知识大部分都是用顺序表来举例的,现在我们就专门用模板来实现顺序表,其中的很多操作都和之前没有多大区别,只是有几个比较重要的知识点需要做专门的详解。

 1 #pragma once
2 #include<iostream>
3 #include<string>
4 #include<stdlib.h>
5 using namespace std;
6
7 template <class T>
8 class Vector
9 {
10 public:
11 Vector() //构造函数
12 :_array(NULL)
13 ,size(0)
14 ,capacity(0)
15 {}
16 Vector(const Vector<T>& v) //拷贝构造函数
17 {
18 _array = (T*)malloc(v._array, sizeof(T)*size); //注:问题一
19 memcpy(v._array, _array, sizeof(T)*size);
20 size = v.size;
21 capacity = v.size;
22 }

问题一实质同下面的问题3,后面再做详细分析。

 问题2:
1
Vector<T>& operator=(const Vector<T>& v) { //赋值运算符重载 2 if (this != &v) {
3 Vector<T> tmp(v);
4 swap(tmp);
5 }
6 return *this;
6 }
6 void swap(Vector<T>& v) {
7 std::swap(_array, v._array);
8 std::swap(size, v.size);
9 std::swap(capacity, v.capacity);
10 }
11 list1 = list2;

这里很有必要详解实现上面赋值运算符重载的现代写法的实现原理 :首先看上面代码(list1 = list2;),赋值运算符重载中的局部变量tmp是由v即list2拷贝构造而来,函数体内通过swap函数将this指针指向的list1与tmp发生了交换,即list1与list2发生了交换,局部变量tmp现在指向之前list1指向的地址,而list1指向tmp原先指向的地址,也就是list1被赋值成了list2,而局部变量tmp一出函数就会自动销毁,就会调用它的析构函数,会使得它指向的内存释放,从而实现list1与list2的交换。图解如下:C++模板实现动态顺序表(更深层次的深浅拷贝)与基于顺序表的简单栈的实现C++模板实现动态顺序表(更深层次的深浅拷贝)与基于顺序表的简单栈的实现

 注:swap函数也不能乱用,一般来说,swap函数适用于内置类型,下面看这句代码

1 swap(*this,l);   //直接交换两个对象岂不更好?

这段代码会出现什么情况呢?转到定义处,来看一下swap函数内部是如何实现的。C++模板实现动态顺序表(更深层次的深浅拷贝)与基于顺序表的简单栈的实现我们用的swap函数是这个模板实例化来的,它的倒数第二行,和倒数第三行都调用了赋值运算符重载函数,这样就造成递归调用,一直生成栈帧,直至出现栈溢出问题。为了解决这种问题,一般我们使用自己写的swap函数来实现需要的功能。

 1 ~Vector() {   //析构函数
2 if (_array) {
3 delete[] _array;
4 _array = NULL;
5 size = 0;
6 capacity = 0;
7 }
8 }
9 void PushBack(const T& x) { //尾插
10 _CheckCapacity();
11 _array[size] = x;
12 ++size;
13 }
14 void PopBack() { //尾删
15 if(!Empty())
16 size--;
17 }
18 void PushFront(const T& x) { //头 插
19 _CheckCapacity();
20 for (size_t i = size; i > 0; i--) {
21 _array[i] = _array[i - 1];
22 }
23 _array[0] = x;
24 ++size;
25 }
26 void PopFront() { //头删
27 if(!Empty()){
28 for (size_t i = 0; i < size; i++) {
29 _array[i] = _array[i + 1];
30 }
31 size--;
32 }
33 }
34 void Insert(size_t pos, const T& x) { //任意位置插入
35 _CheckCapacity();
36 for (size_t i = size; i > pos; i--) {
37 _array[i] = _array[i - 1];
38 }
39 _array[pos] = x;
40 ++size;
41 }
42 void Erase(size_t pos) { //任意位置删除
43 if (!Empty()) {
44 if (pos >= size)
45 return;
46 else {
47 for (size_t i = pos; i < size; i++) {
48 _array[i] = _array[i + 1];
49 }
50 size--;
51 }
52 }
53 }
54 size_t Size()const { //返回顺序表的数据个数
55 return size;
56 }
57 size_t Capacity()const { //返回顺序表的容量
58 return capacity;
59 }
60 T& Top() { //取顺序表头值
61 return _array[0];
62 }
63 bool Empty() { //清空顺序表
64 return size == 0;
65 }
66 void Print() { //打印顺序表
67 for (size_t i = 0; i < size; i++)
68 {
69 cout << _array[i] << " ";
70 }
71 cout << endl;
72 }
73 private:
74 void CheckCapacity() //注:问题三
75 {
76 if (_size > _capacity)
77 {
78 _capacity = _capacity * 2 + 3;
79 _a = (T*)realloc(_a, (_capacity) * sizeof(T));
80 }
81 }
82

  83      T* _array;
  84     size_t size;
  85     size_t capacity;
  86     };

来看上面代码,这些代码在int, char等一些内置类型下是可以被顺利执行的,但是一旦换成string类型或其他自定义类型就会出现问题,在执行插入操作时,代码就会崩掉,这是什么问题呢?其实很容易看出问题出在新开辟空间时,即代码中标注的问题一与问题三(见代码中标注),在拷贝构造函数Vector(const Vector<T>& v)与扩容函数CheckCapacity()函数中,我们开辟新空间用的是malloc与realloc函数,这里有个问题,malloc和realloc函数只负责开空间,但不初始化,所以在插入操作的赋值语句时挂了,调试你会发现它的_array就是NULL,所以就会出现问题。所以我们用new[]来开辟空间,用delete[]来销毁空间,其实它与malloc和realloc函数最大的区别是new[]开辟新空间时顺便会调用构造函数初始化对象,这是这个问题的重点所在。我们将这个问题一改用new[]和delete[]分别代替malloc/realloc和free。改完之后的代码如下:

        Vector(const Vector<T>& v)   //拷贝构造函数
: _array(new T[sizeof(T) * v.capacity])
, size(v.size)
, capacity(v.capacity)
{
memcpy(_array, v._array,
sizeof(T)*size);
}
void _CheckCapacity() { //扩容函数
if (size == capacity) {
size_t newCapacity
= 2 * capacity + 3;
T
* tmp = new T[newCapacity];
if (_array) {
memcpy(tmp._array, _array,
sizeof(T)*size);
}
delete[] _array;
_array
= tmp;
capacity
= newCapacity;
}
}

上面这段代码在int, char等一些内置类型下是可以被顺利执行的,而且貌似string类型或其他自定义类型下也没有问题。而其实这里面还存在另外一个更重要的问题,就是标题说到的更深层次的深浅拷贝的问题。当我用下面这段代码测试的时候,会有乱码出现

1 void Test1() {
2 Vector<string>v1;
3 v1.PushBack("111");
4 v1.PushBack("222222222222222222222222222222222222222");
5 v1.PushBack("333");
6 v1.PushBask("444")
6 v1.Print();
7 }

输的结果不尽如任意:C++模板实现动态顺序表(更深层次的深浅拷贝)与基于顺序表的简单栈的实现但是将第二行测试程序改为v1.PushBack(“22222222222”);又会正常输出,或者将v1.PushBaack(“444”)这句给屏蔽屏蔽掉,同样会正常输出。所以有理由相信在一定的范围内,或某种情况下,可以正常输出,超过一定范围就会出现异常。这里详解更深层次的深浅拷贝问题。

这里我们从String类的内部成员说起,其实string里面由下面四部分组成,这是一种以空间换时间的优化,如果String里保存的字符串长度小于15(实际可存16为16这里考虑了‘\0’),它就会将字符串保存于它自带的空间_Buf,而大于等于15时,他就会重新开辟一份空间存放这个字符串,并使用_Pre指向这块内存空间。

1 class string
2 {
3 string* _Buf[16];
4 string* _Ptr;
5 size_t _Mysize;
6 size_t _Myres;
7 };

可以在vs2008上面验证一下(调试窗口就可以看),我用的vs2015不能展示出来。如此,我们便可以知道上面的代码在拷贝时出现了问题,下面我用图示来解释上面的测试代码测出的问题。 C++模板实现动态顺序表(更深层次的深浅拷贝)与基于顺序表的简单栈的实现当我们测试的代码往String里存放的字符串长度值小于15时,它保存在字符数组_Buf[16]中,memcpy()函数可以正常拷贝,所以正常输出,当其值大于15时,将会开辟足够的新空间以存放字符串,并使_Pre指向新空间的起始地址,使用memcpy()函数拷贝时仅仅只拷贝了数据,即值拷贝,那么两个指针指向同一块地址,当原来那个String析构掉,开辟的空间销毁时,另一个指针任然指向原来的地址,那么它向后访问到的就是随机值,当析构拷贝过来的String时,又会调用析构函数对那块已经被析构的空间进行析构,所以程序最终崩溃。为了解决这个问题我们再次改进

    Vector(const Vector<T>& v)    //拷贝构造函数
: _array(new T[sizeof(T) * v.capacity])
, size(v.size)
, capacity(v.capacity)
{
for (size_t i = 0; i < size; i++) {
_array[i]
= v._array[i];
}
}
void _CheckCapacity() { //扩容函数
if (size == capacity) {
size_t newCapacity
= 2 * capacity + 3;
T
* tmp = new T[newCapacity];
if (_array) {
for (size_t i = 0; i < size; i++) {
tmp[i]
= _array[i];
}
}
delete[] _array;
_array
= tmp;
capacity
= newCapacity;
}
}

其中调用了赋值运算符的重载,即就是实现深拷贝。

 以下是测试程序

 1 void Test1() {     //深拷贝测试程序
2 Vector<string>v1;
3 v1.PushBack("111");
4 v1.PushBack("2222222222222222222222222222222222222222222222");
5 v1.PushBack("333");
6 v1.PushBack("444")
7 v1.Print();
8 }
9 void Test2()
10 {
11 Vector<int> list1;
12 list1.PushBack(1); //尾插
13 list1.PushBack(2);
14 list1.PushBack(3);
15 list1.PushBack(4);
16 list1.PushBack(5);
17 list1.Print();
18 list1.PopBack(); //尾删
19 list1.PopBack();
20 list1.PopBack();
21 list1.PopBack();
22 list1.Print();
23 list1.PushFront(2); //头插
24 list1.PushFront(3);
25 list1.PushFront(4);
26 list1.Print();
27 list1.PushFront(5);
28 list1.Print();
29 list1.PopFront(); //头删
30 list1.PopFront();
31 list1.PopFront();
32 list1.Print();
33 Vector<int> list2(list1); //拷贝构造函数测试
34 list2.Print();
35 list1.Insert(1, 0); //任意位置插入
36 list1.Print();
37 list1 = list2; //赋值运算符
38 list1.Print();
39 list1.Erase(1); //任意位置删除
40 list1.Print();
41 }
42 int main()
43 {
44 Test1();
45 Test2();
46 getchar();
47 return 0;
48 }

下面是输出结果:C++模板实现动态顺序表(更深层次的深浅拷贝)与基于顺序表的简单栈的实现

基于顺序表的简单栈的实现

 1 template<class T,class Container = Vector<T>>
2 class Stack
3 {
4 public:
5 void Push(const T& x) { //入栈
6 Vector<T>::PushBack(x);
7 }
8 void Pop() { //出栈
9 Vector<T>::PopBack();
10 }
11 const T& Top() { //取栈顶元素值
12 return Vector<T>::Top();
13 }
14 const size_t Size() { //返回栈中元素个数
15 return Vector<T>::Size();
16 }
17 bool Empty() { //判空栈
18 return Vector<T>::Empty();
19 }
20 private:
21 Container _con;
22 };