当前位置： 首页 > article >正文

list容器（详解）

article 2025/2/4 14:13:46

 1. list的介绍及使用

1.1 list的介绍（双向循环链表）

https://cplusplus.com/reference/list/list/?kw=list（list文档介绍）

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。

4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。

1.2 list的使用（可以对照模拟实现看，重要的都有，后边模拟实现都会讲）

list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口。

1.2.1 list的构造

1.2.2 list iterator的使用

此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。

【注意】

1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动

2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

1.2.3 list capacity

1.2.4 list element access

1.2.5 list modifiers

list中还有一些操作，需要用到时大家可参阅list的文档说明。

1.2.6 list的迭代器失效

        注意，insert不会失效，迭代器依旧指向原来位置，erase会失效（删除后返回下一个地址），跟vector的迭代器失效类比，都是因为没有接收删除后的迭代器。insert不会失效，因为插入后返回新的节点地址，本身就指向新节点，不会失效

错误代码：

void TestListIterator1()
{
 int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
 list<int> l(array, array+sizeof(array)/sizeof(array[0]));
 auto it = l.begin();
 while (it != l.end())
 {
 // erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给
其赋值
 l.erase(it); 
 ++it;
 }
}

改正后：

// 改正
void TestListIterator()
{
 int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
 list<int> l(array, array+sizeof(array)/sizeof(array[0]));
 auto it = l.begin();
 while (it != l.end())
 {
 l.erase(it++); // it = l.erase(it);两种写法都对
 }
}

2. list的模拟实现

       要模拟实现list，必须要熟悉list的底层结构以及其接口的含义，通过上面的学习，这些内容已基本掌握，现在我们来模拟实现list。

2.1源码

test.cpp

#include<iostream>
#include<list>
#include<vector>
#include<algorithm>
using namespace std;

#include"List.h"

namespace jzy
{
	void test_list1()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

		list<int>::iterator it = lt.begin();
		while (it != lt.end())
		{
			//*it += 10;

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

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void test_list2()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);


		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		lt.push_back(5);
		lt.push_front(0);

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		lt.pop_back();
		lt.pop_front();

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		lt.clear();

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		lt.push_back(10);
		lt.push_back(20);

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void test_list3()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		list<int> copy(lt);
		for (auto e : copy)
		{
			cout << e << " ";
		}
		cout << endl;

		list<int> lt1;
		lt1.push_back(10);
		lt1.push_back(20);
		lt1.push_back(30);
		lt1.push_back(40);

		lt = lt1;
		for (auto e : copy)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void print_list(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			//*it += 10;

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

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void test_list4()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

		print_list(lt);


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

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

	struct AA
	{
		int _a1;
		int _a2;

		AA(int a1 = 1, int a2 = 1)
			:_a1(a1)
			, _a2(a2)
		{
		}
	};

	void test_list5()
	{
		list<AA> lt;
		AA aa1;
		lt.push_back(aa1);

		lt.push_back(AA());

		AA aa2(2, 2);
		lt.push_back(aa2);

		lt.push_back(AA(2, 2));

		list<AA>::iterator it = lt.begin();

		
			cout << (*it)._a1 << ":" << (*it)._a2 << endl;
			cout << it.operator*()._a1 << ":" << it.operator*()._a2 << endl;

			cout << it->_a1 << ":" << it->_a2 << endl;
			cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl;
	

	
		cout << endl;
	}


	
}


	int main()
	{
		jzy::test_list1();
		

		return 0;
	}
list.h
#pragma once
#include<assert.h>

namespace jzy
{
	template<class T>
	struct ListNode
	{
		ListNode<T>* _next;
		ListNode<T>* _prev;
		T _data;

		ListNode(const T& x = T())
			:_next(nullptr)
			, _prev(nullptr)
			, _data(x)
		{
		}
	};

	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef ListNode<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self;
		Node* _node;

		__list_iterator(Node* x)
			:_node(x)
		{
		}

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

		// it++
		self operator++(int)
		{
			
			self tmp(*this);

			_node = _node->_next;

			return tmp;
		}

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

		self operator--(int)
		{
			self tmp(*this);

			_node = _node->_prev;

			return tmp;
		}

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

		Ptr operator->()
		{
			return &_node->_data;
		}

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

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

	//template<class T>
	//struct __list_const_iterator
	//{
	//	typedef ListNode<T> Node;
	//	typedef __list_const_iterator<T> self;
	//	Node* _node;

	//	__list_const_iterator(Node* x)
	//		:_node(x)
	//	{}

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

	//	// it++
	//	self operator++(int)
	//	{
	//		self tmp(*this);

	//		_node = _node->_next;

	//		return tmp;
	//	}

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

	//	self operator--(int)
	//	{
	//		self tmp(*this);

	//		_node = _node->_prev;

	//		return tmp;
	//	}

	//	const T& operator*()
	//	{
	//		return _node->_data;
	//	}

