天天看點
傳回

[C++STL]C++實作list容器

代碼如下：

#pragma once
#include <iostream>
using namespace std;

template<typename T>
struct ListNode
{
	T _data;
	ListNode<T> *_next;
	ListNode<T> *_prev;

	ListNode(const T & val = T()) :_data(val), _next(nullptr), _prev(nullptr) {};
};


//template<typename T>
//struct ListIterator
//{
//	typedef ListNode<T> Node;
//	typedef ListIterator<T>  Self;
//	Node *_node;
//
//	ListIterator(Node * node = nullptr) :_node(node) {}
//
//
//	//但是該操作并不友善，通過解引用再擷取對象值。
//	/*以上的操作支援内置類型的基本操作，但是并不能滿足當結點存儲的内置類型的操作，
//	當對對象解引用時，是傳回的結點的_data，但是這個_data是一個對象，
//	也就并非能得到内置類型的值。*it得到的是對象，再通過.來獲得對象的屬性值。
//	例如:
//	struct A
//	{
//		int _a;
//		A(int a = 0):_a(a){}
//	};
//
//	使用時:
//	List<A> lst;
//	List<A>::iterator it = lst.begin();
//	cout<<(*it)._a<<endl;
//
//	*/
//	T &operator*()
//	{
//		return _node->_data;
//	}
//
//
//	//在STL庫中的疊代器可以直接通過->_a來擷取，疊代器是一個對象，
//	//怎麼可以通過->來擷取自定義類型的屬性呢？我們就必須重載->來實作。
//	//就是it->獲得自定義類型對象的位址，
//	//再通過->就可以獲得自定義類型對象的指定的值it->->_a
//	//	隻是在C++會進行優化，省略了其中的一個->。
//	//	下面是實作第一個->的代碼
例如:
	List<A> lst;
	List<A>::iterator it = lst.begin();
	cout << it->_a << endl;
//
//
//	T *operator->()
//	{
//		return &(_node->_data)
//	}
//
//	Self & operator++()
//	{
//		_node = _node->_next;
//		return *this;
//	}
//
//	Self operator++(int)
//	{
//		Self tmp(_node);
//		_node = _node->_next;
//		return tmp;
//	}
//
//	Self &operator--()
//	{
//		_node = _node->prev;
//		return *this;
//	}
//
//	Self operator--(int)
//	{
//		Self tmp(_node);
//		_node = _node->prev;
//		return tmp;
//	}
//
//	bool operator ==(const Self &s)
//	{
//		return _node == s._node;
//	}
//
//	bool operator!=(const Self &s)
//	{
//		return _node != s._node;
//	}
//};


//template<typename T>
//struct ConstListIterator
//{
//	typedef ListNode<T> Node;
//	typedef ConstListIterator<T> Self;
//	Node * _node;
//	ConstListIterator(Node *node = nullptr) :_node(node) {}
//
//	ConstListIterator(const Self &s):node(s._node){}
//
//	Self & operator++()
//	{
//		_node = _node->_next;
//		return *this;
//	}
//
//	Self operator++(int)
//	{
//		Self tmp(_node);
//		_node = _node->_next;
//		return tmp;
//	}
//
//	Self &operator--()
//	{
//		_node = _node->prev;
//		return *this;
//	}
//
//	Self operator--(int)
//	{
//		Self tmp(_node);
//		_node = _node->prev;
//		return tmp;
//	}
//
//	bool operator ==(const Self &s)
//	{
//		return _node == s._node;
//	}
//
//	bool operator!=(const Self &s)
//	{
//		return _node != s._node;
//	}
//
//	const T&operator*()
//	{
//		return _node->_data;
//	}
//
//	const T*operator->()
//	{
//		return &(_node->_data);
//	}
//	
//};



//上面是iterator 和 const_iterator 的分開實作，
//但是STL庫中實作并不是這樣子的，我們發現兩個疊代器類型隻是類中兩個成員函數的傳回值不一樣而已。
//其他代碼邏輯都是一樣的，是以我們可以通過多加兩個模闆類型來解決這個問題，讓他們成為一個類，隻是類型有所差别。
//在原來的疊代器中将模闆改為template<class T, class Ref, class Ptr> T為普通類型，Ref為引用類型，Ptr為指針類型。

template<typename T, typename Ref, typename Ptr>
struct ListIterator
{
	typedef ListNode<T> Node;
	typedef ListIterator<T, Ref, Ptr> Self;
	Node *_node;

	ListIterator(Node *node = nullptr) :_node(node) {}

	ListIterator(const Self &s) : _node(s._node) {}

	Self & operator++()
	{
		_node = _node->_next;
		return *this;
	}

	Self operator++(int)
	{
		Self tmp(_node);
		_node = _node->_next;
		return tmp;
	}

	Self &operator--()
	{
		_node = _node->_prev;
		return *this;
	}

	Self operator--(int)
	{
		Self tmp(*this);
		_node = _node->_prev;
		return tmp;
	}

	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &(_node->_data);
	}

	bool operator!=(const Self &s)
	{
		return _node != s._node;
	}

	bool operator==(const Self &s)
	{
		return _node == s._node;
	}
};


template<typename T>
class List
{
public:
	typedef ListNode<T> Node;
	typedef ListIterator<T, T &, T *> iterator;
	typedef ListIterator<T, const T&, const T*> const_iterator;


