STL list的模拟实现

不同于vector,List不是连续线性空间，

list的好处是每次插入或删除一个一个元素，就配置或释放一个元素的空间，因此，它对空间一点都不浪费，而且对于任何位置的插入或删除，list永远是时间常数。

list有一个重要性质，插入、接合操作都不会造成原有迭代器失效，这在vector中是不存在的,而list的删除操作也只有“指向被删除元素”的那个迭代器失效，其它迭代器不受影响。

List.h

#ifndef __List__
#define __List__

//STL对于区间前闭后开

//List的节点
template<class T>
struct ListNode
{
	typedef ListNode<T>* Node_p;
	Node_p _prev;
	Node_p _next;
	T _data;
	ListNode(const T& data=T() )
		:_prev(NULL)
		, _next(NULL)
		, _data(data)
	{}
};

//List中的迭代器(由于list不是线性空间结构，通用迭代器无法正常移动，所以list需要定义专门的迭代器。)
template<class T,class Ref,class Ptr>
struct Iterator
{
	typedef ListNode<T> Node, *Node_p;
	typedef Iterator<T, Ref, Ptr> Self;
	Node_p _node;

	Iterator()
	{}
	Iterator(Node_p node)
		:_node(node)
	{}
	//取节点的数值
	Ref operator*()const
	{
		return _node->_data;
	}
	/*Ptr operator->()const
	{
		return &(operator*());
	}*/
	bool operator == (const Self& x)
	{
		return (_node==x._node);
	}
	bool operator != (const Self& x)
	{
		return (_node != x._node);
	}
	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	Self operator++(int)
	{
		Self old = *this;
		++(*this);
		return old;
	}
	Self& operator--()
	{
		(_node = _node->_prev);
		return *this;
	}
	Self operator--(int)
	{
		Self old = *this;
		--(*this);
		return old;
	}
};

//List是一个带头结点的双向循环链表
template<class T>
class List
{
public:
	typedef Iterator<T, T&, T*> Iterator;//STL强制要求*******
private:
	typedef ListNode<T> Node, *Node_p;
	typedef T& Reference;
public:
	List()
		:_list(new Node())
	{
		_list->_next = _list;
		_list->_prev = _list;
	}
	Iterator Begin()
	{
		return Iterator(_list->_next);
	}
	Iterator End()
	{
		return Iterator(_list);
	}
	void PushBack(const T& data)
	{
		Insert(End(),data);
	}
	void PopBack()
	{
		Erase(Iterator(_list->_prev));
	}
	void PushFront(const T& data)
	{
		Insert(Iterator(_list->_next),data);
	}
	void PopFront()
	{
		Erase(Iterator(_list->_next));
	}
	//取头结点的内容（元素值）
	Reference Front()
	{
		return *Begin();
	}
	Reference Back()
	{
		return *(--End());
	}
	//在当前位置的前面插入
	void Insert(Iterator pos, const T& data)
	{
		Node_p cur = pos._node;
		Node_p prev = cur->_prev;
		Node_p next = cur->_next;
		Node_p tmp = new Node(data);
		tmp->_next = cur;
		cur->_prev = tmp;
		prev->_next = tmp;
		tmp->_prev = prev;
	}
	Iterator& Erase(Iterator pos)
	{
		Node_p cur = pos._node;
		Node_p prev = cur->_prev;
		Node_p next = cur->_next;
		prev->_next = next;
		next->_prev = prev;
		delete cur;
		return Iterator(next);
	}
	bool Empty()const
	{
		if (_list->_next == _list){
			return true;
		}
		else{
			return false;
		}
	}
	size_t Size()
	{
		int size = 0;
		Node_p start = _list->_next;
		Node_p end = _list;
		while (start != end){
			++size;
			start = start->_next;
		}
		return size;
	}
	//不支持随机访问，无[]重载
	
protected:
	Node_p _list;
};
#endif

Test.cpp

#include <iostream>
#include "List.h"

void Test()
{
	List<int> l;
	l.PushBack(1);
	l.PushBack(2);
	l.PushBack(3);
	l.PushBack(4);
	List<int>::Iterator ite;
	for (ite = l.Begin(); ite != l.End(); ++ite){
		std::cout << *ite << std::endl;
	}
	std::cout << l.Size() << std::endl;

	ite = l.Begin();
	l.Insert(ite,100);
	std::cout << *ite << std::endl;

	/*l.PopFront();
	l.PopBack();
	l.PushFront(78);
	l.PushFront(100);*/

	/*List<int>::Iterator it = l.Begin();
	List<int>::Iterator its = l.End();
	List<int>::Iterator item;
	std::cout<<*it<<std::endl;
	++it;
	its--;
	std::cout << (it != its) << std::endl;
	
	int data1 = l.Front();
	int data2= l.Back();
	std::cout<<l.Size()<<std::endl;
	std::cout << !l.Empty() << std::endl;*/
}

int main()
{
	Test();

	system("pause");
	return 0;
}

本文出自 “零蛋蛋” 博客，谢绝转载！

STL list的模拟实现

原文：http://lingdandan.blog.51cto.com/10697032/1829378