首页 > 其他分享 >【STL】模拟实现list

【STL】模拟实现list

时间：2024-10-15 12:19:13浏览次数：10  
标签：node 结点 const iterator STL list 模拟 指针

目录

list需要实现的接口

结点类的创建

迭代器类的实现

构造函数

++运算符的重载

--运算符的重载

!=运算符重载和==运算符重载

operator*

operator->

list的模拟实现

构造函数

拷贝构造函数

 赋值运算符重载函数

析构函数

迭代器相关函数

begin和end

front和back

push_front和push_back   

pop_front和pop_back

其他函数

size

clear

empty

swap

list需要实现的接口

namespace cl
{
	//模拟实现list当中的结点类
	template<class T>
	struct _list_node
	{
		//成员函数
		_list_node(const T& val = T()); //构造函数

		//成员变量
		T _val;                 //数据域
		_list_node<T>* _next;   //后继指针
		_list_node<T>* _prev;   //前驱指针
	};

	//模拟实现list迭代器
	template<class T, class Ref, class Ptr>
	struct _list_iterator
	{
		typedef _list_node<T> Node;
		typedef _list_iterator<T, Ref, Ptr> self;

		_list_iterator(node* node);  //构造函数

		//各种运算符重载函数
		self operator++();
		self operator--();
		self operator++(int);
		self operator--(int);
		bool operator==(const self& s) const;
		bool operator!=(const self& s) const;
		Ref operator*();
		Ptr operator->();

		//成员变量
		Node* _node; //一个指向结点的指针
	};

	//模拟实现list
	template<class T>
	class list
	{
	public:
		typedef _list_node<T> node;
		typedef _list_iterator<T, T&, T*> iterator;
		typedef _list_iterator<T, const T&, const T*> const_iterator;

		//默认成员函数
		list();
		list(const list<T>& lt);
		list<T>& operator=(const list<T>& lt);
		~list();

		//迭代器相关函数
		iterator begin();
		iterator end();
		const_iterator begin() const;
		const_iterator end() const;

		//访问容器相关函数
		T& front();
		T& back();
		const T& front() const;
		const T& back() const;

		//插入、删除函数
		void insert(iterator pos, const T& x);
		iterator erase(iterator pos);
		void push_back(const T& x);
		void pop_back();
		void push_front(const T& x);
		void pop_front();

		//其他函数
		size_t size() const;
		void clear();
		bool empty() const;
		void swap(list<T>& lt);

	private:
		Node* _head; //指向链表头结点的指针
        size_t _szie;
	};
}

结点类的模拟实现：

list在底层中，就是以带头双向循环链表实现的

所以实现list我们首先的创建一个结点类。

该结点类需要三个成员变量：

1. 数据

2. 上一个结点的指针

3.下一个结点的指针

结点类的创建

_list_node

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

	list_node(list_node<T> val = T())
		:_next(nullptr)
		,_prev(nullptr)
		,_val(val)
	{}
};

在结点类中我们需要一个构造函数来帮我们完成结点以及数据的初始化，因为结点类需要被_list_iterator和list使用，所以这里我们使用struct

迭代器类的实现

之前string和vector我们都没说需要实现迭代器类，为什么list需要实现一个迭代器类呢？

因为string和vector对象都将其数据存储在了一块连续的内存空间，我们通过指针的自增自减以及解引用操作等一系列操作，就可以对相应位置的数据进行操作，所以string和vector当中的迭代器就是原生指针

对于list来说，它的构成并不是一块连续的空间，它的结点在内存中的位置是随机的，我们不能通过结点指针的自增自减以及解引用操作对相应结点的数据进行操作

迭代器的意义是，让使用者不必在意容器的底层实现原理，可以用简单统一的方式对容器内数据进行访问

因为迭代器·结点指针的行为不能满足迭代器定义，那么我们可以对这个结点指针进行封装，对结点指针的各种运算符进行重载，使得我们可以像使用string和vector当中的迭代器一样去使用list当中的迭代器

迭代器类的模板参数说明

_list_iterator<class T, class Ref, class Ptr>

在list类中，我们typedef了两种类型的模板类，分别实现的是const 迭代器和非 const 迭代器

typedef _list_iterator<T, T&, T*> iterator
typedef _list_iterator<T, const T&, const T*> const_ierator

从这里就可以看出，Ref是引用类型，Ptr是指针类型

当我们使用不同迭代器时编译器就会根据模板来实例化出一个普通迭代器，当我们使用const迭代器时，编译器就会实例化出一个const迭代器对象

若没有设计这三种模板参数，那么就不能很好的区分普通迭代器和const迭代器

构造函数

迭代器类实际上就是对结点指针进行了封装，成员变量只有一个，那就是结点指针，其构造函数直接根据所给结点指针构造出一个迭代器对象即可

_list_iterator(Node* node)
	:_node(ndoe)
{}

++运算符的重载

前置++，作用是让结点指针指向后面一个位置，然后返回自增的结点指针即可

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

对于后置++，我们需要记录结点指针当前的位置，让结点指针向指向后一个结点，然后返回自增前的结点指针即可

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

