开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【C++】list的模拟实现@STL —— 迭代器 -> 正文阅读

[数据结构与算法]【C++】list的模拟实现@STL —— 迭代器

本文依旧按照依赖逻辑模拟实现list，重点讲解 迭代器。

正文开始@边通书

0. list

list即带头双向循环链表，支持在任意位置**O(1)**的插入和删除。

1. list框架

ListNode节点；list即一个头结点指针。

	template<class T>
	struct ListNode
	{
		ListNode<T>* _prev;
		ListNode<T>* _next;
		T _data;

		ListNode(const T& x = T())
		{
			_prev = nullptr;
			_next = nullptr;
			_data = x;
		}
	};

    template<class T>
	class list
	{
		typedef ListNode<T> Node;
        
	public:
		list()
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
		}
    private:
		Node* _head;
	};

为了随写随测，迅速先写一个尾插，这老生常谈了。当然一会儿写完insert(需要迭代器pos) 可以直接复用——

		void push_back(const T& x)
		{
			Node* newnode = new Node(x);
			Node* tail = _head->_prev;
			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;
		}

2. 迭代器(重点)

?? 迭代器访问容器就是在模仿指针的两个重点行为：解引用 能够访问数据；++可以到下一个位置。对于string和vector这样连续的物理空间，原生指针就是天然的迭代器；然而对于list这样在物理空间上不连续的数据结构，解引用就是结点访问不到数据，++不能到下一个结点，原生指针做不了迭代器。

因此，对于链表的迭代器，我们用自定义类型对结点的指针进行封装，底层仍然是结点的指针。C++的自定义类型支持运算符重载，原本的运算符编程变成函数调用，这样就可以实现像内置类型一样使用运算符。这就是类型的力量！

构造迭代器，一个节点的指针就可以构造 ——

	template<class T>
	struct __list_iterator
	{
		typedef ListNode<T> Node;
		typedef __list_iterator<T,Ref,Ptr> Self;
		Node* _node;

		__list_iterator(Node* x)
			: _node(x)
		{}
    };

迭代器的拷贝构造&赋值重载都不需要我们自己实现，因为要的就是浅拷贝，用编译器默认生成的即可。

析构函数呢？也不需要我们实现。那释放链表呢，节点属于链表list，迭代器是借助结点指针来访问修改链表的，不属于迭代器。就像是你自己的碗要自己洗，去外面吃就不用自己洗；我把结点的指针给你让你访问，结果你把我链表给释放了这不搞笑嘛。

2.1 iterator & const_iterator

迭代器遍历。下面是测试代码 ——

	void print_list(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			// *it /= 2; 不可写
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

	// 测试迭代器
	void test_list1()
	{
		list<int> lt;
 		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

		list<int>::iterator it = lt.begin();
		while (it != lt.end())
		{
			*it *= 2; //可写
			cout << *it << " ";
			++it;
		}
		cout << endl;

		//测试const迭代器
		print_list(lt);
	}

可以看到我们首先需要重载++，*，!=这些运算符。

2.1.1 重载*

我们在list中进行typedef，这样所有容器迭代器名字统一都是iterator。
关于iterator和const_iterator：普通迭代器返回的是T&，可读可写；const迭代器返回的是const T&，可读不可写。我们当然可以再封装一个类就叫做__const_list_iterator，稍作修改，但是这样会造成严重的代码冗余，因为++/–/==的重载都没有区别，只是返回值不同罢了。我们巧妙的传入模板参数解决了这个问题，这也是迭代器的精华。
我们把类模板typedef成self

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xRfb4xoc-1648974512795)(C:\Users\13136\AppData\Roaming\Typora\typora-user-images\image-20220402162738840.png)]$

迭代器相关完整代码附在2.1.3小节.

2.1.2 重载->

