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

-> 数据结构与算法 -> C++：仿写STL的 list | 工业级代码 | 迭代器的仿写 | 功能单一的插入和删除函数所带来的便利 -> 正文阅读

[数据结构与算法]C++：仿写STL的 list | 工业级代码 | 迭代器的仿写 | 功能单一的插入和删除函数所带来的便利

前言

这篇文章是仿写 STL的list

设计模板类，展现typedef重命名的作用。
完成了迭代器的仿写。
展现了功能单一的插入删除函数为程序带来的便利。

设计模板类

template<typename _Ty>
class list
{
};

List结点类型的定义

因为STLlist的迭代器有双向的，所以仿写时候也是让其具有前驱结点和后继结点。

首先要设计为模板类。
首先声明结点，再重命名一个结点指针
设计该结点，使其具有前驱、后继和值域。

template<typename _Ty>
class list
{
protected:
	struct _Node;
	typedef struct _Node* _Nodeptr;
	struct _Node
	{
		_Nodeptr _Prev;  // 前驱
		_Nodeptr _Next;	// 后继
		_Ty _Value;			// 值 | _Ty为模板类型
	};
};

图示：
在这里插入图片描述

提供返回引用的函数

为了方便访问，设计一些重命名和返回引用的函数。

结点指针的引用重命名
结点值的引用的重命名
返回该结点值的引用
返回该结点前驱的引用
返回该结点后继的引用

struct _Acc; // 声明
struct _Acc	 // 设计
{
	typedef struct _Node*& _Nodepref;  // 1
	typedef _Ty& _Vref;				// 2
	
	static _Vref _Value(_Nodeptr _P) // 3
	{
		return (*_P)._Value;
	}
	
	static _Nodepref _Prev(_Nodeptr _P) // 4
	{
		return (*_P)._Prev;
	}

	static _Nodepref _Next(_Nodeptr _P) // 5
	{
		return (*_P)._Next;  // return _P->_Next;
	}
};

用法示例1

可以这样使用来获取值，或改变值，因为是引用返回。

int x = _Acc::_Value(_P);  // 获取值
_Acc::_Value(_P) = 20;     // 修改值

示例2

_Nodeptr s = _Acc::_Prev(_P);	// 使s指向_P的前驱结点
_Acc::_Prev(_P) = NULL;			// 使_P的前驱置为空

迭代器类

设计迭代器类，以达到访问list的结点，这里设计两种，常性迭代器和普通迭代器。
普通迭代器继承常性迭代器，原因是普通迭代器比常性迭代器功能多。

public:
	typedef _Ty			value_type;
	typedef _Ty&		reference;
	typedef const _Ty&	const_reference;
	typedef _Ty*		pointer;
	typedef const _Ty*	const_pointer;
	typedef size_t		size_type;
	typedef int			diference_type;

public:	
	class const_iterator;
	class iterator;

	class const_iterator
	{
	protected:
		_Nodeptr _Ptr;
	public:
		const_iterator(_Nodeptr _P) : _Ptr(_P) {}

		const_reference operator*() const
		{
			return _Acc::_Value(_Ptr);
		}

		const_pointer operator->() const
		{
			return &**this;
		}

		const_iterator& operator++()
		{
			_Ptr = _Acc::_Next(_Ptr);
			return *this;
		}
		const_iterator operator++(int)
		{
			const_iterator tmp = *this;
			++* this;
			return tmp;
		}

		const_iterator& operator--()
		{
			_Ptr = _Acc::_Prev(_Ptr);
			return *this;
		}
		const_iterator operator--(int)
		{
			const_iterator tmp = *this;
			--* this;
			return tmp;
		}

		bool operator==(const const_iterator& _X) const
		{
			return this->_Ptr == _X._Ptr;
		}

		bool operator !=(const const_iterator& _X) const
		{
			return !(*this == _X);
		}

		_Nodeptr _Mynode() const
		{
			return _Ptr;
		}

	};

	class iterator : public const_iterator
	{
		typedef const_iterator base;
	public:
		iterator(_Nodeptr _P) : const_iterator(_P) {}

		iterator& operator++()
		{
			base::_Ptr = _Acc::_Next(base::_Ptr);
			return *this;
		}
		
		iterator operator++(int)
		{
			iterator tmp = *this;
			++* this;
			return tmp;
		}

		iterator& operator--()
		{
			base::_Ptr = _Acc::_Prev(base::_Ptr);
			return *this;
		}
		iterator operator--(int)
		{
			iterator tmp = *this;
			++* this;
			return tmp;
		}

		bool operator==(const iterator& _X) const
		{
			return this->_Ptr == _X._Ptr;
		}

		bool operator !=(const iterator& _X) const
		{
			return !(*this == _X);
		}
	};

