首页 > 其他分享 >List类函数使用讲解及模拟实现

List类函数使用讲解及模拟实现

时间：2024-11-02 17:20:39浏览次数：6  
标签：const List list front ls 讲解 push include 模拟

一.List介绍

        1.List是一个支持在任意位置进行插入和删除的序列式容器。

        2.List底层实现时使用的是双向链表结构，每个节点之间都互不相干，通过指针进行前后结点的指向。

        3.List的优点在于进行数据的插入和删除的时候，不需要去大量的挪动数据，效率更高。

        4.List的缺陷就是List并不是使用一段连续的空间存储，所以它并不支持随机访问。

二.List的构造

        1.list ()

                第一种构造函数可以简化为这种形式，主要的作用就是构造出一个空的链表。

#include<iostream>
#include<list>
using namespace std;
int main()
{
	list<int> ls;
	return 0;
}

        注意在使用list类定义出一个对象时，list底层是使用模板来定义的，所以需要用<>来声明节点存储内容的类型。

        2.list(size_t n,const value_type& val=value_type())

                 该构造函数的含义为，将定义出的对象用n个内容为val的数据进行初始化，因为val有缺省参数，所以传参后使用传参的数值，不传参就使用默认的数值。

#include<iostream>
#include<list>
using namespace std;
int main()
{
	list<int> ls1(5);
	for (auto e : ls1)
	{
		cout << e << " ";
	}
	cout << endl;
	list<int> ls2(5, 1);
	for (auto e : ls2)
	{
		cout << e << " ";
	}
	return 0;
}

        3.list(const list& x)

        该构造函数为拷贝构造，作用为使用另外一个list容器去构造当前list容器。

#include<iostream>
#include<list>
using namespace std;
int main()
{
	list<int> ls1(5, 1);
	list<int> ls2(ls1);
	for (auto e : ls2)
	{
		cout << e << " ";
	}
	return 0;
}

        4.list(Inputiterator first,Inputiterator last)

        该构造函数的含义为使用同种或者其他类型的迭代器进行构造当前迭代器，Inputiterator在list底层实现中是使用模板实现的，支持各种类型的迭代器进行构造。

#include<iostream>
#include<list>
#include<vector>
using namespace std;
int main()
{
	vector<int> vi(5, 1);
	list<int> ls1(vi.begin(),vi.end());
	for (auto e : ls1)
	{
		cout << e << " ";
	}
	return 0;
}

三.list中迭代器iterator的使用

        在前面两篇文章中，string的迭代器和vector的迭代器在底层实现时实际上就是指针的typedef，但是在list中，由于空间并不是连续的所以无法用指针++去访问到下一个结点，所以在list的底层实现中，list的iterator被包装成了一个类，同时重载了++等运算符，但是使用方式依旧和指针相差无几。

        begin()： 返回容器开头位置的迭代器。

        end()：返回容器末尾的下一个位置的迭代器。

#include<iostream>
#include<list>
#include<vector>
using namespace std;
int main()
{
	vector<int> vi;
	vi.push_back(1);
	vi.push_back(2);
	vi.push_back(3);
	vi.push_back(4);
	vi.push_back(5);
	list<int> ls1(vi.begin(),vi.end());
	list<int>::iterator l1 = ls1.begin();
	list<int>::iterator l2 = ls1.end();
	while (l1 != l2)
	{
		cout << *l1 << " ";
		l1++;
	}
	return 0;
}

          

        rbegin()和rend()以及cbegin()和cend()的用法同vector一致。

四.list中一些函数的使用

        1.reference front()和const_reference front()const

        该函数的主要作用是返回首节点内容的引用，有无const修饰的区别在于返回的引用支不支持修改。

#include<iostream>
#include<list>
#include<vector>
using namespace std;
int main()
{
	vector<int> vi;
	vi.push_back(1);
	vi.push_back(2);
	vi.push_back(3);
	vi.push_back(4);
	vi.push_back(5);
	list<int> ls1(vi.begin(), vi.end());
	for (auto e : ls1)
	{
		cout << e << " ";
	}
	cout << endl << ls1.front() << endl;
	ls1.front() = 2;
	for (auto e : ls1)
	{
		cout << e << " ";
	}
	return 0;
}

    

        2.reference back()和const_reference back()const

        该函数的作用是返回list容器最后一个节点的引用。

