C++ list模拟实现

一.前置说明

对于list而言,最难的点是它如何进行设计与封装的
尤其是list的迭代器
而不是链表的基础操作

只要实现好迭代器之后,list就非常好实现了

1.前言

首先我们要说明的是:
1.list就是数据结构当中的带头双向循环链表
2.list的迭代器不是简简单单的原生指针,而是在原生指针的基础上进行了一层封装
3.关于链表的操作我们就不再赘述了,因为带头双向循环链表的知识并不难,而且大家应该都是掌握了的

2.list是如何封装的?

1.STL库中的实现

下面我们依次看一下成员变量,构造函数和迭代器

1.成员变量

2.构造函数

3.迭代器

因此我们要实现的这三个类的介绍如下:

2.节点类

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

	list_node(const T& x = T())
		:_data(x)
		, _next(nullptr)
		, _prev(nullptr)
	{}
};

3.迭代器类

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

	Node* _node;
	__listIterator(Node* node)
		:_node(node)
	{}

	__listIterator(const iterator& it)
		:_node(it._node)
	{}

	self& operator++();

	self& operator--();

	self operator++(int);

	Ref operator*();

	Ptr operator->();

	//注意:一定是判断节点指针是否相等,不是迭代器是否相等!!!!
	bool operator!=(const self& s);

	bool operator==(const self& s);
};

这里把节点类和迭代器类都用struct来定义
是因为这两个类我们一般都是开放使用的
而struct的默认访问限定符是public 外部可以访问

4.list类

template<class T>
class list
{
	typedef list_node<T> Node;
public:
	typedef __list_iterator<T> iterator;
	typedef __list_iterator<T, const T&, const T*> const_iterator;
	
	iterator begin();

	iterator end();

	const_iterator begin() const;

	const_iterator end() const;

	list()
	{
		empty_init();
	}
	
	void empty_init()
	{
		_head = new Node;
		_head->_next = _head;
		_head->_prev = _head;
		_size = 0;
	}
	//其他一堆成员函数
	
private:
	Node* _head;
	size_t _size;//记录数据个数
};

3.const迭代器的说明

我们先基于非const迭代器实现完整个list之后
最后在加上const迭代器的版本形成最终的大致框架

4.最终的大致框架:

namespace wzs
{
	template<class T>
	struct list_node
	{
		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;

		list_node(const T& x = T());
	};

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

		Node* _node;
		__listIterator(Node* node)
			:_node(node)
		{}

		__listIterator(const iterator& it)
			:_node(it._node)
		{}

		self& operator++();

		self& operator--();

		self operator++(int);

		self operator--(int);

		Ref operator*();

		Ptr operator->();

		//注意:一定是判断节点指针是否相等,不是迭代器是否相等!!!!
		bool operator!=(const self& s);

		bool operator==(const self& s);
	};

	template<class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;
		iterator begin();

		iterator end();

		const_iterator begin() const;

		const_iterator end() const;

		void empty_init();

		list();

		list(const list<T>& lt);

		void swap(list<T>& lt);

		//现代写法
		list<int>& operator=(list<int> lt);
		
		~list();

		//复用erase
		void clear();

		//复用insert
		void push_back(const T& x);

		void push_front(const T& x);

		void pop_front();

		void pop_back();

		//list的insert没有迭代器失效的问题
		iterator insert(iterator pos, const T& x);

		//list的erase有迭代器失效的问题
		iterator erase(iterator pos);

		size_t size() const;

		bool empty() const;

	private:
		Node* _head;
		size_t _size;
	};
}

5.初步版本(不包含const迭代器的版本)

namespace wzs
{
	template<class T>
	struct list_node
	{
		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;

		list_node(const T& x = T());
	};

	template<class T>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T> self;
		Node* _node;

		__list_iterator(Node* node);

		self& operator++();

		self& operator--();

		self operator++(int);

		self operator--(int);

		Ref operator*();

		Ptr operator->();

		//注意:一定是判断节点指针是否相等,不是迭代器是否相等!!!!
		bool operator!=(const self& s);

