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

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

 #pragma once
 #include<iostream>
 #include<string>
 #include<stdlib.h>
 using namespace std;

 template <class T>
 class Vector
 {
 public:
     Vector()   //构造函数
         :_array(NULL)
         ,size()
         ,capacity()
     {}
        Vector(const Vector<T>& v)    //拷贝构造函数
       {
            _array = (T*)malloc(v._array, sizeof(T)*size); //注：问题一
            memcpy(v._array, _array, sizeof(T)*size);
            size = v.size;
            capacity = v.size;
        }

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

 问题2：
 1     Vector<T>& operator=(const Vector<T>& v) {   //赋值运算符重载
     if (this != &v) {
         Vector<T> tmp(v);
         swap(tmp);
     }
 6     return *this;
 6     }
         void swap(Vector<T>& v) {
         std::swap(_array, v._array);
         std::swap(size, v.size);
         std::swap(capacity, v.capacity);
     }
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函数适用于内置类型，下面看这句代码

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

这段代码会出现什么情况呢？转到定义处，来看一下swap函数内部是如何实现的。我们用的swap函数是这个模板实例化来的，它的倒数第二行，和倒数第三行都调用了赋值运算符重载函数，这样就造成递归调用，一直生成栈帧，直至出现栈溢出问题。为了解决这种问题，一般我们使用自己写的swap函数来实现需要的功能。

 ~Vector() {   //析构函数
         if (_array) {
             delete[] _array;
             _array = NULL;
             size = ;
             capacity = ;
         }
     }
     void PushBack(const T& x) {   //尾插
         _CheckCapacity();
         _array[size] = x;
         ++size;
     }
     void PopBack() {   //尾删
         if(!Empty())
         size--;
     }
     void PushFront(const T& x) {   //头 插
         _CheckCapacity();
         for (size_t i = size; i > ; i--) {
             _array[i] = _array[i - ];
         }
         _array[] = x;
         ++size;
     }
     void PopFront() {   //头删
         if(!Empty()){
             for (size_t i = ; i < size; i++) {
                 _array[i] = _array[i + ];
             }
             size--;
         }
     }
 void Insert(size_t pos, const T& x) {   //任意位置插入
         _CheckCapacity();
         for (size_t i = size; i > pos; i--) {
             _array[i] = _array[i - ];
         }
         _array[pos] = x;
         ++size;
     }
     void Erase(size_t pos) {   //任意位置删除
         if (!Empty()) {
             if (pos >= size)
                 return;
             else {
                 for (size_t i = pos; i < size; i++) {
                     _array[i] = _array[i + ];
                 }
                 size--;
             }
         }
     }
     size_t Size()const {   //返回顺序表的数据个数
         return size;
     }
     size_t Capacity()const {   //返回顺序表的容量
         return capacity;
     }
     T& Top() {   //取顺序表头值
         return _array[];
     }
     bool Empty() {   //清空顺序表
         return size == ;
     }
     void Print() {   //打印顺序表
         for (size_t i = ; i < size; i++)
         {
             cout << _array[i] << " ";
         }
         cout << endl;
     }
 private:
 void CheckCapacity()   //注：问题三
     {
         if (_size > _capacity)
         {
             _capacity = _capacity *  + ;
             _a = (T*)realloc(_a, (_capacity) * sizeof(T));
         }
     }
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 =  * capacity + ;
            T* tmp = new T[newCapacity];
            if (_array) {
                memcpy(tmp._array, _array, sizeof(T)*size);
            }
            delete[] _array;
            _array = tmp;
            capacity = newCapacity;
        }
    }

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

 void Test1() {
     Vector<string>v1;
     v1.PushBack("111");
     v1.PushBack("222222222222222222222222222222222222222");
     v1.PushBack("");
6     v1.PushBask("444")
     v1.Print();
 }

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

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

 class string
 {
   string* _Buf[];
   string* _Ptr;
     size_t _Mysize;
     size_t _Myres;
 };

可以在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 = ; i < size; i++) {
            _array[i] = v._array[i];
        }
    }
    void _CheckCapacity() {    //扩容函数
        if (size == capacity) {
            size_t newCapacity =  * capacity + ;
            T* tmp = new T[newCapacity];
            if (_array) {
                for (size_t i = ; i < size; i++) {
                    tmp[i] = _array[i];
                }
            }
            delete[] _array;
            _array = tmp;
            capacity = newCapacity;
        }
    }

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

以下是测试程序

 void Test1() {     //深拷贝测试程序
     Vector<string>v1;
     v1.PushBack("");
     v1.PushBack("2222222222222222222222222222222222222222222222");
     v1.PushBack("");
     v1.PushBack("")
     v1.Print();
 }
 void Test2()
 {
     Vector<int> list1;
     list1.PushBack();   //尾插
     list1.PushBack();
     list1.PushBack();
     list1.PushBack();
     list1.PushBack();
     list1.Print();
     list1.PopBack();   //尾删
     list1.PopBack();
     list1.PopBack();
     list1.PopBack();
     list1.Print();
     list1.PushFront();   //头插
     list1.PushFront();
     list1.PushFront();
     list1.Print();
     list1.PushFront();
     list1.Print();
     list1.PopFront();      //头删
     list1.PopFront();
     list1.PopFront();
     list1.Print();
     Vector<int> list2(list1);     //拷贝构造函数测试
     list2.Print();
     list1.Insert(, );     //任意位置插入
     list1.Print();
     list1 = list2;    //赋值运算符
     list1.Print();
         list1.Erase();      //任意位置删除
         list1.Print();
 }
 int main()
 {
     Test1();
     Test2();
     getchar();
     return ;
 }

下面是输出结果：

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

 template<class T,class Container = Vector<T>>
 class Stack
 {
 public:
     void Push(const T& x) {  //入栈
         Vector<T>::PushBack(x);
     }
     void Pop() {  //出栈
         Vector<T>::PopBack();
     }
     const T& Top() {  //取栈顶元素值
         return Vector<T>::Top();
     }
     const size_t Size() {  //返回栈中元素个数
         return Vector<T>::Size();
     }
     bool Empty() {  //判空栈
         return Vector<T>::Empty();
     }
 private:
     Container _con;
 };