【C++】list的模拟实现

  • 开发
  • 23

目录

前言：

list是带头双向循环链表，与vector的底层结构不一样，vector是连续的空间，list的每个节点是独立的空间。

模拟实现list主要有以下类：

struct ListNode//节点类
struct ListIterator//正向迭代器类
struct ReverseIterator//反向迭代器类
class list//模拟实现list类

1 节点类

每个节点都有它的指针域和数据域，因为是双向的，所以指针域有两个分别为前指针和后指针。同时写个构造函数，用来创建新节点。

template<class T>
struct ListNode//节点类
{
   
	ListNode<T>* _prev;
	ListNode<T>* _next;
	T _val;

	ListNode(const T& x = T())
		:_prev(nullptr)
		,_next(nullptr)
		,_val(x)
	{
   }
};

使用类模板可以传任意类型。

2 模拟实现list类

2.1 成员变量

私有成员变量是链表的头，即哨兵位节点，类型是节点类指针类型，方便连接其他节点。

节点类的名字有点长，可以重命名简化：

typedef ListNode<T> Node;

成员变量：

private:
	Node* _head;

2.2 初始化

初始化是对哨兵位的初始化，即让哨兵位成为一个节点，这个节点不放数据，只是用来连接。它的前指针和后指针都是指向自己。

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

2.3 构造

1️⃣无参构造
复用初始化即可。

list()
{
   
	Init();
}

2️⃣有参构造1
先对哨兵位节点初始化，然后n为多少尾插多少元素

//有参构造1
list(int n, const T& x = T())
{
   
	Init();
	while (n--)
	{
   
		push_back(x);
	}
}

3️⃣有参构造2

该函数的参数只要是迭代器就行，先初始化哨兵位，然后逐个尾插迭代器指向的内容。

template <class Iterator>
list(Iterator first, Iterator last)
{
   
	Init();
	while (first != last)
	{
   
		push_back(*first);
		++first;
	}
}

2.4 拷贝构造

先初始化哨兵位，然后从被拷贝的链表里逐个节点尾插到新链表里。

//拷贝构造
list(const list<T>& lt)
{
   
	Init();
	for (const auto& e : lt)
	{
   
		push_back(e);
	}
}

2.5 赋值重载

1️⃣写法1
判断被赋值的对象与要赋值的对象是否地址相同，相同直接返回当前对象，不相同先清理链表的元素，然后用范围for逐个尾插。

//写法1
list<T>& operator=(const list<T>& lt)
{
   
	if (this != &lt)
	{
   
		clear();
		for (const auto& e : lt)
		{
   
			push_back(e);
		}
	}
	return *this;
}

1️⃣写法2
这个不多说了，还是复用交换函数，然后返回this指针。

//写法2
list<T>& operator=(list<T> lt)
{
   
	swap(lt);
	return *this;
}

2.6 析构

先清理链表里的所有元素，除了哨兵位节点，然后释放哨兵位节点，置空。

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

2.7 交换、清理、返回元素个数、判空

//交换
void swap(const list<T>& lt)
{
   
	std::swap(_head, lt._head);
}
//清理
void clear()
{
   
	iterator it = begin();
	while (it != end())
	{
   
		it = erase(it);
	}
}
//获取元素个数
size_t size() const
{
   
	Node* cur = _head->_next;
	size_t count = 0;
	while (cur != _head)
	{
   
		count++;
		cur = cur->_next;
	}
	return count;
}
//判空
bool empty() const
{
   
	return _head->_next == _head;
}

2.8 获取第一个节点数据和最后一个节点数据

//获取第一个节点数据
T& front()
{
   
	return _head->_next->_val;
}
const T& front()const
{
   
	return _head->_next->_val;
}
//获取最后一个节点数据
T& back()
{
   
	return _head->_prev->_val;
}
const T& back()const
{
   
	return _head->_prev->_val;
}

2.9 pos位置插入

//pos位置插入
iterator insert(iterator pos, const T& x)
{
   
	Node* newnode = new Node(x);//创建新节点
	Node* cur = pos._node;//得到pos位置的节点
	Node* Prev = cur->_prev;//pos位置前一个节点
	newnode->_prev = Prev;//Prev<=>newnode
	Prev->_next = newnode;
	newnode->_next = cur;//newnode<=>cur
	cur->_prev = newnode;
	return newnode;//返回
}