		bool operator==(const self& s);
	};

	template<class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		typedef __list_iterator<T> iterator;
		iterator begin();

		iterator end();

		void empty_init();

		list();

		list(list<T>& lt);

		void swap(list<T>& lt);

		//现代写法
		list<int>& operator=(list<int> lt);
		
		~list();

		//复用erase
		void clear();

		//复用insert
		void push_back(const T& x);

		void push_front(const T& x);

		void pop_front();

		void pop_back();

		//list的insert没有迭代器失效的问题
		iterator insert(iterator pos, const T& x);

		//list的erase有迭代器失效的问题
		iterator erase(iterator pos);

		size_t size() const;

		bool empty() const;

	private:
		Node* _head;
		size_t _size;
	};
}

二.迭代器类的实现

1.iterator的成员变量和构造函数

typedef list_node<T> Node;
typedef __list_iterator<T> self;
Node* _node;

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

注意这两个typedef
一个是把list_node<T>给命名为Node
一个是把迭代器自身__list_iterator<T>命名为self
增强代码的可读性

这里的构造函数的作用就是能够通过节点指针直接转换为迭代器

2.前置后置++ –

迭代器++就是指向下一个元素
迭代器–就是指向前一个元素
在链表这里
假设有这么一个节点:Node* cur
指向下一个元素就是
cur=cur->_next
指向前一个元素就是
cur=cur->_prev

因此我们可以写出这样的代码
self就是这个迭代器本身的类型

//前置++
self& operator++()
{
	_node = _node->_next;
	return *this;
}
//前置--
self& operator--()
{
	_node = _node->_prev;
	return *this;
}
//后置++
self operator++(int)
{
	//拷贝构造一个tmp
	self tmp(*this);
	_node = _node->_next;
	return tmp;
}
//后置--
self operator--(int)
{
	//拷贝构造一个tmp
	self tmp(*this);
	_node = _node->_prev;
	return tmp;
}

3.解引用* ->

迭代器解引用就是取出迭代器指向的数据
因此对于链表而言
假设有这么一个节点:Node* cur
*就是 cur->data,类型为T&
->就是&cur->data,类型为T*
因此我们写出这样的代码

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

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

4.== !=

注意:我们一定是判断节点指针是否相等,而不是判断迭代器是否相等!

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

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

list的iterator体现了一个非常重要面向对象的设计思想:

封装:屏蔽了底层差异和实现细节,提供了统一的访问修改遍历方式

也正是因为这层封装,list的迭代器在使用的时候才能够让我们无需关心底层的具体实现细节而能够快速上手和使用

list的非const迭代器就是这些内容

三.list类的实现

1.构造函数

typedef list_node<T> Node;
void empty_init()
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
	_size = 0;
}
list()
{
	empty_init();
}

头节点一开始就是要存在的
头节点的前驱是自己,后继也是自己

2.begin end

begin是指向第一个有效数据的迭代器
end是指向最后一个有效数据的下一个位置的迭代器
又因为list是带头双向循环链表,头节点_head是不存储有效数据的

因此第一个有效数据的节点是_head->_next
最后一个有效数据的节点是_head->_prev
最后一个有效数据的下一个节点就是_head

typedef __list_iterator<T> iterator;
iterator begin()
{
	return iterator(_head->_next);
}

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

list类中把__list_iterator<T>typedef成了iterator
这里调用了iterator这个类的构造函数

3.insert

list的insert没有迭代器失效的问题
因为list没有扩容这一概念,节点都是一个一个按需申请的

//在pos位置前面插入x
iterator insert(iterator pos, const T& x)
{
	//new一个新节点
	Node* newnode = new Node(x);

	//利用迭代器取出其中的节点
	Node* cur = pos._node;
	//记录当前节点的前驱
	Node* prev = cur->_prev;

	//插入新节点
	newnode->_next = cur;
	cur->_prev = newnode;
	newnode->_prev = prev;
	prev->_next = newnode;
	
	//有效数据个数+1
	++_size;
	//返回新节点的迭代器
	return iterator(newnode);
}

到此我们就可以插入数据并且遍历访问修改数据了

4.erase

//list的erase有迭代器失效的问题
//因此要返回被删除位置的下一个位置的迭代器
iterator erase(iterator pos)
{
	//利用迭代器取出当前节点
	Node* cur = pos._node;
	//找到当前节点的前驱和后继
	Node* prev = cur->_prev;
	Node* next = cur->_next;
	//在链表中删除当前节点
	prev->_next = next;
	next->_prev = prev;
	//释放当前节点
	delete cur;
	cur = nullptr;
	//有效数据个数-1
	--_size;
	//返回被删除位置的下一个位置的迭代器
	//也就是后继指针的迭代器
	return iterator(next);
}

