怎样在list中实现迭代器的使用

浅浅的花香味﹌ 2023-01-16 11:15 201阅读 0赞

![在这里插入图片描述][20210425170228561.png]

### list中使用迭代器 ###

*  目录:
 *   *  一.原因
     *  二.封装list迭代器
     *  三.函数内部对于迭代器的使用

# 目录: #

## 一.原因 ##

因为list是一个双向带头循环链表,我们之前用的迭代器在这里是无法实现的,所以我们就要对这里的迭代器进行自定义的封装,才能达到对于迭代器的使用

## 二.封装list迭代器 ##

template<class T>
    struct ListIterator{ 
    	ListIterator(ListNode<T>* node)		//迭代器构造函数
    	:_node(node)
    	{ }
    
    
    	//获取数据本身
    	T& operator*(){ 
    		return _node->_data;	
    	}
    
    	//++iterator
    	ListIterator<T>& operator++(){ 
    
    		_node = _node->_next;
    		return *this;
    	}
    	bool operator!=(const ListIterator<T>& it){ 
    
    		//只要判断成员指针_node是否是指向同一个节点
    		return _node != it._node;
    	}
    
    
    	//封装节点
    	ListNode<T>* _node;
    };

## 三.函数内部对于迭代器的使用 ##

template<class T>
    class List{ 
    
    public:
    	typedef ListNode<T> Node;
    	typedef Node* pNode;
    	typedef ListIterator<T> iterator;
    	typedef const ListIterator<T> const_iterator;
    
    	
    	typedef ListIterator<T> iterator;
    	iterator begin(){ 
    
    		return iterator(_header->_next);
    	}
    	iterator end(){ 
    
    		return iterator(_header);
    	}
    
    
    	List()
    		:_header(new Node())
    	{ 	//对于一个简单的list的创建,要让其内部的两个指针指向自己,才能完成初始化
    
    		_header->_next = _header->_prev = _header;
    	}
    
    	List(size_t n, const T& val = T())
    		:_header(new Node())
    	{ 
    		_header->_next = _header->_prev = _header;
    
    		for (size_t i = 0; i < n; ++i){ 
    
    			pushBack(val);
    		}
    	}
    
    	template<class inputIterator>
    	List(inputIterator first, inputIterator last)
    		:_header(new Node())
    	{ 
    		_header->_next = _header->_prev = _header;
    		while (first != last){ 
    
    			pushBack(*first);
    			++first;
    		}
    	}
    
    
    	void pushBack(const T& val){ 
    		insert(end(), val);			//尾插通过insert调用end()迭代器实现
    	}
    
    	void pushFront(const T& val){ 
    
    		insert(begin(), val);		//头插通过insert调用begin()迭代器实现
    	}
    
    	void insert(iterator pos, const T& val){ 
    
    		//理解
    		pNode cur = pos._node;
    		pNode prev = cur->_prev;
    		pNode newNode = new Node(val);
    
    		prev->_next = newNode;
    		newNode->_prev = prev;
    
    		newNode->_next = cur;
    		cur->_prev = newNode;
    	}
    
    	iterator erase(iterator pos){ 	//迭代器实现erase
    
    		if (pos != end()){ 
    
    			pNode cur = pos._node;
    			pNode prev = cur->_prev;
    			pNode next = cur->_next;
    
    			delete cur;
    			next->_prev = prev;
    			prev->_next = next;
    
    			//在进行删除以后,内部的迭代器会失效
    			//所以我们要通过更新迭代器来指向对应的下一个元素
    			return iterator(next);
    		}
    		return pos;
    	}
    
    	void popFront(){ 
    
    		erase(begin());		//迭代器调用end()实现头删
    	}
    
    	void popBack(){ 
    
    		erase(--end());		//对于这里的--操作要进行operator
    	}
    
    
    	//深拷贝
    	List(const List<T>& lst)
    		:_header(new Node())
    	{ 
    		//循环结构
    		_header->_next = _header->_prev = _header;
    
    		//元素拷贝
    		Node* cur = lst._header->_next;
    		while (cur != lst._header){ 
    
    			pushBack(cur->_data);
    		}
    	}
    
    	List<T>& operator=(const List<T>& lst){   
    
    		if (this != &lst){ 
    			//释放原来有的节点
    			Node* cur = _header->_next;
    			while (cur != _header){ 
    
    				Node* next = cur->_next;
    				delete cur;
    				cur = next;
    			}
    			_header->_next = _header->_prev = _header;
    			//拷贝
    			for (auto& e : lst)
    				pushBack(e);
    		}
    		return *this;
    	}
    
    	List<T>& operator=(List<T>& lst){ 
    
    		swap(_header, lst._header);
    		return *this;
    	}
    
    
    	~List(){ 
    		if (_header){ 
    
    			pNode* node = _header->_next;
    			while (node != _header){ 
    
    				pNode* next = node->_next;
    				delete node;
    				node = next;
    			}
    			delete _header;
    			_header = nullptr;
    		}
    	}
    
    private:
    	ListNode<T>* _header;
    };

这一篇文章主要是对于双向带头循环链表实现迭代器的使用,主要就是利用迭代器方便其他函数接口的实现.

[20210425170228561.png]: /images/20221022/a61981f20d8241a19d9419fddec239e0.png