【STL】list类的讲解及模拟实现

  • 开发
  • 37

🪐🪐🪐欢迎来到程序员餐厅💫💫💫

         今日主菜：vector类

         主厨：邪王真眼

          所属专栏：c++专栏

          主厨的主页：Chef‘s blog

总用光环在陨落，总有新星在闪烁

【本节目标】

1. 节点

2.迭代器

3.list

4. list与vector的对比

前言：

这次的list类较vector和string会更复杂，因此我们将他拆分为节点的类，迭代器的类，以及list类主体三点进行讲解。

一. list的介绍

  • 1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
  • 2. list的底层是双向带头循环链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
  • 3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
  • 4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
  • 5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素

二.节点

要点须知：

  1. 使用struct，标明公有属性（这样从外部调用比较方便）
  2. list是带头双向循环链表
template<class T>
struct ListNode//驼峰式命名
{
	ListNode<T>* _prev;
	ListNode<T>* _last;
	T _val;
	ListNode(const T &val=T())//缺省参数
		:_prev(nullptr)
	    ,_last(nullptr)
		,_val(val)
	{}
};

二、迭代器

由于list的每个结点物理空间不连续，导致迭代器不能像之前string、vector那样简单的设计为指针，而是设计为一个类（进行封装），以此完成*、->、++、–-等一系列操作。

2.1 成员变量与默认构造函数

注意事项：

仍然使用struct，标明公有属性成员变量是一个结点的指针

template <class T,class Ref,class Ptr>
struct ListIterator
{
	typedef ListNode<T> Node;//为了方便使用节点类，我们给它重命名一下
	typedef ListIterator<T, Ref,  Ptr>self;//原理同上
	ListIterator(Node* ptr)
		:Node(ptr)
	{}

	Node* _Node;
};

我知道你现在很疑惑为什么模版要用到三个参数，别急，等会讲解。

这里的迭代器的实际不可谓不妙，后面你就会称赞它的

2.2 operator*

Ref operator*()
{
	return _Node->_val;
}

解释：对比一下以前的代码

不难看出我们常常要对const和非const对象进行分类重载函数以满足他们的不同需求，但是硬要说这里的operator*重载也就传参的返回值类I型不同，而且由于权限的放大缩小规则，传参也可以写成一样的，那就只有返回值不同了，于是直接对他进行模板泛型编程，直接设计参数Ref，然后把它当作返回值，就可以达到重载的效果了。
这里的返回值是数据val类型的引用，分为const和非const

2.3 operator->

Ptr operator->()
{
	return &_Node->val;
 }

同样的的道理，这就是为什么迭代器的模板参数有三个。

这里的返回值是数据val类型的指针，分为const和非const

2.4 operator++

注意事项：

  1. 为了区分前置和后置，后置参数加上int（无实际意义，以示区分）
  2. 前置传引用返回，后置传值返回
self& operator++()
{
	_Node = _Node->_last;
	return _Node;
}

self operator++(int)
{
	Node* tmp = _Node;
	_Node = _Node->last;
	return tmp;
}

2.5 operator- -

与++同理

self operator--(int)
{

	Node* tmp = _Node;
	_Node = _Node->_prev;
	return tmp;
}
self operator--()
{
	_Node = _Node->_prev;
	return _Node;
}

2.6operator==

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

2.6operator！=

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

三、list

3.1 成员变量

注意事项：

head是哨兵位

template<class T>
class List
{
public:
	typedef ListNode Node;
private:
	Node* _head;
};

3.2对迭代器的处理

typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&,const T*> const_iterator;
【注意】
  • 1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
  • 2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动我们现在只实现begin和end

3.2.1begin()

注意事项：

  • 1.返回值类型要强制类型转换
  • 2.返回的是_head的下一个，不是_head，_head是哨兵位
iterator begin()
{
	return iterator(_head->_last);
}
const_iterator begin()const
{
	return const_iterator(_head->_last);
}

3.2.2 end

细节：

1.返回值类型要强制类型转换

2.返回的是_head

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

3.3 默认成员函数

3.3.1构造函数

