探秘 C++ list：在复杂数据管理的编程世界里，它宛如灵动的魔法链条，高效实现元素频繁增删，有序维系数据秩序，无论是海量动态数据缓存、游戏角属性集处理，还是复杂任务调度编排

2025-07-27 20:03:15

探秘 C++ list：在复杂数据管理的编程世界里，它宛如灵动的魔法链条，高效实现元素频繁增删，有序维系数据秩序，无论是海量动态数据缓存、游戏角属性集处理，还是复杂任务调度编排 list的介绍及使用list的介绍list底层就是一个双向循环链表。forward_list底层是单链表，用法都差不多一样。list的使用 list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后

探秘 C++ list：在复杂数据管理的编程世界里，它宛如灵动的魔法链条，高效实现元素频繁增删，有序维系数据秩序，无论是海量动态数据缓存、游戏角属性集处理，还是复杂任务调度编排

list的介绍及使用

list的介绍

list底层就是一个双向循环链表。

forward_list底层是单链表，用法都差不多一样。

list的使用

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

list的构造

构造函数（ (ctructor)）	接口说明
list (size_type n, ct value_type& val = value_type())	构造的list中包含n个值为val的元素
list()	构造空的list
list (ct list& x)	拷贝构造函数
list (InputIterator ﬁrst, InputIterator last)	用[ﬁrst, last)区间中的元素构造 list

构造的list中包含n个值为val的元素

构造了10个1的元素

构造空的list

空构造，也会构造一个哨兵位节点，方便后面插入数值。

不管是空构造还是构造有元素的，都会构造一个哨兵位节点。

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

list<int> li;

拷贝构造函数

下面我们可以看到，li拷贝构造给li2

用[ﬁrst, last)区间中的元素构造 list

也就是用迭代器区间构造list

begin从li的第一个位置的元素开始，到end最后一个位置的元素，构造给li2

list iterator的使用

函数声明	接口说明
begin + end	返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin + rend	返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置

begin是在1这个位置，end是在哨兵位。

【注意】 1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动 2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动。

【begin+end】

下面从begin位置开始打印，end位置结束。

【rbegin+ rend】反向迭代器

begin就是指向最后一个位置的元素。

end就是指向第一个位置的元素。

list capacity

函数声明	接口说明
empty	检测list是否为空，是返回true，否则返回false
size	返回list中有效节点的个数

【empty】检测list是否为空

是空返回true，不是空就返回false.

下面我们可以看到，不是空返回false,就是0，是空返回true就是1.

【size 】返回list中有效节点的个数

下面我们可以看到，有效个数是7，就是有7个元素。

list element access

函数声明	接口说明
front	返回list的第一个节点中值的引用
back	返回list的最后一个节点中值的引用

【front】返回list的第一个节点中值的引用

下面我们可以看到，返回了第一个位置的元素。

【back 】返回list的最后一个节点中值的引用

下面我们可以看到，返回了最后的那个位置的元素。

list modiﬁers

函数声明	接口说明
push_front	在list首元素前插入值为val的元素
pop_front	删除list中第一个元素
push_back	在list尾部插入值为val的元素
pop_back	删除list中最后一个元素
insert	在list position 位置中插入值为val的元素
erase	删除list position位置的元素
swap	交换两个list中的元素
clear	清空list中的有效元素

【push_front】在list首元素前插入值为val的元素

我们可以看到，在首元素插入了99

【pop_front】删除list中第一个元素

下面删除了首元素

【push_back】在list尾部插入值为val的元素

下面在尾部插入99。

【pop_back】删除list中最后一个元素、

删除尾部的数据，可以看到把7删除了

【insert】在list position 位置中插入值为val的元素

下面，用find查询的位置，然后在位置前插入99

【erase】删除list position位置的元素

用find查询的位置，然后进行删除操作

【swap】交换两个list中的元素

下面li和li2交换了

【clear】清空list中的有效元素

我们可以看到清空了

list的迭代器失效

前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

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

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

list的模拟实现

模拟实现list

list.h

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

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;


namespace bit
{
	//双向链表的数据
	template<class T>
	struct list_node
	{
		T data;
		list_node<T>* _prev;
		list_node<T>* _next;