5.头插头删,尾插尾删的复用

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

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

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

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

6.clear和析构函数

1.clear

clear:清空所有有效数据,恢复到原始状态(无参构造后的状态)
超级传统的版本

void clear()
{
	if (!empty())
	{
		//释放所有有效数据的节点
		Node* cur = _head->_next;
		while (cur != _head)
		{
			Node* next = cur->_next;
			delete cur;
			cur = next;
		}
		//恢复成原始状态
		_head->_next = _head;
		_head->_prev = _head;
		_size = 0;
	}
}

复用erase的版本

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

2.析构函数

有了clear之后,析构函数就能复用clear了

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

注意:我们new节点的时候是直接new的
不是这样new []的
因此delete的时候要直接delete
而不要这样delete[]
否则会出现错误的,而且不容易看出来

7.swap和其他小函数

1.swap

因为list的成员变量只有Node*和size,而且他们都是内置类型(指针类型和int类型)
因此交换这两个成员变量即可

void swap(list<T>& lt)
{
	std::swap(_head, lt._head);
	std::swap(_size, lt._size);
}

2.empty

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

只有头节点自己的时候就是空链表

3.size

记录链表当中有效数据的个数

size_t size() const
{
	return _size;
}

8.拷贝构造函数

对于拷贝构造函数
参数类型应该是const list<T>& lt的
但是因为我们还没有实现const迭代器,所以这里先用一下非const的引用作为参数

list(list<T>& lt)
{
	//先初始化list
	empty_init();
	//然后逐个取出lt中的数据尾插到list当中即可
	typename list<T>::iterator it = lt.begin();
	while (it != lt.end())
	{
		push_back(*it);
		++it;
	}
}

9.赋值运算符重载

这里我们直接写现代写法了

list<int>& operator=(list<int> lt)
{
	swap(lt);
	return *this;
}

四.const迭代器加入后的改动

想要加入const迭代器
首先想到的就是再写一个const_iterator类
首先我们要明白:const迭代器中const修饰的是迭代器指向的内容不能被修改
而通过迭代器修改数据的方式就是解引用
因此只需要修改一下解引用的地方即可

对于非const迭代器来说
*返回的是T&
->返回的是T*

因此对于const迭代器来说
*返回的是const T&
->返回的是const T*

同时不要忘了改一下名字
把iterator改为const_iterator
并且在list类当中实现const修饰后的begin和end

1.原版

其他的地方都跟非const迭代器一样

template<class T>
struct __list_const_iterator
{
	typedef list_node<T> Node;
	typedef __list_const_iterator<T> self;
	Node* _node;

	__list_const_iterator(Node* node)
		:_node(node)
	{}
	//T& 改为了 const T&
	const T& operator*()
	{
		return _node->_data;
	}
	//修改的地方:
	//T* 改为了 const T*
	const T* operator->()
	{
		return &_node->_data;
	}
};

template<class T>
class list
{
	typedef list_node<T> Node;
public:
	typedef __list_iterator<T> iterator;
	//加上const_iterator
	typedef __list_const_iterator<T> const_iterator;

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

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

	//实现const修饰后的begin和end
	const_iterator begin() const
	{
		return const_iterator(_head->_next);
	}

	const_iterator end() const
	{
		return const_iterator(_head);
	}
	其他的成员函数,成员变量等等都不用修改....

不过这样的话代码就有些冗余了
有没有更好的方法呢?
设计STL的大佬就出了这么一个主意

2.精简版

既然你const迭代器和非const迭代器只有两个地方不同
那么我就直接把那两个地方也放到类模板当中
这样不就能把你们两个合并成一个类了吗?

Ref:reference:引用的英文
Ptr:pointer:指针的英文

template<class T,class Ref,class Ptr>
struct __list_iterator
{
	typedef list_node<T> Node;
	typedef __list_iterator<T, Ref, Ptr> self;
	typedef __listIterator<T, T&, T*> iterator;
	Node* _node;

	__list_iterator(Node* node)
		:_node(node)
	{}
	
	//const_iterator和iterator的转化
	//支持用iterator构造const_iterator
	__listIterator(const iterator& it)
		:_node(it._node)
	{}
	
