STL list迭代器实现

素颜马尾好姑娘i 2021-12-03 14:33 403阅读 0赞

##### list #####

list是一个线性双向链表结构，它的数据由若干个节点构成，每一个节点都包括一个信息块（即实际存储的数据）、一个前驱指针和一个后驱指针。它无需分配指定的内存大小且可以任意伸缩，这是因为它存储在非连续的内存空间中，并且由指针将有序的元素链接起来。由于其结构的原因，list 随机检索的性能非常的不好，因为它不像vector 那样直接找到元素的地址，而是要从头一个一个的顺序查找，这样目标元素越靠后，它的检索时间就越长。检索时间与目标元素的位置成正比。虽然随机检索的速度不够快，但是它可以迅速地在任何节点进行插入和删除操作。因为list 的每个节点保存着它在链表中的位置，插入或删除一个元素仅对最多三个元素有所影响，不像vector 会对操作点之后的所有元素的存储地址都有所影响，这一点是vector 不可比拟的。

###### list的节点 ######

节点跟一般的链表节点一样

//list的节点
    template<class T>
    struct ListNode
    {
        
    	typedef ListNode* pointer;
    	pointer prev;
    	pointer next;
    	T data;
    };

###### list的迭代器 ######

list不再能够像vector一样以普通的指针来作为迭代器，因为其节点不保证在存储空间中连续存在。list迭代器必须有能力指向list的节点，并有能力进行正确的递增、递减、取值、成员存取等操作。递增时指向下一个节点，递减的时候指向上一个节点，取值时候取的是节点的数据值，成员取用的是节点的成员。

由于STL list是一个双向链表（double linked-list），迭代器必须具备前移和后移的能力，所有list提供的是Bidirectional iterators；

另外，值得注意的是，插入（insert）和接合操作（splice）都不会造成原有的list迭代器失效。

#ifndef _MYLIST
    #define _MYLIST
    
    
    //list的节点
    template<class T>
    struct ListNode
    {
        
    	typedef ListNode* pointer;
    	pointer prev;
    	pointer next;
    	T data;
    };
    
    template<class T, class Ref, class Ptr>
    struct MyListIterator
    {
        
    	//迭代器类型
    	typedef MyListIterator<T, T&, T*>	iterator;
    
    	//跟MyListIterator类型相同
    	typedef	MyListIterator<T, Ref, PTR> self;
    
    	typedef	bidirectional_iterator_tag iterator_category;
    	
    	//数据的类型，如int
    	typedef T value_type;
    
    	//指向数据的指针，如int*
    	typedef Ptr pointer;
    
    	//数据的引用，如int&
    	typedef Ref reference;
    
    	//指向list节点的指针
    	typedef ListNode<T>* link_type;
    
    	//大小
    	typedef	size_t size_type;
    
    	link_type node;
    
    	//************************************
    	// Method:    	MyListIterator
    	// Desc:		构造函数
    	// Author:    
    	// Date: 	  	2019/07/18
    	// FullName:  	MyListIterator<T, Ref, Ptr>::MyListIterator
    	// Returns:   	
    	// Parameter: 	link_type x：	指向list节点的指针
    	//************************************
    	MyListIterator(link_type x) :node(x)
    	{
        
    	}
    	MyListIterator()
    	{
        
    	}
    	//************************************
    	// Method:    	MyListIterator
    	// Desc:		构造函数
    	// Author:    
    	// Date: 	  	2019/07/18
    	// FullName:  	MyListIterator<T, Ref, Ptr>::MyListIterator
    	// Returns:   	
    	// Parameter: 	const iterator &x： 另一个迭代器
    	//************************************
    	MyListIterator(const iterator &x) const: node(x.node)
    	{
        
    	}
    	
    	//************************************
    	// Method:    	operator==
    	// Desc:		重载==，判断两个迭代器是否相同
    	// Author:    
    	// Date: 	  	2019/07/18
    	// FullName:  	MyListIterator<T, Ref, Ptr>::operator==
    	// Returns:   	bool
    	// Parameter: 	const self & x	:MyListIterator类型的迭代器
    	//************************************
    	bool operator==(const self& x) const
    	{
        
    		return node == x.node;
    	}
    	bool operator!=(const self& x) const
    	{
        
    		return node != x.node;
    	}
    
    	//************************************
    	// Method:    	operator*
    	// Desc:		对迭代器取值，取的是节点的数据值
    	// Author:    
    	// Date: 	  	2019/07/18
    	// FullName:  	MyListIterator<T, Ref, Ptr>::operator*
    	// Returns:   	reference
    	//************************************
    	reference operator*() const
    	{
        
    		return (*node).data;
    	}
    
    	//************************************
    	// Method:    	operator->
    	// Desc:		对迭代器的成员存取运算子的标准做法
    	// Author:    
    	// Date: 	  	2019/07/18
    	// FullName:  	MyListIterator<T, Ref, Ptr>::operator->
    	// Returns:   	pointer
    	//************************************
    	pointer operator->()const
    	{
        
    		return &(operator*());
    	}
    	
    	//************************************
    	// Method:    	operator++
    	// Desc:		前置自增
    	// Author:    
    	// Date: 	  	2019/07/18
    	// FullName:  	MyListIterator<T, Ref, Ptr>::operator++
    	// Returns:   	self&：	自身迭代器
    	//************************************
    	self& operator++()
    	{
        
    		node = node.next;
    		return *this;
    	}
    
    	//************************************
    	// Method:    	operator++
    	// Desc:		后置自增
    	// Author:    
    	// Date: 	  	2019/07/18
    	// FullName:  	MyListIterator<T, Ref, Ptr>::operator++
    	// Returns:   	self&：	新的迭代器
    	// Parameter: 	int：	无用的
    	//************************************
    	self& operator++(int)
    	{
        
    		self temp = *this;
    		++(*this);
    		return temp;
    	}
    
    	self& operator++()
    	{
        
    		node = node.prev;
    		return *this;
    	}
    
    	self& operator--(int)
    	{
        
    		self temp = *this;
    		--(*this);
    		return temp;
    	}
    
    
    };
    
    
    #endif