	//	bool operator!=(const self& s)
	//	{
	//		return _node != s._node;
	//	}

	//	bool operator==(const self& s)
	//	{
	//		return _node == s._node;
	//	}
	//};

	template<class T>
	class list
	{
		typedef ListNode<T> Node;
	public:
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;

	


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

		iterator end()
		{
			return _head;
		}

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

		const_iterator end() const
		{
			return _head;
		}

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

		list()
		{
			empty_init();
		}

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

		~list()
		{
			clear();

			delete _head;
			_head = nullptr;
		}

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

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

		// lt1 = lt2;
		// list<T>& operator=(const list<T>& lt)
		/*list<T>& operator=(list<T>& lt)
		{
			if (this != &lt)
			{
				clear();
				for (const auto& e : lt)
				{
					push_back(e);
				}
			}
			return *this;
		}*/

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

		//list& operator=(list lt)
		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}

		void push_back(const T& x)
		{
			/*Node* newnode = new Node(x);
			Node* tail = _head->_prev;

			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;*/

			insert(end(), x);
		}

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

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

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

		// vector insert会导致迭代器失效
		// list会不会？不会
		iterator insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(x);

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

			//return iterator(newnode);
			return newnode;
		}

		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;

			return next;
		}

	private:
		Node* _head;
	};
}

注意list的const迭代器可以实现为一个类，也可以实现为模版参数实例化后的结果，一般实现为后者，会少写很多冗余代码

2.2 list的反向迭代器

  ReverseIterator.h
template<class Iterator,class Ref,class Ptr>
struct ReverseIterator
{
	typedef ReverseIterator<Iterator, Ref, Ptr> Self;
	Iterator cur;
	ReverseIterator(Iterator it)
		:cur(it)
	{ }
	Self& operator++()
	{
		--cur;
		return *this;
	}
	Ref operator*()
	{
		Iterator tmp = cur;
		--tmp;
		return *tmp;
	}
	Ptr operator->()
	{
		return &(operator*());
	}
	bool operator!=(const Self& s)
	{
		return cur != s.cur;
	}
};
List.h

在list类内部多了一些改动，将反向迭代器的类重命名，并且新加两个成员函数

test.cpp
#define _CRT_SECURE_NO_WARNINGS 1


#include<iostream>
#include<list>

using namespace std;

#include"List.h"

int main()
{
	jzy::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	jzy::list<int>::reverse_iterator rit = lt.rbegin();
	while (rit != lt.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;

	return 0;
}

可以看到反向迭代器起了作用，下面我来讲解反向迭代器的原理

反向迭代器可以理解成封装了正向迭代器，正向迭代器又封装了原生指针，反向迭代器++等价于正向迭代器--，反向迭代器解引用相当于正向迭代器--再解引用

因为反向迭代器的开始是正向迭代器结束位置，结束是正向的开始，所以反向迭代器要先--在解引用才是正确的值

反向迭代器的->也就是*拿到存放的值再取地址，和之前讲的是一个道理


		typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
		//typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;

		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}

		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}

反向迭代器在list类那里要多加一些东西，重命名反向迭代器这个类，当是普通反向迭代器的时候实例化iterator，T&,T*，当是const反向迭代器的时候，实例化参数是const_iterator,const T&,const T*

总体来讲，可以把反向迭代器看成适配器，当实例化参数是普通迭代器，会按照普通迭代器的行为进行操作，当参数是const时，会调用const的操作

3. list与vector的对比

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

list模拟实现讲解

定义结点结构体，结构体成员是前仆后继指针和元素data，还要写一个构造函数用来初始化结点

迭代器封装为一个类，类定义的对象存放每个节点的地址，也就是_node，相当于迭代器指针被封装成了一个类里存放，typedef是将类型重命名，将长的类型重命名为短的，记住类名不是类型，类名<类型>才是类型

这里模版有三个参数，第一个T是实例化类型，第二个和第三个参数是为了*和->，const类型会匹配T,constT& ,constT* ，正常类型会匹配T,T&,T*

这里将原生指针封装了一层包装在一个类里边，类定义的对象会通过操作指针前后移动来操作结点，解引用拿到对应结点的值，或者->拿到对应的地址

迭代器构造函数，当返回值是iterator类型时，会构造一个临时对象来操作

迭代器++，--，和日期类的原理类似，++it是当前指针往后走一步，this是it的地址，然后返回++之后的值，后置++，参数多传一个int就行，构造一个局部对象，指针向后走一步，返回走之前的值，迭代器--和++同理，无非是向前走

operator*是（*it）相当于拿到对应的值，我们就把it当成指针，*it当成解引用地址即可，这里是把指针封装到类里边，和前边string和vector的指针有所区分；->箭头相当于拿到存放对象的地址，当在list内部存放结构体时会用到

最简单的两个运算符重载，当判断不等于的时候会用到

list类要把上边两个类typedef后的类型写上去，方便等会用

