C++初阶 List的模拟实现

作者：@小萌新
专栏：@C++初阶
作者介绍：大二学生 希望能和大家一起进步
本篇博客简介：模拟STL中List的实现

本篇博客目标

1. 模拟List类的实现
2. 模拟迭代器类的实现
3. 模拟List实现

节点类的实现

List在底层实现的时候实际上就是一个底层带头循环双向链表

结构表示如下

如果说对于带头双向循环链表没有一个清晰认知的同学可以参考下我的这篇博客

带头循环双向链表

在实现List之前我们首先要实现一个节点类

（因为是自定义类型的数据）

大概的结构表示如下

template<typename T> // Class T
class _list_node
{
public:
	
	_list_node(const T& val = T()) // 默认初始化一个


	T _val;     // 值
	T* _next;   // 指向后面一个node
	T* _prev;   // 指向前面一个node
};
1
2
3
4
5
6
7
8
9
10
11
12

节点类的作用只有一个 创建一个新的类给我们的List

至于释放则不用管 我们List里面会考虑

这就相当于我们用C语言写的一个Buylistnode函数一样

构造函数

	_list_node(const T& val = T()) // 默认初始化一个
		:_val(val) // 默认初始化为0 这里实际上用到了一个匿名函数
		,_next(nullptr)
		,_prev(nullptr)
	{

	}
1
2
3
4
5
6
7

代码表示如上 到这里我们节点类的所有任务就都完成了

迭代器类的实现

迭代器类模拟实现的意义

回想看我们之前的vector类和String类 我们是不是就直接开始写了啊

迭代器好像就直接typedef一下就可以了那为什么List里面要专门写一个迭代器类呢？

这个就跟这俩数据的结构有关系了

对于Vector或者是String类来说 它们的底层是用使用一块连续的空间 因此通过指针的加加减减就可以得

到后面的数据 因此vector和string中的迭代器就是原生指针

那么我们为什么在list当中要使用迭代器类呢？

因为我们说过了list的数据结构是一个带头双向循环链表 是不连续的 所以我们必须要使用指针的

next prev来找到前后元素

那么我们为什么不直接找 而使用迭代器呢？

这是因为

可以不让用户关心底层实现 用简单统一的方式对容器进行访问

总结下来就是

list中的迭代器类 实际上就是对指针节点进行了封装 对其各种运算符进行了重载 使得节点指针的

各种行为看上去和原生指针一模一样。

（回想看看我们之前的日期类的++）

迭代器类的三个参数说明

template<class T, class Ref, class Ptr>
1

这里的三个参数的意义分别是 原类型 引用类型 指针类型

至于为什么这么设计 我相信大家在看完所有的代码之后会有一个很好的感悟

框架如下

template<class T, class Ref, class Ptr>
struct _list_iterator
{
	typedef _list_node<T>  node;
	typedef _list_iterator<T, Ref, Ptr>  self;

	node* _pnode; 
};
1
2
3
4
5
6
7
8

构造函数

迭代器类实际上就是对节点指针进行了封装 其成员变量只有一个 那就是一个指针 所以我们初始化也只

用初始化这个指针就可以

代码表示如下

//构造函数
_list_iterator(node* pnode)
	:_pnode(pnode)
{}

1
2
3
4
5

++运算符重载

前置++操作符本来的意思的是让数据自增 然后返回自增后的数据

但是对于我们这里的迭代器来说++的意思则是让它指向下一个数据

所以说我们应该这么写

代码表示如下

	self operator++()
	{
		_pnode = _pnode->_next;
		return *this;
	}
1
2
3
4
5

而为了区分前置++和后置++ 我们在参数内部放置一个占位操作符

	self operator++(int)
	{
		self tmp(*this) //作为返回值
		_pnode = _pnode->_next;
		return tmp;
	}
1
2
3
4
5
6

- -运算符的重载

跟++运算符很类似 我们这里直接给出代码

前置- -

	self operator--()
	{
		_pnode = _pnode->_prev;
		return *this;
	}
1
2
3
4
5

后置–

	self operator--(int)
	{
		self tmp(*this); // 作为返回值
		_pnode = _pnode->_prev;
		return *this;
	}
1
2
3
4
5
6
7

==运算符重载

当我们使用两个==运算符重载的时候 我们实际上是比较的两个迭代器是否是同一个迭代器

那么想想看我们应该怎么比较呢？ 看看两个的指针是否是同一个是不是就好了

	bool operator==(const self& it) const
	{
		return it._pnode == _pnode;
	}
1
2
3
4

!=运算符重载

这里我们直接判断两个指针不同就可以

	bool operator!=(const self& it) const
	{
		return it._pnode != _pnode;
	}
1
2
3
4

*运算符重载

我们使用解引用运算符的时候 我们希望的是拿到该位置的数据

	ref operator *()
	{
		return _pnode->_val; // 返回指针指向的值
	}
1
2
3
4

->运算符重载

我们使用解引用运算符的时候我们是想访问我们内部的值

所以说这个时候呢我们需要返回值的地址即可

	Ptr operator ->()
	{
		return &(_pnode->_val);
	}
1
2
3
4

行文至此 我们应该能够明白为啥要定义三个参数了吧

因为我们要返回不同的三个类型的值

List的模拟实现

构造函数

List的结构是一个带头双向循环链表 所以说我们让头尾指针都指向自己即可

	List()
	{
		_head = new node; //创建一个新的头节点
		_head->_prev = _head; // 头节点的前一个指针指向自身
		_head->_next = _head; // 头节点的后一个指针指向自身
	}
1
2
3
4
5
6

接下来的几个函数都需要用到我们后面的实现的接口函数 所以说我们放到后面再实现