如果T不是int这样的内置类型，而是自定义类型，我们要访问其中的每一个成员，还需要重载->。我们以日期类为例 ——

	struct Date
	{
		Date(int year = 0,int month = 0,int day = 0)
			: _year(year)
			, _month(month)
			, _day(day)
		{}

		int _year;
		int _month;
		int _day;
	};

	void test_list2()
	{
		list<Date> lt;
		lt.push_back(Date(2022, 3, 31));
		lt.push_back(Date(2022, 3, 31));
		lt.push_back(Date(2022, 3, 31));

		// 遍历链表，打印日期
		list<Date>::iterator it = lt.begin();
		while (it != lt.end())
		{
            //cout << *it << endl; // 错误示范，请勿模仿
            // 因为Date是自定义类型，需要重载<<来打印，但要就是不给你提供呢，下面这样是可以的
			cout << (*it)._year << "." << (*it)._month << "." << (*it)._day << endl;
			it++;
		}
		cout << endl;
	}
	//小细节：Date构造函数需要给缺省值，因为哨兵位头结点没给数

迭代器it是去模仿指针的行为。在list中，如果节点中是int这样的内置类型，解引用(本质调用函数)访问数据即可；而像这里一个结构体的指针，我们固然可以(*it)拿到日期类对象.访问成员，但我们更希望能->访问成员，因此我们还需要重载-> ——

    cout << it->_year << "." << it->_month << "." << it->_day << endl;

这里本来应该是it->->_year，但是这样写运算符可读性太差了，所以编译器进行了优化，省略了一个->，所有类型想要重载->都是这样。对于const对象，可读不可写，那么应该返回const指针，因此我们在添加一个Ptr参数。
$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uK6PjyBu-1648974512796)(C:\Users\13136\AppData\Roaming\Typora\typora-user-images\image-20220402190825429.png)]$

2.1.3 重载++/-- & ==/!=

++/–这些都比较简单，迭代器的完整代码附在这里了 ——

	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef ListNode<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self;
		Node* _node;

		__list_iterator(Node* x)
			: _node(x)
		{}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &_node->_data;
		}

		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		self operator++(int)
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		self operator--(int)
		{
			self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}

		bool operator==(const Self& it) const
		{
			return _node = it._node;
		}

		bool operator!=(const Self& it) const
		{
			return _node != it._node;
		}

	};

list中的begin()和end()接口 ——

	template<class T>
	class list
	{
		typedef ListNode<T> Node;
	public:
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;

		list()
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
		}
        
        iterator begin()
		{
			return iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_head);
		}

		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}

		const_iterator end() const
		{
			return const_iterator(_head);
		}
        private:
			Node* _head;
	};

2.2 reverse_iterator

反向迭代器就是对正向迭代器的封装，这样它可以是任意容器的反向迭代器。

它们的不同就在于++调的是正向迭代器的–；–调的是正向迭代器的++
源码中为了使正向迭代器&反向迭代器的开始和结束保持对称，解引用*取前一个位置

这样做是有一定原因的，对于vector的反向迭代器，如果是我们预想的那样(解引用取的是当前位置)，会有越界访问问题。

为了获取数据类型T，我们还需要增加两个类模板参数Ref、Ptr。源码中不带这两个参数，是通过迭代器萃取技术实现的。

#pragma once

namespace beatles
{
	// 可以是任意容器的反向迭代器
	// Iterator是哪个容器的迭代器，reverse_iterator<Iterator>就可以适配哪个容器的反向迭代器(复用)
	template<class Iterator, class Ref, class Ptr>
	class reverse_iterator
	{
		typedef reverse_iterator<Iterator, Ref, Ptr> self;
	public:
		reverse_iterator(Iterator it)
			:_it(it)
		{}

		Ref operator*()
		{
			Iterator prev = _it;
			return *--prev;
		}

		Ptr operator->()
		{
			return &operator*();
		}

		self& operator++()
		{
			--_it;
			return *this;
		}

		self operator++(int)
		{
			self tmp(*this);
			--_it;
			return tmp;
		}

