首页 > 其他分享 >【STL_list 模拟】——打造属于自己的高效链表容器

【STL_list 模拟】——打造属于自己的高效链表容器

时间：2024-11-03 11:46:19浏览次数：4  
标签：Node head STL list next 链表 prve newnode

一、list节点

​ list是一个双向循环带头的链表，所以链表节点结构如下：

	template<class T>
	struct ListNode
	{
		T val;
		ListNode* next;
		ListNode* prve;
		ListNode(int x)
		{
			val = x;
			next = prve = this;
		}
	};

二、list迭代器

2.1、list迭代器与vector迭代器区别

​ list迭代器与vector迭代器不一样，不能使用简单的原生指针了；

vector中迭代器可以使用原生指针，因为vector的存储空间是连续的，可以通过指针+/-/++/–找到下一个（上一个）位置；而list(链表)我们知道存储空间是不连续的，不能通过指针++/—找到下一个（上一个）节点；那我们就不能使用原生指针。

2.2、list迭代器实现

​ 既然原生指针不能满足我们的需求，那我们就要用其他的方法来实现迭代器，这时候类的封装的意义就体现出来了；我们只需要对原生指针进行封装，然后使用运算符重载来修改迭代器++/–这些行为，这样就可以满足我们的需求了。

具体代码如下：

	template<class T, class Ref, class Str>
	class list_iterator
	{
		typedef ListNode Node;
		typedef list_iterator iterator;
	public:
		list_iterator(Node* node)
		{
			_node = node;
		}
		//前置++
		iterator operator++()
		{
			Node tmp(_node);
			_node = _node->_next;
			return tmp;
		}
		//后置++
		iterator operator++(int)
		{
			_node = _node->_next;
			return *this;
		}
		//前置--
		iterator operator--()
		{
			Node tmp(_node);
			_node = _node->_prve;
			return tmp;
		}
		iterator operator++(int)
		{
			_node = _node->_prve;
			return *this;
		}
		bool operator==(const iterator& it)
		{
			return _node == it._node;
		}
		bool operator!=(const iterator& it)
		{
			return _node != it._node;
		}
		Ref operator*()
		{
			return _node->val;
		}
		Ptr operator->()
		{
			return &(_node->_val);
		}
	private:
		Node* _node;
	};

三、list实现

3.1、构造函数

在这里插入图片描述

先看一下list构造函数的接口

构造函数接口说明
list()默认构造函数，构造一个空的list
list (size_type n, const value_type& val =value_type())用n个val值构造list
list (InputIterator first, InputIterator last)还有一段迭代器区间初始化
list (const list& x)拷贝构造函数

​ 这里我们实现的list是带头双向循环链表，具体结构与之前的双向链表相同。

在构造之前，我们需要先构造一个头结点，这里就写一个函数 empty_init 来构造这个头结点。

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

默认构造函数

list()
{
	empty_init();
	_size = 0;
}

用n个val值构造

list(size_t n, const T& val)
{
	/*_head = new Node();
	_head->_next = _head;
	_head->_prve = _head;*/
	empty_init();
	for (size_t i = 0; i < n; i++)
	{
		Node* newnode = new Node(val);

		newnode->_next = _head->_next;
		newnode->_prve = _head->_next;
		_head->_next->_prve = newnode;
		_head->_next = newnode;
	}
	_size = n;
}

迭代器区间构造

​ 使用迭代器区间构造，这里复用一下后面的push_back直接尾插来构造。

template<class InputIterator>
list(InputIterator first, InputIterator last)
{
	empty_init();
	_size = 0;
	while (first != last)
	{
		push_back(*first);
		_size++;
	}
}
void push_back(const T& val)
{
	Node* newnode = new Node(val);
	newnode->_next = _head;
    newnode->_prve = _head->_prve;
	_head->_prve->_next = newnode;
	_head->_prve = newnode;
}

拷贝构造函数

​ 拷贝构造，这里直接复用上面迭代器构造即可。

		list(const list& l)
		{
			empty_init();
			list(l.begin(), l.end());
			_size = l.size();
		}

3.2、迭代器

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