	/*typedef ListIterator<T> iterator;

	iterator begin()
	{
		return iterator(_header->_next);
	}

	iterator end()
	{
		return iterator(_header);
	}

	typedef ConstListIterator<T> const_iterator;

	const_iterator cbegin() const
	{
		return const_iterator(_header->_next);
	}

	const_iterator cend() const
	{
		return const_iterator(_header);
	}*/

	//上面是由于iterator 和 const_iterator 的分開實作，是以要這樣寫。


	//下面是iterator 和 const_iterator 合在一起後的寫法。
	iterator begin()
	{
		return iterator(_header->_next);
	}

	iterator end()
	{
		return iterator(_header);
	}

	const_iterator cbegin() const
	{
		return const_iterator(_header->_next);
	}

	const_iterator cend() const
	{
		return const_iterator(_header);
	}



	List() :_header(new Node())
	{
		_header->_next = _header->_prev = _header;
	}

	List(int n, const T&val = T()) :_header(new Node())
	{
		_header->_next = _header->_prev = _header;
		for (size_t i = 0; i < n; i++)
		{
			push_back(val);
		}
	}

	template<typename inputIterator>
	List(inputIterator first, inputIterator last) :_header(new Node())
	{
		_header->_next = _header->_prev = _header;
		while (first != last)
		{
			push_back(*first);
			++first;
		}
	}

	//拷貝構造函數，現代寫法
	List(List<T> &l) :_header(new Node())
	{
		_header->_next = _header->_prev = _header;
		List<T> tmp(l.begin(), l.end());
		swap(tmp);
	}


	//交換兩個對象的頭結點
	void swap(List<T> &l)
	{
		Node *tmp = l._header;
		l._header = this->_header;
		this->_header = tmp;
	}


	/*利用了拷貝構造函數建立新空間，
	然後再交換他們的頭結點，
	tmp離開函數就會自動釋放了*/

	List<T> &operator = (List<T> tmp)
	{
		swap(tmp);
		return *this;
	}

	void push_back(const T &val)
	{
		Node *tail = _header->_prev;
		Node *newNode = new Node(val);

		tail->_next = newNode;
		newNode->_prev = tail;

		newNode->_next = _header;
		_header->_prev = newNode;
	}

	void clear()
	{
		if (_header != nullptr)
		{
			Node *cur = _header->_next;
			while (cur != _header)
			{
				Node *next = cur->_next;
				delete[] cur;
				cur = nullptr;
				cur = next;
			}
		}
	}

	size_t size() const
	{
		int sz = 0;
		Node *cur = _header->_next;
		while (cur != _header)
		{
			++sz;
			cur = cur->_next;
		}
		return sz;
	}

	iterator erase(iterator pos)
	{
		if (pos != end())
		{
			Node *next = pos._node->_next;
			Node *prev = pos._node->_prev;

			prev->_next = next;
			next->_prev = prev;
			delete[] pos._node;
			return iterator(next);
		}
		return pos;
	}

	void insert(iterator pos, const T &val)
	{
		Node * newNode = new Node(val);
		Node *prev = pos._node->_prev;
		Node *cur = pos._node;

		prev->_next = newNode;
		newNode->_prev = prev;
		newNode->_next = cur;
		cur->_prev = newNode;
	}

	void push_front(const T& val)
	{
		insert(begin(), val);
	}

	void pop_back()
	{
		erase(--end());
	}

	void pop_front()
	{
		erase(begin());
	}



	~List()
	{
		clear();
		delete _header;
		_header = nullptr;
	}
private:
	Node *_header;
};

template<typename T>
void PrintFor(List<T> &lst)
{
	for (auto &e : lst)
	{
		cout << e << " ";
	}
	cout << endl;
}

測試代碼如下:

#include <iostream>
#include "List.h"
using namespace std;

struct A
{
	int _a;
	A(int a = 0) :_a(a) {};
};

int main()
{
	List<int> lst;
	List<int> lst2(3, 1);
	string str = "12345";
	List<char> lst3(str.begin(), str.end());
	lst.push_back(1);
	lst.push_back(2);
	lst.push_back(3);
	lst.push_back(4);

	List<int>::iterator it = lst.begin();
	while (it != lst.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	List<A> lst4;
	lst4.push_back(1);
	lst4.push_back(2);
	lst4.push_back(3);
	lst4.push_back(4);

	List<A>::iterator it1 = lst4.begin();
	while (it1 != lst4.end())
	{
		cout << it1->_a << " ";
		++it1;
	}
	cout << endl;

	PrintFor(lst2);

	List<int> lst5;
	lst5.push_back(1);
	lst5.push_back(2);
	lst5.push_back(3);
	lst5.push_back(4);
	lst5.push_back(5);

	List<int>::iterator it2 = lst5.begin();
	while (it2 != lst5.end())
	{
		if (*it2 % 2 == 0) it2 = lst5.erase(it2);
		else ++it2;
	}
	PrintFor(lst5);

	return 0;
}

測試結果:

[C++STL]C++實作list容器
[C++STL] c++ 多态 類 STL list
上一篇: 在PDA裝置上安裝Microsoft .Net Compact FrameWork
下一篇: java實作word生成并轉pdf

繼續閱讀