#include<iostream>
#include<list>
#include<vector>
using namespace std;
int main()
{
	vector<int> vi;
	vi.push_back(1);
	vi.push_back(2);
	vi.push_back(3);
	vi.push_back(4);
	vi.push_back(5);
	list<int> ls1(vi.begin(), vi.end());
	for (auto e : ls1)
	{
		cout << e << " ";
	}
	cout << endl << ls1.back() << endl;
	ls1.back() = 2;
	for (auto e : ls1)
	{
		cout << e << " ";
	}
	return 0;
}

        

        3.bool empty()const

        该函数的作用为返回一个bool数值，判断链表是否为空。

#include<iostream>
#include<list>
#include<vector>
using namespace std;
int main()
{
	vector<int> vi;
	vi.push_back(1);
	vi.push_back(2);
	vi.push_back(3);
	vi.push_back(4);
	vi.push_back(5);
	list<int> ls1(vi.begin(), vi.end());
	cout << ls1.empty();
	return 0;
}

        4.void push_front(const value_type& val) 

        头插！

#include<iostream>
#include<list>
using namespace std;
int main()
{
	list<int> ls;
	ls.push_front(1);
	ls.push_front(2);
	ls.push_front(3);
	ls.push_front(4);
	ls.push_front(5);
	for (auto e : ls)
	{
		cout << e << " ";
	}
	return 0;
}

        5.void pop_front()

        头删！

#include<iostream>
#include<list>
using namespace std;
int main()
{
	list<int> ls;
	ls.push_front(1);
	ls.push_front(2);
	ls.push_front(3);
	ls.push_front(4);
	ls.push_front(5);
	for (auto e : ls)
	{
		cout << e << " ";
	}
	cout << endl;
	ls.pop_front();
	for (auto e : ls)
	{
		cout << e << " ";
	}
	return 0;
}

        6.void push_back(const value_type& val) 

        尾插！

#include<iostream>
#include<list>
using namespace std;
int main()
{
	list<int> ls;
	ls.push_front(1);
	ls.push_front(2);
	ls.push_front(3);
	ls.push_front(4);
	ls.push_front(5);
	for (auto e : ls)
	{
		cout << e << " ";
	}
	cout << endl;
	ls.push_back(6);
	for (auto e : ls)
	{
		cout << e << " ";
	}
	return 0;
}

        7.void pop_back()

        尾删！

#include<iostream>
#include<list>
using namespace std;
int main()
{
	list<int> ls;
	ls.push_front(1);
	ls.push_front(2);
	ls.push_front(3);
	ls.push_front(4);
	ls.push_front(5);
	for (auto e : ls)
	{
		cout << e << " ";
	}
	cout << endl;
	ls.pop_back();
	for (auto e : ls)
	{
		cout << e << " ";
	}
	return 0;
}

        8.size_t size()const

        该函数的作用为返回有效节点的个数。

#include<iostream>
#include<list>
using namespace std;
int main()
{
	list<int> ls;
	ls.push_front(1);
	ls.push_front(2);
	ls.push_front(3);
	ls.push_front(4);
	ls.push_front(5);
	for (auto e : ls)
	{
		cout << e << " ";
	}
	cout << endl << ls.size();
	return 0;
}

        9.iterator insert(iterator position,const value_type& val)

        该insert函数的作用为在迭代器为position的位置插入一个节点，同时返回插入节点位置的迭代器。

#include<iostream>
#include<list>
using namespace std;
int main()
{
	list<int> ls;
	ls.push_front(1);
	ls.push_front(2);
	ls.push_front(3);
	ls.push_front(4);
	ls.push_front(5);
	for (auto e : ls)
	{
		cout << e << " ";
	}
	cout << endl;
	ls.insert(++ls.begin(), 10);
	for (auto e : ls)
	{
		cout << e << " ";
	}
	return 0;
}

        10.iterator erase(iterator position) / iterator erase(iterator first,iterator last)

        前一个erase函数函数的作用为删除迭代器position位置的节点，后一个函数的作用为删除迭代器first和迭代器last之间的所有结点。