​ 这里迭代器返回值，可以直接返回节点指针（因为单参数的构造函数支持隐式类型转换）。

3.3、Capacity

在这里插入图片描述
​ 主要就是empty和size（判断空和数据个数）

		//Capacity
		bool empty()
		{
			return _head == _head->_next;
		}
		size_t size()
		{
			/*size_t ret = 0;
			Node* ptail = _head->_next;
			while (ptail != head)
			{
				ret++;
				ptail = ptail->_next;
			}
			return ret;*/
			return _size;
		}

​ 这里遍历链表来计算数据个数，代价太大了，我们直接写一个成员变量，在初始化，插入和删除时修改，会方便很多。

3.4、增删查改

在这里插入图片描述

​ 这里增删查改就实现其中的一部分，其他的不太常用。

3.4.1、push_back、push_front、pop_back、pop_front

​ 头插尾插，头删尾删，对于list而言，只需要修改指针的指向；

void push_back(const T& val)
{
	Node* newnode = new Node(val);
	newnode->_next = _head;
	newnode->_prve = _head->_prve;
	_head->_prve->_next = newnode;
	_head->_prve = newnode;
	_size++;
}
void push_front(const T& val)
{
	Node* newnode = new Node(val);
	newnode->_next = _head->_next;
	newnode->_prve = _head;
	_head->_next->_prve = newnode;
	_head->_next = newnode;
	_size++;
}

//删
void pop_back()
{
	if (!empty())
	{
		Node* del = _head->_prve;
		_head->_prve->_prve->_next = _head;
		_head->_prve = _head->_prve->_prve;
		delete del;
		_size--;
	}
}
void pop_front()
{
	if (!empty())
	{
		Node* del = _head->_next;
		_head->_next->_next->_prve = _head;
		_head->_next = _head->_next->_next;
		delete del;
		_size--;
	}
}

3.4.2、insert

在这里插入图片描述

​ insert在指定位置插入数据，看它的参数列表，大概就知道，要在迭代器position 迭代器位置（之前）插入数据（1个或者n个），或者插入一段迭代器区间的数据。

//insert
void insert(iterator pos, const T& val)
{
	Node* newnode = new Node(val);
	Node* tmp = pos._node;
	newnode->_next = tmp;
	newnode->_prve = tmp->_prve;

	tmp->_prve->_next = newnode;
	tmp->_prve = newnode;
    ++_size;
}
void insert(iterator pos, size_t n, const T& val)
{
	for(size_t i = 0; i < n; i++)
	{
		Node* newnode = new Node(val);
		Node* tmp = pos._node;
		newnode->_next = tmp;
		newnode->_prve = tmp->_prve;

		tmp->_prve->_next = newnode;
		tmp->_prve = newnode;
	}
    _size+=n;
}
void insert(iterator pos, int n, const T& val)
{
	for(size_t i = 0; i < n; i++)
	{
		Node* newnode = new Node(val);
		Node* tmp = pos._node;
		newnode->_next = tmp;
		newnode->_prve = tmp->_prve;

		tmp->_prve->_next = newnode;
		tmp->_prve = newnode;
	}
}

这里需要注意：

​ 看到这里可能会疑惑，为什么实现了两个插入n个数据 的insert函数；

​ 因为，当数据类型是int时，下面模版实例化出的函数（iterator , int , int）比这里实现的(iterator , size_t , int)更加匹配；编译器就会去调用更加匹配的函数，就会出错。这里就是为了防止这种出错。

​ 插入迭代器的数据，与使用迭代器区间构造初始化相似，list只需改变指针指向即可。

		template<class InputIterator>
		void insert(iterator pos, InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				Node* newnode = new Node(*first);
				Node* tmp = pos._node;
				newnode->_next = tmp;
				newnode->_prve = tmp->_prve;

				tmp->_prve->_next = newnode;
				tmp->_prve = newnode;
				++first;
			}
		}

3.4.3、erase

​ erase删除一个节点，我们要修改前后节点的指针指向。