迭代器的重载，当我们用begin（）或者end（）的时候，会调用这四个重载，普通对象调用普通迭代器，返回普通可修改指向对象的迭代器（这个对象可以用类名（），也可以直接返回Node*的结点指针（单参数的构造函数支持隐式类型转换），这两个写法都会生成一个临时对象，然后进行使用），const类型调用const迭代器，返回const不可修改指向对象的迭代器（慢慢理解这部分，其实没有想象的那么难）

list类的私有成员是_head，充当一个指针用来声明第一个哨兵位头结点

默认构造是初始化一个哨兵位头结点，结点内部存放前仆后继指针和data值（是某个类型的默认构造），然后让_head指向第一个哨兵位结点，并且_next和_prev都指向自己，完成哨兵位结点的初始化

析构函数先用clear清理，删除除了哨兵位结点的剩余存放有效数据的结点（释放了空间），最后释放哨兵位结点空间，_head置空就OK

拷贝构造，先初始化一个哨兵位结点，然后将要构造的对象内容依次给给e，尾插到新对象后边

赋值拷贝，先拷贝构造一个lt，将lt和新对象交换，lt是局部对象，出作用域会调用析构函数，新对象引用返回，完成赋值拷贝

insert插入，参数是迭代器指针（生成临时对象+2次拷贝构造）和要插入的值，cur指向要插入位置，prev存放要插入位置前边的指针，new一个新节点是要插入的新结点

三个指针相对位置是这样的，一般都是在某个位置之前插入，所以是这样的关系，然后按顺序链接这三个位置，前一个位置的后继指针和后一个位置的前驱指针都指向中间位置，最后返回插入节点的迭代器（单参数构造函数支持隐式类型转换）

删除很简单，不能删除哨兵位结点，找到要删除节点，记录要删除结点的前一个和后一个，链接两边的节点，最后释放要删除节点的空间，返回下一个节点的迭代器（会隐式类型转换成iterator类型的对象）

尾插，可以自己重新写逻辑，也可以复用insert逻辑，将第一个参数换成最后一个位置的迭代器，相当于在哨兵位节点之前插入，效果是一样的

头插，尾插，尾删是一样的，复用insert，erase逻辑就行

这部分在c语言实现数据结构链表那里讲的很详细了，想看的可以看看

代码样例讲解

这是一个很基础的尾插和打印对象逻辑，可以用第一个迭代器打印，也可以用第二个，范围for打印（范围for底层就是迭代器，无脑替换成迭代器进行打印），可以看到*it和it++，都是我们封装成类的功劳，原理很简单前面讲过

测试插入删除逻辑，可以看到不管是头插，头删，尾插，尾删都很清晰明了，clear是直接删除有效结点只剩哨兵位，所以打印不出来

可以看到，拷贝构造和赋值拷贝都完成了使命，前边讲的很详细，这里不再赘述

这里主要测试普通迭代器和const迭代器，各自调用各自，const迭代器不可修改对象，普通迭代器可以修改对象

最后一个样例，插入AA类对象，*it是拿到存放的结构体变量，.操作符访问结构体成员，拿到1:1，打印第二行是编译器会将*it转换成it.operator*()，效果是一样的

->箭头访问操作符会特殊处理一个箭头可以当做两个->->，并且编译器会转换成it.operator->()->_a1去访问，会特殊处理，这里当成特殊处理就好

以上就是我对list容器内容的讲解，很详细，欢迎大神交流！！！


http://www.kler.cn/a/531171.html

相关文章：

  • 51c嵌入式~电路~合集25
  • 前端力扣刷题 | 6：hot100之 矩阵
  • C++基础day1
  • QT知识点复习
  • Linux多路转接poll
  • 书生大模型实战营3
  • diffusion 训练trick 多横纵比设置
  • 算法总结-二分查找
  • 取模与加减乘除原理,模拟实现代码及相关公式推导
  • 【线程】基于阻塞队列的生产者消费者模型
  • 【C语言篇】“三子棋”
  • kubernetes（二）
  • 对比JSON和Hessian2的序列化格式
  • 前端 | JavaScript中的reduce方法
  • 【14】WLC3504 HA配置实例
  • 【股票数据API接口49】如何获取股票实时交易数据之Python、Java等多种主流语言实例代码演示通过股票数据接口获取数据
  • 自动化构建-make/Makefile 【Linux基础开发工具】
  • 本地快速部署DeepSeek-R1模型——2025新年贺岁
  • relational DB与NoSQL DB有什么区别？该如何选型？
  • C++ Primer 迭代器
  • Unity特效插件GodFX
  • 力扣经典题目之14. 最长公共前缀
  • Alibaba开发规范_异常日志之日志规约：最佳实践与常见陷阱
  • 最新功能发布！AllData数据中台核心菜单汇总
  • Win11使用VMware提示：平台不支持虚拟化的 Intel VT-x/EPT
  • 【BUUCTF逆向题】[WUSTCTF2020]level1、[GUET-CTF2019]re