		self& operator--()
		{
			self tmp(*this);
			++_it;
			return tmp;
		}

		self operator--(int)
		{
			return ++_it;
		}

		bool operator==(const self& rit) const
		{
			return _it == rit._it;
		}

		bool operator!=(const self& rit) const
		{
			return _it != rit._it;
		}
	private:
		Iterator _it;
	};
}

3. Modifiers

带头双向循环链表无死角的完美结构，使得任意位置的插入删除变得简单。

3.1 insert & erase

🍓 insert

    iterator insert(iterator pos, const T& x)
    {
        Node* cur = pos._node;
        Node* prev = cur->_prev;
        Node* newnode = new Node(x);
        
        prev->_next = newnode;
        newnode->_prev = prev;
        newnode->_next = cur;
        cur->_prev = newnode;
        
        return iterator(newnode);
    }

返回值是newnode位置的迭代器
list的insert会发生迭代器失效吗？众所周知，vector中insert迭代器失效有两种原因：扩容野指针；pos意义改变。显然，list这里不会再发生迭代器失效。

🍓 erase

    iterator erase(iterator pos)
    {
        assert(pos != end());
        Node* prev = pos._node->_prev;
        Node* next = pos._node->_next;
        delete pos._node;
        
        prev->_next = next;
        next->_prev = prev;
        
        return iterator(next);
    }

返回值是指向erase的下一个节点处的迭代器
erase后迭代器必然要失效，节点都被干掉了，是野指针

3.2 push_back & push_front

注意插入位置。

    void push_back(const T& x)
    {
        insert(end(), x);
    }

    void push_front(const T& x)
    {
        insert(begin(), x);
    }

3.3 pop_back & pop_front

注意删除位置。

    void pop_back()
    {
        erase(--end());
    }

    void pop_front()
    {
        erase(begin());
    }

4. list的默认成员函数

4.1 构造

🍓 无参构造

    list()
    {
        _head = new Node;
        _head->_prev = _head;
        _head->_next = _head;
    }

🍓 迭代器区间构造

    // 迭代器区间构造
    template<class InputIterator>
    list(InputIterator first, InputIterator last)
    {
        _head = new Node;
        _head->_prev = _head;
        _head->_next = _head;
        while (first != last)
        {
            push_back(*first);
            first++;
        }
    }

4.2 clear() & 析构函数

🍓 clear清掉链表中所有数据，在重新进行插入，注意需要保留头结点。

    void clear()
    {
        iterator it = begin();
        while (it != end())
        {
            iterator del = it++;
            delete del._node;
            //delete (it++)._node;
        }
        //更改链接关系
        _head->_prev = _head;
        _head->_next = _head;
    }

🍓 析构函数

    ~list()
    {
        clear();
        delete _head;
        _head = nullptr;
    }

4.3 拷贝构造

深拷贝。传统写法，利用范围for🍬尾插——

     //拷贝构造 - 传统写法
     //lt2(lt1)
    list(const list<T>& lt)
    {
        _head = new Node;
        _head->_prev = _head;
        _head->_next = _head;

        for (auto e : lt)
        {
            push_back(e);
        }
    }

🍓 拷贝构造现代写法，需要迭代器区间构造

    // 拷贝构造 - 现代写法
    // lt2(lt1)
    list(const list<T>& lt)
    {
        _head = new Node;
        _head->_prev = _head;
        _head->_next = _head;

        list<T> tmp(lt.begin(), lt.end());
        swap(_head, tmp._head);
    }

注意必须给一个头，否则_head是一个随机值，换给tmp后出作用域调用析构函数，clear时获取begin()要解引用 _head-> _next会崩溃。

4.4 赋值重载

传统写法，复用clear()和尾插 ——

     //赋值重载 - 传统写法
     //lt1 = lt3
    list<T>& operator=(const list<T>& lt)
    {
        if (this != &lt)
        {
            clear(); //lt1
            for (auto e : lt)
            {
                push_back(e);
            }
        }
        return *this;
    }

