list C++实现

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

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/119251.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Zuul网关集群_zuul网关

    Zuul网关集群_zuul网关1,Zuul网关集群原理![在这里插入图片描述](https://img-blog.csdnimg.cn/20201019212045203.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4ODQ1Mjcx,size_16,color_FFFFFF,t_70#pic_center)…

  • Linux用telnet判断端口是否通

    Linux用telnet判断端口是否通通的[root@1222~]#telnet127.0.0.14531Trying127.0.0.1…Connectedto127.0.0.1.Escapecharacteris’^]’.不通[root@1222~]#telnet127.0.0.14581Trying127.0.0.1…telnet:connecttoaddress127.0.0.1:Connectionrefused退出方式1.输入Ctrl+】键,然后

    2022年10月22日
  • 图论(二):图的四种最短路径算法

    图论(二):图的四种最短路径算法本文总结了图的几种最短路径算法的实现:深度或广度优先搜索算法,弗洛伊德算法,迪杰斯特拉算法,Bellman-Ford算法1),深度或广度优先搜索算法(解决单源最短路径)从起始结点开始访问所有的深度遍历路径或广度优先路径,则到达终点结点的路径有多条,取其中路径权值最短的一条则为最短路径。下面是核心代码:voiddfs(intcur,intdst){/

  • ora 01017问题解决办法

    ora 01017问题解决办法SQL&gt;startup ORACLEinstancestarted. TotalSystemGlobalArea 914358272bytes FixedSize                 2088184bytes VariableSize            528483080bytes DatabaseBuffers         3774873…

  • python3 gil锁_python同步锁

    python3 gil锁_python同步锁前言python的使用者都知道Cpython解释器有一个弊端,真正执行时同一时间只会有一个线程执行,这是由于设计者当初设计的一个缺陷,里面有个叫GIL锁的,但他到底是什么?我们只知道因为他导致pyt

  • day 08 String类、Random类、ArrayList类

    day 08 String类、Random类、ArrayList类

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号