学习STL，实现一个单链表的迭代器

╰半夏微凉° 2022-08-05 08:25 75阅读 0赞

STL源码剖析中，空间配置器和迭代器属于比较晦涩难懂的两章，这里学习了STL迭代器后也尝试自己写一个迭代器，实现单链表的迭代器，实现不难，可以说是一个玩具而已，但是能够帮助我们理解STL迭代器的基本原理。

## 1.节点Node和单链表的定义LinkList ##

//声明
    template<typename T>
    class ListIterator;
    template<typename T>
    class LinkList;
    
    //链表节点
    template<typename T>
    class Node{
    	friend class LinkList<T>;
    	friend class ListIterator<T>;
    
    	template<typename T1>
    	friend ostream& operator<<(ostream &out,const LinkList<T1>& list);
    
    private:
    	//私有构造函数，只能友员类可以实例化该类
    	Node(const T& datavalue):data(datavalue),next(NULL){};
    	T data;
    	Node* next;
    };
    
    //带头结点的单链表
    template<typename T>
    class LinkList{
    	template<typename T1>
    	friend ostream& operator<<(ostream &out,const LinkList<T1>& list);
    
    	friend class ListIterator<T>;
    public:
    	LinkList();
    	~LinkList();
    	//链表操作
    	void Insert(const T& data, int index);
    	bool IsEmpty() const;
    private: 
    	Node<T>* first; //带头节点的单链表	
    };

节点的定义成上述形式，主要就是为了实现oo思想中的封装。单链表的声明中省去来了很多成员函数，因为这里只是为了实现迭代器思想。

## 2.单链表迭代器的声明ListIterator ##

//链表迭代器
    template<typename T>
    class ListIterator{
    public:
    	ListIterator(const LinkList<T>& _list):list(_list),currentNode((_list.first)->next){};
    
    	//重载*
    	const T& operator*() const throw(std::out_of_range);
    	T& operator*() throw(std::out_of_range);
    	//重载->
    	const Node<T>* operator->()const throw(std::out_of_range);
    	Node<T>* operator->() throw(std::out_of_range);
    	//重载++
    	ListIterator& operator++() throw(std::out_of_range);
    	ListIterator& operator++(int) throw(std::out_of_range);
    	//重载=
    	ListIterator& operator=(const LinkList<T>& list) throw (std::out_of_range);
    	bool IsEmpty() const;
    private:
    	const LinkList<T>& list;
    	Node<T>* currentNode;
    };

实现的关键在于，\*、++ 、=的运算符重载，将单链表指针作为自己的成员，来实现。

## 3.LinkList和ListIterator实现代码 ##

template<typename T>
    LinkList<T>::LinkList()
    {
    	Node<T>* head = new Node<T>(0);
    	first = head;
    	head->next = NULL;
    }
    
    template<typename T>
    LinkList<T>::~LinkList()
    {
    	Node<T>* delNode = NULL;
    	while(first != NULL)
    	{
    		delNode = first;
    		first = first->next;
    		delete delNode;
    	}
    }
    
    template <typename T>
    void LinkList<T>::Insert(const T &data, int index)
    {
    	int count = 1;
    	Node<T> *searchNode = first;
    
    	while (count < index && searchNode->next != NULL)
    	{
    		++count;
    		searchNode = searchNode->next;
    	}
    
    	// 插入链表
    	Node<T> *newNode = new Node<T>(data);
    	newNode->next = searchNode->next;
    	searchNode->next = newNode;
    }
    
    //显示链表中的所有数据(测试用)  
    template <typename T>  
    ostream &operator<<(ostream &os, const LinkList<T> &list)  
    {  
    	for (Node<T> *searchNode = list.first->next;  searchNode != NULL;  searchNode = searchNode->next)  
    	{  
    		os << searchNode -> data;  
    		if (searchNode -> next != NULL) //尚未达到链表的结尾  
    			cout << " -> ";  
    	}  
    	return os;  
    } 
    
    //ListIterator的实现
    template <typename T>
    const T& ListIterator<T>::operator*() const throw (std::out_of_range)
    {
    	if (IsEmpty())
    		throw std::out_of_range("iterator is out of range");
    	// 返回当前指针指向的内容
    	return currentNode->data;
    }
    template <typename T>
    T &ListIterator<T>::operator*() throw (std::out_of_range)
    {
    	//首先为*this添加const属性,以调用该函数的const版本,
    	//然后再使用const_case,将该函数调用所带有的const属性转除
    	//operator->()的non-const版本与此类同
    	return
    		const_cast<T &>(static_cast<const ListIterator<T> &>(*this).operator*());
    }
    
    template <typename T>
    const Node<T> *ListIterator<T>::operator->() const throw (std::out_of_range)
    {
    	if (IsEmpty())
    		throw std::out_of_range("iterator is out of range");
    	//直接返回指针
    	return currentNode;
    }
    
    template <typename T>
    Node<T> *ListIterator<T>::operator->() throw (std::out_of_range)
    {
    	return const_cast<Node<T> *> (static_cast<const ListIterator<T> >(*this).operator->());
    }
    
    template <typename T>
    ListIterator<T>& ListIterator<T>::operator++() throw (std::out_of_range)
    {
    	if (IsEmpty())
    		throw std::out_of_range("iterator is out of range");
    	//指针前移
    	currentNode = currentNode->next;
    	return *this;
    }
    
    template <typename T>
    ListIterator<T>& ListIterator<T>::operator++(int) throw (std::out_of_range)
    {
    	ListIterator tmp(*this);
    	++(*this); //调用前向++版本
    	return tmp;
    }
    
    template<typename T>
    ListIterator<T>& ListIterator<T>::operator=(const LinkList<T>& list) throw (std::out_of_range)
    {
    	this->list = list;
    	this->currentNode = list.first->next;
    	return *this;
    }
    
    template <typename T>
    bool ListIterator<T>::IsEmpty() const
    {
    	if (currentNode == NULL)
    		return true;
    	return false;
    }

## 4.测试代码 ##

#include "link_list.h"
    int _tmain(int argc, _TCHAR* argv[])
    {
    	LinkList<int> iMyList;
    	for (int i = 0; i < 10; ++i)  
    	{  
    		iMyList.Insert(i+1, i+1);  
    	}  
    	cout << "Iterator:";
    	for (ListIterator<int> iter(iMyList); !iter.IsEmpty(); ++iter)  
    	{  
    		cout << *iter << " ";  
    	}  
    	cout << endl;  
    
    	cout << "Iterator2:";
    	for (ListIterator<int> iter2 = iMyList; !iter2.IsEmpty();++iter2)
    	{
    		cout << *iter2 << " ";
    	}
    	cout << endl;  
    
    	cout << "ostream:" << iMyList << endl;  
    
    	ListIterator<int> iter(iMyList);  
    	cout << "first = " << *iter << endl;  
    
    	system("pause");
    	return 0;
    }

本示例直接粘贴运行。

最后，虽然实现简单，但是与STL中的迭代器是不能相提并论的，设计一个良好的迭代器不是一件简单的事情，从STL的迭代器的设计中就可以看出。