使用迭代器的方法

	iterator begin() { 
		return iterator(_Acc::_Next(_Head));
	}

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

	const_iterator begin() const {
		return const_iterator(_Acc::_Next(_Head));
	}
	const_iterator end() const {
		return const_iterator(_Head);
	}

list的其他私有成员和方法

申请结点和释放结点
_Head：头结点
_Size ：结点个数

private:
	// 购买结点
	_Nodeptr _BuyNode(_Nodeptr _Parg = NULL, _Nodeptr _Narg = NULL)
	{
		_Nodeptr _S = (_Nodeptr)malloc(sizeof(_Node));
		_Acc::_Prev(_S) = NULL == _Parg ? _S : _Parg;
		_Acc::_Next(_S) = NULL == _Narg ? _S : _Narg;

		return _S;
	}
	// 释放结点
	void _FreeNode(_Nodeptr _P)
	{
		free(_P);
	}

	_Nodeptr _Head;  // 头结点
	size_type _Size; // 结点个数，不包括头结点

list类方法

构造函数

list() :_Head(_BuyNode()), _Size(0) {}

插入函数方法一（重要）

如果在使用插入方法时是这种形式，插入一个值。

int main(void)
{
	list<int> ilist;
	ilist.insert(ilist.begin(), 10);
}

那插入函数应当这样写：

指针获取当前结点信息
购买结点: a.让新结点的prev指向当前结点的前驱； b. 让新节点的next指向当前结点； c. 当前结点的前驱指向新节点。
让新节点作为当前结点。
让当前结点（新节点）的前驱的后继指向当前结点。（因为第二步的abc并没有完成这一步）
使用定位new ，先得到当前结点的值域的地址，使用定位new 构造_Ty类型。（为什么不直接赋值？因为这个例子中使用的是内置类型int，如果是一个其他设计的类作为值域，就需要调动构造函数，为了统一，就是用定位new）
让list的节点个数加一，返回当前迭代器。

	iterator insert(iterator _P, const _Ty& val)
	{
		_Nodeptr _S = _P._Mynode();	// 1
		_Acc::_Prev(_S) = _BuyNode(_Acc::_Prev(_S), _S); // 2
		_S = _Acc::_Prev(_S);	// 3
		_Acc::_Next(_Acc::_Prev(_S)) = _S; // 4
		new(&_Acc::_Value(_S)) _Ty(val);	// 5
		_Size += 1;		// 6
		return iterator(_S);
	}

头插法和尾插法

有了insert函数，那么头插和尾插就很容易

	void push_front(const _Ty& val)
	{
		insert(begin(), val);
	}
	void push_back(const _Ty& val)
	{
		insert(end(), val);
	}

插入函数方法二

如果需要这样的需求，插入一个数组，给定的数组地址

int main(void)
{
	Srh::list<int> ilist;
	int nums[] = { 12,23,34,45,56,67,78,89,90 };
	int n = sizeof(nums) / sizeof(nums[0]);

	ilist.insert(ilist.begin(), nums, nums + n);

	return 0;
}

那么由于insert方法一的存在，这个也好实现了

_F 和 _L表示数组的第一个元素地址和最后一个元素地址
for循环，调动insert方法一。

	void insert(iterator _P, const _Ty* _F, const _Ty* _L)
	{
		for (; _F != _L; ++_F)
		{
			insert(_P, *_F);
		}
	}

