天天看點
傳回

C++模闆封裝Vector和帶頭結點的雙向連結清單

C++模闆封裝Vector:

注意：

在Vector的拷貝構造，擴容函數中，需要注意string的影響。（深層次的深淺拷貝的問題）

在插入string類的變量時，這裡會發生兩個錯誤，一個是對已經釋放的記憶體進行通路，另一個是記憶體的多次析構。

我們知道在windows下或者是說在VS2013環境下,string類的大小為28，這是因為string類為了高效的存取資料，類中有一個大小為16的空間，當建立的對象大小小于16時将直接存在對象中，是以在發生記憶體拷貝時，memcpy并不會出現問題。析構時，新空間和舊空間各自釋放各自的空間，并不會發生錯誤。

但是當對象的大小超過16時，編譯器就會建立一塊空間存放字元串，并使string中的指針指向這塊空間，但是memcpy拷貝時就隻拷貝指向空間的指針，這是發生的就是淺拷貝，兩個指針指向了同一塊記憶體，在擴容函數中調用delete時已經釋放了這塊記憶體，再對其進行通路時，獲得的就是随機值，并且在最後析構的時候，因為對已經析構了的記憶體進行析構，就會導緻程式崩潰。

C++模闆封裝Vector和帶頭結點的雙向連結清單

為了解決這個問題：我們可以采用for循環對對象進行深拷貝。（本質是調用string類的 operator=），但是我們不能進行類型的判斷而選擇不同的代碼執行方案（可以選擇類型萃取），是以目前選擇深拷貝來進行拷貝。

代碼：

為了防止分離編譯的問題這裡将類的聲明和定義都放在 Vector.h中。

#pragma once 

#include <iostream>
#include <assert.h>
#include <string.h>
#include <string>

using namespace std;

template<class T>
class Vector
{
public:

	Vector();
	Vector(const Vector<T>& v);
	//Vector<T>& operator=(const Vector<T>& v);
	Vector& operator=(Vector<T> v);
	~Vector();
	

	//inline size_t Size()const;
	inline size_t Size() const;
	inline size_t Capacity() const;
	inline bool Empty();
	void PushBack(const T& x);
	void PopBack();
	void Insert(size_t pos, const T& x);
	void Erase(size_t pos);
	size_t Find(const T& x);
	void Print();
	const T& Back()const
	{
		return *(_finish - 1);
	}
	T& operator[](size_t index)
	{
		return _start[index];
	}
	void Expand(size_t n);
	void Clear()
	{
		_finish = _start;
	}
protected:
	
	T* _start;
	T* _finish;
	T* _endofstorage;
};

//類名  ：  aa  vector
//類型名：  aa  vector<T>

template<class T>
Vector<T>::Vector()
:_start(NULL)
, _finish(NULL)
, _endofstorage(NULL)
{}

//v1(v2);
template<class T>
Vector<T>::Vector(const Vector<T>& v)   
{
	_start = new T[v.Size()];
//	memcpy(_start, v._start, sizeof(T)* v.Size());   //string類型資料的拷貝會存在深淺拷貝的問題
	for (int i = 0; i < Size(); ++i)
	{
		_start[i] = v._start[i];
	}

	_finish = _start + v.Size();
	_endofstorage = _start + v.Capacity();
}

template<class T>
Vector<T>& Vector<T>::operator=(Vector<T> v)			//Vector<T>類型   Vector 類名
{
	if (_start != v._start)
	{
		swap(_start, v._start);
		swap(_finish, v._finish);
		swap(_endofstorage, v._endofstorage);
	}
	return *this;
}

template<class T>
Vector<T>::~Vector()
{
	delete []_start;		
	_start = _finish = _endofstorage = NULL;
}

template<class T>
inline size_t Vector<T>::Size()const
{
	return _finish - _start;
}

template<class T>
inline size_t Vector<T>::Capacity() const
{
	return _endofstorage - _start;
}

template<class T>
inline bool Vector<T>::Empty()
{
	return _start == _finish;
}

template<class T>
void Vector<T>::Insert(size_t pos, const T& x)
{
	assert(pos <= Size());

	if (Size() >= Capacity())
	{
		Expand(Capacity() * 2);
	}

	T* end = _finish - 1;
	while (end >= _start + pos)
	{
		*(end + 1) = *end; 
		--end;
	}
	_start[pos] = x;
	++_finish;
}

template<class T>
void Vector<T>::Erase(size_t pos)
{
	assert(pos < Size());

	T* Cur = _start + pos + 1;
	while (Cur != _finish)//<
	{
		*(Cur - 1) = *Cur;
		++Cur;
	}
	--_finish;
}

template <class T>
void Vector<T>::Expand(size_t n)
{
	if (Empty())
	{
		_start = new T[3];
		_finish = _start;
		_endofstorage = _start + 3;
	}
	else if (n > Capacity())	//擴容時進行記憶體拷貝如果是string類型的時候會出現錯誤，因為要進行資料拷貝，
								//string有16個字元大小的buf數組空間，小一點的時候是存放在buf中
								//大的時候進行拷貝發生的是淺拷貝，開辟空間，指針指向同一個位置釋放空間出錯
	{
		size_t size = Size();
		T* tmp = new T[n];
		memcpy(tmp, _start, sizeof(T)* Size());
		//for (size_t i = 0; i < Size(); i++)
		//{
		//	tmp[i] = _start[i];
		//}

		delete []_start;						//調析構函數，再調free, 如果是string深層次調用string的析構函數，
											//淺拷貝導緻的析構兩次的問題
		_start = tmp;
		_finish = _start + size;
		_endofstorage = _start + n;
	}
}

template <class T>
void Vector<T>::PushBack(const T& x)
{
	Insert(Size(), x);
}

