前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
腾讯云架构师技术同盟
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP腾讯云架构师技术同盟
返回腾讯云官网
社区首页 >专栏 >模拟实现c++中的list模版

模拟实现c++中的list模版

作者头像
用户11458826
发布于 2025-01-23 16:57:36
发布于 2025-01-23 16:57:36
5000
代码可运行
举报
文章被收录于专栏：杀马特杀马特
运行总次数：0
代码可运行

一·list简述：

即相当于一个放入任意类型的一个容器，底层就是链表。即是与vector的区别。

二·库内常用接口函数使用：

这里简单介绍一下除了下面要实现的接口函数还有些其他接口函数：

1·reverse():

对于以前的vector和string，它们用的是算法库里的，故括号里还要传迭代器区间，而list库自己实现了，可以不传参：

代码语言：javascript
代码运行次数：0
复制
list<int> lt;
lt.emplace_back(1);
lt.emplace_back(2);
lt.emplace_back(3);
lt.emplace_back(4);

lt.reverse();
list<int>::iterator it = lt.begin();
it = lt.begin();
while (it != lt.end()) {
	cout << *it << " ";
	it++;
}

2.sort():

对于list库里的sort（）是默认升序。

代码语言：javascript
代码运行次数：0
复制
list<int> ltt;
ltt.emplace_back(5);
ltt.emplace_back(3);
ltt.emplace_back(7);
ltt.emplace_back(10);
ltt.sort();
list<int>::iterator itt = ltt.begin();
while (itt != ltt.end()) {
	cout << *itt << " ";
	itt++;
}

当然也可以也可以这样完成升降序：

同理，这里其实也可以不创建对象，直接匿名对象也可以。

3.merge():

即把两个list对象按升序拼接起来（前提是两个对象都是有序的，不是的话要提前给它sort一下），最后拼到前者对象，后者对象清空，如：

代码语言：javascript
代码运行次数：0
复制
list<int> lt;
lt.emplace_back(1);
lt.emplace_back(2);
lt.emplace_back(3);
lt.emplace_back(4);
list<int> ltt;
ltt.emplace_back(5);
ltt.emplace_back(3);
ltt.emplace_back(7);
ltt.emplace_back(10);
ltt.sort();
list<int>::iterator it = lt.begin();
lt.merge(ltt);
it = lt.begin();
while (it != lt.end()) {
	cout << *it << " ";
	it++;
}
cout << endl;

4.unique():

去重复操作，但是要求list对象要有序：

代码语言：javascript
代码运行次数：0
复制
///去重操作：
list<int> lt;
lt.emplace_back(1);
lt.emplace_back(1);
lt.emplace_back(1);
lt.emplace_back(2);
lt.unique();
list<int>::iterator it = lt.begin();
it = lt.begin();
while (it != lt.end()) {
	cout << *it << "";
	it++;
}
cout << endl;

5·remove():

删除链表中值为val的节点：

代码语言：javascript
代码运行次数：0
复制
//删除指定元素，只删除找到一个即可：
list<int> lt;
lt.emplace_back(5);
lt.emplace_back(2);
lt.emplace_back(4);
lt.emplace_back(2);
lt.remove(2);
list<int>::iterator it = lt.begin();
it = lt.begin();
while (it != lt.end()) {
	cout << *it << "";
	it++;
}

5.splice():

本意是粘连的意思，可以给某个位置前面粘连一个对象的链表也可以给某个位置前粘连任意一个对象的迭代器区间：

一个对象给另一个对象粘：

代码语言：javascript
代码运行次数：0
复制
list<int> lt;
lt.emplace_back(5);
lt.emplace_back(2);
lt.emplace_back(4);
lt.emplace_back(2);
list<int> ltt;
ltt.emplace_back(5);
ltt.emplace_back(3);
ltt.emplace_back(7);
ltt.emplace_back(10);
list<int>::iterator it = lt.begin();
lt.splice(++lt.begin(), ltt);
it = lt.begin();
while (it != lt.end()) {
	cout << *it << " ";
	it++;
}

给pos位置前粘一个迭代器区间：

代码语言：javascript
代码运行次数：0
复制
list<int> lt;
lt.emplace_back(5);
lt.emplace_back(2);
lt.emplace_back(4);
lt.emplace_back(2);
list<int> ltt;
ltt.emplace_back(5);
ltt.emplace_back(3);
ltt.emplace_back(7);
ltt.emplace_back(10);
list<int>::iterator it = lt.begin();
lt.splice(it, lt, ++lt.begin(), lt.end());
it = lt.begin();//这里会把242转移粘在5的前面，故要重新给begin赋值
while (it != lt.end()) {
		cout << *it << " ";
		it++;
	}

