首页 > 代码库 > C++模板实现动态顺序表（更深层次的深浅拷贝）与基于顺序表的简单栈的实现
C++模板实现动态顺序表（更深层次的深浅拷贝）与基于顺序表的简单栈的实现
前面介绍的模板有关知识大部分都是用顺序表来举例的，现在我们就专门用模板来实现顺序表，其中的很多操作都和之前没有多大区别，只是有几个比较重要的知识点需要做专门的详解。
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的交换。图解如下：
注：swap函数也不能乱用，一般来说，swap函数适用于内置类型，下面看这句代码
1 swap(*this,l); //直接交换两个对象岂不更好？
这段代码会出现什么情况呢？转到定义处，来看一下swap函数内部是如何实现的。
我们用的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 }
输的结果不尽如任意：
但是将第二行测试程序改为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不能展示出来。如此，我们便可以知道上面的代码在拷贝时出现了问题，下面我用图示来解释上面的测试代码测出的问题。 
当我们测试的代码往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 }
下面是输出结果：
基于顺序表的简单栈的实现
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 };
C++模板实现动态顺序表（更深层次的深浅拷贝）与基于顺序表的简单栈的实现