	//这里修改成了Ref
	Ref operator*()
	{
		return _node->_data;
	}
	//这里修改成了Ptr
	Ptr operator->()
	{
		return &_node->_data;
	}
};

对于list类的修改

template<class T>
class list
{
	typedef list_node<T> Node;
public:
	//把实例化的操作放在list类当中完成
	typedef __list_iterator<T, T&, T*> iterator;

	typedef __list_iterator<T,const T&,const T*> const_iterator;

	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);
	}
	其他的成员函数,成员变量等等都不用修改....
};

此时const迭代器实现完毕了
拷贝构造就可以改回来了

list(const list<T>& lt)
{
	empty_init();
	list<T>::const_iterator it = lt.begin();
	while (it != lt.end())
	{
		push_back(*it);
		++it;
	}
}

五.完整代码

#pragma once
#include <iostream>
using namespace std;
#include <string>
#include <vector>
namespace wzs
{
	template<class T>
	struct list_node
	{
		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;

		list_node(const T& x = T())
			:_data(x)
			, _next(nullptr)
			, _prev(nullptr)
		{}
	};

	template<class T,class Ref,class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self;
		typedef __listIterator<T, T&, T*> iterator;
		Node* _node;
	
		__list_iterator(Node* node)
			:_node(node)
		{}
		
		//const_iterator和iterator的转化
		//支持用iterator构造const_iterator
		__listIterator(const iterator& it)
			:_node(it._node)
		{}

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

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

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

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

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

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

		//注意:一定是判断节点指针是否相等,不是迭代器是否相等!!!!
		bool operator!=(const self& s)
		{
			return _node != s._node;
		}

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

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

		typedef __list_iterator<T,const T&,const T*> const_iterator;

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

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

		list()
		{
			empty_init();
		}

		//const迭代器搞完之后:修改为
		//list(const list<T>& lt);

		list(const list<T>& lt)
		{
			empty_init();
			list<T>::const_iterator it = lt.begin();
			while (it != lt.end())
			{
				push_back(*it);
				++it;
			}
		}

		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}

		//现代写法
		list<int>& operator=(list<int> lt)
		{
			swap(lt);
			return *this;
		}

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

		//超级传统版本
		
		//void clear()
		//{
		//	if (!empty())
		//	{
		//		//释放所有有效数据的节点
		//		Node* cur = _head->_next;
		//		while (cur != _head)
		//		{
		//			Node* next = cur->_next;
		//			delete cur;
		//			cur = next;
		//		}
		//		//恢复成原始状态
		//		_head->_next = _head;
		//		_head->_prev = _head;
		//		_size = 0;
		//	}
		//}

		//复用erase
		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;
		//	tail->_next = newnode;
		//	newnode->_prev = tail;
		//	newnode->_next = _head;
		//	_head->_prev = newnode;
		//	_size++;
		//}

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

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

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

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

		//list的insert没有迭代器失效的问题
		iterator insert(iterator pos, const T& x)
		{
			Node* newnode = new Node(x);
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			newnode->_prev = prev;
			prev->_next = newnode;

			++_size;
			//调用iterator的构造函数构造一个新的迭代器并返回
			return iterator(newnode);
		}

		//list的erase有迭代器失效的问题
		iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			prev->_next = next;
			next->_prev = prev;
			delete cur;
			cur = nullptr;
			//调用iterator的构造函数构造一个新的迭代器并返回
			--_size;
			return iterator(next);
		}

		size_t size() const
		{
			return _size;
		}

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

	private:
		Node* _head;
		size_t _size;
	};
}

六.补充

1.一个"奇怪"的现象

template<class T>
void print_list(const list<T>& lt)
{
	list<T>::const_iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
}

这是一个打印list的内容的函数
不过运行的时候却会报错

2.小小优化一下

刚才那个只能打印list
如果我想让它也能打印vector,string等等类型呢?
在上面加一个模板即可

template<typename Container>

void print_container(const Container& con)
{
	typename Container::const_iterator it = con.begin();
	while (it != con.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

因此我们就能知道

模板实现了泛型编程
而泛型编程的本质就是把本来应该由我们做的工作交给了编译器去做

以上就是C++ list模拟实现的全部内容,希望能对大家有所帮助!