粘连别人的迭代器区间：

代码语言：javascript
代码运行次数：0
复制
list<int> lt;
lt.emplace_back(5);
lt.emplace_back(2);
lt.emplace_back(4);
lt.emplace_back(2);
list<int> ltt;
ltt.emplace_back(5);
ltt.emplace_back(3);
ltt.emplace_back(7);
ltt.emplace_back(10);
list<int>::iterator it = lt.begin();
lt.splice(++lt.begin(), ltt, ++ltt.begin(), ltt.end());
it = lt.begin();
while (it != lt.end()) {
		cout << *it << " ";
		it++;
	}

三·list的模拟实现相关函数接口：

框架构造：list是吧每个节点连接起来，故首先把节点封装成一个类，接着由于迭代器相当于节点指针，即双向迭代器，只能是++或者--无-，+即还要对迭代器去遍历链表，可以把迭代器封装也成一个类。如：

节点类：

代码语言：javascript
代码运行次数：0
复制
namespace li {
	template<class T>
	struct list_node {
		list_node* _pre;
		list_node* _next;
		T _val;
		list_node(const T _val = T())
			:_val(_val)
			, _pre(nullptr)
			, _next(nullptr) { }



	};

迭代器 类：

代码语言：javascript
代码运行次数：0
复制
template<class T,class ref,class ptr >
	struct list_iterator {
		typedef list_node<T> Node;
		Node* _node;

		list_iterator( Node* node)
			:_node(node)
		{}
};

它们没有资源产生和释放，故只用写所需要的构造函数即可。

这里的template<class T,class ref,class ptr >是为了少写一次const迭代器的类，而多加了对原来的类的模版参数可以实例化出const和普通的迭代器类。

list框架：

代码语言：javascript
代码运行次数：0
复制
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;
private:


		Node* _head;
		int _size;

	};

1.创建头结点和无参构造：

代码语言：javascript
代码运行次数：0
复制
void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_pre = _head;
			_size = 0;
		}

		list() {
			empty_init();

		}

由于后面等有参构造list的时候也是需要构造出头结点，故可以把它封装成一个empty_init函数。

2·有参构造：

代码语言：javascript
代码运行次数：0
复制
list( initializer_list<T> m)//这个模版化出的m对象可以想象成一个数组
		{
			empty_init();
			for (auto& e : m)
			{
				push_back(e);
			}
		}
代码语言：javascript
代码运行次数：0
复制
initializer_list<int> il = { 10, 20, 30 };
	li::list<int> llt(il);
	//拷贝构造：
	li::list<int>lt1({ 1,22,223 });//先是隐式类型转换生成的临时对象再拷贝构造给lt1
  //隐式类型转换：
	const li::list<int>&lt2={ 1,22,223 };//直接隐式类型转换生成临时对象，由于是给临时对象引用（起别名）故临时对象只能读不能写，故用const

这里可以用 initializer_list这个模版来进行{}的初始化。

3·拷贝构造：

代码语言：javascript
代码运行次数：0
复制
list(const list<T>& lt)
		{
			empty_init();//创建链表的头结点

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

4·赋值重载的现代版本实现：

代码语言：javascript
代码运行次数：0
复制
		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}
		list<T>& operator=(list<T> lt)//不是引用传参故不会改变lt；
		{
			swap(lt);
			return *this;
		}

5.析构函数：

代码语言：javascript
代码运行次数：0
复制
void clear()
		{
			auto it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}//利用迭代器遍历链表删除各个节点
		~list() {
			clear();
			delete _head;
			_head = nullptr;
		}

6·list的迭代器类模版内接口函数的实现：

代码语言：javascript
代码运行次数：0
复制
ref operator*() {

			return _node->_val;
		}
		ptr operator->() {
			return &(_node->_val) ;
		}
		list_iterator<T,ref, ptr> &operator++(int) {
			list_iterator<T,ref,ptr> tmp = *this;
			++*this;
			return tmp;
		}
		list_iterator<T,ref, ptr>&operator--(int) {
			list_iterator<T,ref,ptr> tmp = *this;
			--*this;
			return tmp;
		}
		list_iterator<T,ref, ptr>& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		list_iterator<T,ref, ptr>& operator--()
		{
			_node = _node->_pre;
			return *this;
		}

		bool operator!=(const  list_iterator<T,ref,ptr>& s) const
		{
			return _node != s._node;
		}

		bool operator==(const  list_iterator<T,ref,ptr>& s) const
		{
			return _node == s._node;
		}

