[C++] 模拟实现list（二）

标题：[C++] 模拟实现list（二）

@水墨不写bug

目录

（一）回顾

（二）迭代器类的封装设计

（1）成员函数简要分析

 （2）const迭代器类的设计

（3）list类的封装设计

（4）反向迭代器类的设计

（三）实现list类

正文开始：

（一）回顾

        本篇文章接续《[C++] 模拟实现list（二）》继续讲解STL实现list的逻辑和思考，最终提供实现的list的最终版本。

        [C++] 模拟实现list（二）中，我们定义了三个类：

template<typename T>
struct ListNode;

template<typename T>
struct ListIterator;

template<class T>
class list;

        ListNode即是list的一个节点；ListIterator即对节点的指针的封装的一个类，也就是迭代器；list即是链表的类；

         我们一般通过指针来维护链表，但是如果直接拿指针这个内置类型作为迭代器，迭代器的行为不符合我们的要求，所以我们将这个指针封装为一个类，这样就可以通过类的成员函数重载运算符来使得迭代器的行为符合我们的要求。

（二）迭代器类的封装设计

（1）成员函数简要分析

        我们实现迭代器类ListIterator，本质就是通过封装节点的指针，来实现要求的功能。这个迭代器类，看似是一个自定义类，其实我们可以把它的行为等效的看为一个指针类型：

        指针的前置++，就是节点指针先向后移动再使用。

        指针的前置--，就是节点指针的先向前移动，再使用。

        指针的后置++，后置--，先使用，再移动。

        指针的解引用，就得到了数据——然而对于封装的类，我们把它的行为定义为返回节点指针的数据。

        变量引用返回，得到这个变量本身——对于ListIterator类，我们返回数据T的引用；

        以及对==和 != 的重载，只需要比较节点指针内的数据是否一致即可。

 （2）const迭代器类的设计

        有普通的迭代器，就会有const迭代器，我们根据上面的分析，可以实现的普通迭代器如下：

template<typename T>
struct ListIterator
{
	typedef ListNode<T> Node;
	typedef ListIterator<T> Self;
	ListIterator(Node* node = nullptr)
		:_node(node)
	{}
	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	Self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}
	Self& operator++(int)
	{
		Self tem(*this);
		_node = _node->_next;
		return tem;
	}
	Self& operator--(int)
	{
		Self tem(*this);
		_node = _node->_prev;
		return *this;
	}
	T& operator*()
	{
		return _node->_data;
	}
	T* operator->()
	{
		return &(_node->_data);
	}
	bool operator==(const Self& ltt)
	{
		return _node == ltt._node;
	}
	bool operator!=(const Self& ltt)
	{
		return !(*this == ltt);
	}
	 Node* _node;
};

        如果第一次思考，你可能会想到直接在实例化的时候在普通迭代器前面加上const，但是这是错误的做法：如果直接在普通迭代器前面加上const，这就表明const修饰迭代器本身（类本身，也就是类对象本身不能修改：由于类内部只有一个节点的指针类型，所以这个指针本身不能修改，这是一个与事实相悖的结果：指针不能移动了！）

        想要解决上述问题，我们只有再定义一个类ConstListIterator，在类内部我们发现其实现与普通迭代器相比，只有两个不同的地方：

        这两个地方自然是涉及对象内数据的成员函数重载，他们是：

operator*()

operator->()

         如果我们执意要实现ConstListIterator类，可以实现如下：

template<typename T>
struct ListIterator
{
	typedef ListNode<T> Node;
	typedef ListIterator<T> Self;
	ListIterator(Node* node = nullptr)
		:_node(node)
	{}
	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	Self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}
	Self& operator++(int)
	{
		Self tem(*this);
		_node = _node->_next;
		return tem;
	}
	Self& operator--(int)
	{
		Self tem(*this);
		_node = _node->_prev;
		return *this;
	}
	const T& operator*()
	{
		return _node->_data;
	}
	const T* operator->()
	{
		return &(_node->_data);
	}
	bool operator==(const Self& ltt)
	{
		return _node == ltt._node;
	}
	bool operator!=(const Self& ltt)
	{
		return !(*this == ltt);
	}
	 Node* _node;
};

通过比较两个类，我们发现只有他们的返回值不同而已，这两个类的大部分代码都是重复的。那么有没有一种方法可以缩减代码量，减少我们的工作量呢？

        我们可以通过额外多传入两个参数Ptr，Ref来解决这个问题：