在这里插入图片描述

2.10 pos位置删除

//pos位置删除
iterator erase(iterator pos)
{
   
	assert(pos != _head);//pos不能是哨兵位节点
	Node* cur = pos._node; // 得到pos位置的节点
	Node* Prev = cur->_prev;//pos位置前一个节点
	Node* Next = cur->_next;//pos位置后一个节点
	Prev->_next = Next;//Prev<=>Next
	Next->_prev = Prev;
	delete cur;//清理cur
	return Next;//返回
}

在这里插入图片描述

2.11 尾插、尾删、头插、头删

复用begin 和 end

//尾插
void push_back(const T& x)
{
   
	insert(end(), x);
}
//头插
void push_front(const T& x)
{
   
	insert(begin(), x);
}
//尾删
void pop_back()
{
   
	erase(--end());
}
//头删
void pop_front()
{
   
	erase(begin());
}

2.12 迭代器遍历

分为两种：

  • 正向——begin+end
  • 反向——rbegin+rend

begin返回第一个节点的位置，end返回最后一个节点的下一个位置

//正向迭代器遍历
iterator begin()
{
   
	return _head->_next;
}
iterator end()
{
   
	return _head;
}
const_iterator begin() const
{
   
	return _head->_next;
}
const_iterator end() const
{
   
	return _head;
}

rbegin返回最后一个节点的下一个位置，rend返回第一个节点的位置

//反向迭代器遍历
reverse_iterator rbegin()
{
   
	return end();
}
reverse_iterator rend()
{
   
	return begin();
}
const_reverse_iterator rbegin() const
{
   
	return end();
}
const_reverse_iterator rend() const
{
   
	return begin();
}

3 正向迭代器类

迭代器类是对迭代器的行为另作处理。在vector里，iterator++就是正常的++，因为空间是连续的。但是list不是，如果还是像前面的++一样就不会指向下一个节点，因为list的每个节点是独立的空间，不连续，所以要对迭代器的++、–等操作符作封装，重新定义它们的行为。

	template<class T, class Ref, class Ptr>
	struct ListIterator//正向迭代器类
	{
   
		typedef ListNode<T> Node;
		typedef ListIterator<T, Ref, Ptr> self;
		Node* _node;
		//构造
		ListIterator(Node* x)
			:_node(x)
		{
   }
		//前置++
		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;//返回临时对象，不能引用
		}
		// *
		Ref operator*()
		{
   
			return _node->_val;//返回该节点的数据
		}
		// ->
		Ptr operator->()
		{
   
			return &_node->_val;//返回该节点的数据的成员(数据是自定义类型)
		}
		//判断不相等
		bool operator!=(const self& lt)
		{
   
			return _node != lt._node;
		}
		//判断相等
		bool operator==(const self& lt)
		{
   
			return _node == lt._node;
		}
	};

这里的Ref、Ptr是模板参数，这样写更方便，不管传过来的是const类型还是非const类型，都可以在一段代码里处理好，减少了代码冗余。

在list类里重命名：

typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;

4 反向迭代器类

反向迭代器类其实是对正向迭代器作了一层封装，它的第一个模板参数是iterator，后面两个与正向迭代器相同，作用在rbegin和rend函数上。

下面的图可以知道正、反向迭代器在链表里的位置：
在这里插入图片描述
可以看出，它们是对称的。但由于是这样的结构，所以反向迭代器的++、- - 以及解引用操作就会有些不一样。

	template<class Iterator, class Ref, class Ptr>
	struct ReverseIterator//反向迭代器类
	{
   
		typedef ReverseIterator<Iterator, Ref, Ptr> self;	
		
		Iterator cur;
		ReverseIterator(Iterator x)
			:cur(x)
		{
   }
		//前置++
		self& operator++()
		{
   
			--cur;//++就是--
			return *this;
		}
		//后置++
		self operator++(int)
		{
   
			Iterator tmp = cur;
			--cur;
			return tmp;
		}
		//前置--
		self& operator--()
		{
   
			++cur;//--就是++
			return *this;
		}
		//后置--
		self operator--(int)
		{
   
			Iterator tmp = cur;
			++cur;
			return tmp;
		}
		// *  解引用前一个位置的元素
		Ref operator*()
		{
   
			Iterator tmp = cur;
			--tmp;
			return *tmp;
		}
		// ->
		Ptr operator->()
		{
   
			return &(operator*());//复用
		}
		//判断不相等
		bool operator!=(const self& it)
		{
   
			return cur != it.cur;
		}
		//判断相等
		bool operator==(const self& it)
		{
   
			return cur == it.cur;
		}
	};

