一， list概念

C++ STL list 容器详解

基本定义
list 是标准模板库（STL）提供的双向链表实现，属于序列式容器。它以泛型模板方式设计，支持存储任意类型（包括内置类型和用户自定义类）。例如：

list<int> intList;       // 存储整数的链表
list<string> strList;    // 存储字符串的链表

核心特性

• 高效增删元素：在任何位置插入或删除元素的时间复杂度为 O(1)，仅需调整相邻节点的指针。
• 不支持随机访问：必须通过迭代器顺序访问元素，访问第 N 个元素的时间复杂度为 O(N)。

与其他容器对比

• vector：连续内存，随机访问高效（O(1)），但中间插入/删除效率低（O(N)）。
• list：非连续内存，随机访问效率低（O(N)），但插入/删除高效（O(1)）。

列表成员函数分类表格

类别	函数名	描述
构造/析构	constructor	构造列表
	destructor	列表析构函数
	operator=	赋值操作
迭代器	begin	返回指向起始位置的迭代器
	end	返回指向末尾位置的迭代器
	rbegin	返回指向反向起始位置的迭代器
	rend	返回指向反向末尾位置的迭代器
	cbegin	返回指向起始位置的常量迭代器
	cend	返回指向末尾位置的常量迭代器
	crbegin	返回指向反向起始位置的常量迭代器
	crend	返回指向反向末尾位置的常量迭代器
容量	empty	检查容器是否为空
	size	返回容器大小
	max_size	返回容器最大可能大小
元素访问	front	访问第一个元素
	back	访问最后一个元素
修改器	assign	分配新内容到容器
	emplace_front	在起始位置构造并插入元素
	push_front	在起始位置插入元素
	pop_front	删除第一个元素
	emplace_back	在末尾位置构造并插入元素
	push_back	在末尾位置插入元素
	pop_back	删除最后一个元素
	emplace	在指定位置构造并插入元素
	insert	插入元素
	erase	删除元素
	swap	交换内容
	resize	调整容器大小
	clear	清空容器内容
操作	splice	将元素从一个列表转移到另一个列表
	remove	删除具有特定值的元素
	remove_if	删除满足条件的元素
	unique	删除重复值
	merge	合并已排序的列表
	sort	对容器中的元素进行排序
	reverse	反转元素的顺序

常用操作

定义与初始化

list<int> l1;                     // 空链表
list<int> l2(10, 1);              // 10 个值为 1 的元素
vector<int> v{1, 2, 3};
list<int> l3(v.begin(), v.end()); // 通过迭代器范围构造
list<int> l4(l3);                 // 拷贝构造

插入与删除

l1.push_front(0);    // 头部插入元素
l1.push_back(2);     // 尾部插入元素
l1.insert(++l1.begin(), 1); // 在第二个位置插入 1
l1.pop_front();      // 删除头部元素
l1.pop_back();       // 删除尾部元素
l1.erase(l1.begin()); // 删除指定位置元素

元素访问

int first = l1.front(); // 获取首元素
int last = l1.back();   // 获取尾元素

大小与容量

int size = l1.size();   // 元素数量
bool isEmpty = l1.empty(); // 判断是否为空
l1.resize(5);           // 调整大小为 5
l1.clear();             // 清空所有元素

迭代器操作

for (auto it = l1.begin(); it != l1.end(); ++it) {
    cout << *it << " "; // 顺序遍历
}

二，内容新增

        实际list就是我们在数据结构学习的双链表的增删改查，但是在c++中实现有一个新知识：迭代器的实现，vector和string我们都学习了迭代器，但是vector和string是数组指针可以直接访问节点的数据，list链表指针访问不了，所以我们要新增加一个知识迭代器的实现。

其中我们可以先理解以下内容(不理解也没有什么关系，后面继承会讲)：

这个图是继承关系比如（Bidirectional继承了Forward特性，好比一个儿子继承了父亲的东西，儿子可以使用父亲的东西，但是父亲不能使用访问儿子东西（这个是比喻不用骂我））

前向迭代器（Forward Iterator）

