此List仿照的时STL中的list 写的,完成了一些基本功能。学习时候时按照书上(数据结构与算法分析,c++描述)学习的,了解到了迭代器的基本实现,感觉很有成就感。List用双向链表实现的,这样就可以方便地对迭代器应用++,–操作符。链表中又添加了两个节点tail和head,这样在插入删除元素的时候在操作上就统一了。
虽然说写出来了,而且经过简单的测试,没有啥问题(当然,我没有做任何的错误处理。。),但是感觉这种接口与实现分离的写法实在是太麻烦了。以后考虑把这些接口都放到注释中去,然后再在实际代码中实现,这样就不用去写一堆的template<typename Object>了。
前两天学习了git的用法,准备把自己的代码放到github上面,repo名称为fkcode。有兴趣的可以watch me。放代码~
#include&lt;iostream&gt; template&lt;typename Object&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; rhs ); ~List(); const List &amp; operator= (const List &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; front(); Object &amp; back(); const Object &amp; front() const; const Object &amp; back() const; void push_front( const Object &amp; x ); void push_back( const Object &amp; x ); void pop_front(); void pop_back(); iterator insert( iterator itr, const Object &amp; x ); iterator erase( iterator itr ); iterator erase( iterator start, iterator end ); };
template&lt;typename Object&gt; struct List&lt;Object&gt;::Node{ Object data; Node *prev; Node *next; Node( const Object &amp; d = Object(), Node *p = NULL, Node *n = NULL ): data(d),prev(p),next(n){} }; template&lt;typename Object&gt; void List&lt;Object&gt;::init(void){ theSize = 0; head = new Node; tail = new Node; head-&gt;next = tail; tail-&gt;prev = head; } template&lt;typename Object&gt; List&lt;Object&gt;::List(){ init();} template&lt;typename Object&gt; List&lt;Object&gt;::List( const List &amp; rhs ){ init(); *this = rhs; } template&lt;typename Object&gt; List&lt;Object&gt;::~List(){ clear(); delete head; delete tail; } template&lt;typename Object&gt; const List&lt;Object&gt; &amp; List&lt;Object&gt;::operator= ( const List&lt;Object&gt; &amp; rhs ){ if( this == &amp;rhs ) return *this; clear(); for( const_iterator itr = rhs.begin(); itr != rhs.end(); ++itr ) push_back( *itr ); return *this; } // begin end 返回的是第一个元素和最后一个元素之后位置的迭代器 template&lt;typename Object&gt; typename List&lt;Object&gt;::iterator List&lt;Object&gt;::begin() { return iterator( List&lt;Object&gt;::head-&gt;next ); } template&lt;typename Object&gt; typename List&lt;Object&gt;::iterator List&lt;Object&gt;::end() { return iterator( List&lt;Object&gt;::tail ); } template&lt;typename Object&gt; typename List&lt;Object&gt;::const_iterator List&lt;Object&gt;::begin() const { return const_iterator( List&lt;Object&gt;::head-&gt;next); } template&lt;typename Object&gt; typename List&lt;Object&gt;::const_iterator List&lt;Object&gt;::end() const { return const_iterator( List&lt;Object&gt;::tail); } template&lt;typename Object&gt; int List&lt;Object&gt;::size() const { return theSize; } template&lt;typename Object&gt; bool List&lt;Object&gt;::empty() const { return size() == 0; } template&lt;typename Object&gt; void List&lt;Object&gt;::clear() { while( !empty() ) pop_front(); } //front back返回第一个和最后一个元素 template&lt;typename Object&gt; Object &amp; List&lt;Object&gt;::front() { return *begin(); } template&lt;typename Object&gt; Object &amp; List&lt;Object&gt;::back() { return *--end(); } template&lt;typename Object&gt; const Object &amp; List&lt;Object&gt;::front() const { return *begin(); } template&lt;typename Object&gt; const Object &amp; List&lt;Object&gt;::back() const { return *--end(); } template&lt;typename Object&gt; void List&lt;Object&gt;::push_front( const Object &amp; x ) { insert( begin(), x ); } template&lt;typename Object&gt; void List&lt;Object&gt;::push_back( const Object &amp; x ) { insert( end(), x ); } template&lt;typename Object&gt; void List&lt;Object&gt;::pop_front() { erase( begin() ); } template&lt;typename Object&gt; void List&lt;Object&gt;::pop_back() { erase( end() ); } //很精简的插入元素的代码,在书上看到的 template&lt;typename Object&gt; typename List&lt;Object&gt;::iterator List&lt;Object&gt;::insert ( List&lt;Object&gt;::iterator itr, const Object &amp; x ){ Node *p = itr.current; theSize++; return List&lt;Object&gt;::iterator(p-&gt;prev=p-&gt;prev-&gt;next=new Node( x,p-&gt;prev,p ) ); } template&lt;typename Object&gt; typename List&lt;Object&gt;::iterator List&lt;Object&gt;::erase ( List&lt;Object&gt;::iterator itr ){ Node *p = itr.current; iterator retVal( p-&gt;next ); p-&gt;prev-&gt;next = p-&gt;next; p-&gt;next-&gt;prev = p-&gt;prev; delete p; theSize--; return retVal; } template&lt;typename Object&gt; typename List&lt;Object&gt;::iterator List&lt;Object&gt;::erase ( List&lt;Object&gt;::iterator start,List&lt;Object&gt;::iterator end ){ for( iterator itr = start; itr != end; ) itr = erase( itr ); return end; } template&lt;typename Object&gt; class List&lt;Object&gt;::const_iterator{ public: const_iterator():current(NULL){} Object &amp; operator* () { return retrieve(); } const Object &amp; operator* () const { current = current-&gt;next; return *this; } const_iterator operator-- () { current = current-&gt;prev; return *this; } const_iterator operator++ (){ current = current-&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; rhs ) const { return current == rhs.current; } bool operator!= (const const_iterator &amp; rhs ) const { return !( *this == rhs ); } protected: Node *current; Object &amp; retrieve() const { return current-&gt;data; } const_iterator( Node *p ):current(p){} friend class List&lt;Object&gt;; }; template&lt;typename Object&gt; class List&lt;Object&gt;::iterator:public const_iterator{ public: iterator(){} Object &amp; operator* () { return const_iterator::retrieve(); } const Object &amp; operator* () const { return const_iterator::operator*(); } iterator &amp; operator-- (){ const_iterator::current = const_iterator::current-&gt;prev; return *this; } iterator &amp; operator++ (){ const_iterator::current = const_iterator::current-&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&lt;Object&gt;; }; int main () { List&lt;int&gt; L; for( int i = 0; i &lt; 10; i++ ) L.push_back( i*i ); for( int i = 0; i &lt; 10; i++ ) L.insert( L.end(), i*i ); //测试push_back 和 insert for( List&lt;int&gt;::iterator it = L.begin(); it != L.end(); it++ ) std::cout &lt;&lt; *it &lt;&lt; ' '; std::cout &lt;&lt; std::endl; L.erase( --L.end() ); //测试erase 和 ++运算符 std::cout &lt;&lt; L.size() &lt;&lt; std::endl; for( List&lt;int&gt;::const_iterator it = L.begin(); it != L.end(); ++it ) std::cout &lt;&lt; *it &lt;&lt; ' '; //测试const_iterator std::cout &lt;&lt; std::endl; return 0; }