template<typename T,class Ref,class Ptr>
struct ListIterator
{
	typedef ListNode<T> Node;
	typedef ListIterator<T, Ref, Ptr> Self;
	ListIterator(Node* node = nullptr)
		:_node(node)
	{}
	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	Self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}
	Self& operator++(int)
	{
		Self tem(*this);
		_node = _node->_next;
		return tem;
	}
	Self& operator--(int)
	{
		Self tem(*this);
		_node = _node->_prev;
		return *this;
	}
	T& operator*()
	{
		return _node->_data;
	}
	Ref operator*() const
	{
		return _node->_data;
	}
	T* operator->()
	{
		return &(_node->_data);
	}
	Ptr operator->() const
	{
		return &(_node->_data);
	}
	bool operator==(const Self& ltt)
	{
		return _node == ltt._node;
	}
	bool operator!=(const Self& ltt)
	{
		return !(*this == ltt);
	}

	 Node* _node;
};

        由于const迭代器与普通迭代器的大部分行为都是类似的，只有上述两个重载函数的返回值不同，这意味着const迭代器的*和->的返回值不能修改，是一个常量，这于事实相符。

        所以我们的第一个模板参数相同。都是T，而第二与第三个模板参数则根据迭代器类型的不同而不同：如果实例化的对象是const迭代器，则传入的Ref接受的是const T&，Ptr接受的是const T* ，我们这样就通过一个类模板就可以实现ListIterator和ConstListIterator两种迭代器类型。

（3）list类的封装设计

        由于我们在设计迭代器类的时候，把整个类设置为了struct，可以公开访问，这意味着我们可以在list类中使用迭代器ListIterator，这是我们现前就考虑的。但是在STL中，整个容器的设计按照迭代器模式设计，将迭代器类统称为iterator，所以与STL保持一致，同时与我们的迭代器类相互嵌合，所以我们先typedef出迭代器和const迭代器；接下来对于list的实现，就是我们的老面孔了——实现双向带头循环链表，你可以参考我的这篇文章：《实现双向链表》——里面有非常详细的讲解。

        所以，在这里我们不再赘述实现双向链表的过程。

（4）反向迭代器类的设计

        反向迭代器与普通迭代器的实现基本一致，只是在++改为节点前移动；--改为节点后移动。

反向迭代器类实现如下：

template<typename T, class Ref, class Ptr>
struct ReverseListIterator
{
	typedef ListNode<T> Node;
	typedef ReverseListIterator<T, Ref, Ptr> Self;
	ReverseListIterator(Node* node = nullptr)
		:_node(node)
	{}
	Self& operator++()
	{
		_node = _node->_prev;
		return *this;
	}
	Self& operator--()
	{
		_node = _node->_next;
		return *this;
	}
	Self& operator++(int)
	{
		Self tem(*this);
		_node = _node->_prev;
		return tem;
	}
	Self& operator--(int)
	{
		Self tem(*this);
		_node = _node->_next;
		return *this;
	}
	T& operator*()
	{
		return _node->_data;
	}
	Ref operator*() const
	{
		return _node->_data;
	}
	T* operator->()
	{
		return &(_node->_data);
	}
	Ptr operator->() const
	{
		return &(_node->_data);
	}
	bool operator==(const Self& ltt)
	{
		return _node == ltt._node;
	}
	bool operator!=(const Self& ltt)
	{
		return !(*this == ltt);
	}

	Node* _node;
};

        需要注意的是，反向迭代器也有const类型，所以采用了和普通迭代器同样的处理方法：设置三个模板参数：<T，Ref，Ptr>

（三）实现list类

        源代码如下：

#pragma once
#include<iostream>
#include<cstdbool>
#include<cassert>
using namespace std;

namespace ddsm
{
	template<typename T>
	struct ListNode
	{
		ListNode<T>* _prev;
		ListNode<T>* _next;
		T _data;

		ListNode(const T& val = T())
			:_prev(nullptr)
			,_next(nullptr)
			,_data(val)
		{}
	};


	template<typename T,class Ref,class Ptr>
	struct ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T, Ref, Ptr> Self;
		ListIterator(Node* node = nullptr)
			:_node(node)
		{}
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		Self& operator++(int)
		{
			Self tem(*this);
			_node = _node->_next;
			return tem;
		}
		Self& operator--(int)
		{
			Self tem(*this);
			_node = _node->_prev;
			return *this;
		}
		T& operator*()
		{
			return _node->_data;
		}
		Ref operator*() const
		{
			return _node->_data;
		}
		T* operator->()
		{
			return &(_node->_data);
		}
		Ptr operator->() const
		{
			return &(_node->_data);
		}
		bool operator==(const Self& ltt)
		{
			return _node == ltt._node;
		}
		bool operator!=(const Self& ltt)
		{
			return !(*this == ltt);
		}