在list类里重命名：

typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<iterator, const T&, const T*> const_reverse_iterator;

5 全部代码

list.h

#include <iostream>
#include <assert.h>
using namespace std;

namespace yss
{
   
	template<class T>
	struct ListNode//节点类
	{
   
		ListNode<T>* _prev;
		ListNode<T>* _next;
		T _val;

		ListNode(const T& x = T())
			:_prev(nullptr)
			,_next(nullptr)
			,_val(x)
		{
   }
	};

	template<class T, class Ref, class Ptr>
	struct ListIterator//正向迭代器类
	{
   
		typedef ListNode<T> Node;
		typedef ListIterator<T, Ref, Ptr> self;
		Node* _node;
		//构造
		ListIterator(Node* x)
			:_node(x)
		{
   }

		//前置++
		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;
		}

		// *
		Ref operator*()
		{
   
			return _node->_val;
		}
		// ->
		Ptr operator->()
		{
   
			return &_node->_val;
		}

		//判断不相等
		bool operator!=(const self& lt)
		{
   
			return _node != lt._node;
		}
		//判断相等
		bool operator==(const self& lt)
		{
   
			return _node == lt._node;
		}

	};

	template<class Iterator, class Ref, class Ptr>
	struct ReverseIterator//反向迭代器类
	{
   
		typedef ReverseIterator<Iterator, Ref, Ptr> self;	
		
		Iterator cur;
		ReverseIterator(Iterator x)
			:cur(x)
		{
   }

		//前置++
		self& operator++()
		{
   
			--cur;
			return *this;
		}
		//后置++
		self operator++(int)
		{
   
			Iterator tmp = cur;
			--cur;
			return tmp;
		}
		//前置--
		self& operator--()
		{
   
			++cur;
			return *this;
		}
		//后置--
		self operator--(int)
		{
   
			Iterator tmp = cur;
			++cur;
			return tmp;
		}
		// *  解引用前一个位置的元素
		Ref operator*()
		{
   
			Iterator tmp = cur;
			--tmp;
			return *tmp;
		}
		// ->
		Ptr operator->()
		{
   
			return &(operator*());
		}
		//判断不相等
		bool operator!=(const self& it)
		{
   
			return cur != it.cur;
		}
		//判断相等
		bool operator==(const self& it)
		{
   
			return cur == it.cur;
		}
	};

	template<class T>
	class list//模拟实现list
	{
   
	public:
		typedef ListNode<T> Node;

		typedef ListIterator<T, T&, T*> iterator;
		typedef ListIterator<T, const T&, const T*> const_iterator;

		typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
		typedef ReverseIterator<iterator, const T&, const T*> const_reverse_iterator;

		//正向迭代器遍历
		iterator begin()
		{
   
			return _head->_next;
		}
		iterator end()
		{
   
			return _head;
		}
		const_iterator begin() const
		{
   
			return _head->_next;
		}
		const_iterator end() const
		{
   
			return _head;
		}

		//反向迭代器遍历
		reverse_iterator rbegin()
		{
   
			return end();
		}
		reverse_iterator rend()
		{
   
			return begin();
		}
		const_reverse_iterator rbegin() const
		{
   
			return end();
		}
		const_reverse_iterator rend() const
		{
   
			return begin();
		}

		// 初始化
		void Init()
		{
   
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}
		//无参构造
		list()
		{
   
			Init();
		}
		//有参构造1
		list(int n, const T& x = T())
		{
   
			Init();
			while (n--)
			{
   
				push_back(x);
			}
		}
		//有参构造2
		template <class Iterator>
		list(Iterator first, Iterator last)
		{
   
			Init();
			while (first != last)
			{
   
				push_back(*first);
				++first;
			}
		}

		//交换
		void swap(const list<T>& lt)
		{
   
			std::swap(_head, lt._head);
		}

		//拷贝构造
		list(const list<T>& lt)
		{
   
			Init();
			for (const auto& e : lt)
			{
   
				push_back(e);
			}
		}

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

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

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

		//获取元素个数
		size_t size() const
		{
   
			Node* cur = _head->_next;
			size_t count = 0;
			while (cur != _head)
			{
   
				count++;
				cur = cur->_next;
			}
			return count;
		}

		//判空
		bool empty() const
		{
   
			return _head->_next == _head;
		}

		//获取第一个节点数据
		T& front()
		{
   
			return _head->_next->_val;
		}
		const T& front()const
		{
   
			return _head->_next->_val;
		}
		//获取最后一个节点数据
		T& back()
		{
   
			return _head->_prev->_val;
		}
		const T& back()const
		{
   
			return _head->_prev->_val;
		}

		//尾插
		void push_back(const T& x)
		{
   
			insert(end(), x);
		}
		//头插
		void push_front(const T& x)
		{
   
			insert(begin(), x);
		}
		//尾删
		void pop_back()
		{
   
			erase(--end());
		}
		//头删
		void pop_front()
		{
   
			erase(begin());
		}

		//pos位置插入
		iterator insert(iterator pos, const T& x)
		{
   
			Node* newnode = new Node(x);//创建新节点
			Node* cur = pos._node;//得到pos位置的节点
			Node* Prev = cur->_prev;//pos位置前一个节点
			newnode->_prev = Prev;//Prev<=>newnode
			Prev->_next = newnode;
			newnode->_next = cur;//newnode<=>cur
			cur->_prev = newnode;
			return newnode;//返回
		}
		//pos位置删除
		iterator erase(iterator pos)
		{
   
			assert(pos != _head);//pos不能是哨兵位节点
			Node* cur = pos._node; // 得到pos位置的节点
			Node* Prev = cur->_prev;//pos位置前一个节点
			Node* Next = cur->_next;//pos位置后一个节点
			Prev->_next = Next;//Prev<=>Next
			Next->_prev = Prev;
			delete cur;//清理cur
			return Next;//返回
		}

	private:
		Node* _head;
	};
}