#include<iostream>
#include<list>
using namespace std;
int main()
{
	list<int> ls;
	ls.push_front(1);
	ls.push_front(2);
	ls.push_front(3);
	ls.push_front(4);
	ls.push_front(5);
	for (auto e : ls)
	{
		cout << e << " ";
	}
	cout << endl;
	ls.erase(ls.begin());
	for (auto e : ls)
	{
		cout << e << " ";
	}
	cout << endl;
	ls.erase(++ls.begin(), ls.end());
	for (auto e : ls)
	{
		cout << e << " ";
	}
	return 0;
}

 

        11. void swap(list& x)

        该函数的作用为交换调用链表和参数链表x的所有结点。

#include<iostream>
#include<list>
using namespace std;
int main()
{
	list<int> ls1;
	ls1.push_front(1);
	ls1.push_front(2);
	ls1.push_front(3);
	ls1.push_front(4);
	ls1.push_front(5);
	list<int> ls2;
	ls2.push_front(6);
	ls2.push_front(7);
	ls2.push_front(8);
	ls2.push_front(9);
	for (auto e : ls1)
	{
		cout << e << " ";
	}
	cout << endl;
	for (auto e : ls2)
	{
		cout << e << " ";
	}
	cout << endl;
	ls1.swap(ls2);
	for (auto e : ls1)
	{
		cout << e << " ";
	}
	cout << endl;
	for (auto e : ls2)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}

        12.void clear()

        该函数的作用为清除list中的所有节点。

#include<iostream>
#include<list>
using namespace std;
int main()
{
	list<int> ls1;
	ls1.push_front(1);
	ls1.push_front(2);
	ls1.push_front(3);
	ls1.push_front(4);
	ls1.push_front(5);
	for (auto e : ls1)
	{
		cout << e << " ";
	}
	cout << endl;
	ls1.clear();
	for (auto e : ls1)
	{
		cout << e << " ";
	}
	return 0;
}

 五.list中的迭代器失效 

         在list中，所谓的迭代器失效指的就是定义出来的迭代器所指向的节点无效，在vector中，插入删除节点时，数据会发生移动，会导致一些迭代器指向了不是其应该指向的位置，从而导致迭代器失效。

        在list中，迭代器失效也是这个道理。但是较vector一段连续的空间不同的是，list是一段双向循环的链表，节点与节点之间只有逻辑关系并没有空间关系，所以一个迭代器失效的时候，并不会导致其他迭代器失效。

        所以通常情况下，删除一个节点会导致一个迭代器失效，而插入节点并不会导致迭代器失效。

六.list的模拟实现

        1.节点类的模拟实现

        由于list是一个双向链表，所以每一个节点都必须包含一个数据项data，两个指针分别指向前后节点。

template<class T>
	class ListNode
	{
	public:
		ListNode<T>* prev;
		ListNode<T>* next;
		T data;
		ListNode(const T& val = T())//构造函数
			:prev(nullptr)
			, next(nullptr)
			, data(val)
		{}
	};

        2.迭代器的模拟实现

         list的迭代器与vector不同，并不是由原生指针进行的指向，并不能支持++等操作，所以为了实现迭代器的功能，我们选择使用一个类进行封装。

        并在迭代器类中完成迭代器所应该支持的各项功能。

template<class T,class Ref,class Ptr>
	class ListIterator
	{
	public:
		typedef ListNode<T>* PNode;
		typedef ListIterator<T, Ref, Ptr> Self;
		ListIterator(PNode pnode = nullptr)
			:_pNode(pnode)
		{}
		ListIterator(const Self& x)
			:_pNode(x._pNode)
		{}
		Ref operator*()
		{
			return _pNode->data;
		}
		Ptr operator->()
		{
			return &(_pNode->data);
		}
		Self operator++()
		{
			_pNode = _pNode->next;
			return *this;
		}
		Self operator++(int)
		{
			Self temp(*this);
			_pNode = _pNode->next;
			return temp;
		}
		Self operator--()
		{
			_pNode = _pNode->prev;
			return *this;
		}
		Self operator--(int)
		{
			Self temp(*this);
			_pNode = _pNode->prev;
			return temp;
		}
		bool operator!=(const Self& x)
		{
			return _pNode != x._pNode;
		}
		bool operator==(const Self& x)
		{
			return _pNode == x->_pNode;
		}
		PNode _pNode;
	};

        （1）迭代器模板为何会有三个参数

                迭代器分为普通迭代器和const迭代器，给迭代器加const的作用为使其指向的内容无法进行修改，而不是迭代器本身无法修改，所以不能够直接在模板前面加const。

                而迭代器加const的目的是为了使其指向的内容无法修改，也就是迭代器内部封装的一些功能返回值必须要是const T*或者const T&的方式，这样迭代器指向的内容就无法进行修改，但是对封装的内容只在返回值不同时，根据c++的命名规则并不能完成重载。

                所以进行需要三个模板参数，在后续list的模拟实现时，普通迭代器定义时，模板参数传T*和T&，而const迭代器定义时，模板参数传const T*和const T&，如此以来就自动对应上了所应该返回的权限类型。

        3.list模拟实现总代码