		list_node(ct T& x = T())
			:data(x)
			,_prev(nullptr)
			,_next(nullptr)
		{}
	};
	//迭代器
	template<class T, class Ref,class Pef>
	struct list_iterator
	{
		typedef list_node<T> ode;
		typedef list_iterator<T,Ref,Pef> self;
		ode* _node;

		list_iterator(ode* x)
			:_node(x)
		{}
		
		bool operator!=(ct self& x)
		{
			return _node != x._node;
		}

		Pef operator*()
		{
			return _node->data;
		}
		Ref operator->()
		{
			return &_node->data;
		}

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

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

	};

	迭代器
	//template<class T>
	//struct list_ct_iterator
	//{
	//	typedef list_node<T> ode;
	//	typedef list_ct_iterator<T> self;
	//	ode* _node;

	//	list_ct_iterator(ode* x)
	//		:_node(x)
	//	{}

	//	bool operator!=(ct self& x)
	//	{
	//		return _node != x._node;
	//	}

	//	ct T& operator*()
	// 	{
	//		return _node->data;
	//	}

	//	ct T* operator->()
	//	{
	//		return &_node->data;
	//	}

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

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

	//};


	//list类模版
	template<class T>
	class list
	{
		typedef list_node<T> ode;
	public:
		//typedef list_iterator<T> iterator;
		//typedef list_ct_iterator<T> ct_iterator;
		  
		typedef list_iterator<T,T,T> iterator;
		typedef list_iterator<T,ct T*,ct T&> ct_iterator;


		//哨兵位
		void add()
		{
			_head = new ode();
			_head->_prev = _head;
			_head->_next = _head;
		}
		iterator begin()
		{
			return _head->_next;
		}

		iterator end()
		{
			return _head;
		}

		ct_iterator begin()ct
		{
			return _head->_next;
		}

		ct_iterator end()ct
		{
			return _head;
		}




		list()
		{
			add();
		}
		//bit::list<int> v(10,1);
		list(size_t n,ct T& val = T())
		{
			add();
			for (size_t i = 0; i < n; i++)
			{
				push_back(val);
			}

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

		void clear()
		{
			auto i = begin();
			while (i != end())
			{
				i = erase(i);
			}
		}

		list<T>& operator=(list<T> v1)
		{
			swap(v1);
			return *this;

		}

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

		//头插
		void push_front(ct T& val)
		{
			insert(begin(),val);
		}
		

		//尾插
		void push_back(ct T& x)
		{
			/*ode* tmp = new ode(x);
			ode* kali = _head->_prev;

			kali->_next = tmp;
			_head->_prev = tmp;

			tmp->_prev = kali;
			tmp->_next = _head;*/

			insert(end(), x);
		}
		//头删
		void pop_front()
		{
			erase(begin());
		}

		//尾删
		void pop_back()
		{
			ode* pop = _head->_prev;
			erase(pop);
		}

		//指定位置插入
		iterator insert(iterator pos, ct T& val)
		{

			ode* fun = new ode(val);

			ode* next = pos._node;
			ode* prev = next->_prev;

			prev->_next = fun;
			fun->_prev = prev;

			next->_prev = fun;
			fun->_next = next;

			return iterator(fun);
		}
		//指定位置删除数据
		iterator erase(iterator pos)
		{
			assert(pos != end());


			ode* fun = pos._node;
			ode* next = fun->_next;
			ode* prev = fun->_prev;


			next->_prev = prev;
			prev->_next = next;
			delete fun;

			return iterator(next);

		}

	private:
		ode* _head;
	};
}

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

int main()
{
	bit::list<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back();
	v1.push_back(4);

	for (auto i : v1)
	{
		cout << i << " ";
	}
	cout << endl;

	bit::list<int> v2;
	v2 = v1;

	for (auto i : v1)
	{
		cout << i << " ";
	}
	cout << endl;
}

list的反向迭代器

通过前面例子知道，反向迭代器的++就是正向迭代器的--，反向迭代器的--就是正向迭代器的++，因此反向迭代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口进行包装即可。

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

template<class Iterator>
class ReverseListIterator
{
	// 注意：此处typename的作用是明确告诉编译器，Ref是Iterator类中的类型，而不是静态成员变量
		// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
		// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
public:
	typedef typename Iterator::Ref Ref;
	typedef typename Iterator::Ptr Ptr;
	typedef ReverseListIterator<Iterator> Self;
public:
	//
	// 构造
	ReverseListIterator(Iterator it) : _it(it) {}
	//
	// 具有指针类似行为
	Ref operator*() {
		Iterator temp(_it);
		--temp;
		return *temp;
	}
	Ptr operator->() { return &(operator*()); }
	//
	// 迭代器支持移动
	Self& operator++() {
		--_it;
		return *this;
	}
	Self operator++(int) {
		Self temp(*this);
		--_it;
		return temp;
	}
	Self& operator--() {
		++_it;
		return *this;
	}
	Self operator--(int)
	{
		Self temp(*this);
		++_it;
		return temp;
	}
	//
	// 迭代器支持比较
	bool operator!=(ct Self& l)ct { return _it != l._it; }
	bool operator==(ct Self& l)ct { return _it != l._it; }
	Iterator _it;
};

list与vector的对比

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

