模仿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();
}