一个简单的list实现

此List仿照的时STL中的list 写的,完成了一些基本功能。学习时候时按照书上(数据结构与算法分析,c++描述)学习的,了解到了迭代器的基本实现,感觉很有成就感。List用双向链表实现的,这样就可以方便地对迭代器应用++,–操作符。链表中又添加了两个节点tail和head,这样在插入删除元素的时候在操作上就统一了。

虽然说写出来了,而且经过简单的测试,没有啥问题(当然,我没有做任何的错误处理。。),但是感觉这种接口与实现分离的写法实在是太麻烦了。以后考虑把这些接口都放到注释中去,然后再在实际代码中实现,这样就不用去写一堆的template<typename Object>了。

前两天学习了git的用法,准备把自己的代码放到github上面,repo名称为fkcode。有兴趣的可以watch me。放代码~

#include&amp;lt;iostream&amp;gt;
template&amp;lt;typename Object&amp;gt;
class List{
private:
	struct Node;	//存放节点信息
	int theSize;	//List包含的元素的个数
	Node *head,*tail; //当容器为空的时候,有两个节点

	void init();
public:
	class const_iterator; //const迭带器
	class iterator;			//迭带器

	List();//constructor
	List( const List &amp;amp; rhs );
	~List();
	const List &amp;amp; operator= (const List &amp;amp; rhs );
	//the "Big Three"

	//basic routines, easy to understand by name
	iterator begin();
	iterator end();
	const_iterator begin() const;
	const_iterator end() const;

	int size() const;
	bool empty() const;
	void clear();

	Object &amp;amp; front();
	Object &amp;amp; back();
	const Object &amp;amp; front() const;
	const Object &amp;amp; back()  const;

	void push_front( const Object &amp;amp; x );
	void push_back(  const Object &amp;amp; x );
	void pop_front();
	void pop_back();

	iterator insert( iterator itr, const Object &amp;amp; x );
	iterator erase( iterator itr );
	iterator erase( iterator start, iterator end );

};

template&amp;lt;typename Object&amp;gt;
struct List&amp;lt;Object&amp;gt;::Node{
	Object data;
	Node *prev;
	Node *next;
	Node( const Object &amp;amp; d = Object(), Node *p = NULL, Node *n = NULL ):
		data(d),prev(p),next(n){}
};

template&amp;lt;typename Object&amp;gt;
void List&amp;lt;Object&amp;gt;::init(void){
	theSize = 0;
	head = new Node;
	tail = new Node;
	head-&amp;gt;next = tail;
	tail-&amp;gt;prev = head;
}

template&amp;lt;typename Object&amp;gt;
List&amp;lt;Object&amp;gt;::List(){ init();}

template&amp;lt;typename Object&amp;gt;
List&amp;lt;Object&amp;gt;::List( const List &amp;amp; rhs ){
	init();
	*this = rhs;
}

template&amp;lt;typename Object&amp;gt;
List&amp;lt;Object&amp;gt;::~List(){
	clear();
	delete head;
	delete tail;
}

template&amp;lt;typename Object&amp;gt;
const List&amp;lt;Object&amp;gt; &amp;amp; List&amp;lt;Object&amp;gt;::operator= ( const List&amp;lt;Object&amp;gt; &amp;amp; rhs ){
	if( this == &amp;amp;rhs ) return *this;
	clear();
	for( const_iterator itr = rhs.begin(); itr != rhs.end(); ++itr )
		push_back( *itr );
	return *this;
}
// begin end 返回的是第一个元素和最后一个元素之后位置的迭代器
template&amp;lt;typename Object&amp;gt;
typename List&amp;lt;Object&amp;gt;::iterator List&amp;lt;Object&amp;gt;::begin()
	{ return iterator( List&amp;lt;Object&amp;gt;::head-&amp;gt;next ); }
template&amp;lt;typename Object&amp;gt;
typename List&amp;lt;Object&amp;gt;::iterator List&amp;lt;Object&amp;gt;::end()
	{ return iterator( List&amp;lt;Object&amp;gt;::tail ); }
template&amp;lt;typename Object&amp;gt;
typename List&amp;lt;Object&amp;gt;::const_iterator List&amp;lt;Object&amp;gt;::begin() const
	{ return const_iterator( List&amp;lt;Object&amp;gt;::head-&amp;gt;next); }
template&amp;lt;typename Object&amp;gt;
typename List&amp;lt;Object&amp;gt;::const_iterator List&amp;lt;Object&amp;gt;::end() const
	{ return const_iterator( List&amp;lt;Object&amp;gt;::tail); }

template&amp;lt;typename Object&amp;gt;
int List&amp;lt;Object&amp;gt;::size() const { return theSize; }
template&amp;lt;typename Object&amp;gt;
bool List&amp;lt;Object&amp;gt;::empty() const { return size() == 0; }
template&amp;lt;typename Object&amp;gt;
void List&amp;lt;Object&amp;gt;::clear() { while( !empty() ) pop_front(); }
//front back返回第一个和最后一个元素
template&amp;lt;typename Object&amp;gt;
Object &amp;amp; List&amp;lt;Object&amp;gt;::front() { return *begin(); }
template&amp;lt;typename Object&amp;gt;
Object &amp;amp; List&amp;lt;Object&amp;gt;::back() { return *--end(); }
template&amp;lt;typename Object&amp;gt;
const Object &amp;amp; List&amp;lt;Object&amp;gt;::front() const { return *begin(); }
template&amp;lt;typename Object&amp;gt;
const Object &amp;amp; List&amp;lt;Object&amp;gt;::back() const { return *--end(); }