begin和end函数

我们这里要明白 begin返回的是第一个节点（头节点的下一个节点的指针） end返回的是头节点

知道这两个返回的是啥之后我们的代码就好写了

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

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

1
2
3
4
5
6
7
8
9
10

当然我们这里还需要重载一个const版本

代码表示如下

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

	const_iterator end() const
	{
		return iterator(_head);
	}
1
2
3
4
5
6
7
8
9

front和back函数

这两个函数的作用是返回front的back的值

	T& front()
	{
		return *begin();
	}

	T& back()
	{
		return *(--end());
	}
1
2
3
4
5
6
7
8
9

当然啦 还有它们的const版本

	const T& front() const
	{
		return *begin();
	}

	const T& back() const
	{
		return *(--end());
	}
1
2
3
4
5
6
7
8
9

insert

我们这里插入一个新节点

传入两个参数就可以 一个迭代器来表示位置 一个数值来表示我们要插入的数

代码表示如下

	void insert(iterator pos, const T& x)
	{
		node* cur = pos._pnode;
		node* prev = cur->_prev;
		node* newnode = new node(x);

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

		prev->_next = newnode;
		newnode->_prev = prev;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13

earse

就是一个双链表的删除 保存下头尾节点就好了

代码表示如下

	iterator earse(iterator pos)
	{
		assert(pos != end());

		node* cur = pos._pnode; //迭代器pos处的结点指针
		node* prev = cur->_prev; //迭代器pos前一个位置的结点指针
		node* next = cur->_next; //迭代器pos后一个位置的结点指针

		delete cur; //释放cur结点

		//建立prev与next之间的双向关系
		prev->_next = next;
		next->_prev = prev;

		return iterator(next); //返回所给迭代器pos的下一个迭代器
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

push_back和push_front

我们这里复用前面的insert就可以啦

尾差就是插入到end迭代器的前面

头插入就是插入到头的下一个节点的前面

代码表示如下

//尾插
void push_back(const T& x)
{
	insert(end(), x); //在头结点前插入结点
}
//头插
void push_front(const T& x)
{
	insert(begin(), x); //在第一个有效结点前插入结点
}

1
2
3
4
5
6
7
8
9
10
11

pop_back和pop_front

void pop_back()
{
	erase(--end()); //删除头结点的前一个结点
}

void pop_front()
{
	erase(begin()); //删除第一个有效结点
}
1
2
3
4
5
6
7
8
9

size

因为我们是链表 我们只能逐个统计有效节点的个数只能遍历计数

size_t size() const
{
	size_t sz = 0; //统计有效数据个数
	const_iterator it = begin(); //获取第一个有效数据的迭代器
	while (it != end()) //通过遍历统计有效数据个数
	{
		sz++;
		it++;
	}
	return sz; //返回有效数据个数
}

1
2
3
4
5
6
7
8
9
10
11
12

clear

我们通过遍历的方式 逐个删除即可

代码表示如下

void clear()
{
	iterator it = begin();
	while (it != end()) //逐个删除结点，只保留头结点
	{
		it = erase(it);
	}
}

1
2
3
4
5
6
7
8
9

empty

我们直接看看头尾迭代器是否相同就好

bool empty() const
{
	return begin() == end(); //判断是否只有头结点
}

1
2
3
4
5

swap

因为其实里面只有两个指针 所以说我们交换指针之后就完成交换了

void swap(list<T>& lt)
{
	::swap(_head, lt._head); //交换两个容器当中的头指针即可
}

1
2
3
4
5

resize

resize的规则如下

1 当给予的数小于我们目前数 我们删除到我们给予的数为止（earse）
2 当给予的数大于我们目前数 我们增加到我们给予的数为止 （push_back）

代码表示如下

void resize(size_t n, const T& val = T())
{
	iterator i = begin(); //获取第一个有效数据的迭代器
	size_t len = 0; //记录当前所遍历的数据个数
	while (len < n&&i != end())
	{
		len++;
		i++;
	}
	if (len == n) //说明容器当中的有效数据个数大于或是等于n
	{
		while (i != end()) //只保留前n个有效数据
		{
			i = erase(i); //每次删除后接收下一个数据的迭代器
		}
	}
	else //说明容器当中的有效数据个数小于n
	{
		while (len < n) //尾插数据为val的结点，直到容器当中的有效数据个数为n
		{
			push_back(val);
			len++;
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

后续补

析构函数

对整个List对象进行析构的时候是不是记得要将前面所有的节点释放啊

之后释放下头节点并且置空之不是就完成了

所以说这里的代码也很简单

~list()
{
	clear(); //清理容器
	delete _head; 
	_head = nullptr; 
}

1
2
3
4
5
6
7
8

拷贝构造

我们创建一个新的头节点

然后遍历老数组的数据 一个一个的往后插入是不是就可以啦？

代码表示如下

//拷贝构造函数
list(const list<T>& lt)
{
	_head = new node; 
	_head->_next = _head; 
	_head->_prev = _head; 
	for (const auto& x : lt)
	{
		push_back(x); 
	}
}

1
2
3
4
5
6
7
8
9
10
11
12

赋值构造

这里就很简单了 我们现代写法

使用临时变量接受参数 这样形参是不是就是实参的一份临时拷贝了

然后我们将它们swap一下就可以了

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

1
2
3
4
5
6
7

这里还用不用管形式参数会怎么样了呢？

答案是不用的 因为它出了作用域会自动销毁

总结

本篇博客模拟了List的实现
由于博主才疏学浅错误在所难免 如果大佬看到希望能及时指正啊
如果本文帮助到了你别忘了一键三连啊
阿尼亚 哇酷哇酷！