#pragma once
namespace wangfish
{
	template<class T>
	class ListNode
	{
	public:
		ListNode<T>* prev;
		ListNode<T>* next;
		T data;
		ListNode(const T& val = T())//构造函数
			:prev(nullptr)
			, next(nullptr)
			, data(val)
		{}
	};
	template<class T,class Ref,class Ptr>
	class ListIterator
	{
	public:
		typedef ListNode<T>* PNode;
		typedef ListIterator<T, Ref, Ptr> Self;
		ListIterator(PNode pnode = nullptr)
			:_pNode(pnode)
		{}
		ListIterator(const Self& x)
			:_pNode(x._pNode)
		{}
		Ref operator*()
		{
			return _pNode->data;
		}
		Ptr operator->()
		{
			return &(_pNode->data);
		}
		Self operator++()
		{
			_pNode = _pNode->next;
			return *this;
		}
		Self operator++(int)
		{
			Self temp(*this);
			_pNode = _pNode->next;
			return temp;
		}
		Self operator--()
		{
			_pNode = _pNode->prev;
			return *this;
		}
		Self operator--(int)
		{
			Self temp(*this);
			_pNode = _pNode->prev;
			return temp;
		}
		bool operator!=(const Self& x)
		{
			return _pNode != x._pNode;
		}
		bool operator==(const Self& x)
		{
			return _pNode == x->_pNode;
		}
		PNode _pNode;
	};
	template<class T>
	class list
	{
	public:
		typedef ListNode<T> Node;
		typedef Node* PNode;
		typedef ListIterator<T, T&, T*> iterator;
		typedef ListIterator<T, const T&, const T*> const_iterator;
	private:
		PNode _pHead;
		void CreatHead()
		{
			_pHead = new Node;
			_pHead->next = _pHead;
			_pHead->prev = _pHead;
		}
	public:
		list()
		{
			CreatHead();
		}
		list(int n, const T& value = T())
		{
			CreatHead();
			for (int i = 0; i < n; i++)
			{
				push_back(value);
			}
		}
		template<class Iterator>
		list(Iterator first, Iterator last)
		{
			CreatHead();
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}
		list(const list& x)
		{
			CreatHead();
			list<T> temp(x.cbegin(), x.cend());
			swap(temp);
		}
		list& operator=(list<T> x)
		{
			swap(x);
			return *this;
		}
		~list()
		{
			clear();
			delete _pHead;
			_pHead = nullptr;
		}
		iterator begin()
		{
			return iterator(_pHead->next);
		}
		iterator end()
		{
			return iterator(_pHead);
		}
		const_iterator cbegin()const
		{
			return const_iterator(_pHead->next);
		}
		const_iterator cend()const
		{
			return const_iterator(_pHead);
		}
		size_t size()
		{
			int count = 0;
			PNode temp = _pHead->next;
			while (temp != _pHead)
			{
				temp = temp->next;
				count++;
			}
			return count;
		}
		bool empty()
		{
			return _pHead->next == _pHead->prev ? 1 : 0;
		}
		T& front()
		{
			return _pHead->next->data;
		}
		const T& front()const
		{
			return _pHead->next->data;
		}
		T& back()
		{
			return _pHead->prev->data;
		}
		const T& back()const
		{
			return _pHead->prev->data;
		}
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		void pop_front()
		{
			erase(begin());
		}
		void push_back(const T& x)
		{
			insert(end(), x);
		}
		void pop_back()
		{
			erase(--end());
		}
		iterator insert(iterator position, const T& x)
		{
			PNode temp = new Node(x);
			PNode pos = position._pNode;
			temp->prev = pos->prev;
			temp->next = pos;
			pos->prev->next = temp;
			pos->prev = temp;
			return iterator(temp);
		}
		iterator erase(iterator position)
		{
			PNode temp = position._pNode;
			PNode _prev = temp->prev;
			PNode _next = temp->next;
			_prev->next = _next;
			_next->prev = _prev;
			delete temp;
			return iterator(_next);
		}
		void clear()
		{
			PNode temp = _pHead->next;
			PNode ntemp;
			while (temp != _pHead)
			{
				ntemp = temp->next;
				delete temp;
				temp = ntemp;
			}
			_pHead->next = _pHead;
			_pHead->prev = _pHead;
		}
		void swap(list<T>& x)
		{
			std::swap(_pHead, x._pHead);
		}
		
	};
}

        