test.cpp

#include "list.h"
int main()
{
   
	/*yss::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_front(100);
	lt.push_front(200);
	lt.push_front(300);
	lt.pop_back();
	lt.pop_front();
	lt.pop_front();
	auto it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;*/

	yss::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	yss::list<int>::reverse_iterator it = lt.rbegin();
	while (it != lt.rend())
	{
   
		cout << *it << " ";
		++it;
	}
	cout << endl;

	return 0;
}
阅读全部

相关推荐

  1. MFC CList＜CRect, CRect&＞ m_listRect；的用法

    2024-01-29 10:36:03       9 阅读

  9. string的模拟实现

    2024-01-29 10:36:03       11 阅读

最近更新

  4. TCP协议是安全的吗?

    2024-01-29 10:36:03       16 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2024-01-29 10:36:03       16 阅读

  13. 【Python教程】压缩PDF文件大小

    2024-01-29 10:36:03       15 阅读

  18. 通过文章id递归查询所有评论（xml）

    2024-01-29 10:36:03       18 阅读

热门阅读

  2. Qlik Sense : IntervalMatch(离散匹配)

    2024-01-29 10:36:03       29 阅读

  6. Leetcode 3021. Alice and Bob Playing Flower Game

    2024-01-29 10:36:03       36 阅读

  8. 记录 | ubuntu查看系统信息如系统版本、cpu信息

    2024-01-29 10:36:03       33 阅读

  9. ubuntu 添加 sudo 权限

    2024-01-29 10:36:03       31 阅读

  12. Matlab自学笔记二十六：sprintf函数用法简介

    2024-01-29 10:36:03       38 阅读

  21. 向爬虫而生---Redis 拓宽篇6＜redis分布式锁 ---ZooKeeper＞

    2024-01-29 10:36:03       28 阅读

  23. Transformer模型 | Pytorch实现Transformer模型进行时间序列预测

    2024-01-29 10:36:03       38 阅读

  25. pytorch交换数组元素坑

    2024-01-29 10:36:03       38 阅读

  28. “语法糖“

    2024-01-29 10:36:03       29 阅读