C++实现的一个Order-List有序链表 带迭代器 模板类(class)

使用方法: 在项目中导入头文件
MYLIB::OrderedList<int> lists;
MYLIB::OrderedList<double> dlists;

P.S: 迭代器有点小问题

//
// Author: Kotarou.
// Email: t.k@07.gs
// FileName: OrderedList.h
// Last modify: 28/05/2015
//

#ifndef __ORDEREDLIST_H__
#define __ORDEREDLIST_H__
#include 
namespace MYLIB
{
	template
	class OrderedList;
	
	template 
	class ListNode
	{
		friend class OrderedList;
		friend class OrderedList::iterator;
		
		private:
			T Element;
			ListNode *prev;
			ListNode *next;
		public:
			ListNode() : next(NULL), prev(NULL) {};
	};
	
	template
	class OrderedList
	{
		private:
			ListNode *head;
			ListNode *tail;
		public:
			OrderedList() : head(NULL), tail(NULL) {};
			
			~OrderedList()
			{
				// delete all elements
				ListNode *temp = NULL;
				while(head)
				{
					temp = head->next;
					delete head;
					head = temp;
				}
			};
			
			// insertion sort
			void insert(const T &Element)
			{
				ListNode *temp = new ListNode;
				temp->Element = Element;
				
				if(!head && !tail)
				{
					head = temp;
					tail = temp;
				}
				else
				{
					//if the Element smaller than head, insert it before the head
					if(temp->Element <= head->Element)
					{
						temp->next = head;
						head->prev = temp;
						head = temp;
						return;
					}
					
					//if the Element greater than tail, insert it after the tail
					if(temp->Element >= tail->Element)
					{
						temp->prev = tail;
						tail->next = temp;
						tail = temp;
						return;
					}
					
					//find a position to insert
					ListNode *cur = head;
					while(cur)
					{
						if(temp->Element <= cur->Element)
						{
							temp->prev = cur->prev;
							cur->prev->next = temp;
							temp->next = cur;
							cur->prev = temp;
							break;
						}
						
						cur = cur->next;
					}
				}
			};
			
			class iterator
			{
				private:
					ListNode *node;
					bool done;
				public:
					iterator() : node(NULL), done(false) {};
					iterator(ListNode *in) : node(in), done(false){};
					
					T& operator*() // dereference
					{ 
						return node->Element; 
					};
					
					const T& operator*() const 
					{
						return node->Element; 
					};
					
					iterator& operator++() // prefix
					{
						node = node->next;
						return *this;
					};
					
					iterator operator++(int) // postfix
					{
						iterator temp = *this;
						++(*this);
						return temp;
					};
					
					iterator& operator--() // prefix
					{
						node = node->prev;
						return *this;
					};
					
					iterator operator--(int) // postfix
					{
						iterator temp = *this;
						--(*this);
						return temp;
					};
					
					bool operator==(const iterator& x) const
					{
						return (node == x.node);
					};
					
					bool operator!=(const iterator &rv)
					{
						if((node == rv.node && node) && done)
							return false;							
						
						if(node == rv.node && node)
							done = true;
						
						return ( node );
					};
			};
			
			iterator begin()
			{
				return iterator(head);
			};
			
			iterator end() 
			{
				return iterator(tail);
			};
	};
}
#endif


发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注


此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据