运行结果：

在这里插入图片描述

插入函数方法三

如果按个数插入同一个值

int main(void)
{
	Srh::list<int> ilist;

	ilist.insert(ilist.begin(), 10, 100);

	return 0;
}

还是可以用insert方法一完成：

void insert(iterator _P, size_t count, const _Ty& val)
{
	while (count--)
	{
		insert(_P, val);
	}
}

插入方法四(插入一个list)

int main(void)
{
	Srh::list<int> ilist1;

	ilist1.insert(ilist1.begin(), 10, 100);
	Srh::list<int> ilist2;
	ilist2.insert(ilist2.begin(), ilist1.begin(), ilist1.end());

	return 0;
}

typedef const_iterator _It;
void insert(iterator _P, _It _F, _It _L)
{
	for (; _F != _L; ++_F)
	{
		insert(_P, *_F);
	}
}

运行结果：

在这里插入图片描述

其他构造函数

给定个数和值域

list(size_t count, const _Ty& val) : _Head(_BuyNode()), _Size(0)
{
	insert(begin(), count, val);
}

给定数组来构造

list(const _Ty* _F, const _Ty* _L) : _Head(_BuyNode()), _Size(0)
{
	insert(begin(), _F, _L);
}

拷贝构造

给定一个list来拷贝另一个list

list(const list& _X) : _Head(_BuyNode()), _Size(0)
{
	insert(begin(), _X.begin(), _X.end());
}

erase删除函数

既然有插入函数，那么对应的，也有删除函数，这个函数同样比较麻烦，存在一些易错点。
流程：

利用一个指针指向当前结点，并让当前迭代器_P指向下一个结点。
让当前结点的前驱的后继，指向当前结点的后继。
让当前结点的后继的前驱，指向当前结点的前驱。

在这里插入图片描述

对结点的值域取地址，调动其析构函数（这里的_Ty是内置类型整型，为了防止以后会用到设计的类型，比较复杂，所以调动析构函数来达到删除释放的目的）
释放当前结点
返回下个迭代器

iterator erase(iterator _P)
{
	_Nodeptr _S = _P++._Mynode();		// 1
	_Acc::_Next(_Acc::_Prev(_S)) = _Acc::_Next(_S); // 2
	_Acc::_Prev(_Acc::_Next(_S)) = _Acc::_Prev(_S); // 3
	(&_Acc::_Value(_S))->~_Ty();		// 4
	_FreeNode(_S);  						// 5
	return _P;							// 6
}

关于后置++的问题

上面删除函数的第一步，_P++._Mynode()，是先执行什么？

答：该表达式可替换为

_P.operator++(0)._Mynode();

也就是说，先调用的后置++,再取得其结点信息，那这样取到的是当前节点信息还是后继结点？

根据监视器结果：
_S指针得到了当前结点信息，而_P也指向下一个结点，因此这样编写没有错误。（实际上是先对 _P++，这个_Mynode()取得的是一个将亡值的结点信息）

在这里插入图片描述

其他删除函数

头删与尾删法

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

erase方法二

基于erase方法一来实现

void erase(iterator _F, iterator _L)
{
	for (; _F != _L; )
	{
		erase(_F++);
	}
}

清除函数

根据删除函数二

void clear()
{
	erase(begin(), end());
}

移除元素（值得形式

移除一个

void remove(const _Ty& val)
{
	iterator _F = this->begin(), _L = this->end();
	while (_F != _L)
	{
		if (*_F == val)
		{
			this->erase(_F);
			return;
		}
		_F++;
	}
}

移除所有等于这个值的

void remove_all(const _Ty& val)
{
	iterator _F = this->begin(), _L = end();
	while (_F != _L)
	{
		if (*_F == val)
		{
			erase(_F++);
		}
		_F++;
	}
}

析构函数

调用clear()，再free头结点

~list()
{
	clear();
	_FreeNode(_Head);
}

其他特殊函数

交换函数