注意：self是当前迭代器对象的类型：

_list_iterator<class T, class Ref, class Ptr>

--运算符的重载

前置--，作用是让结点指针指向前面一个位置，然后返回自减的结点指针即可

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

对于后置--，我们需要记录结点指针当前的位置，让结点指针向指向前一个结点，然后返回自减前的结点指针即可

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

!=运算符重载和==运算符重载

使用!= , ==运算符比较两个迭代器的时候，其实我们比较的是两个迭代器是否指向相同的结点指针，或者指向不同的结点指针

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

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

operator*

当我们使用解引用操作符时，是想得到该位置的数据内容，所以我们直接返回当前结点指针所指向的数据即可，但是这里需要解引用返回，得到数据之后，我们后面可能会对这个数据进行修改

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

operator->

指向运算符重载我们只需要返回数据的地址就可以了

Ptr operator->()  
{
	return &_node->val
}

但是看到这里，你可能觉得有点问题

这里应该是两个箭头去访问it，第一个->调用指向运算符重载函数，返回一个指针，然后再通过指针加指向运算符去访问对象当中的变量

但是一个地方出现两个箭头可读性太差了，为了增加可读性，编译器做了优化处理，优化了一个箭头

list的模拟实现

list是一个带头双向循环链表

构造函数

将初始化操作进行封装，后续会多次使用到，创建一个指针结点_head，并且让前驱指针和后驱指针指向自己即可完成初始化

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

list()
{
	empty_init();
}

拷贝构造函数

 创建一个新头结点_head，使前驱指针和后驱指针指向自己，遍历lt对象，将lt的数据通过尾插的方式给新的容器

list(const list<T>& lt)
{
	empty_init();

    //这里加引用提高效率，减少拷贝
    //加const是防止e不被篡改
	for (const auto& e : lt)
	{
		push_back(e);
	}
}

 赋值运算符重载函数

传统写法：

		list<T>& opertor=(const list<T>& lt)
		{
			if (*this != &lt)
			{
				clear();//清空容器

				for (const auto& e : lt)
				{
					push_back(e);
				}
			}

		return *this;
		}

现代写法：

这个写法代码量较少，首先利用编译器机制，故意不使用引用接收参数，通过编译器自动调用list的拷贝构造函数生成一个临时对象，使用这个临时对象给新容器进行交换即可完成操作，结束之后lt会调用析构函数销毁

//现代写法：
list<T>& opertor = (list<T> lt)
{
	swap(lt);

return *this;
}

析构函数

使用clear函数清理容器当中的数据，然后将头结点释放，最后将头指针置空

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

迭代器相关函数

begin和end

begin()迭代器指向第一个元素，end()迭代器指向末尾元素的后一个元素

iterator begin()
{
	//隐式类型转换
	// return _head;
	//强制类型转换
	return iterator(_head->_next);
}

iterator end()
{
	//隐式类型转换
	return _head;
	//强制类型转换
	//return iterator(_head);
}

以上两种方式都可以

第一种是Node*类型对iterator的强制类型转换

第二种是Node*类型对itreator的隐式类型转换

还有const类型的迭代器

const_iterator end() const
{
	//隐式类型转换
	// return _head->prev;
	//强制类型转换
	return iterator(_head);
}

const_iterator begin() const
{
	//隐式类型转换
	// return _head;
	//强制类型转换
	return iterator(_head->_next);
}

front和back

//获取尾部元素
T& back() const
{
	return *(end() - 1);
}
//获取头部元素
T& front() const
{
	return *begin();
}

//获取尾部元素
const T& back() const
{
	return *(end() - 1);
}
//获取头部元素
const T& front() const
{
	return *begin();
}

push_front和push_back   

pop_front和pop_back

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

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

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

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

插入，删除函数

insert

pos位置前插入新结点

先通过所给迭代器得到该位置出的结点指针cur，然后通过cur指针找到前一个位置的结点指针prev

然后根据所给val的值建立一个新结点指针，然后实现和prve，cur的双向连接连接

iterator insert(iterator pos, const T& val)
{
	//在pos位置前插入,保存pos前面的地址，以防找不到
	Node* cur = pos->_node;
	Node* prev = cur->_prev;
	Node* newnode = new Node(val);

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

	newnode->_prev = prev;
	prev ->_next  = newnode;

	++_size;

	//返回插入结点的地址,更新迭代器，以免迭代器失效
	return newnode;
}

erase

先根据所给迭代器得到该位置处的结点指针cur，通过cur指针找到前一个位置的结点prev和后一个位置的结点next，然后释放cur，最后将prev与next两个结点连接起来

iterator erase(iterator pos)
{
	assert(pos != end());
	Node* cur = pos._node
	Node* Prev = cur->prev;
	Node* Next = cur->next;

	Prev->next = next;
	Next->_prev = prev;

	delete cur;
	--_size;

	return pos;
}

其他函数

size

这里size的设计是，创建_size成员，使用增加结点的函数（例：push_back insert时）时，对_size进行++处理，进行删除操作时_size做--操作，即_size就是当前结点个数

