310-基于STL的内存对list的实现

青旅半醒 2023-01-22 05:52 4阅读 0赞

## 基于STL的内存对list的实现 ##

#pragma once
    
    #include"yhp_alloc.h"//开空间 
    #include"yhp_construct.h"//构造对象 
    
    namespace yhp
    {
        
    template<class _Ty,class _A = yhp::alloc>
    
    class list
    {
        
    private:
    	struct _Node;
    	typedef struct _Node* _Nodeptr;
    	struct _Node
    	{
        
    		_Nodeptr _Prev, _Next;//前驱，后继 
    		_Ty _Value;//值域 
    	};
    
    	struct _Acc;
    	struct _Acc
    	{
        
    		typedef struct _Node*& _Nodepref;//引用 指针类型 
    		typedef _Ty& _Vref;//值的引用类型 
    		static _Vref _Value(_Nodeptr _P)
    		{
        
    			return (*_P)._Value;
    		}
    		static _Nodepref _Prev(_Nodeptr _P)
    		{
        
    			return (*_P)._Prev;
    		}
    		static _Nodepref _Next(_Nodeptr _P)
    		{
        
    			return (*_P)._Next;
    		}
    
    	};
    
    public: 
        //进行分解 
    	typedef _Ty value_type;
    	typedef _Ty& reference;
    	typedef _Ty* pointer;
    	typedef const _Ty& const_reference;
    	typedef const _Ty* const_pointer;
        //以上做法是 为以后对list的萃取类型 
    	typedef _A  allocator_type;
    	typedef yhp::simple_alloc<_Node, _A> data_allocate;//进一步的说明 
    public:
    	class iterator;//普通迭代器，可以取值或者赋值 
    	class const_iterator;//常性迭代器，只能取值，不能赋值 
    
    	friend class iterator;
    	friend class const_iterator;
    
    	class const_iterator
    	{
        
    	public:
    		const_iterator(_Nodeptr _P = nullptr) :_Ptr(_P) {
        }//构造函数 
    		const_reference operator*() const//重载*，把迭代器所指之物返回 
    		{
        
    			return _Acc::_Value(_Ptr);
    		}
    		const_pointer operator->() const//重载-> 迭代器访问的数据的地址 
    		{
        
    			return (&**this);
    		}
    		const_iterator operator++()//重载前置++ 
    		{
        
    			_Ptr = _Acc::_Next(_Ptr);
    			return *this;
    		}
    		const_iterator operator++(int)//重载后置++ 
    		{
        
    			const_iterator  _Tmp = *this;
    			++* this;
    			return _Tmp;
    		}
    		const_iterator operator--()//重载前置-- 
    		{
        
    			_Ptr = _Acc::_Prev(_Ptr);
    			return *this;
    		}
    		const_iterator operator--(int)//重载后置-- 
    		{
        
    			const_iterator  _Tmp = *this;
    			--* this;
    			return _Tmp;
    		}
    		bool operator==(const const_iterator _X) const//重载== 
    		{
        
    			return this->_Ptr == _X._Ptr;
    		}
    		bool operator!=(const const_iterator _X) const//重载！= 
    		{
        
    			return !(*this == _X);
    		}
    
    		_Nodeptr _Mynode() const//获取指针 
    		{
        
    			return _Ptr;
    		}
    	protected:
    		_Nodeptr _Ptr;
    	};
    
    	
    	class iterator : public const_iterator//普通迭代器 
    	{
        
    	public:
    		iterator(_Nodeptr _P = nullptr) :const_iterator(_P) {
        }
    		reference operator*() const
    		{
        
    			return _Acc::_Value(this->_Ptr);
    		}
    		pointer operator->() const
    		{
        
    			return (&**this);
    		}
    		iterator operator++()
    		{
        
    			this->_Ptr = _Acc::_Next(this->_Ptr);
    			return *this;
    		}
    		iterator operator++(int)
    		{
        
    			iterator  _Tmp = *this;
    			++* this;
    			return _Tmp;
    		}
    		iterator operator--()
    		{
        
    			this->_Ptr = _Acc::_Prev(this->_Ptr);
    			return *this;
    		}
    		iterator operator--(int)
    		{
        
    			iterator  _Tmp = *this;
    			--*this;
    			return _Tmp;
    		}
    		bool operator==(const iterator _X) const
    		{
        
    			return this->_Ptr == _X._Ptr;
    		}
    		bool operator!=(const iterator _X) const
    		{
        
    			return !(*this == _X);
    		}
    	};
    
    public:
    	iterator begin() {
         return iterator(_Acc::_Next(_Head)); }//获取第一个数据结点 
    	iterator end() {
         return iterator(_Head); }//最后一个结点的后继，也就是头 
    	const_iterator begin() const {
         return const_iterator(_Acc::_Next(_Head)); }
    	const_iterator end() const {
         return const_iterator(_Head); }
    public:
    	typedef const_iterator _It;//常性迭代器的别名 
    	list() :_Size(0), _Head(_Buynode()) {
        }//构造函数 
    	list(const list& _X):_Size(0),_Head(_Buynode())
    	{
        
    		iterator _F=_X.begin(), _L=_X.end();
    		for(;_F!=_L;++_F)
    		{
        
    			insert(end(),*_F);
    		} 
    	}
    	~list()//析构函数 
    	{
        
    		clear();
    		_Freenode(_Head);
    		_Head=nullptr;
    		_Size=0;
    	}
    
    	reference front() {
         return *begin(); }//取得链表的第一个元素 
    	const_reference front() const {
         return *begin(); }//取得链表的第一个元素，常性 
    	reference back() {
         return *--end(); }//取得链表的最后一个元素 
    	const_reference back() const {
         return *--end(); }//取得链表的最后一个元素，常性 
    
    	iterator insert(iterator _P, const _Ty& _X)//插入函数，数据的插入，在_p之前插入_x 
    	{
        
    		_Nodeptr _S = _P._Mynode();
    		_Acc::_Prev(_S) = _Buynode(_Acc::_Prev(_S), _S);
    		_S = _Acc::_Prev(_S);
    		_Acc::_Next(_Acc::_Prev(_S)) = _S;
    		yhp::construct(&_Acc::_Value(_S), _X);
    		_Size += 1;
    		return iterator(_S);
    	}
    
    	void push_front(const _Ty& _X)//头插 
    	{
        
    		insert(begin(), _X);
    	}
    	void push_back(const _Ty& _X)//尾插 
    	{
        
    		insert(end(), _X);
    	}
    	void insert(iterator _P, size_t _N, const _Ty& _X)//在_p位置插入_N个_x 
    	{
        
    		for (int i = 0; i < _N; ++i)
    		{
        
    			insert(_P, _X);
    		}
    	}
    	void insert(iterator _P, const _Ty* _F, const _Ty* _L)//把*_F到*_ L的连续空间插入到_p的位置 
    	{
        
    		for (; _F != _L; ++_F)
    		{
        
    			insert(_P, *_F);
    		}
    	}
    	void insert(iterator _P, _It _F, _It _L)//把另一个链表的_F到_L插入到这条链表的_p的位置 
    	{
        
    		for (; _F != _L; ++_F)
    		{
        
    			insert(_P, *_F);
    		}
    	}	
    	iterator erase(iterator _p)
    	{
        
    		_Nodeptr _S=_P++._Mynode();
    		_Acc::_Next(_Acc::_Prev(_S))=_Acc::_Next(_S);
    		_Acc::_Prev(_Acc::_Next(_S))=_Acc::_Prev(_S);
    		yhp::destroy(&_Acc::_Value(_S));
    		_Freenode(_S);
    		_Size=-1;
    		return _P; 
    	}
    	void remove(const _Ty& _X)
    	{
        
    		iterator _F=begin(), _L=end();
    		for(;_F!=_L;)
    		{
        
    			if(*_F=_X)
    			{
        
    				erase(_F++);
    			}
    			else
    			{
        
    				_F++;
    			}
    		}
    	}
    	void erase(iterator _F,iterator _L)
    	{
        
    		for(;_F!=_L;)
    		{
        
    			erase(_F++);
    		}
    	}
    	void clear()
    	{
        
    		erase(begin(),end());
    	}
    	void pop_back()
    	{
        
    		erase(--end());
    	}
    	void pop_front()
    	{
        
    		erase(begin());
    	}
    		
    
    private:  
    	_Nodeptr _Buynode(_Nodeptr _Parg = nullptr, _Nodeptr _Narg = nullptr)//购买结点 
    	{
        
    		_Nodeptr _S = data_allocate::allocate(1);
    		_Acc::_Prev(_S) = _Parg == nullptr ? _S : _Parg;
    		_Acc::_Next(_S) = _Narg == nullptr ? _S : _Narg;
    		return _S;
    	}
    	void _Freenode(_Nodeptr _P)//释放结点 
    	{
        
    		data_allocate::deallocate(_P, 1);
    	}
    	_Nodeptr _Head; 
    	size_t   _Size;
    	_A       allocator;
    };
    
    }