list C++实现

模仿STL中list，实现了其大部分功能。list可以高效地利用内存资源，常数时间的插入删除操作。并且，list除了erase外，不怎么存在迭代器失效的现象。

#include<iostream> #include<iterator> #include<algorithm> using namespace std; template<class T> struct _List_node{ typedef void* void_pointer; void_pointer next; void_pointer prev; T data; }; template<class T,class Ref,class Ptr> class _List_iterator{ public: typedef _List_iterator<T, T&, T*> iterator; typedef _List_iterator<T, const T&, const T*> const_iterator; typedef _List_iterator<T, Ref, Ptr> self; typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef _List_node<T>* link_type; typedef size_t size_type; typedef ptrdiff_t difference_type; link_type node; _List_iterator(link_type x):node(x){} _List_iterator(){} _List_iterator(const iterator &x):node(x.node){} bool operator== (const iterator& x )const{return node == x.node;} bool operator!= (const iterator& x)const{return node != x.node;} reference operator*()const{return (*node).data;} pointer operator->()const{return &(operator*());} T operator *(){return node->data;} iterator &operator++(int){ iterator tmp = *this; ++*this; return tmp; } iterator& operator++(){ node = (link_type)((*node).next); return *this; } iterator& operator--(){ node = (link_type)((*node).prev); return *this; } iterator& operator--(int){ iterator tmp = *this; --*this; return tmp; } }; template<class T> class List{ public: typedef _List_node<T>* link_type; typedef _List_iterator<T,T&,T*> iterator; typedef T value_type; typedef T* pointer; typedef T& reference; typedef size_t size_type; typedef ptrdiff_t difference_type; protected: typedef _List_node<T> list_node; link_type node; //..... public: List(){create_node();} List(List& alist){ create_node(); for(List<T>::iterator ite=alist.begin();ite!=alist.end();++ite) push_back(*ite); } iterator begin(){return (link_type)((*node).next);} iterator end(){return node;} bool empty()const{return node->next == node;} size_type size()const{ size_type result = 0; distance(begin(),end(),result); return result; } reference front(){return *begin();} reference back(){return *(--end());} iterator insert(iterator position,const T& x){ link_type tmp = create_node(x); tmp->next = position.node; tmp->prev = position.node->prev; (link_type(position.node->prev))->next = tmp; position.node->prev = tmp; return tmp; } link_type create_node(const T& x){ link_type p = new list_node; p->data = x; p->prev = NULL; p->next = NULL; return p ; } void create_node(){ node = new list_node(); node->next = node; node->prev = node; } inline difference_type distance(iterator first,iterator last,difference_type &n){ n = 0; while(first != last){++first;++n;} return n; } void push_front(const T& x){insert(begin(),x);} void push_back(const T& x){insert(end(),x);} void pop_front(){erase(begin());} void pop_back(){iterator tmp = end();erase(--tmp);} iterator erase(iterator position){ link_type next_node = link_type(position.node->next); link_type prev_node = link_type(position.node->prev); prev_node->next = next_node; next_node->prev = prev_node; destory_node(position.node); return iterator(next_node); } iterator erase(iterator first,iterator last){ while(first!=last){ first = erase(first); } return last; } void destory_node(link_type p){delete p;} ~List(){ clear(); delete node; } void clear() { while (!empty()) pop_back(); } iterator find(const T& value){ iterator first = begin(); while(first!= end()){ if(*first == value)return first; ++first; } return first; } void remove(const T& value){ iterator first = begin(); iterator last = end(); while(first != last){ if(*first == value)first = erase(first); else ++first; } } void transfer(iterator position,iterator first,iterator last){ if(position != last){ (*(link_type((*last.node).prev))).next = position.node; (*(link_type((*first.node).prev))).next = last.node; (*(link_type((*position.node).prev))).next = first.node; link_type tmp = link_type((*position.node).prev); (*position.node).prev = (*last.node).prev; (*last.node).prev = (*first.node).prev; (*first.node).prev = tmp; } } void splice(iterator position,List<T> &x){ if(!x.empty()) transfer(position,x.begin(),x.end()); } void splice(iterator position,List<T> &,iterator i){ iterator j = i; ++j; if(position == i||position == j)return; transfer(position,i,j); } void splice(iterator position,List<T>&,iterator first,iterator last){ if(first!=last) transfer(position,first,last); } }; void test1(){ //数据类型存储測试 List<int> listInt; listInt.push_back(1); listInt.push_back(2); listInt.push_back(3); for(List<int>::iterator ite = listInt.begin();ite != listInt.end();++ite) cout<<*ite<<" "; cout<<endl; List<double> listDouble; listDouble.push_back(0.1); listDouble.push_back(0.2); listDouble.push_back(0.3); for(List<double>::iterator ite = listDouble.begin();ite != listDouble.end();++ite) cout<<*ite<<" "; cout<<endl; class A{ int data; public: A(int a=0):data(a){} operator int(){return data;} }; List<A> listA; A a(1),b(2),c(3); listA.push_back(a); listA.push_back(b); listA.push_back(c); for(List<A>::iterator ite = listA.begin();ite != listA.end();++ite) cout<<*ite<<" "; cout<<endl; } void test2(){// 功能測试 List<int> listInt; List<int>::iterator ite; listInt.push_back(1); listInt.push_back(2); listInt.push_back(3); listInt.push_back(4); listInt.push_back(5); listInt.push_back(6); listInt.push_back(7); listInt.push_back(8); listInt.push_back(9); for(ite = listInt.begin();ite != listInt.end();++ite) cout<<*ite<<" "; cout<<endl; List<int> listInt2(listInt); for(ite = listInt2.begin();ite != listInt2.end();++ite) cout<<*ite<<" "; cout<<endl; listInt.push_front(0); for(ite = listInt.begin();ite != listInt.end();++ite) cout<<*ite<<" "; cout<<endl; listInt.pop_back(); listInt.pop_front(); for(ite = listInt.begin();ite != listInt.end();++ite) cout<<*ite<<" "; cout<<endl; ite = listInt.find(6); if(ite != listInt.end())listInt.erase(ite); for(ite = listInt.begin();ite != listInt.end();++ite) cout<<*ite<<" "; cout<<endl; ite = listInt.find(5); if(ite != listInt.end())listInt.erase(ite,listInt.end()); for(ite = listInt.begin();ite != listInt.end();++ite) cout<<*ite<<" "; cout<<endl; listInt.pop_front(); listInt.pop_back(); for(ite = listInt.begin();ite != listInt.end();++ite) cout<<*ite<<" "; cout<<endl; listInt.remove(2); for(ite = listInt.begin();ite != listInt.end();++ite) cout<<*ite<<" "; cout<<endl; listInt.clear(); for(ite = listInt.begin();ite != listInt.end();++ite) cout<<*ite<<" clear()"; cout<<endl; } void test3(){//拼接功能測试 List<int> listInt1; List<int>::iterator ite; listInt1.push_back(1); listInt1.push_back(2); listInt1.push_back(3); listInt1.push_back(4); listInt1.push_back(5); List<int> listInt2(listInt1); cout<<"listInt1: "; for(ite = listInt1.begin();ite != listInt1.end();++ite) cout<<*ite<<" "; cout<<endl; cout<<"listInt2: "; for(ite = listInt2.begin();ite != listInt2.end();++ite) cout<<*ite<<" "; cout<<endl; ite = listInt1.find(4); List<int>::iterator first = listInt2.find(2); List<int>::iterator last = listInt2.find(4); listInt1.transfer(ite,first,last); for(ite = listInt1.begin();ite != listInt1.end();++ite) cout<<*ite<<" "; cout<<endl; for(ite = listInt2.begin();ite != listInt2.end();++ite) cout<<*ite<<" "; cout<<endl; ite = listInt1.find(2); listInt1.splice(ite,listInt2); for(ite = listInt1.begin();ite != listInt1.end();++ite) cout<<*ite<<" "; cout<<endl; } int main(){ cout<<"--------data type test----------"<<endl; test1(); cout<<"--------function test----------"<<endl; test2(); cout<<"---------splice test-----------"<<endl; test3(); }