模仿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();
}
随机推荐
-
Create and Install Timer Job in MOSS 2007
Excute Timerjob public class TriggerLoadCacheTimerJob : SPJobDefinition { string ExceptionFlag = str ...
-
windows装了双系统设置默认启动系统
我们装了双系统后,在开机设置时会自动启动其中一个系统,有时提示时间会很短,以至于不能判断自己是否装了双系统,以下,当电脑打开后,我们可以观察是否装了双系统 1.按组合键<Win+R>,打开 ...
-
ORACLE SQL 分组
select max(cost),suppliercode from tel_bill where period = '2014005' group by suppliercode;select * ...
-
.net 连接sqlserver类库
using System; using System.Collections.Generic; using System.Linq; using System.Web; using System.Da ...
-
fedora 取消自动升级
fedora启动时经常CPU使用很高,看下进程原来是yumBackend.这是个yum的自动更新进程 只要关闭自动更新就可以了 gsettings set org.gnome.settings-dae ...
-
libevent入门（1）
libevent是什么 libevent 库实际上没有更换 select().poll() 或其他机制的基础.而是使用对于每个平台最高效的高性能解决方案在实现外加上一个包 ...
-
Nape实现坐标旋转角度回弹
乒乓球以一个向量运动,碰到障碍后反弹以一个新的向量运动,如下图: 要实现回弹只需要求出向量v1,把向量v0取反,再旋转(a+b)度就可以得到向量v1. 向量取反: var v:vec2 = new V ...
- 统计函数：MAX,MIN,SUM,AVG,COUNT
-
JetBrains系列IDE快捷键大全（转载）
编辑 快捷键组合 说明 Ctrl + Space 代码自动完成提示(选择) Alt + Enter 显示意图动作和快速修复 Ctrl + P 参数信息 (在调用方法参数忘记的时候,提示) Ctrl + ...
-
Judy Beta 第八天
Progress 人员 今日进展 明日任务 前端 Manli Shu, Yuechen Wang 测试发现了比如嵌套块和多文件断点的bug 进行测试和回归测试 后端 Zhiqi Lin, Yu Xin ...