template <class T>
void Vector<T>::PopBack()
{
	Erase(Size() - 1);
}

template <class T>
size_t Vector<T>::Find(const T& x)
{
	T* Cur = _start;
	while (Cur != _finish)
	{
		if (*Cur == x)
		{
			return Cur - _start;
		}
	}
	return -1;
}

template <class T>
void Vector<T>::Print()
{
	T* Cur = _start;
	while (Cur != _finish)
	{
		cout << *Cur << " ";
		++Cur;
	}
	cout << endl;
}



void TestVector()
{
	//Vector<char> v1;
	//v1.PushBack('c');
	//v1.PushBack('c');
	//v1.PushBack('c');
	//v1.PushBack('c');
	//v1.PushBack('c');
	//v1.PushBack('c');
	//v1.PushBack('c');

	//v1.Print();
	//Vector<char>v2(v1);
	//v2.Print();

	Vector<string> v3;  //string類型發生擴容的時候的空間拷貝比較特殊
	v3.PushBack("1");				//char*  []
	v3.PushBack("2");
	//v3.PushBack("111b1111111111111111111111111111111111111111");		
	v3.PushBack("4");
	//v3.PopBack();
	v3.Print();

}

SList.h

#pragma once

#include <iostream>
#include <string>
#include <assert.h>

using namespace std;

template<class T>
struct SListNode{
	SListNode(const T& x)
		: _data(x)
		, _prev(NULL)
		, _next(NULL)
	{}
	T _data;
	SListNode<T>* _prev;
	SListNode<T>* _next;
};

template<class T>
class SList{
	typedef SListNode<T> Node;
public:
	SList()
	{
		_head = new Node(T());
		_head->_prev = _head;
		_head->_next = _head;
	}

	SList(const SList<T>& l);

	//SList<T>& operator=(const SList<T>& l);
	SList<T>& operator=(SList<T> l);

	~SList();
	void PushBack(const T& x);
	void PopBack();
	void PushFront(const T& x);
	void PopFront();
	// pre  newnd  pos
	void Insert(Node* pos, const T& x);
	// pre pos next
	void Erase(Node* pos);
	void Clear();
	void Print();
	void Swap(SList<T>& l);
	size_t Size()const;
	const T& Back()const;
	const T& Front()const;
	bool Empty()const;

protected:
	Node* _head;
};

template<class T>
SList<T>::SList(const SList<T>& l)
:_head(new Node(T()))
{
	_head->_next = _head;
	_head->_prev = _head;

	Node* pCur = l._head->_next;
	while (pCur != l._head)
	{
		PushBack(pCur->_data);
		pCur = pCur->_next;
	}
}

template<class T>
SList<T>& SList<T>::operator=(SList<T> l)
{
	swap(_head, l._head);

	return *this;
}

template<class T>
SList<T>::~SList()
{
	//Node* pCur = _head->_next;
	//Node* Next = NULL;
	//while (pCur != _head)
	//{
	//	Next = pCur->_next;
	//	delete pCur;
	//	pCur = Next;
	//}
	Clear();
	delete _head;
	_head = NULL;
}

template<class T>
void SList<T>::PushBack(const T& x)
{
	Insert(_head, x);
}

template<class T>
void SList<T>::PopBack()
{
	Erase(_head->_prev);
}

template<class T>
void SList<T>::PushFront(const T& x)
{
	Insert(_head->_next, x);
}

template<class T>
void SList<T>::PopFront()
{
	Erase(_head->_next);
}

template<class T>
void SList<T>::Insert(Node* pos, const T& x)
{
	assert(NULL != pos);
	Node* NewNode = new Node(T(x));
	Node* Pre = pos->_prev;

	NewNode->_prev = Pre;
	NewNode->_next = pos;
	Pre->_next = NewNode;
	pos->_prev = NewNode;
}

template<class T>
void SList<T>::Erase(Node* pos)
{
	assert(_head != pos);
	Node* Pre = pos->_prev;
	Node* Next = pos->_next;

	Pre->_next = Next;
	Next->_prev = Pre;
	delete pos;
	pos = NULL;
}

template<class T>
void SList<T>::Clear()
{
	Node* Cur = _head->_next;
	Node* Next = NULL;
	while (Cur != _head)
	{
		Next = Cur->_next;
		delete Cur;
		Cur = Next;
	}
}

template<class T>
void SList<T>::Print()
{
	Node* pCur = _head->_next;

	while (pCur != _head)
	{
		cout << pCur->_data << " ";
		pCur = pCur->_next;
	}
	cout << endl;

}

template<class T>
void SList<T>::Swap(SList<T>& l)
{
	swap(_head, l._head);
}

template<class T>
size_t SList<T>::Size()const
{
	size_t size = 0;
	Node* Cur = _head->_next;
	while (Cur != _head)
	{
		++size;
		Cur = Cur->_next;
	}
	return size;
}

template<class T>
const T& SList<T>::Back()const
{
	return _head->_prev->_data;
}

template<class T>
const T& SList<T>::Front()const
{
	return _head->_next->_data;
}

template<class T>
bool SList<T>::Empty() const
{
	return _head->_next == _head;
}

void TestSList()
{
	SList<string> l1;
	l1.PushBack("1111");
	l1.PushBack("1112");
	l1.PushBack("1113");
	l1.PushBack("1114");
	l1.PushBack("1115");
	l1.Print();
	l1.PopBack();
	l1.Print();
	
}
c++ vector模拟實作 list模拟實作
上一篇: C++ Vector用法深入剖析http://developer.51cto.com/art/201002/183645.htmC++ Vector用法深入剖析
下一篇: string類的模拟之深淺拷貝

繼續閱讀