（1）创建哨兵位，缺省参数
List(T val=T())
:_head(new Node)
{
	_head->_last = _head;
	_head->_prev = _head;
	_head->_val = val;
}
（2）迭代器区间构造
template <class InputIterator>
List(InputIterator first, InputIterator last)
{
	_head=new Node;
	_head->_last = _head;
	_head->_prev = _head;
	_head->_val = T();
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

push_back是尾插，这个我们之后再写，先挖个坑

3.3.2 析构函数

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

clear的作用是消除除了哨兵位之外的节点。咱们后面实现

3.3.3拷贝构造函数

摩登写法：

List(List<T>& l)
{
	_head(new Node);
	_head->_last = _head;
	_head->_prev = _head;
	_head->_val = T();
	List<T>tmp(l.begin(), l.end());
	swap(tmp);
}

3.3.4 operator=

现代写法

注意事项：

  1. 传参变成传值，这样就会拷贝构造出一个临时对象
  2. 再使用list中的swap，交换*this和tmp的值，完成赋值重载
List<T>& operator=(List<T>l)
{
	swap(l);
	return*this;
}

3.4 修改

3.4.1 insert

注意事项：

迭代器不会失效

void intsert(iterator pos,T val)//原本在这个位置的节点向后移
{
	Node* cur = pos._Node;
	Node* prev = cur->_prev;
	Node* NewNode = new Node(val);
	NewNode->_prev = prev;
	prev->_last = NewNode;
	NewNode->_last = cur;
	cur->_prev = NewNode;
}

3.4.2 push_front

头插

void push_front(T val)
{
	Node* NewNode = new Node(val);
	Node* last = _head->_last;
	NewNode->_prev = _head;
	NewNode->_last = last;
	last->_prev = NewNode;
	_head->_last = NewNode;
}

3.4.3 push_back

尾插

void  push_back(T val)
{
	Node* NewNode = new Node(val);
	Node* tail = _head->_prev;
	tail->_last = NewNode;
	NewNode->_prev = tail;
	NewNode->_last = _head;
	_head->_prev = NewNode;
}

3.4.4 erase

指定位置删除

注意事项：

  1. assert断言，防止删除哨兵位
  2. 返回删除节点的下一位，防止迭代器失效
iterator erase(iterator pos)
{
assert(pos!=end());
	Node* cur = pos._Node;
	Node* prev = cur->_prev;
	Node* last = cur->_last;
	prev->_last =last;
	last->_prev = prev;
	delete cur;
	return iterator(last);
}

3.4.5 pop_front

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

3.4.6 pop_back

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

3.4.7 clear

清除所有结点（除哨兵位以外）

void clear()
{
	Node* New = _head->_last;
	while (New != _head)
	{
		Node* News = New->_last;
		delete New;
		New = News;
	}
}

3.4.8 swap

交换两个list类的值

注意事项：

使用std库中的swap函数，要带有std::,不然会被认成你所写的swap，进而导致无限递归。

void swap(List<T>&l)
{
	std::swap(_head,l._head);
}

3.4.9list的迭代器失效

前面说过，此处大家可将迭代器暂时理解成类似于指针， 迭代器失效即迭代器所指向的节点的无效，即该节 点被删除了 。因为 list 的底层结构为带头结点的双向循环链表 ，因此 在 list 中进行插入时是不会导致 list 的迭代 器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响 。

4. list与vector的对比

vector 与 list 都是 STL 中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：

我的模拟源码仅供参考，第一次写，有错误欢迎在评论区指出

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<assert.h>
using namespace std;
template<class T>
struct ListNode//驼峰式命名
{
	ListNode<T>* _prev;
	ListNode<T>* _last;
	T _val;
	ListNode(const T &val=T())//缺省参数
		:_prev(nullptr)
	    ,_last(nullptr)
		,_val(val)
	{}
};

template <class T,class Ref,class Ptr>
struct ListIterator
{
	typedef ListNode<T> Node;//为了方便使用节点类，我们给它重命名一下
	typedef ListIterator<T, Ref,  Ptr>self;//原理同上
	ListIterator(Node* ptr)
		:_Node(ptr)
	{}
	Ref operator*()
	{
		return _Node->_val;
	}

	Ptr operator->()
	{
		return &_Node->val;
	 }
	self& operator++()
	{
		_Node = _Node->_last;
		return _Node;
	}

	self operator++(int)
	{
		Node* tmp = _Node;
		_Node = _Node->last;
		return tmp;
	}
	self operator--(int)
	{

		Node* tmp = _Node;
		_Node = _Node->_prev;
		return tmp;
	}
	self operator--()
	{
		_Node = _Node->_prev;
		return _Node;
	}
	bool operator==(self& s)
	{
		return _Node == s._Node;
	}
	bool operator!=(self& s)
	{
		return _Node != s._Node;
	}
	Node* _Node;
};
template<class T>
class List
{
public:
	typedef ListIterator<T, T&, T*> iterator;
	typedef ListIterator<T, const T&,const T*> const_iterator;
	typedef ListNode<T> Node;
	iterator begin()
	{
		return iterator(_head->_last);
	}
	const_iterator begin()const
	{
		return const_iterator(_head->_last);
	}
	iterator end()
	{
		return iterator(_head);
	}
	const_iterator end()const
	{
		return const_iterator(_head);
	}
	List(T val=T())
	:_head(new Node)
	{
		_head->_last = _head;
		_head->_prev = _head;
		_head->_val = val;
	}
	template <class InputIterator>
	List(InputIterator first, InputIterator last)
	{
		_head=new Node;
		_head->_last = _head;
		_head->_prev = _head;
		_head->_val = T();
		while (first != last)
		{
			push_back(*first);
			++first;
		}
	}

	~List()
	{
		clear();
		delete _head;
		_head = nullptr;
	}
	List(List<T>& l)
	{
		_head(new Node);
		_head->_last = _head;
		_head->_prev = _head;
		_head->_val = T();
		List<T>tmp(l.begin(), l.end());
		swap(tmp);
	}
	List<T>& operator=(List<T>l)
	{
		swap(l);
		return*this;
	}
	void intsert(iterator pos,T val)//原本在这个位置的节点向后移
	{
		Node* cur = pos._Node;
		Node* prev = cur->_prev;
		Node* NewNode = new Node(val);
		NewNode->_prev = prev;
		prev->_last = NewNode;
		NewNode->_last = cur;
		cur->_prev = NewNode;
	}
	void push_front(T val)
	{
		Node* NewNode = new Node(val);
		Node* last = _head->_last;
		NewNode->_prev = _head;
		NewNode->_last = last;
		last->_prev = NewNode;
		_head->_last = NewNode;
	}
	void  push_back(T val)
	{
		Node* NewNode = new Node(val);
		Node* tail = _head->_prev;
		tail->_last = NewNode;
		NewNode->_prev = tail;
		NewNode->_last = _head;
		_head->_prev = NewNode;
	}
	iterator erase(iterator pos)
	{
		assert(pos != end());
		Node* cur = pos._Node;
		Node* prev = cur->_prev;
		Node* last = cur->_last;
		prev->_last = last;
		last->_prev = prev;
		delete cur;
		return iterator(last);
	}
	void  pop_front()
	{
		erase(begin());
	}
	void pop_back()
	{
		erase(--end());
	}
	void clear()
	{
		Node* New = _head->_last;
		while (New != _head)
		{
			Node* News = New->_last;
			delete New;
			New = News;
		}
	}
	void swap(List<T>&l)
	{
		std::swap(_head,l._head);
	}
private:
	Node* _head;
};

 

总结

学习完list类，与之前相比，最大的收获就是迭代器的设计，同时也对多参数模板有了更深一步的了解，虽然过程艰辛，但是，List，over！

相信下一个难题也会被攻克

觉得有用的话，就点个赞支持一下吧😘😘😘

阅读全部

相关推荐

  7. 类模板与继承及成员、全局函数的实现

    2024-03-25 16:18:05       82 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-03-25 16:18:05       94 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-03-25 16:18:05       101 阅读

  9. 在Django里面运行非项目文件

    2024-03-25 16:18:05       82 阅读

  19. Python语言-面向对象

    2024-03-25 16:18:05       91 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-03-25 16:18:05       85 阅读

热门阅读

  2. 链表去重介绍

    2024-03-25 16:18:05       41 阅读

  3. 【机器学习300问】41、如果数据集中有少量带有标签，到底是选择异常检测还是有监督学习呢？

    2024-03-25 16:18:05       38 阅读

  7. [flask]响应数据+跳转页面

    2024-03-25 16:18:05       42 阅读

  9. 使用Docker搭建Convoy

    2024-03-25 16:18:05       39 阅读

  13. 深入探讨YUV图像处理：理论原理与OpenCV实践

    2024-03-25 16:18:05       41 阅读

  21. css样式几种定义方式

    2024-03-25 16:18:05       34 阅读

  22. 蓝桥杯每日一题（Dijkstra最短路算法）

    2024-03-25 16:18:05       44 阅读

  23. 【ARM 嵌入式 C 入门及渐进 12 --寄存器位清0和置位函数实现】

    2024-03-25 16:18:05       45 阅读

  25. git 提交空目录

    2024-03-25 16:18:05       47 阅读