🍓 现代写法

    // 赋值重载
    // lt1 = lt3
    list<T>& operator=(list<T> lt)
    {
        swap(_head, lt._head);
        return *this;
    }

5. list & vector 区别和联系

【面试题】 list & vector的区别和联系

	vector	list
互补	连续的物理空间，可以随机访问，是优势也是劣势	带头双向循环链表，不能随机访问
	1. 空间不够需要增容，增容代价比较大	1. 按需申请释放空间
	2. 按需申请，一般是2倍左右扩容，可能存在一定的空间浪费 (reseve一定程度缓解)
	3. 头部和中间的插入删除需要挪动数据，效率低下	2.支持任意位置O(1)的插入删除
迭代器	原生指针	用类去封装节点指针。重载*、++等操作符，让它像指针一样

附：

list.h

#pragma once

#include<iostream>
#include<assert.h>
#include"reverse_iterator.h"

using namespace std;

namespace beatles
{
	template<class T>
	struct ListNode
	{
		ListNode<T>* _prev;
		ListNode<T>* _next;
		T _data;

		ListNode(const T& x = T())
		{
			_prev = nullptr;
			_next = nullptr;
			_data = x;
		}
	};

	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef ListNode<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self;
		Node* _node;

		__list_iterator(Node* x)
			: _node(x)
		{}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &_node->_data;
		}

		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		self operator++(int)
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		self operator--(int)
		{
			self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}

		bool operator==(const self& it) const
		{
			return _node = it._node;
		}

		bool operator!=(const self& it) const
		{
			return _node != it._node;
		}

	}; 

	template<class T>
	class list
	{
		typedef ListNode<T> Node;
	public:
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;

		//把正向迭代器作为模板参数传给反向迭代器
		typedef reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
		typedef reverse_iterator<iterator, T&, T*> reverse_iterator;
		list()
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
		}

		// 迭代器区间构造
		template<class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;

			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}

		// 拷贝构造 - 现代写法
		// lt2(lt1)
		list(const list<T>& lt)
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;

			list<T> tmp(lt.begin(), lt.end());
			swap(_head, tmp._head);
		}

		// 赋值重载
		// lt1 = lt3
		list<T>& operator=(list<T> lt)
		{
			swap(_head, lt._head);
			return *this;
		}

		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				iterator del = it++;
				delete del._node;
				//delete (it++)._node;
			}
			//更改链接关系
			_head->_prev = _head;
			_head->_next = _head;
		}

		 //拷贝构造 - 传统写法
		 //lt2(lt1)
		/*list(const list<T>& lt)
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
			
			for (auto e : lt)
			{
				push_back(e);
			}
		}*/

		 //赋值重载 - 传统写法
		 //lt1 = lt3
		//list<T>& operator=(const list<T>& lt)
		//{
		//	if (this != &lt)
		//	{
		//		clear(); //lt1
		//		for (auto e : lt)
		//		{
		//			push_back(e);
		//		}
		//	}
		//	return *this;
		//}

		iterator begin()
		{
			return iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_head);
		}

		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}

		const_iterator end() const
		{
			return const_iterator(_head);
		}

		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}
		
		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}

		const_reverse_iterator rbegin() const
		{
			return const_reverse_iterator(end());
		}

		const_reverse_iterator rend() const
		{
			return const_reverse_iterator(begin());
		}


		iterator insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(x);
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			return iterator(newnode);
		}

		void push_back(const T& x)
		{
			/*Node* newnode = new Node(x);
			Node* tail = _head->_prev;
			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;*/
			insert(end(), x);
		}

		void push_front(const T& x)
		{
			insert(begin(), x);
		}

		iterator erase(iterator pos)
		{
			assert(pos != end());
			Node* prev = pos._node->_prev;
			Node* next = pos._node->_next;
			delete pos._node;
			prev->_next = next;
			next->_prev = prev;
			return iterator(next);
		}

		void pop_back()
		{
			erase(--end());
		}

		void pop_front()
		{
			erase(begin());
		}
	private:
		Node* _head;
	};

	void print_list(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			// *it /= 2; 不可写
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

	// 测试迭代器
	void test_list1()
	{
		list<int> lt;
 		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

		list<int>::iterator it = lt.begin();
		while (it != lt.end())
		{
			*it *= 2; //可写
			cout << *it << " ";
			++it;
		}
		cout << endl;

		//测试const迭代器
		print_list(lt);
	}

	struct Date
	{
		Date(int year = 0,int month = 0,int day = 0)
			: _year(year)
			, _month(month)
			, _day(day)
		{}

		int _year;
		int _month;
		int _day;
	};

	void test_list2()
	{
		list<Date> lt;
		lt.push_back(Date(2022, 3, 31));
		lt.push_back(Date(2022, 3, 31));
		lt.push_back(Date(2022, 3, 31));

		// 遍历链表，打印日期
		list<Date>::iterator it = lt.begin();
		while (it != lt.end())
		{
			//cout << (*it)._year << "." << (*it)._month << "." << (*it)._day << endl;
			cout << it->_year << "." << it->_month << "." << it->_day << endl;
			it++;
		}
		cout << endl;
	}

	// 测试插入&删除
	void test_list3()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_front(0);
		lt.push_front(-1);
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		lt.pop_back();
		lt.pop_front();
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	// 测试拷贝构造&赋值重载
	void test_list4()
	{
		list<int> lt1;
		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		lt1.push_back(4);

		/*lt1.clear();
		for (auto e : lt1)
		{
			cout << e << " ";
		}
		cout << endl;*/

		list<int> lt2(lt1);
		for (auto e : lt2)
		{
			cout << e << " ";
		}
		cout << endl;

		list<int> lt3;
		lt3.push_back(10);
		lt3.push_back(20);
		lt3.push_back(30);
		lt3.push_back(40);
		lt3.push_back(50);
		lt1 = lt3;
		for (auto e : lt1)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	// 测试反向迭代器
	void test_list5()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

		list<int>::reverse_iterator rit = lt.rbegin();
		while (rit != lt.rend())
		{
			cout << *rit << " ";
			rit++;
		}
		cout << endl;
	}
}