标签：const,List,list,front,ls,讲解,push,include,模拟
From： https://blog.csdn.net/2301_81245562/article/details/143255764

相关文章

  • 多校A层冲刺NOIP2024模拟赛17
    多校A层冲刺NOIP2024模拟赛17T1、网格首先看上去很麻烦，但是最终所有的式子都可以写成几个数的积相加的形式，那么我们只要处理数（拼接起来）、数的积以及积的和。那么我们维护三个变量，第一个是$x$，表示最后一个积前面所有的数和，第二个是$y$，表示目前的积，第三个是z，表......
  • CW 11.02 模拟赛 FSYo T2
    算法看到交换,这里有一个套路:确定最终的形态后,交换次数即为逆序对个数我们直接设\(f_{i,j,k,0/1/2}\)表示\(3\)种颜色填到哪里了，最后一个是什么颜色，逆序对数最少是多少转移分最后一个是什么颜色讨论关于\(O(1)\)求逆序对的方法:if(i==0&&a)f[a][b][......
  • 拉取易仓API的亚马逊Listing数据-listing表现接口
    设计一个程序，按照api返回的json数据自动生成一张表，并且表的ID为xxxxxxxxxx，提供一个通用的接口：save_date_to_table_id，这个接口应该是自动判断存在的列的并集，然后按照id做insert操作或者是update操作。拉去亚马逊Listing表现数据接口代码如下： importdatetimeimportjsonimp......
  • 基于微信小程序的大学生兼职平台的设计与实现(源码+springboot+uinapp+部署文档+讲解
    收藏关注不迷路！！......
  • CW 11.02 模拟赛 FSYo T1
    题面自出题挂个pdf题面下载算法暴力可能的答案只有\(O(n^2)\)个,考虑每个答案\(\rm{check}\)是\(O(n\logn)\)的总时间复杂度\(O(n^3\logn)\)/*O(answer*n*logn),即O(n^3logn)的算法,预期60pts*//*对于每一种可能的答案,首先对于每一个点,计算......
  • 2024.11.02模拟赛
    挂了至少30分！！不——开——心——钢哥说，大家要休息好，于是模拟赛晚点，变成了3小时3道题。T1打的正解(但没调出来版)，T2T3打的暴力(但全挂了版)，预计总分120+，但实际总分80。小小总结一下：昨晚多睡了一小时，今天思路确实感觉更清晰了(但也有可能是因为题目不难……)。但今天时间没分配......
  • 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组件数据展示自定义列......
  • 113java ssm springboot基于微信小程序的剧本杀游玩一体化平台系统剧本预约（源码+文档+
      文章目录系列文章目录前言一、详细视频演示二、项目部分实现截图三、技术栈后端框架springboot前端框架vue持久层框架MyBaitsPlus系统测试四、代码参考源码获取前言......
  • 11.2 炼石模拟赛
    T1贪心即可。T2考虑贪心。观察1不能出玩偶的机子应该最后修。所有钦定不出玩偶的机子都是平凡的，就是假在这里了！观察2所有人一起修机是最优的。观察3对于所有钦定出玩偶的机子，应该按照\(b\)数组从小到大排序后修理。有以上的观察，不难发现应该按照\(b\)数组排序。......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99