template&amp;lt;typename Object&amp;gt;
void List&amp;lt;Object&amp;gt;::push_front( const Object &amp;amp; x ) { insert( begin(), x ); }
template&amp;lt;typename Object&amp;gt;
void List&amp;lt;Object&amp;gt;::push_back( const Object &amp;amp; x ) { insert( end(), x ); }
template&amp;lt;typename Object&amp;gt;
void List&amp;lt;Object&amp;gt;::pop_front() { erase( begin() ); }
template&amp;lt;typename Object&amp;gt;
void List&amp;lt;Object&amp;gt;::pop_back() { erase( end() ); }
//很精简的插入元素的代码,在书上看到的
template&amp;lt;typename Object&amp;gt;
typename List&amp;lt;Object&amp;gt;::iterator List&amp;lt;Object&amp;gt;::insert
	( List&amp;lt;Object&amp;gt;::iterator itr, const Object &amp;amp; x ){
	Node *p = itr.current;
	theSize++;
	return List&amp;lt;Object&amp;gt;::iterator(p-&amp;gt;prev=p-&amp;gt;prev-&amp;gt;next=new Node( x,p-&amp;gt;prev,p ) );
}

template&amp;lt;typename Object&amp;gt;
typename List&amp;lt;Object&amp;gt;::iterator List&amp;lt;Object&amp;gt;::erase
	( List&amp;lt;Object&amp;gt;::iterator itr ){
	Node *p = itr.current;
	iterator retVal( p-&amp;gt;next );
	p-&amp;gt;prev-&amp;gt;next = p-&amp;gt;next;
	p-&amp;gt;next-&amp;gt;prev = p-&amp;gt;prev;
	delete p;
	theSize--;
	return retVal;
}

template&amp;lt;typename Object&amp;gt;
typename List&amp;lt;Object&amp;gt;::iterator List&amp;lt;Object&amp;gt;::erase
	( List&amp;lt;Object&amp;gt;::iterator start,List&amp;lt;Object&amp;gt;::iterator end ){
	for( iterator itr = start; itr != end; )
		itr = erase( itr );
	return end;
}

template&amp;lt;typename Object&amp;gt;
class List&amp;lt;Object&amp;gt;::const_iterator{
public:
	const_iterator():current(NULL){}

	Object &amp;amp; operator* () { return retrieve(); }
	const Object &amp;amp; operator* () const {
		current = current-&amp;gt;next;
		return *this;
	}
	const_iterator operator-- () {
		current = current-&amp;gt;prev;
		return *this;
	}
	const_iterator operator++ (){
		current = current-&amp;gt;next;
		return *this;
	}
	const_iterator operator-- (int){
		const_iterator old = *this;
		--( *this );return old;
	}
	const_iterator operator++ (int){
		const_iterator old = *this;
		++( *this );
		return old;
	}
	bool operator== (const const_iterator &amp;amp; rhs ) const
		{ return current == rhs.current; }
	bool operator!= (const const_iterator &amp;amp; rhs ) const
		{ return !( *this == rhs ); }

protected:
	Node *current;
	Object &amp;amp; retrieve() const { return current-&amp;gt;data; }
	const_iterator( Node *p ):current(p){}
	friend class List&amp;lt;Object&amp;gt;;
};

template&amp;lt;typename Object&amp;gt;
class List&amp;lt;Object&amp;gt;::iterator:public const_iterator{
public:
	iterator(){}

	Object &amp;amp; operator* ()
		{ return const_iterator::retrieve(); }
	const Object &amp;amp; operator* () const
		{ return const_iterator::operator*(); }
	iterator &amp;amp; operator-- (){
		const_iterator::current =
			const_iterator::current-&amp;gt;prev;
		return *this;
	}
	iterator &amp;amp; operator++ (){
		const_iterator::current =
			const_iterator::current-&amp;gt;next;
		return *this;
	}
	iterator operator--(int){
		iterator old = *this;
		++( *this );
		return old;
	}
	iterator  operator++ (int) {
		iterator old = *this;
		++( *this );
		return old;
	}
	protected:
	iterator( Node *p ) : const_iterator(p){}
	friend class List&amp;lt;Object&amp;gt;;
};

int main ()
{
	List&amp;lt;int&amp;gt; L;
	for( int i = 0; i &amp;lt; 10; i++ )
		L.push_back( i*i );
	for( int i = 0; i &amp;lt; 10; i++ )
		L.insert( L.end(), i*i );
	//测试push_back 和 insert

	for( List&amp;lt;int&amp;gt;::iterator it = L.begin(); it != L.end(); it++ )
		std::cout &amp;lt;&amp;lt; *it &amp;lt;&amp;lt; ' ';
	std::cout &amp;lt;&amp;lt; std::endl;
	L.erase( --L.end() );
	//测试erase 和 ++运算符
	std::cout &amp;lt;&amp;lt; L.size() &amp;lt;&amp;lt; std::endl;
	for( List&amp;lt;int&amp;gt;::const_iterator it = L.begin(); it != L.end(); ++it )
		std::cout &amp;lt;&amp;lt; *it &amp;lt;&amp;lt; ' ';
	//测试const_iterator
	std::cout &amp;lt;&amp;lt; std::endl;
	return 0;

}

发表评论

电子邮件地址不会被公开。