template<typename T>
void Swap(T& a, T& b)
{
	T tmp = a;
	a = b;
	b = tmp;
}
void Swap(list& _X)
{
	Srh::Swap(this->_Head, _X._Head);
	Srh::Swap(this->_Size, _X._Size);
}

赋值运算符重载

	list& operator =(const list _X)
	{
		if (this == &_X) return *this;
		iterator _F1 = begin();
		iterator _L1 = end();
		const_iterator _F2 = _X.begin();
		const_iterator _L2 = _X.end();
		for (; _F1 != _L1 && _F2 != _L2; ++_F1, ++_F2)
		{
			*_F1 = *_F2;
		}

		erase(_F1, _L1);
		insert(_L1, _F2, _L2);
		return *this;
	}

完整代码

#ifndef SRH_LIST_H
#define SRH_LIST_H

namespace Srh
{
template<typename T>
void Swap(T& a, T& b)
{
	T tmp = a;
	a = b;
	b = tmp;
}

template<typename _Ty>
class list
{
protected:
	struct _Node;
	typedef struct _Node* _Nodeptr;
	struct _Node
	{
		_Nodeptr _Prev;
		_Nodeptr _Next;
		_Ty _Value;
	};
	struct _Acc; // 声明
	struct _Acc	 // 设计
	{
		typedef struct _Node*& _Nodepref;
		typedef _Ty& _Vref;
		static _Vref _Value(_Nodeptr _P)
		{
			return (*_P)._Value;
		}
		static _Nodepref _Prev(_Nodeptr _P)
		{
			return (*_P)._Prev;
		}
		static _Nodepref _Next(_Nodeptr _P)
		{
			return (*_P)._Next;  // return _P->_Next;
		}
	};

public:
	typedef _Ty			value_type;
	typedef _Ty&		reference;
	typedef const _Ty&	const_reference;
	typedef _Ty*		pointer;
	typedef const _Ty*	const_pointer;
	typedef size_t		size_type;
	typedef int			diference_type;

public:	
	class const_iterator;
	class iterator;

	class const_iterator
	{
	protected:
		_Nodeptr _Ptr;
	public:
		const_iterator(_Nodeptr _P) : _Ptr(_P) {}

		const_reference operator*() const
		{
			return _Acc::_Value(_Ptr);
		}

		const_pointer operator->() const
		{
			return &**this;
		}

		const_iterator& operator++()
		{
			_Ptr = _Acc::_Next(_Ptr);
			return *this;
		}
		const_iterator operator++(int)
		{
			const_iterator tmp = *this;
			++* this;
			return tmp;
		}

		const_iterator& operator--()
		{
			_Ptr = _Acc::_Prev(_Ptr);
			return *this;
		}
		const_iterator operator--(int)
		{
			const_iterator tmp = *this;
			--* this;
			return tmp;
		}

		bool operator==(const const_iterator& _X) const
		{
			return this->_Ptr == _X._Ptr;
		}

		bool operator !=(const const_iterator& _X) const
		{
			return !(*this == _X);
		}

		_Nodeptr _Mynode() const
		{
			return _Ptr;
		}

	};

	class iterator : public const_iterator
	{
		typedef const_iterator base;
	public:
		iterator(_Nodeptr _P) : const_iterator(_P) {}

		iterator& operator++()
		{
			base::_Ptr = _Acc::_Next(base::_Ptr);
			return *this;
		}
		
		iterator operator++(int)
		{
			iterator tmp = *this;
			++* this;
			return tmp;
		}

		iterator& operator--()
		{
			base::_Ptr = _Acc::_Prev(base::_Ptr);
			return *this;
		}
		iterator operator--(int)
		{
			iterator tmp = *this;
			++* this;
			return tmp;
		}

		bool operator==(const iterator& _X) const
		{
			return this->_Ptr == _X._Ptr;
		}

		bool operator !=(const iterator& _X) const
		{
			return !(*this == _X);
		}
	};

public:
	iterator begin() { 
		return iterator(_Acc::_Next(_Head));
	}

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

