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

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

article 2025/2/11 1:23:45

 🌟个人主页:落叶

 🌟当前专栏:C++专栏

目录

list的介绍及使用

list的介绍

list的使用 

list的构造

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

 构造空的list

拷贝构造函数

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

list iterator的使用 

【begin+end】

【rbegin+ rend】反向迭代器

 list capacity

【empty】检测list是否为空

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

 list element access

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

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

 list modifiers

【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中的有效元素

 list的迭代器失效

 list的模拟实现

模拟实现list

list.h

list的反向迭代器

list与vector的对比

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

单向迭代器

双向迭代器 

 随机访问迭代器

list的介绍及使用

list的介绍

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

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

list的使用 

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

list的构造

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

构造了10个1的元素

 构造空的list

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

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

list<int> li;
拷贝构造函数

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

 用[first, 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 modifiers

函数声明接口说明
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查询3的位置，然后在3位置前插入99

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

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

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

下面li和li2交换了

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

我们可以看到清空了

 list的迭代器失效

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

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);
   }
}

 list的模拟实现

模拟实现list
list.h
#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(const T& x = T())
			:data(x)
			,_prev(nullptr)
			,_next(nullptr)
		{}
	};
	//迭代器
	template<class T, class Ref,class Pef>
	struct list_iterator
	{
		typedef list_node<T> Node;
		typedef list_iterator<T,Ref,Pef> self;
		Node* _node;

		list_iterator(Node* x)
			:_node(x)
		{}
		
		bool operator!=(const 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_const_iterator
	//{
	//	typedef list_node<T> Node;
	//	typedef list_const_iterator<T> self;
	//	Node* _node;

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

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

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

	//	const 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> Node;
	public:
		//typedef list_iterator<T> iterator;
		//typedef list_const_iterator<T> const_iterator;
		  
		typedef list_iterator<T,T,T> iterator;
		typedef list_iterator<T,const T*,const T&> const_iterator;


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

		iterator end()
		{
			return _head;
		}

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

		const_iterator end()const
		{
			return _head;
		}




		list()
		{
			add();
		}
		//bit::list<int> v(10,1);
		list(size_t n,const 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(const T& val)
		{
			insert(begin(),val);
		}
		

		//尾插
		void push_back(const T& x)
		{
			/*Node* tmp = new Node(x);
			Node* 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()
		{
			Node* pop = _head->_prev;
			erase(pop);
		}

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

			Node* fun = new Node(val);

			Node* next = pos._node;
			Node* 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());


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


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

			return iterator(next);

		}

	private:
		Node* _head;
	};
}

test.cpp

int main()
{
	bit::list<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	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的反向迭代器

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

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!=(const Self& l)const { return _it != l._it; }
	bool operator==(const Self& l)const { return _it != l._it; }
	Iterator _it;
};

list与vector的对比

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

vectorlist

底

层

结

构

动态顺序表，一段连续空间 带头结点的双向循环链表

随

机

访

问

支持随机访问，访问某个元素效率O(1) 不支持随机访问，访问某个元 素效率O(N)

插

入

和

删

除

任意位置插入和删除效率低，需要搬移元素，时间 复杂度为O(N)，插入时有可能需要增容，增容： 开辟新空间，拷贝元素，释放旧空间，导致效率更 低 任意位置插入和删除效率高， 不需要搬移元素，时间复杂度 为O(1)

空

间

利

用

率

底层为连续空间，不容易造成内存碎片，空间利用 率高，缓存利用率高 底层节点动态开辟，小节点容 易造成内存碎片，空间利用率 低，缓存利用率低

迭

代

器

原生态指针对原生态指针(节点指针)进行 封装

迭

代

器

失

效

在插入元素时，要给所有的迭代器重新赋值，因为 插入元素有可能会导致重新扩容，致使原来迭代器 失效，删除时，当前迭代器需要重新赋值否则会失 效 插入元素不会导致迭代器失 效，删除元素时，只会导致当 前迭代器失效，其他迭代器不 受影响

使

用

场

景

需要高效存储，支持随机访问，不关心插入删除效 率 大量插入和删除操作，不关心 随机访问

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

单向迭代器

特点：

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

适用场景：

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

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

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

双向迭代器 

特点：

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

适用场景：

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

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

 随机访问迭代器

特点：

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

适用场景：

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

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

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

 


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

相关文章：

  • 【SQL server】关于SQL server彻底的卸载删除。
  • 增量hdfs数据追平
  • 学习数据结构（8）双向链表
  • RabbitMq入门
  • MyBatis面试题解析
  • C 移位运算符
  • 网络通信小白知识扫盲（五）
  • deepseek本地部署-linux
  • 设计模式实战运用之模板方法模式
  • 算法兵法全略
  • 链表专题-01
  • Delphi语言的云计算
  • 【免费】2011-2020年各省长途光缆线路长度数据
  • Linux 调用可执行程序
  • pytest-xdist 进行多进程并发测试
  • 网络安全 架构 网络安全架构师考试
  • Listener监听器和Filter过滤器
  • 【真一键部署脚本】——一键部署deepseek
  • 【练习】PAT 乙 1046 划拳
  • 【如何掌握CSP-J 信奥赛中的深搜算法】
  • 索引失效的14种常见场景
  • YONBIP后端环境搭建-IDEA
  • 3D数字化营销：重塑家居电商新生态
  • 对极几何方法——2D图片特征点估计运动
  • DeepSeek大模型本地部署实战
  • 【数据结构中链表常用的方法实现过程】