		 Node* _node;
	};
	template<typename T, class Ref, class Ptr>
	struct ReverseListIterator
	{
		typedef ListNode<T> Node;
		typedef ReverseListIterator<T, Ref, Ptr> Self;
		ReverseListIterator(Node* node = nullptr)
			:_node(node)
		{}
		Self& operator++()
		{
			_node = _node->_prev;
			return *this;
		}
		Self& operator--()
		{
			_node = _node->_next;
			return *this;
		}
		Self& operator++(int)
		{
			Self tem(*this);
			_node = _node->_prev;
			return tem;
		}
		Self& operator--(int)
		{
			Self tem(*this);
			_node = _node->_next;
			return *this;
		}
		T& operator*()
		{
			return _node->_data;
		}
		Ref operator*() const
		{
			return _node->_data;
		}
		T* operator->()
		{
			return &(_node->_data);
		}
		Ptr operator->() const
		{
			return &(_node->_data);
		}
		bool operator==(const Self& ltt)
		{
			return _node == ltt._node;
		}
		bool operator!=(const Self& ltt)
		{
			return !(*this == ltt);
		}

		Node* _node;
	};


	template<class T>
	class list
	{
		typedef ListNode<T> Node;
	public:
		typedef ListIterator<T, T&, T*> iterator;
		typedef ListIterator<T, const T&, const T*> const_iterator;
		typedef ReverseListIterator<T, T&, T*> reverse_iterator;
		typedef ReverseListIterator<T, const T&, const T*> const_reverse_iterator;
	public:
		//对于空链表的初始化（只创建一个头节点）
		void init_empty()
		{
			_pHead = new Node;
			_pHead->_next = _pHead;
			_pHead->_prev = _pHead;
		}
		//默认构造
		list()
		{
			init_empty();
		}
		// n 个值初始化
		list(int n, const T& value = T())
		{
			init_empty();
			for (size_t i = 0; i < n; i++)
			{
				push_back(value);
			}
		}
		//拷贝构造,深拷贝
		//list<int> l1(l2)
		list(const list<T>& lt)
		{
			init_empty();
			for (const auto& e : lt)
			{
				push_back(e);
			}
		}

		//赋值重载现代写法
		//复用拷贝构造
		void operator=(list<T> lt)
		{
			std::swap(_pHead,lt._pHead);
		}

		//初始化列表，初始化
		list(std::initializer_list<T> init)
		{
			init_empty();
			for (const auto& e : init)
			{
				push_back(e);
			}
		}


		void clear()
		{
			auto pos = begin();
			while (pos != end())
			{
				pos = erase(pos);//迭代器更新防止失效
			}
		}

		~list()
		{
			clear();
			delete _pHead;
			_pHead = nullptr;
		}
		/*void push_back(const T& value = T()) const
		{
			Node* newnode = new Node(value);

			newnode->_next = _pHead;
			newnode->_prev = _pHead->_prev;
			_pHead->_prev->_next = newnode;
			_pHead->_prev = newnode;
		}*/
		/*void push_back(const T& value)
		{
			Node* newnode = new Node(value);

			newnode->_next = _pHead;
			newnode->_prev = _pHead->_prev;
			_pHead->_prev->_next = newnode;
			_pHead->_prev = newnode;
		}*/

		reverse_iterator rbegin()
		{
			return reverse_iterator(_pHead->_prev);
		}
		const_reverse_iterator rbegin() const
		{
			return const_reverse_iterator(_pHead->_prev);
		}
		reverse_iterator rend()
		{
			return reverse_iterator(_pHead);
		}
		const_reverse_iterator rend() const
		{
			return const_reverse_iterator(_pHead);
		}
		iterator begin()
		{
			return iterator(_pHead->_next);
		}
		const_iterator begin() const
		{
			return const_iterator(_pHead->_next);
		}
		iterator end()
		{
			return iterator(_pHead);
		}
		const_iterator end() const
		{
			return const_iterator(_pHead);
		}
		//在指定位置之前插入
		iterator insert(iterator pos,const T& val = T())
		{
			Node* newnode = new Node(val);
			Node* cur = pos._node;
			Node* prev = cur->_prev;

			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;

			return iterator(newnode);
		}
		//删除指定位置的节点
		iterator erase(iterator pos)
		{
			assert(pos != end());

			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			prev->_next = next;
			next->_prev = prev;

			delete cur;

			return iterator(next);
		}
		void push_front(const T& value)
		{
			insert(begin(), value);
		}
		void push_back(const T& value)
		{
			insert(end(), value);
		}
		void pop_front()
		{
			erase(begin());
		}
		void pop_back()
		{
			erase(--end());
		}
		T& front()
		{
			return begin()._node->_data;
		}
		const T& front()const
		{
			return begin()._node->_data;
		}
		T& back()
		{
			return (--end())._node->_data;
		}
		const T& back()const
		{
			return (--end())._node->_data;
		}
		size_t size()const
		{
			int count = 0;
			for (const auto& e : *this)
			{
				count++;
			}
			return count;
		}
		bool empty()const
		{
			return size() == 0;
		}
	private:
		Node* _pHead;
	};

}

完~

未经作者同意禁止转载