这里需要说的也就是里面对->的重载运算符函数的实现，这样返回节点内数据的地址作用在哪？

其实是为了：如果这里面的val放的自定义类型如：

代码语言：javascript
代码运行次数：0
复制
struct AA {

	int a1 = 1;
	int a2 = 2;
};

这时候这个操作就可以直接访问到val里的a1，a2，而不用再有通过AA的对象再去访问a1和a2。

代码语言：javascript
代码运行次数：0
复制
li::list<AA> at;
	at.push_back(AA());
	at.push_back(AA());
	at.push_back(AA());
	at.push_back(AA());
	li::list<AA>::iterator ait = at.begin();

	 
	cout << (ait-> a1 )<<" ";//如果是自定义类型则迭代器（也就是节点的指针）可以直接访问到此自定义类型的变量。
	//如果没有这个重载：
	cout << ((ait._node)->_val.a1 )<< " ";
	//重载后把两个->省略成一个
	cout << (ait.operator->()->a1) << " ";

7·begin（）和end（）的实现：

这里是list直接访问的，故放在list类模版的函数里。

代码语言：javascript
代码运行次数：0
复制
iterator begin() {
			return _head->_next;//隐式类型转换，直接传递对应类的构造参数
		}
		iterator end() {
			return _head;
		}
		const_iterator begin() const
		{
			return _head->_next;
		}

		const_iterator end() const//对应的迭代器实例化出的普通和const类型
		{
			return _head;
		}

7.insert的接口函数的实现：

代码语言：javascript
代码运行次数：0
复制
iterator  insert(iterator pos, const T& x) {
			//在pos和pos前的位置插入数据，故先保存这两个位置。以防后面找不到，然后在连接指针
			Node* pre = pos._node->_pre ;
			Node* cur = pos._node;
			Node* pnode = new Node(x);
			pnode->_next = cur;
			cur->_pre = pnode;
			pre->_next = pnode;
			pnode->_pre = pre;
			_size++;
			return pnode;
		}

这里其实和vector的迭代器不一样，这里插入不会导致迭代器失效，因为它所指向的对象并没有改变，而只是在它前面插入新节点。

8.push_back和push_front的实现：

代码语言：javascript
代码运行次数：0
复制
void push_back(const T& x) {
			insert(end(), x);

		}

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

9·erase的接口函数的实现：

这里如果删除了就会导致迭代器失效，故要利用返回值接收再次使用。

代码语言：javascript
代码运行次数：0
复制
iterator erase(iterator pos) {
			assert(pos != end());
			Node* pre = pos._node->_pre;
			Node* next = pos._node->_next;
			delete pos._node ;
			pre->_next = next;
			next->_pre = pre;
			_size--;
			return next;

		}

10·pop_front和pop_back的实现：

代码语言：javascript
代码运行次数：0
复制
void pop_front() {
			erase(begin());
		}
		void pop_back() {
			erase(--end());

		}

11·size和empty的实现：

代码语言：javascript
代码运行次数：0
复制
size_t size() const
		{
			return _size;
		}

		bool empty() const
		{
			return _size == 0;
		}

12·front和back的实现：

代码语言：javascript
代码运行次数：0
复制
T& front() {
			return begin()._node->_val;
		}
		const T& front()const {
			return begin()._node->_val;
		}
		T& back() {
			return (--end())._node->_val;
		}
		const T& back()const {
			return --end()._node->_val;
		}//分别是拿到val可修改与不可修改

13·不同容器利用迭代器打印数据：

代码语言：javascript
代码运行次数：0
复制
//不同容器的打印
template<class Container>
void  con_print(const Container & con) {
	typename Container::const_iterator it = con.begin();//告诉未实例化的模版是类型
	//auto it = con.begin();
	while (it != con.end())
	{

		cout << *it << " ";
		++it;
	}
	cout << endl;

	
}

14.list实现代码汇总：

代码语言：javascript
代码运行次数：0
复制
#include<iostream>
#include<string>
#include<assert.h>
using namespace std;
namespace li {
	template<class T>
	struct list_node {
		list_node* _pre;
		list_node* _next;
		T _val;
		list_node(const T _val = T())
			:_val(_val)
			, _pre(nullptr)
			, _next(nullptr) { }



	};
	template<class T,class ref,class ptr >
	struct list_iterator {
		typedef list_node<T> Node;
		Node* _node;

