• list的简单模拟实现


    1.节点结构


    template <class T>
    struct list_node
    {
    	
    	typedef list_node<T> Node;
    	list_node(const T& v = T()) 
    		:prev(nullptr), next(nullptr), val(v)
    	{
    	}
    	Node* prev;
    	Node* next;
    	T val;
    };
    

    2. 迭代器结构


    2.1 迭代器结构定义

    template <class T,class Ref,class Ptr>
    struct list_iterator
    {
    	
    	typedef list_node<T> Node;
    	typedef list_iterator <T,Ref,Ptr> Self;
    	 list_iterator( Node* v)  
    		:node(v)  
    	{
    
    	}
    	list_iterator( const Self& v) 
    	{  
    		node = v.node;
    	}
    	Self& operator++()
    	{
    		node = node->next;
    		return *this;
    	}
    	Self& operator--(int)
    	{
    		Self tmp = *this;
    		node = node->prev;
    		return tmp;
    	}
    	Self& operator++(int)
    	{
    		Self tmp = *this;
    		node = node->next;
    		return tmp;
    	}
    	Self& operator--()
    	{
    		node = node->prev;
    		return *this;
    	}
    	Ptr operator->()
    	{
    		return &node->val;
    	}
    	Ref operator*()
    	{
    		return node->val;
    	}
    	bool operator!=(const Self& v)
    	{
    		return node != v.node;
    	}
    	bool operator ==(const Self& v)
    	{
    		return  node == v.node;
    	}
    	 Node* node;
    };
    

    2. 2 迭代器成员函数的实现

    list_iterator( Node* v)  
    		:node(v)  
    	{
    
    	}
    	list_iterator( const Self& v) 
    	{  
    		node = v.node;
    	}
    	Self& operator++()
    	{
    		node = node->next;
    		return *this;
    	}
    	Self& operator--(int)
    	{
    		Self tmp = *this;
    		node = node->prev;
    		return tmp;
    	}
    	Self& operator++(int)
    	{
    		Self tmp = *this;
    		node = node->next;
    		return tmp;
    	}
    	Self& operator--()
    	{
    		node = node->prev;
    		return *this;
    	}
    	Ptr operator->()
    	{
    		return &node->val;
    	}
    	Ref operator*()
    	{
    		return node->val;
    	}
    	bool operator!=(const Self& v)
    	{
    		return node != v.node;
    	}
    	bool operator ==(const Self& v)
    	{
    		return  node == v.node;
    	}
    

    3. list结构


    3.1 list结构定义

    template <class T>
    class list
    {
    	typedef list_node<T> Node;  //T是aa
    public:
    	typedef list_iterator<T,T&,T*> iterator;//这个是正常对象的迭代器
    	typedef list_iterator<T,const T&,const T*> const_iterator;//这个是const对象的迭代器
    
    	
    private:
    	Node* head;
    	size_t size;
    };
    

    2. 2 list成员函数的实现

    void empty_init()
    	{
    		head = new Node;
    		head->next = head;
    		head->prev = head;
    		head->val = T();
    		size = 0;
    	}
    	list()
    	{
    		empty_init();
    	}
    	list(int n, const T& value = T())
    	{
    		empty_init();
    		for (int i = 0; i < n; i++)
    		{
    			push_back(value);
    		}
    	}
    	template <class Iterator>
    	list(Iterator first, Iterator last)
    	{
    		empty_init();
    		while (first != last)
    		{
    			push_back(*first);
    			first++;
    		}
    	}
    	list(const list<T>& l)
    	{
    		empty_init();
    		const_iterator it = l.begin();
    		while (it != l.end())
    		{
    			push_back(*it);
    			it++;
    		}
    	}
    	void swap(const list<T>& l)
    	{
    		std::swap(head, l.head);
    		std::swap(size, l.size);
    	}
    	list<T>& operator=(const list<T> l)
    	{
    		swap(l);
    	}
    	list(initializer_list<T> l)
    	{
    		empty_init();
    		for (auto& ch : l)
    		{
    			push_back(ch);
    		}
    	}
    	void clear()
    	{
    		auto it = begin();
    		while (it != end())
    		{
    			it = erase(it);
    		}
    	}
    	~list()
    	{
    		clear();
    		delete head;
    		head == nullptr;
    	}
    	iterator begin()
    	{
    		//隐式类型转换
    		return head->next;
    	}
    	iterator end()
    	{
    		//隐式类型转换
    		return head;
    	}
    	const_iterator begin()const
    	{
    		//隐式类型转换 
    		return head->next;  //构造函数
    	}
    	const_iterator end()const
    	{
    		//隐式类型转换
    		return head;
    	}
    	size_t _size()const
    	{
    		return size;
    	}
    	bool empty()const
    	{
    		return head->next == head;
    	}
    	T& front()
    	{
    		return head->next;
    	}
    	const T& front()const
    	{
    		return head->next;
    	}
    	T& back()
    	{
    		return head->prev;
    	}
    	const T& back()const
    	{
    		return head->prev;
    	}
    	void push_back(const T& val = T())
    	{
    		//先申请一个节点
    		/*Node* newnode = new Node(val);
    		Node* cur = head->prev;
    		cur->next = newnode;
    		newnode->prev = cur;
    		newnode->next = head;
    		head->prev = newnode;
    		size++;*/
    		insert(end(), val);
    	}
    	void pop_back() { erase(--end()); }
    	void push_front(const T& val=T()) { insert(begin(), val); }
    	void pop_front() { erase(begin()); }
    	iterator insert(iterator pos,const T& val= T())
    	{
    		Node* newnode = new Node(val);
    		Node* prev = pos.node->prev;
    		prev->next = newnode;
    		newnode->prev = prev;
    		newnode->next = pos.node;
    		pos.node->prev = newnode;
    		++size;
    		return newnode;
    	}
    	iterator erase(iterator pos)
    	{
    		assert(pos != end());
    		Node* pcur = pos.node;
    		Node* prev = pcur->prev;
    		Node* next = pcur->next;
    		prev->next = next;
    		next->prev = prev;
    		delete pcur;
    		pcur = nullptr;
    		--size;
    		//这里会调用迭代器的单参数构造函数
    		return next;
    	}
    
  • 相关阅读:
    记录一次阿里云服务器ECS上启动的portainer无法访问的问题
    26.XML
    15、Python -- 阶段总结:变量与流程控制
    【算法每日一练]-图论(保姆级教程 篇4(遍历))#传送门 #负环判断 #灾后重建
    【20221103】【每日一题】二叉搜索树中的众数
    uniapp:使用百度API提取身份证信息(微信小程序适用)
    Apache Kudu的Schema设计(column数据类型)
    浅克隆和深克隆的详细教程~
    stack和queque
    [附源码]计算机毕业设计springboot学生综合数据分析系统
  • 原文地址:https://blog.csdn.net/GOATLong/article/details/140911302