前向迭代器支持单向遍历，只能从容器头部向尾部移动，适用于单次线性访问的场景。常见应用包括链表（如 std::forward_list）和需要顺序读取的数据结构。例如，遍历未排序的日志文件时，只需单向读取每条记录。

双向迭代器（Bidirectional Iterator）

双向迭代器支持前向和后向移动（如 ++ 和 -- 操作），适用于需要双向遍历的容器。典型应用包括 std::list 和 std::set。在需要反向检查或修改数据的场景（如撤销操作的历史记录）中，双向迭代器尤为实用。

随机访问迭代器（Random Access Iterator）

随机访问迭代器支持直接跳转到任意位置（如 +n 或 [] 操作），时间复杂度为 O(1)。常见于连续内存容器（如 std::vector 和 std::deque）。适用于需要高效随机访问的场景，例如快速排序算法或数值计算中的矩阵元素访问。

输入迭代器（Input Iterator）

输入迭代器仅支持单向读取数据，且每个元素只能读取一次。适用于一次性输入流（如 std::istream_iterator）。典型场景包括从文件或网络流中读取数据，例如逐行解析 CSV 文件。

输出迭代器（Output Iterator）

输出迭代器仅支持单向写入数据，适用于单向输出流（如 std::ostream_iterator）。常见于数据导出或流式处理，例如将计算结果写入文件或传输到外部设备

三，list和veorct区别

特性	list	vector
底层结构	双向链表	动态数组
内存分配	非连续内存，节点分散存储	连续内存，支持随机访问
插入/删除效率	O(1)（已知迭代器位置）	O(n)（需移动后续元素）
随机访问效率	O(n)（需遍历）	O(1)（直接通过下标访问）
迭代器失效	插入/删除操作不影响其他迭代器	插入/删除可能导致所有迭代器失效
空间开销	每个元素额外存储前后指针，占用更多空间	仅存储元素，空间利用率高
扩容机制	无扩容概念，按需动态分配节点	容量不足时重新分配内存并拷贝元素
适用场景	频繁插入/删除，无需随机访问	需要快速随机访问，较少插入/删除

关键差异说明

内存连续性
vector的数据存储在连续内存块，适合CPU缓存预取；list的节点分散在内存中，访问局部性较差。

性能权衡
vector的随机访问速度快，但中间插入/删除成本高；list在任何位置插入/删除高效，但查找元素需线性遍历。

迭代器稳定性
vector在增删元素后，原有迭代器可能失效；list的迭代器除非指向被删除元素，否则保持有效。

容量管理
vector需预留容量（capacity）以减少扩容次数；list无预留空间概念，每次插入动态分配节点。

四，list实现

1,节点结构体

因为list是一个带头双向循环链表这个节点有：访问下一个的指针，访问上一个指针和存放数据

c++中struct和类没有区别一定要写构造，如果没有构造默认构造可能达不到预期，可能会报错。

	template <class T>
	struct ListNode
	{
		ListNode(const T& val = T())
			:_val(val),
			pre(nullptr),
			next(nullptr)
		{

		}
		struct ListNode* pre;
		struct ListNode* next;
		T _val;
	};

2,迭代器

迭代器这里难度就上来了，你要理解iterator和const_iterator的哪里不同。

这里的const_iterator不是const iterator如果是这样子节点不能访问下一个节点，这里的Ref是引用（reference），Ptr是指针(pointer)

如果没有Ref修饰operator*(),是用T&和const T&这里会是虚假的const_iterator，这个_val是可以改变的。

template<class T,class Ref,class Ptr>
struct ListIterator
{
	typedef struct ListNode<T> Node;

	typedef struct ListIterator<T, Ref, Ptr> Self;
	typedef Node* PNode;
	ListIterator(PNode pNode = nullptr)
		:_pNode(pNode)
	{
		
	}
	
	Ref operator*()
	{
		return _pNode->_val;
	}
	Ptr operator->()
	{
		return &_pNode->_val;
	}
	Self& operator++()
	{
		_pNode = _pNode->next;
		return *this;
	}
	Self& operator++(int)
	{
		_pNode = _pNode->next;
		return *this;
	}
	Self& operator--()
	{
		_pNode = _pNode->pre;
		return *this;
	}
	Self operator--(int)
	{
		_pNode = _pNode->pre;
		return *this;
	}
	bool operator!=(const Self& l)
	{
		return l._pNode != _pNode;
	}
	bool operator==(const Self& l)
	{
		return l._pNode == _pNode;
	}
	PNode _pNode;
};