iterator erase(iterator pos)
{
	assert(pos != end());
	Node* del = pos._node;
	Node* next = del->_next;
	Node* prve = del->_prve;
	next->_prve = prve;
	prve->_next = next;
	delete del;
	return next;
}

​ 在我们删除节点之后，之前的迭代器就会失效，为了解决迭代器失效问题，我们就使用返回值，返回新的迭代器。

3.4.4、swap

​ 这里实现的list只有一个成员函数（头结点的指针），直接交换即可。

		void swap(list& l)
		{
			std::swap(_head, l._head);
		}

3.4.5、clear

​ clear函数，清理数据，（保留头结点）。

		//清除数据
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

3.5、析构函数

​ 析构函数相对就比较简单了，我们清理完数据，再释放头结点即可。

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

到这里，list的模拟实现就完成了；这里只是实现了其中的一部分内容，感兴趣的可以继续深入了解学习。

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws
ear函数，清理数据，（保留头结点）。

		//清除数据
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

3.5、析构函数

​ 析构函数相对就比较简单了，我们清理完数据，再释放头结点即可。

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

到这里，list的模拟实现就完成了；这里只是实现了其中的一部分内容，感兴趣的可以继续深入了解学习。

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws

标签：Node,head,STL,list,next,链表,prve,newnode
From： https://blog.csdn.net/LH__1314/article/details/143454671

相关文章

  • 【C语言学习】7步轻松掌握C语言链式结构，你也能成为高手！与数组说拜拜，链表你好
    ......
  • 单双链表（数组模拟）笔记
    单双链表（数组模拟）笔记如题，我们要使用数组来模拟链表这个数据结构区别于传统的结构体链表（动态链表）：structnode{ intvalue; structnode*next;//指向下一个节点的指针}user_define_name;//调用链表的别称数组模拟链表（静态链表）的速度更快，但是对于空间的优化不如动态链表......
  • LeetCode24:两两交换链表中的节点
    原题地址：.-力扣（LeetCode）题目描述给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。输入：head=[1,2,3,4]输出：[2,1,4,3]示例2：输入：head=[]输出：[]示例3：输入：head=[1]输出：[1]......
  • LeetCode25:K个一组翻转链表
    原题地址：.-力扣（LeetCode）题目描述给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需......
  • List类函数使用讲解及模拟实现
    一.List介绍    1.List是一个支持在任意位置进行插入和删除的序列式容器。    2.List底层实现时使用的是双向链表结构，每个节点之间都互不相干，通过指针进行前后结点的指向。    3.List的优点在于进行数据的插入和删除的时候，不需要去大量的挪动数据，效......
  • 拉取易仓API的亚马逊Listing数据-listing表现接口
    设计一个程序，按照api返回的json数据自动生成一张表，并且表的ID为xxxxxxxxxx，提供一个通用的接口：save_date_to_table_id，这个接口应该是自动判断存在的列的并集，然后按照id做insert操作或者是update操作。拉去亚马逊Listing表现数据接口代码如下： importdatetimeimportjsonimp......
  • 代码随想录一刷day6 （链表day2）（链表完结）
    24.两两交换链表中的节点分三步走；1.创建dummyhead2.三个指针 cur  t1 t23.  cur->next=t2;  t1->next=t2->next;  t2->t1->next; 最后让cur=t1;注意最后返回的是dummyhead-》next 而不是head；注意最后deletedummyhead19.删除链表的倒数第N个节点注......
  • frida 创建一个ArrayList实例
      //获取ArrayList和Integer类的引用varArrayListClass=Java.use("java.util.ArrayList");varIntegerClass=Java.use("java.lang.Integer");----------------//创建一个ArrayList实例vararrayList=ArrayListClass.$new();//遍历字节数......
  • 「Mac畅玩鸿蒙与硬件16」鸿蒙UI组件篇6 - List 和 Grid 组件展示数据列表
    List和Grid是鸿蒙开发中的核心组件，用于展示动态数据。List适合展示垂直或水平排列的数据列表，而Grid则适用于展示商品或图片的网格布局。本篇将展示如何封装组件，并通过按钮实现布局切换，提升界面的灵活性和用户体验。关键词List组件Grid组件数据展示自定义列......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99