list的模拟实现

2025-05-01 06:00:06 0 阅读

一.list的简单介绍

list是一个带头双向循环的链表，通过头结点分隔开首末尾。它和vector的使用方法类似，可以进行头插尾插，++/--等操作，区别在于list的结点在内存上不是连续的。list属于双向迭代器即可以++/--，不能想vector一样可以进行随机访问。

二.list模拟实现的三个类

1.结点类

根据list的特点带头双向循环，我们可以得知，他需要一个前置结点prev，以及后置结点next，保证能向前向后找到结点。每个结点存有数据data，我们可以用模板T来进行复用。
template 
	struct list_node
	{
		list_node(const T& x = T())//模板有x时情况
		:_next(nullptr)
		,_prev(nullptr)
		,_data(x)
		{}

		list_node* _next;
		list_node* _prev;
		T _data;
	};

2.迭代器类

我们知道迭代器分为普通迭代器和const迭代器，在实现string类和vector类时我们并没有单独对迭代器这一类进行实现，这是因为vector和string类在底层空间上是连续的，可以直接进行++/--，解引用操作。但list在底层中是由指针来连接的，所以直接++/--解引用无法实现我们想要的效果。所以我们要单独提出迭代器对++/--解引用进行重载运算符操作。
template
struct list_iterator
{
	typedef list_node Node;
	typedef list_iterator Self;
	Node* _node;

	list_iterator(Node* node)
		:_node(node)
	{}

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

	T& operator++()//前置
	{
		_node = _node->_next;
		return *this;
	}

	T& operator++(int)//后置,后置++区分前置要加入括号
	{
		Self tmp(*this);
		_node = _node->_next;
		return tmp;
	}

	T& operator--()//前置
	{
		_node = _node->_prev;
		return *this;
	}

	T& operator--(int)//前置
	{
		Self tmp(*this);
		_node = _node->_prev;
		return tmp;
	}

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

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

	bool operator==(const T& it)
	{
		return _node == _it._node;
	}
};
如上我们对迭代器进行了初步的实现，里面的实现内容较为简单就不一一展开叙述。这时候又有了另一个问题，如果迭代器是const类型的该怎么办呢？还是像上面这样，重新封装一个const_iterator类吗？

这样操作固然是没有问题的，但是还不够简略。

我们可以仔细想想，普通迭代器与const迭代器的区别不就是多了一个const吗？所以我们可以考虑用模板来套用实现。
	template//提供模板参数，为const类型提供模板参数,ref代替引用，ptr代替*，复用
	struct list_iterator
	{
		typedef list_node Node;
		typedef list_iterator Self;
		Node* _node;

		list_iterator(Node* node)
		:_node(node)
		{}

		Ref 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;
		}

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

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

		bool operator==(const Self& it)
		{
			return _node == _it._node;
		}
	};
我们将原先的T& 用模板Ref来替代，T* 用模板Ptr来代替。这样就对代码进行了缩减。所以用ref和ptr模板我们就不需要关心是不是const类型迭代器，只要传就是什么，我们就无需关心。

3.链表类

template 
	class list
	{
		typedef list_node Node;
	public:
		typedef list_iterator iterator;
		typedef list_iterator const_iterator;

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

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

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

		list()
		{
			empty_init();
		}

		list(initializer_list it)
		{
			for (auto& e : it)
			{
				push_back(e);
			}
		}

		list(const list& it)
		{
			empty_init();
			for (auto& e : it)
			{
				push_back(e);
			}
		}

		~list()
		{
			clear();
		}

		void swap(list& it)
		{
			std::swap(_head, it._head);
		}

		list& operator=(list it)
		{
			swap(it);
			return *this;
		}

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

		void push_back(const T& x)
		{
			Node* newnode = new Node(x);

			Node* tail = _head->_prev;
			newnode->_prev = tail;
			tail->_next = newnode;
			newnode->_next = _head;
			_head->_prev = newnode;
		}

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

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

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

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

		void 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;
			cur->_prev = newnode;
			newnode->_next = cur;
		}

		iterator erase(iterator pos)
		{
			assert(pos != end());
			Node* cur = pos._node;
			Node* nextNode = cur->_next;
			Node* prevNode = cur->_prev;

			prevNode->_next = nextNode;
			nextNode->_prev = prevNode;

			delete cur;
			return iterator(nextNode);
		}

	private:
		Node* _head;
	};
}

上述只需要注意一点，就是erase的用法。erase在官方库中是有返回值的，在使用时，例如析构时需要用变量来接收erase的返回值，否则容易导致迭代器失效。

链表部分的实现不难，基本都是先前vector类实现的功能相差无几，构造函数，拷贝函数，析构函数，迭代器的运用，以及增删等操作。

三.总结

本篇文章最关键的内容就是对于模板的复用，在面对代码相似度较高，实现功能类似的情况下，我们需要优先考虑模板的复用。

下面放上完整代码：

#pragma once
#include 
using namespace std;

namespace wu
{
	template 
	struct list_node
	{
		list_node(const T& x = T())//模板有x时情况
		:_next(nullptr)
		,_prev(nullptr)
		,_data(x)
		{}

		list_node* _next;
		list_node* _prev;
		T _data;
	};

	template//提供模板参数，为const类型提供模板参数,ref代替引用，ptr代替*，复用
	struct list_iterator
	{
		typedef list_node Node;
		typedef list_iterator Self;
		Node* _node;

		list_iterator(Node* node)
		:_node(node)
		{}

		Ref 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;
		}

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

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

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

	template 
	class list
	{
		typedef list_node Node;
	public:
		typedef list_iterator iterator;
		typedef list_iterator const_iterator;

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

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

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

		list()
		{
			empty_init();
		}

		list(initializer_list it)
		{
			for (auto& e : it)
			{
				push_back(e);
			}
		}

		list(const list& it)
		{
			empty_init();
			for (auto& e : it)
			{
				push_back(e);
			}
		}

		~list()
		{
			clear();
		}

		void swap(list& it)
		{
			std::swap(_head, it._head);
		}

		list& operator=(list it)
		{
			swap(it);
			return *this;
		}

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

		void push_back(const T& x)
		{
			Node* newnode = new Node(x);

			Node* tail = _head->_prev;
			newnode->_prev = tail;
			tail->_next = newnode;
			newnode->_next = _head;
			_head->_prev = newnode;
		}

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

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

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

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

		void 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;
			cur->_prev = newnode;
			newnode->_next = cur;
		}

		iterator erase(iterator pos)
		{
			assert(pos != end());
			Node* cur = pos._node;
			Node* nextNode = cur->_next;
			Node* prevNode = cur->_prev;

			prevNode->_next = nextNode;
			nextNode->_prev = prevNode;

			delete cur;
			return iterator(nextNode);
		}

	private:
		Node* _head;
	};
}