	const_iterator begin() const {
		return const_iterator(_Acc::_Next(_Head));
	}
	const_iterator end() const {
		return const_iterator(_Head);
	}
	
public:
	typedef const_iterator _It;

	list() : _Head(_BuyNode()), _Size(0) {}

	list(size_t count, const _Ty& val) : _Head(_BuyNode()), _Size(0)
	{
		insert(begin(), count, val);
	}
	list(const _Ty* _F, const _Ty* _L) : _Head(_BuyNode()), _Size(0)
	{
		insert(begin(), _F, _L);
	}
	list(const list& _X) : _Head(_BuyNode()), _Size(0)
	{
		insert(begin(), _X.begin(), _X.end());
	}
	
	list& operator =(const list _X)
	{
		if (this == &_X) return *this;
		iterator _F1 = begin();
		iterator _L1 = end();
		const_iterator _F2 = _X.begin();
		const_iterator _L2 = _X.end();
		for (; _F1 != _L1 && _F2 != _L2; ++_F1, ++_F2)
		{
			*_F1 = *_F2;
		}

		erase(_F1, _L1);
		insert(_L1, _F2, _L2);
		return *this;
	}

	~list()
	{
		clear();
		_FreeNode(_Head);
	}

	// 插入
	iterator insert(iterator _P, const _Ty& val)
	{
		_Nodeptr _S = _P._Mynode();
		_Acc::_Prev(_S) = _BuyNode(_Acc::_Prev(_S), _S);
		_S = _Acc::_Prev(_S);
		_Acc::_Next(_Acc::_Prev(_S)) = _S;
		new(&_Acc::_Value(_S)) _Ty(val);
		_Size += 1;
		return iterator(_S);
	}
	void insert(iterator _P, const _Ty* _F, const _Ty* _L)
	{
		for (; _F != _L; ++_F)
		{
			insert(_P, *_F);
		}
	}
	void insert(iterator _P, size_t count, const _Ty& val)
	{
		while (count--)
		{
			insert(_P, val);
		}
	}
	void insert(iterator _P, _It _F, _It _L)
	{
		for (; _F != _L; ++_F)
		{
			insert(_P, *_F);
		}
	}

	void push_front(const _Ty& val)
	{
		insert(begin(), val);
	}
	void push_back(const _Ty& val)
	{
		insert(end(), val);
	}
	
	// 删除
	iterator erase(iterator _P)
	{
		_Nodeptr _S = _P++._Mynode();
		_Acc::_Next(_Acc::_Prev(_S)) = _Acc::_Next(_S);
		_Acc::_Prev(_Acc::_Next(_S)) = _Acc::_Prev(_S);
		(&_Acc::_Value(_S))->~_Ty();
		_FreeNode(_S);

		return _P;
	}
	void erase(iterator _F, iterator _L)
	{
		for (; _F != _L; )
		{
			erase(_F++);
		}
	}

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

	void clear()
	{
		erase(begin(), end());
	}

	void remove(const _Ty& val)
	{
		iterator _F = this->begin(), _L = this->end();
		while (_F != _L)
		{
			if (*_F == val)
			{
				this->erase(_F);
				return;
			}
			_F++;
		}
	}
	void remove_all(const _Ty& val)
	{
		iterator _F = this->begin(), _L = end();
		while (_F != _L)
		{
			if (*_F == val)
			{
				erase(_F++);
			}
			_F++;
		}
	}

private:
	// 购买结点
	_Nodeptr _BuyNode(_Nodeptr _Parg = NULL, _Nodeptr _Narg = NULL)
	{
		_Nodeptr _S = (_Nodeptr)malloc(sizeof(_Node));
		_Acc::_Prev(_S) = NULL == _Parg ? _S : _Parg;
		_Acc::_Next(_S) = NULL == _Narg ? _S : _Narg;

		return _S;
	}
	// 释放结点
	void _FreeNode(_Nodeptr _P)
	{
		free(_P);
	}

	_Nodeptr _Head;  // 头结点
	size_type _Size; // 结点个数，不包括头结点
};
}
#endif