reverse_iterator.h

可以是适配成任意容器的反向迭代器，Iterator是哪个容器的迭代器，reverse_iterator< Iterator>就可以适配哪个容器的反向迭代器(复用)

#pragma once

namespace beatles
{
	// 可以是任意容器的反向迭代器
	// Iterator是哪个容器的迭代器，reverse_iterator<Iterator>就可以适配哪个容器的反向迭代器(复用)
	template<class Iterator, class Ref, class Ptr>
	class reverse_iterator
	{
		typedef reverse_iterator<Iterator, Ref, Ptr> self;
	public:
		reverse_iterator(Iterator it)
			:_it(it)
		{}

		Ref operator*()
		{
			Iterator prev = _it;
			return *--prev;
		}

		Ptr operator->()
		{
			return &operator*();
		}

		self& operator++()
		{
			--_it;
			return *this;
		}

		self operator++(int)
		{
			self tmp(*this);
			--_it;
			return tmp;
		}

		self& operator--()
		{
			self tmp(*this);
			++_it;
			return tmp;
		}

		self operator--(int)
		{
			return ++_it;
		}

		bool operator==(const self& rit) const
		{
			return _it == rit._it;
		}

		bool operator!=(const self& rit) const
		{
			return _it != rit._it;
		}
	private:
		Iterator _it;
	};
}

test.cpp

#define _CRT_SECURE_NO_WARNINGS 1

#include"list.h"

int main()
{
	//beatles::test_list1();
	//beatles::test_list2();
	//beatles::test_list3();
	//beatles::test_list4();
	beatles::test_list5();
	return 0;
}