3,增删改查

这里相信大家数据结构学习过list，增删改查对大家都不是难事。

template <class T>
class list1
{
	typedef struct ListNode<T> Node;
	typedef Node* PNode;

	
public:
	typedef ListIterator<T, T&, T*> iterator;
	typedef ListIterator<T, const T&, const T*> const_iterator;

	list1()
	{
		PHead = new Node;
		PHead->pre = PHead->next = PHead;
	}
	list1(int n, const T& value = T())
	{
		PHead = new Node;
		PHead->pre = PHead->next = PHead;
		while (n--)
		{
			this->push_back(value);
		}
	}
	template <class Iterator>
	list1(Iterator first, Iterator last)
	{
		PHead = new Node;
		PHead->pre = PHead->next = PHead;
		while (first != last)
		{
			push_back(*first);
			first++;
		}
	}
	list1(const list1<T>& l)
	{
		PHead = new Node;
		PHead->pre = PHead->next = PHead;
		list1<T> i(l.begin(), l.end());
		swap(i);
	}
	list1<T>& operator=(const list1<T> l)
	{
		if(!PHead)
		clear();
		list1<T> i(l.begin(), l.end());
		swap(i);
		return *this;
	}
	~list1()
	{
		if (this->PHead)
		{
			auto cur = begin();
			while (end() != cur)
			{
				cur = erase(cur);
			}
			delete PHead;
			PHead = NULL;
		}
		
	}
	// List Iterator
	iterator begin()
	{
		return PHead->next;
	}
	iterator end()
	{
		return PHead;
	}
	const_iterator begin()const
	{
		return PHead->next;
	}
	const_iterator end()const
	{
		return PHead;
	}
	///////////////////////////////////////////////////////////////
	// List Capacity
	size_t size()const
	{
		return _size;
	}
	bool empty()const
	{
		if (!size())
		{
			return true;
		}
		return false;
	}


	////////////////////////////////////////////////////////////
	// List Access
	T& front()
	{
		assert(!empty());
		return PHead->next->_val;
	}
	const T& front()const
	{
		return PHead->next->_val;
	}
	T& back()
	{
		return PHead->pre->_val;
	}
	const T& back()const
	{
		return PHead->pre->_val;
	}
	// List Modify
	void push_back(const T& val)
	{
		PNode Next = new Node;
		Next->_val = val;
		PNode New = PHead;
		Next->next = New;
		Next->pre = New->pre;
		New->pre->next = Next;
		New->pre=Next;
		_size++;
	}
	void pop_back() { erase(--end()); }
	void push_front(const T& val) { insert(begin(), val); }
	void pop_front() {
		erase(begin()); 
	}
	// 在pos位置前插入值为val的节点
	iterator insert(iterator pos, const T& val)
	{
		PNode New = new Node;
		New->_val = val;
		PNode per = pos._pNode->pre;
		PNode cur = pos._pNode;
		New->next = cur;
		cur->pre = New;
		New->pre = per;
		per->next = New;
		_size++;
		return New;
	}
	// 删除pos位置的节点，返回该节点的下一个位置
	iterator erase(iterator pos)
	{
		assert(_size > 0);
		if (pos._pNode == PHead) pos._pNode = pos._pNode->pre;
		PNode per = pos._pNode->pre;
		PNode next = pos._pNode->next;
		per->next = next;
		next->pre = per;
		_size--;
		delete pos._pNode;
		pos._pNode = NULL;
		return next;
	}
	void clear()
	{
		if (this->PHead)
		{
			auto cur = begin();
			while (end() != cur)
			{
				cur = erase(cur);
			}
			delete PHead;
			PHead = NULL;
		}
	}
	void swap(list1<T>& l)
	{
		std::swap(l.PHead, this->PHead);
		std::swap(l._size, this->_size);
	}
private:
	PNode PHead;
	size_t _size = 0;
};