size_t size() const
{
	return _size;
}

clear

清理链表，删除所有结点，erase涉及迭代器失效问题，这里的处理方案是，让erase返回下一个结点的指针，不断去更新lt.

clear这里不能给clear加const，加上const了，就代表给我需要删除的对象加上了const，*this就不能进行删除操作了

	void clear()
	{
		iterator it = begin();
		while (it != end())
		{
			//接收下一个位置的指针,避免迭代器失效
			it = erase(it);
		}

		_size = 0;
	}

empty

判断链表是否为空

bool empty()
{
	return begin() == end();
}

swap

我们访问的是标准库里面的swap，所有需要再swap前面加上::(域作用限定符)

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

标签：node,结点,const,iterator,STL,list,模拟,指针
From： https://blog.csdn.net/m0_73634434/article/details/142857487

相关文章

  • 最详细！如何实现数组和List之间的转换？（含详细代码解析，面试题拓展）
            数组和List都是我们平时工作，或者主动学习中经常使用的数据结构，在项目中难免会出现需要将其相互转换的场景，同时也正因为此，面试也偶尔会被问到。本文将从其调用的方法，以及其原理、特点展开，希望能让各位读者有所收获，码海无涯，愿与大家共勉。1，数组转换为List1，使用......
  • ReorderableList
    目录简介常用委托事件代码示例简介列表重写的数据类，一般使用在Editor下常用委托事件委托名作用drawElementCallback用于绘制list里的每个elementdrawHeaderCallback用于绘制headerelementHeightCallback用于设置每个element的高度onAddCallbackelemen......
  • 1014 CW 模拟赛 D.进化
    题面挂个pdf题面下载算法分析题目发现,一次进化等效于:在\(a\)两端加\(0\)对于\(i\in[1,n],a_i\leftarrowa_{i-1}\oplusa_{i+1}\)于是猜测在\(k\)次操作之后有\(a_i\leftarrowa_{i+k}\oplusa_{i-k}\)代入计算后发现这个式子显然错误,原因......
  • STL.string(上)
    stringstring类string类构造string类对象的容量操作size和lengthmax_sizeappend小总结下size、capacity、append、operator+=resizereserve初识迭代器附录1.vs下string结构的说明（解释前文为什么capacity是16而不是别的）由于string创始初期没有参照导致的冗余问题，这......
  • ArrayList源码分析（底层数据结构，成员变量，构造方法）以及面试题（基于JDK1.8）
    要分析Arraylist,我们首先要从它的底层数据结构实现出发，再结合其底层源码，可能能让读者理解的更加深刻一点。1，底层数据结构（数组）Arraylist底层是基于动态数组实现的。数组是一种使用连续储存空间储存相同数据类型的线性数据结构。面试题1为什么数组索引从0开始不从1开始？分......
  • 2024/10/14 模拟赛总结
    \(0+100+40+0=140\)，怎么都会T3啊#A.char令\(dp_{i,j}\)为已经考虑了文本串前\(i\)位且将所有*填入了字符，匹配了模式串的前\(j\)位的方案总数转移显然，若第\(i\)位不是*，则只有这一位和模式串相等才会有答案，即\(dp_{i,j}=\begin{cases}dp_{i-1,j-1}&s_i=t_k\\0&......
  • csp-s模拟11
    赛时rank11，T1100pts，T217pts，T30pts，T40pts，T510pts这场模拟赛就是糖，告诉我题目难度不按升序排列就是除了T1我都不会呗。玩水(water)签成了，还签了个首切？定义一个形如\(\begin{matrix}A*\\*\\end{matrix}\)的为一个角，角的位置为A的位置。有解的时候就是两个角相邻或......
  • 『模拟赛』CSP-S模拟11
    Rank地狱场，一般A.玩水(water)签。发现\(n\le1000\)，\(T\le10\)，\(\mathcal{O(Tn^2)}\)可过，所以简单考虑。我写的好像是dp？为每个点开一个大小为26的状态，表示从哪个字母转移而来的方案数，到该点的全部合法方案数即为\(\max_{i\in\left[0,25\right]}\cnt_i\)。由于是......
  • 「模拟赛」CSP-S 模拟 11（T2 超详细）
    比赛链接A.玩水(water)签到。发现如果要找两条路径的话，能找到的充要条件是存在一个点的上方和左方的字母相同。（即使两条走过的点截然不同的路径也符合，这时终点会成为这个点）。即存在一个位置\((i,j)\)使得\(s_{i-1,j}=s_{i,j-1}\)，我们称位置\((i,j)\)是好位置。扩展到三......
  • 2024.10.13 模拟赛
    2024.10.13模拟赛T1「KDOI-10」商店砍价赛时直接口胡出一个错误的贪心。一开始的想法是按照\(v[i]\)排序，然后假设输入的长度为\(n\)位。那么对于排序后\(n-5\)位直接选择操作一。对于剩下的，直接bdfs所有情况选答案，复杂度\(O(n\logn)\)。貌似可行，结果随便一个数据......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99