		list_iterator( Node* node)
			:_node(node)
		{}
	
	
		ref operator*() {

			return _node->_val;
		}
		ptr operator->() {
			return &(_node->_val) ;
		}
		list_iterator<T,ref, ptr> &operator++(int) {
			list_iterator<T,ref,ptr> tmp = *this;
			++*this;
			return tmp;
		}
		list_iterator<T,ref, ptr>&operator--(int) {
			list_iterator<T,ref,ptr> tmp = *this;
			--*this;
			return tmp;
		}
		list_iterator<T,ref, ptr>& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		list_iterator<T,ref, ptr>& operator--()
		{
			_node = _node->_pre;
			return *this;
		}

		bool operator!=(const  list_iterator<T,ref,ptr>& s) const
		{
			return _node != s._node;
		}

		bool operator==(const  list_iterator<T,ref,ptr>& s) const
		{
			return _node == s._node;
		}

	};

	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;

		void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_pre = _head;
			_size = 0;
		}

		list() {
			empty_init();

		}
		list( initializer_list<T> m)//这个模版化出的m对象可以想象成一个数组
		{
			empty_init();
			for (auto& e : m)
			{
				push_back(e);
			}
		}

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

			for (auto& e : lt)
			{
				push_back(e);
			}
		}
		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}
		list<T>& operator=(list<T> lt)//不是引用传参故不会改变lt：
		{
			swap(lt);
			return *this;
		}
		void clear()
		{
			auto it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
		~list() {
			clear();
			delete _head;
			_head = nullptr;
		}
		iterator begin() {
			return _head->_next;//隐式类型转换，直接传递对应类的构造参数
		}
		iterator end() {
			return _head;
		}
		const_iterator begin() const
		{
			return _head->_next;
		}

		const_iterator end() const
		{
			return _head;
		}
		
		iterator  insert(iterator pos, const T& x) {
			//在pos和pos前的位置插入数据，故先保存这两个位置。以防后面找不到，然后在连接指针
			Node* pre = pos._node->_pre ;
			Node* cur = pos._node;
			Node* pnode = new Node(x);
			pnode->_next = cur;
			cur->_pre = pnode;
			pre->_next = pnode;
			pnode->_pre = pre;
			_size++;
			return pnode;
		}
		void push_back(const T& x) {
			insert(end(), x);

		}

		void push_front(const T& x) {
			insert(begin(), x);
		}
		iterator erase(iterator pos) {
			assert(pos != end());
			Node* pre = pos._node->_pre;
			Node* next = pos._node->_next;
			delete pos._node ;
			pre->_next = next;
			next->_pre = pre;
			_size--;
			return next;

		}

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

		}
		size_t size() const
		{
			return _size;
		}

		bool empty() const
		{
			return _size == 0;
		}


		// List Access
		T& front() {
			return begin()._node->_val;
		}
		const T& front()const {
			return begin()._node->_val;
		}
		T& back() {
			return (--end())._node->_val;
		}
		const T& back()const {
			return --end()._node->_val;
		}
	private:


		Node* _head;
		int _size;

	};
}



//不同容器的打印
template<class Container>
void  con_print(const Container & con) {
	typename Container::const_iterator it = con.begin();
	//auto it = con.begin();
	while (it != con.end())
	{

		cout << *it << " ";
		++it;
	}
	cout << endl;

	
}

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-01-23，如有侵权请联系 cloudcommunity@tencent.com 删除
list
对象
链表
c++
iterator

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

list
对象
链表
c++
iterator
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 一·list简述：
  • 二·库内常用接口函数使用：
  • 1·reverse():
  • 2.sort():
  • 3.merge():
  • 4.unique():
  • 5.splice():
  • 三·list的模拟实现相关函数接口：
  • 1.创建头结点和无参构造：
  • 2·有参构造：
  • 3·拷贝构造：
  • 4·赋值重载的现代版本实现：
  • 5.析构函数：
  • 6·list的迭代器类模版内接口函数的实现：
  • 7.insert的接口函数的实现：
  • 8.push_back和push_front的实现：
  • 9·erase的接口函数的实现：
  • 10·pop_front和pop_back的实现：
  • 11·size和empty的实现：
  • 12·front和back的实现：
  • 13·不同容器利用迭代器打印数据：
  • 14.list实现代码汇总：
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2025 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论