/* C++顺序表模板练习 以及 剖析易出现的浅拷贝问题 */

#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>

#include <string>

using namespace std;

template <typename T>

class SeqList

{

public:

SeqList();

SeqList(const SeqList& s);

~SeqList();

void PushBack(const T& d);

void PopBack();

void PushFront(const T& d);

void PopFront();

int Find(const T& d);

void Reverse();

void Insert(int pos, const T& d);

void sort();

SeqList& operator=(const SeqList& s);

void Print()

{

int i = 0;

for(i = 0; i < _size; i++)

{

cout<<_data[i]<<"  ";

}

cout<<endl;

}

private:

void _check_capacity()

{

if(_size == _capacity)

{

T* tmp = new T[2 * _capacity + 3];

//======注意 1 memcpy()浅拷贝问题 ===================

//对于含有指向动态开辟空间的类

//memcpy() 会出现浅拷贝现象 导致两个类的成员指针

//指向同一块空间 析构两次时导致【程序崩溃】

//比如 string类 内部含有这样一个指针

//当然 还有初始预留的空间 如果字符串没有超过预留空间

//指向动态空间的指针为空 用memcpy(）也没事

//但当这个指针指向空间是 一等会由于浅拷贝导致析构

//失败的 

//==============================================

string类 结构示意图

//memcpy(tmp, _data, _size * sizeof(T));

//===========================================

//解决方法

//利用 string类 自带的operator=()一个一个复制

//避免出现浅拷贝现象 

//不过memcpy()也有优点 那就是效率高

// 另外一种更加高效的方法 对于不同类型 自动使用不同处理方式 如int 用memcpy

// string用一个一个拷贝 

//这种方法就是 类型萃取

// 详见 http://alick.blog.51cto.com/10786574/1758122

//===========================================

for(int i = 0; i < _size; i++)

{

tmp[i] = _data[i];

}

delete[] _data;

_data = tmp;

_capacity = 2 * _capacity + 3;

}

}

private:

int _size;

int _capacity;

T* _data;

};

//=================注意2 默认拷贝函数出现浅拷贝问题 ===========

//这要写 拷贝构造 防止出现浅拷贝问题

// 例如对于string这种含有指向动态开辟空间 的 指针成员

template <typename T>

SeqList<T>::SeqList(const SeqList<T>& s)

{

_data = new T[s._size];

int i = 0;

for(i = 0; i < s._size; i++)

{

_data[i] = _data[i];

}

_size = s._size;

_capacity = _size;

}

template <typename T>

SeqList<T>::SeqList()

:_size(0)

,_capacity(3)

,_data(new T[_capacity])//注意：声明类变量时要先声明_capacity 再生命_data 

{

//cout<<typeid(_capacity).name() <<endl;

//cout<<"SeqList()"<<endl;

}

template <typename T>

SeqList<T>::~SeqList()

{

if (_data != NULL)

{

delete[] _data;

_data = NULL;

}

}

template <typename T>

void SeqList<T>::PushBack(const T& d)

{

_check_capacity();

_data[_size] = d;

_size++;

}

template <typename T>

void SeqList<T>::PopBack()

{

if(_size > 0)

{

_size--;

}

}

template <typename T>

void SeqList<T>::PushFront(const T& d)

{

_check_capacity();

int i = _size;

while(i)

{

_data[i] = _data[i - 1];

i--;

}

_data[0] = d;

_size++;

}

template <typename T>

void SeqList<T>::PopFront()

{

int i = 0;

for(i = 0; i < _size - 1; i++)

{

_data[i] = _data[i + 1];

}

_size--;

}

template <typename T>

SeqList<T>& SeqList<T>::operator=(const SeqList& s)//注意用SeqList<T>&

{

if(this != &s)

{

delete[] _data;

_data = new T[s._capacity];

memcpy(_data, s._data, s._size * sizeof(T));

_size = s._size;

_capacity = s._capacity;

}

return *this;

}

template <typename T>

int SeqList<T>::Find(const T& d)

{

int i = 0;

for (i = 0; i < _size; i++)

{

if(_data[i] == d)

{

return i;

}

}

return -1;

}

template <typename T>

void SeqList<T>::Reverse()

{

int left = 0;

int right = _size - 1;

while(left < right)

{

swap(_data[left], _data[right]);

left++;

right--;

}

}

template <typename T>

void SeqList<T>::Insert(int pos, const T& d)

{

if(pos < 0 || pos > _size)

{

return;

}

_check_capacity();

int i = _size;

_size++;

while(i > pos)

{

_data[i] = _data[i - 1];

i--;

}

_data[pos] = d;

}

template <typename T>

void SeqList<T>::sort()

{

int i = 0;

for(i = 0; i < _size; i++)

{

bool flag = true;

for(int j = 0; j < _size - i - 1; j++)

{

if(_data[j] > _data[j + 1])

{

T temp = _data[j];

_data[j] = _data[j + 1];

_data[j + 1] = temp;

flag = false;

}

}

if(flag)

{

return;

}

}

}

int main()

{

{

//SeqList<int> s1;

/*s1.PushBack(1);

s1.PushBack(2);

s1.PushBack(3);

s1.PushBack(4);

s1.Print();

s1.PopBack();

s1.Print();

s1.PopBack();

s1.Print();

s1.PopBack();

s1.Print();

s1.PopBack();

s1.Print();

s1.PopBack();

s1.Print();

s1.PopBack();

s1.Print();*/

//s1.PushFront(1);

//s1.PushFront(2);

//s1.PushFront(3);

//s1.PushFront(4);

//s1.Print();

//s1.PopFront();

//s1.Print();

//s1.PopFront();

//s1.Print();

//s1.PopFront();

//s1.Print();

//s1.PopFront();

//s1.Print();

//s1.PopFront();

//s1.Print();

//s1.PopFront();

//s1.Print();

/*SeqList<string> s2;

s2.PushBack("1");

s2.PushBack("11111112222222222");

s2.Print();*/

//s2.PushBack();

//s2.PushBack();

//s2.PushBack();

SeqList <string> s1;

s1.PushBack("11111");

s1.PushBack("222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222");

s1.PushBack("33333");

s1.PushBack("44444");

s1.PushBack("44444");

/*s1.PushBack("44444");

s1.PushBack("44444");

s1.PushBack("44444");

s1.PushBack("44444");

s1.PushBack("44444");

s1.PushBack("44444");*/

s1.Print();

SeqList <string> s2(s1);

//s2 = s1;

s2.Print();

/*s1.PushBack(4);

s1.PushBack(3);

s1.PushBack(2);

s1.PushBack(1);

s1.Print();*/

/*s1.sort();

s1.Print();

cout<<s1.Find(3)<<endl;

s1.Insert(s1.Find(3),4);

s1.Print();*/

/*SeqList<int> s2 = s1;

s2.Print();*/

}

//test2();

getchar();

return 0;

}

本文出自 “城市猎人” 博客，请务必保留此出处http://alick.blog.51cto.com/10786574/1754506