	vector	list
底层结构	动态顺序表，一段连续空间	带头结点的双向循环链表
随机访问	支持随机访问，访问某个元素效率O(1)	不支持随机访问，访问某个元素效率O()
插入和删除	任意位置插入和删除效率低，需要搬移元素，时间复杂度为O()，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低	任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1)
空间利用率	底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高	底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低
迭代器	原生态指针	对原生态指针(节点指针)进行封装
迭代器失效	在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效	插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响
使用场景	需要高效存储，支持随机访问，不关心插入删除效率	大量插入和删除操作，不关心随机访问

迭代器（单向迭代器-双向迭代器-随机访问迭代器）

单向迭代器

特点：

可读写：可以读取和修改指向的元素。
单向移动：只能向前移动，不能向后移动。
支持单步迭代：只能使用 ++ 操作符向前移动。

适用场景：

适用于单向链表（std::forward_list）等数据结构。

单向迭代器就是，只能往前遍历。

下面，i只能++往前走，不能i--往后走。

双向迭代器

特点：

可读写：可以读取和修改指向的元素。
双向移动：既可以向前移动，也可以向后移动。
支持单步迭代：可以使用 ++ 和 -- 操作符。

适用场景：

适用于双向链表（std::list）、树结构等数据结构。

下面我们可以看到，可以i++往前遍历，也可以i--往后遍历。

随机访问迭代器

特点：

可读写：可以读取和修改指向的元素。
支持随机访问：可以像指针一样进行算术运算，如 +, -, +=, -= 等。
支持比较运算符：可以比较两个迭代器的大小关系。

适用场景：

适用于数组、向量（std::vector）、字符串（std::string）等支持随机访问的数据结构。

随机访问就是，就是可以随机访问某个字符。

下面，v1.begin()+访问到4。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。原始发表：2025-01-12，如有侵权请联系 cloudcommunity@tencent 删除编程数据数据管理游戏任务调度

#感谢您对电脑配置推荐网 - 最新i3 i5 i7组装电脑配置单推荐报价格的认可，转载请说明来源于"电脑配置推荐网 - 最新i3 i5 i7组装电脑配置单推荐报价格

本文地址：http://www.dnpztj.cn/biancheng/1184414.html

本站网友美容美发品牌	27分钟前发表
致使原来迭代器失效
本站网友最大二维码	30分钟前发表
支持单步迭代：只能使用 ++ 操作符向前移动
本站网友润肺止咳的食物	19分钟前发表
一段连续空间带头结点的双向循环链表随机访问支持随机访问
本站网友大活络丸	26分钟前发表
还是复杂任务调度编排 list的介绍及使用list的介绍list底层就是一个双向循环链表

探秘 C++ list：在复杂数据管理的编程世界里，它宛如灵动的魔法链条，高效实现元素频繁增删，有序维系数据秩序，无论是海量动态数据缓存、游戏角属性集处理，还是复杂任务调度编排