文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >C++ List容器底层实现大揭秘

C++ List容器底层实现大揭秘

作者头像
用户11831438
发布于 2025-12-30 14:05:07
发布于 2025-12-30 14:05:07
1580
举报

一. 底层结构：List 容器的 “骨架”—— 带头双向循环链表

要手写 List，先明确其底层结构 ——带头双向循环链表，这是所有接口高效实现的基础

那既然是这样的话，是不是就可以说明list中的私有成员仅仅只需要一个头结点就可以了，也就是哨兵位。

list中的私有成员是一个节点类型，那我们就还需要一个节点结构，这个节点结构中需要包含：

  • prev指针：指向当前节点的前一个节点的指针（保存前一个节点的地址）
  • next指针：指向当前节点的后一个节点的指针（保存后一个节点的地址）
  • data：存储数据

也许会有UU想问：为什么会有这个节点结构？

这是因为每个数据存储在一个单独的结构里面，这个结构不仅存储数据，还有指针指向前一个和后一个节点，所以链表必须要有一个节点的结构！！！

ok，话不多说，直接上代码：

  • list.h
代码语言：javascript
复制
namespace carrot
{
    //节点类型
	template<class T>
	struct list_Node
	{
		list_Node<T>* _prev;//指向前一个节点的指针
		list_Node<T>* _next;//指向后一个节点的指针
		T data;//存储数据
	};
	template<class T>
	class list
	{
		using Node = list_Node<T>;
	private:
		Node* _head;//头结点（哨兵位）
	};
}

通过前面数据结构中对双向链表的学习，我们知道我们需要一个空的头结点，那我们就需要构造一个空的头结点：

  • list.h
代码语言：javascript
复制
template<class T>
class list
{
	using Node = list_Node<T>;
	//构造
	//构造一个空的头结点
	list()
	{
		_head = new Node;
		_head->_prev = _head;
		_head->_next = _head;
	}
private:
	Node* _head;//头结点（哨兵位）
};

二、架构构建：核心功能实现详解

2.1 尾插数据：push_back

通过对list底层的分析，我们已经有了一个空的链表，那我们是不是就可以在链表的尾部进行插入数据的操作了~~~

那我们该怎么插入这个数据呢？

在尾插的操作中，哨兵位没有发生改变。

plist本来指向0x100，有了值之后plist指向0x800。

通过前面的学习，我们可以快速写出代码：

当我们运行上面的代码时，会不会有什么问题呢？

那是不是说明我们没有创建一个新的节点空间，并将数据存储进去，那我们就需要在节点结构中加上构造节点的构造函数：

代码语言：javascript
复制
namespace carrot
{
	template<class T>
	struct list_Node
	{
		list_Node<T>* _prev;//指向前一个节点的指针
		list_Node<T>* _next;//指向后一个节点的指针
		T data;//存储数据
        //创建一个节点
		list_Node(const T& x)
			:_prev(nullptr)
			,_next(nullptr)
			,data(x)
		{}
	};
}
  • push_back代码 list.h：
代码语言：javascript
复制
template<class T>
class list
{
public:
	//push_back
	void push_back(const T& x)
	{
		//为x创建一个节点空间
		Node* newnode = new Node(x);
		Node* tail = _head->_prev;
		tail->_next = newnode;
		newnode->_prev = tail;
		newnode->_next = _head;
		_head->_prev = newnode;
	}
}

ok，通过上面的操作，我们就实现了List的一个基本框架，那我们接下来看看list中是如何实现迭代器的

2.2 链表迭代器实现：封装节点指针与运算符重载

也许会有uu想说：迭代器嘛，不就是给指针重新命名成iterator或者const_iterator，然后直接进行 *迭代器或者++迭代器，不就行了，不是很简单嘛~~

ok，我们知道迭代器的特别之处就在于“ * ”和“++”操作，* 就可以直接取出数据，++ 就是下一个位置的迭代器

但是我们想一想，链表list中的迭代器也可以直接进行 * 和 ++ 操作吗？

  • 我们直接进行 * 操作，可以直接取出节点中的数据吗？很明显不能，因为节点中不仅有保存数据的data，还有prev和next指针，无法直接取出数据。
  • 我们直接进行 ++ 操作，可以得到下一个位置的迭代器吗？很明显不能，因为链表中的地址不是连续的。

那我们该怎么实现这个迭代器呢？

问题根源

  • 数据存储在节点内部，*iterator 无法直接访问
  • ++iterator 无法直接跳到下一个节点
  • 节点指针的原始操作太底层、不安全

ok，我们知道迭代器的主要功能无非就是 * 和 ++ 操作，既然数据都在节点中，*iterator无法直接取出数据，++无法直接取下一个接单的地址，所以我们可以用一个类来封装一个迭代器，然后在这个类中实现 * 和 ++ 的运算符重载，在这个类中通过节点的指针来访问数据和++操作，用一个节点的指针来构造一个迭代器

代码语言：javascript
复制
#include<iostream>
using namespace std;
namespace carrot
{
	template<class T>
	struct list_Node
	{
		list_Node<T>* _prev;//指向前一个节点的指针
		list_Node<T>* _next;//指向后一个节点的指针
		T data;//存储数据
		list_Node(const T& x)
			:_prev(nullptr)
			,_next(nullptr)
			,data(x)
		{}
	};
	template<class T>
	struct list_iterator
	{
		using Node = list_Node<T>;
		using Self = list_iterator<T>;
		//用需要访问的节点的指针给_node初始化，构造一个list_iterator对象出来
		list_iterator(Node* node)
			:_node(node)
		{}
		Node* _node;
		//*
		T& operator*()
		{
			return _node->data;
		}
		//++
		Self& operator++()
		{
			_node = _node->_next;
			return *this;//*this的类型是list_iterator<T>
		}
        bool operator!=(const Self& s) const
        {
	        return _node != s._node;
        }
	};
}

ok，这样我们就实现了一个普通迭代器，这个迭代器的关键所在就在于：使用一个节点的指针构造一个迭代器对象

  • 如果要*iterator，就通过构造迭代器的指针访问数据
  • 如果要++，就通过构造迭代器的指针中的next
2.2.1 遍历的起点哨兵：begin()

通过前面的学习，我们知道begin()是第一个有效数据位置的迭代器，那在链表中第一个有效数据所在的节点就是begin()所在的位置

  • list.h
代码语言：javascript
复制
template<class T>
class list
{
public:
	using iterator = list_iterator<T>;
	iterator begin()
	{
		return iterator(_head->_next);
	}
}
2.2.2 遍历的终点哨兵：end()

通过前面的学习，我们知道end()是最后一个有效数据位置的下一个位置的迭代器，那在链表中最后一个有效数据位置的下一个位置所在的节点就是end()所在的位置，也就是“哨兵位”所在的位置

  • list.h
代码语言：javascript
复制
template<class T>
class list
{
public:
	using iterator = list_iterator<T>;
	iterator end()
	{
		return iterator(_head);
	}
}

iterator(_head) ; 和上面 begin() 的解释完全一样！！！

ok，迭代器这块还是有点小难度的，接下来我们接着完善list的相关操作：

2.3 任意位置的插入：灵活添加元素（insert）

inset使用迭代器传位置！！！

  • list.h
代码语言：javascript
复制
template<class T>
class list
{
public:
	void insert(iterator pos, const T& x)
	{
		//为x创建节点空间
		Node* newnode = new Node(x);
		Node* cur = pos._node;
		Node* prev = cur->_prev;
		newnode->_next = cur;
		newnode->_prev = prev;
		prev->_next = newnode;
		cur->_prev = newnode;
	}
}
  • 测试代码：
代码语言：javascript
复制
namespace carrot
{
	void testList1()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
		list<int>::iterator it = lt.begin();
		lt.insert(it, 10);
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}
  • 代码解释：
2.4 任意位置的删除：灵活删除元素（erase）

erase使用迭代器传位置！！！

  • list.h
代码语言：javascript
复制
void  erase(iterator pos)
{
	Node* cur = pos._node;
	Node* next = cur->_next;
	Node* prev = cur->_prev;
	prev->_next = next;
	next->_prev = prev;
	delete cur;
	cur = nullptr;
}

如果我们的erase按照上面的代码的话，在调用erase中的迭代器会出现失效的情况，为了解决这个问题，我们应该让erase返回删除位置的后一个位置的迭代器，也就是pos（why?因为在删除的过程中，pos后的位置上的数据挪动到pos位置上）

  • 修改后的代码：
代码语言：javascript
复制
template<class T>
class list
{
public:
    iterator erase(iterator pos)
    {
	    Node* cur = pos._node;
	    Node* next = cur->_next;
	    Node* prev = cur->_prev;
	    prev->_next = next;
	    next->_prev = prev;
	    delete cur;
	    cur = nullptr;
	    return iterator(next);
    }
}

erase中的pos的解释和insert一样

ok,有了insert和erase，我们就可以在push_back、push_front、pop_back、pop_front中复用insert和erase。

2.5 链表的便捷操作：高效管理头尾元素

ok，3,2,1~直接上代码

  • list.h
代码语言：javascript
复制
template<class T>
class list
{
public:
	//push_back 尾插
	void push_back(const T& x)
	{
		insert(end(), x);
	}
	//push_front 头插
	void push_front(const T& x)
	{
		insert(begin(), x);
	}
	//pop_back 尾删
	void pop_back()
	{
		erase(--end());
	}
	//pop_front 头删
	void pop_front()
	{
		erase(begin());
	}
  • 测试代码：
代码语言：javascript
复制
namespace carrot
{
	void testList2()
	{
		list<int> lt;
        //尾插
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
        //头插
		lt.push_front(0);
		lt.push_front(-1);
		lt.push_front(-2);
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
        //尾删
		lt.pop_back();
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
        //头删
		lt.pop_front();
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}
2.6 链表的有效数据个数：size
代码语言：javascript
复制
//size
size_t size() const
{
	size_t n = 0;
	for (auto e : *this)
	{
		++n;
	}
	return n;
}

ok，如果按照上面的写法，感觉有点呆，我们可以在list的私有成员中加上size，每当插入数据时size++，删除数据时size--，即可。

代码语言：javascript
复制
template<class T>
class list
{
public:
    //size
	size_t size() const
	{
		return _size;
	}
private:
	Node* _head;//头结点（哨兵位）
	size_t _size;
};
2.7 清空容器：clear 操作

将链表中的数据删除，保留头结点

代码语言：javascript
复制
template<class T>
class list
{
    public:
        void clear()
        {
	        it = begin();
	        while (it != end())
	        {
		        it = erase(it);
	        }
        }        
}
2.8 对象生命周期终结：析构函数

析构也是将链表中的数据清空，并且要释放头结点，所以析构函数可以复用clear

代码语言：javascript
复制
template<class T>
class list
{
    public:
       ////析构
    ~list()
    {
	    clear();
	    delete _head;
	    _head = nullptr;
	    _size = 0;
    }
    //clear
    void clear()
    {
	    iterator it = begin();
	    while (it != end())
	    {
		    it = erase(it);
	    }
	    _size = 0;
    }      
}
2.9 深拷贝的核心：拷贝构造与赋值重载实现

在看之前，我们先来看几个构造

2.9.1 initializer_list 构造

可以使用 { } 括一组数据进行构造

ok，当我们使用上面的代码进行构造的时候，发现有运行报错

在进行插入数据之前，头结点不应该为空。

  • 正确代码：
代码语言：javascript
复制
template<class T>
class list
{
public:
	using Node = list_Node<T>;
	void init()
	{
		_head = new Node(T());
		_head->_prev = _head;
		_head->_next = _head;
		_size = 0;
	}
	//构造
	//构造一个空的头结点
	list()
	{
		init();
	}
	//initializer_list
	list(initializer_list<T> il)
	{
        //初始化头节点
		init();
		for (auto& e : il)
		{
			push_back(e);
		}
	}
}
2.9.2 使用迭代区间构造
代码语言：javascript
复制
template<class T>
class list
{
public:
	using Node = list_Node<T>;
	void init()
	{
		_head = new Node(T());
		_head->_prev = _head;
		_head->_next = _head;
		_size = 0;
	}
	//构造
	//构造一个空的头结点
	list()
	{
		init();
	}
	//迭代区间构造
	template <class InputIterator>
	list(InputIterator first, InputIterator last)
	{
		init();
		while (first != last)
		{
			push_back(*first);
			++first;
		}
	}
}
2.9.3 n个val 的构造
代码语言：javascript
复制
//n个值的构造
list(size_t n ,const T& val = T())
{
	init();
	for (size_t i = 0; i < n; i++)
	{
		push_back(val);
	}
}
list(int n, const T& val = T())
{
	init();
	for (size_t i = 0; i < n; i++)
	{
		push_back(val);
	}
}

这里实现了两个版本，防止调用n个val的构造时调用到了 initializer_list 构造

ok,接下来

2.9.4 拷贝构造

编译器默认生成的拷贝是浅拷贝，对于List而言，浅拷贝还是会出现析构两次的情况，所以需要自己手动实现一个拷贝构造从而完成深拷贝。

  • list.h
代码语言：javascript
复制
//构造一个头结点（哨兵位）
void init()
{
	_head = new Node(T());
	_head->_prev = _head;
	_head->_next = _head;
	_size = 0;
}
//构造
//构造一个空的头结点
list()
{
	init();
}
//拷贝构造
list(const list<T>& v)
{
	init();
	for (auto& e : v)
	{
		push_back(e);
	}
}
  • 现代写法：
代码语言：javascript
复制
list(list<T>& v)
{
	init();
	list <T> tmp(v.begin(),v.end());
	swap(tmp);
}
void swap(list<T>& v)
{
	std::swap(_head, v._head);
	std::swap(_size, v._size);
}
2.9.5 赋值运算符重载

自己实现一个赋值运算符重载，还是因为浅拷贝的问题，这里就不过与赘述了，直接上代码：

  • list.h
代码语言：javascript
复制
//赋值运算符重载
list<T>& operator=(const list<T>& v)
{
	if (this != &v)
	{
		clear();
		for (auto& e : v)
		{
			push_back(e);
		}
	}
	return *this;
}
  • 现代写法：
代码语言：javascript
复制
void swap(list<T>& v)
{
	std::swap(_head, v._head);
	std::swap(_size, v._size);
}

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

三、保护数据：const迭代器的设计之道

我们先来完善一下普通迭代器

代码语言：javascript
复制
namespace carrot
{
	template<class T>
	struct list_Node
	{
		list_Node<T>* _prev;//指向前一个节点的指针
		list_Node<T>* _next;//指向后一个节点的指针
		T data;//存储数据
		list_Node(const T& x)
			:_prev(nullptr)
			,_next(nullptr)
			,data(x)
		{}
	};
	template<class T>
	struct list_iterator
	{
		using Node = list_Node<T>;
		using Self = list_iterator<T>;
		//用需要访问的节点的指针给_node初始化，构造一个list_iterator对象出来
		list_iterator(Node* node)
			:_node(node)
		{}
		Node* _node;
		//*
		T& operator*()
		{
			return _node->data;
		}
		//前置++
		Self& operator++()
		{
			_node = _node->_next;
			return *this;//*this的类型是list_iterator<T>
		}
        //后置++
		Self operator++(int)
		{
			Self tmp(*this);
			_node = _ndoe->_next;
			return tmp;
		}
		//前置--
		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
        //后置--
		Self operator--(int)
		{
			Self tmp(*this);
			_node = _ndoe->_prev;
			return tmp;
		}
        //!=
		bool operator!=(const Self& s) const
		{
			return _node != s._node;
		}
        //==
		bool operator==(const Self& s) const
		{
			return _node == s._node;
		}
	};
}

也许会有uu想问：为什么不用写析构、拷贝构造和赋值运算符重载？

这是因为迭代器是借助这个节点的指针去访问链表的数据，但是迭代器销毁后，不销毁对应的节点，节点是归链表管的。这就和我们之前的知识接起来了，不要显示写析构的就不需要显示写拷贝构造！！！

3.1 分别实现：iterator与const_iterator的独立实现

在前面的代码实现中，我们已经实现了普通迭代器，那我们该如何实现const迭代器呢？

我们可以直接利用普通迭代器，然后再写一份const迭代器即可~~~

代码语言：javascript
复制
template<class T>
struct list_const_iterator
{
	using Node = list_Node<T>;
	using Self = list_const_iterator<T>;
	//用需要访问的节点的指针给_node初始化，构造一个list_iterator对象出来
	list_const_iterator(Node* node)
		:_node(node)
	{}
	Node* _node;
	//*
	const T& operator*()
	{
		return _node->data;
	}
	//++
	Self& operator++()
	{
		_node = _node->_next;
		return *this;//*this的类型是list_iterator<T>
	}
	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;
	}
	bool operator!=(const Self& s) const
	{
		return _node != s._node;
	}
	bool operator==(const Self& s) const
	{
		return _node == s._node;
	}
};

有了const迭代器，我们就可以实现相应的const对象的 begin 和 end 了

代码语言：javascript
复制
using const_iterator = list_const_iterator<T>;
const_iterator begin() const
{
	return const_iterator(_head->_next);
}
const_iterator end() const
{
	return const_iterator(_head);
}

但是，我们看到const迭代器和普通迭代器的区别仅仅在于数据能否修改，如果我们按照上面的写法，有点浪费

那我们该怎么写呢？我们接着看~

3.2 进阶技巧：迭代器的模板化实现

我们对普通迭代器进行改写，在原本只有一个模板参数的情况下，再加个模板参数Ref

也许会有uu会感到疑惑，为什么这里再加了模板参数，就可以实现普通迭代器和const迭代器了呢？

这是因为Ref可以是 T& 或者 const T&，这就可以将普通迭代器和const迭代器合并在一个类中了。

通过模板参数 Ref 控制返回类型：

  • T& → 可修改的普通迭代器
  • const T& → 只读的const迭代器

那么 iterator 和 const_iterator ，我们就可以这样写：

这里实现迭代器的本质还是封装指针，我们无法直接 * 和 ++ 得到相应的数据，那我们就可以通过在类中，通过节点的指针构造一个迭代器，在类中实现 * 和 ++ 运算符重载，就可以实现相应的功能。

  • 完整代码：
  • list.h
代码语言：javascript
复制
#pragma once
#include<iostream>
using namespace std;
namespace carrot
{
	template<class T>
	struct list_Node
	{
		list_Node<T>* _prev;//指向前一个节点的指针
		list_Node<T>* _next;//指向后一个节点的指针
		T data;//存储数据
		list_Node(const T& x)
			:_prev(nullptr)
			,_next(nullptr)
			,data(x)
		{}
	};
	template<class T,class Ref>
	struct list_iterator
	{
		using Node = list_Node<T>;
		using Self = list_iterator<T,Ref>;
		//用需要访问的节点的指针给_node初始化，构造一个list_iterator对象出来
		list_iterator(Node* node)
			:_node(node)
		{}
		Node* _node;
		//*
		Ref operator*()
		{
			return _node->data;
		}
		//++
		Self& operator++()
		{
			_node = _node->_next;
			return *this;//*this的类型是list_iterator<T>
		}
		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;
		}
		bool operator!=(const Self& s) const
		{
			return _node != s._node;
		}
		bool operator==(const Self& s) const
		{
			return _node == s._node;
		}
	};
	//template<class T>
	//struct list_iterator
	//{
	//	using Node = list_Node<T>;
	//	using Self = list_iterator<T>;
	//	//用需要访问的节点的指针给_node初始化，构造一个list_iterator对象出来
	//	list_iterator(Node* node)
	//		:_node(node)
	//	{}
	//	Node* _node;
	//	//*
	//	T& operator*()
	//	{
	//		return _node->data;
	//	}
	//	//++
	//	Self& operator++()
	//	{
	//		_node = _node->_next;
	//		return *this;//*this的类型是list_iterator<T>
	//	}
	//	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;
	//	}
	//	bool operator!=(const Self& s) const
	//	{
	//		return _node != s._node;
	//	}
	//	bool operator==(const Self& s) const
	//	{
	//		return _node == s._node;
	//	}
	//};
	//template<class T>
	//struct list_const_iterator
	//{
	//	using Node = list_Node<T>;
	//	using Self = list_const_iterator<T>;
	//	//用需要访问的节点的指针给_node初始化，构造一个list_iterator对象出来
	//	list_const_iterator(Node* node)
	//		:_node(node)
	//	{}
	//	Node* _node;
	//	//*
	//	const T& operator*()
	//	{
	//		return _node->data;
	//	}
	//	//++
	//	Self& operator++()
	//	{
	//		_node = _node->_next;
	//		return *this;//*this的类型是list_iterator<T>
	//	}
	//	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;
	//	}
	//	bool operator!=(const Self& s) const
	//	{
	//		return _node != s._node;
	//	}
	//	bool operator==(const Self& s) const
	//	{
	//		return _node == s._node;
	//	}
	//};
	template<class T>
	class list
	{
	public:
		using Node = list_Node<T>;
		void init()
		{
			_head = new Node(T());
			_head->_prev = _head;
			_head->_next = _head;
			_size = 0;
		}
		//构造
		//构造一个空的头结点
		list()
		{
			init();
		}
		//initializer_list
		list(initializer_list<T> il)
		{
			init();
			for (auto& e : il)
			{
				push_back(e);
			}
		}
		//迭代区间构造
		template <class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			init();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
		//n个值的构造
		list(size_t n ,const T& val = T())
		{
			init();
			for (size_t i = 0; i < n; i++)
			{
				push_back(val);
			}
		}
		list(int n, const T& val = T())
		{
			init();
			for (size_t i = 0; i < n; i++)
			{
				push_back(val);
			}
		}
		//拷贝构造
		list(const list<T>& v)
		{
			init();
			for (auto& e : v)
			{
				push_back(e);
			}
		}
		/*list(list<T>& v)
		{
			init();
			list <T> tmp(v.begin(),v.end());
			swap(tmp);
		}*/
		void swap(const list<T>& v) const
		{
			std::swap(_head, v._head);
			std::swap(_size, v._size);
		}
		//赋值运算符重载
		list<T>& operator=(const list<T>& v)
		{
			if (this != &v)
			{
				clear();
				for (auto& e : v)
				{
					push_back(e);
				}
			}
			return *this;
		}
		/*list<T>& operator=(list<T> tmp)
		{
			swap(tmp);
			return *this;
		}*/
		////析构
		~list()
		{
			/*it = begin();
			while (it != end())
			{
				it = erase(it);
			}*/
			clear();
			delete _head;
			_head = nullptr;
			_size = 0;
		}
		//clear
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
			_size = 0;
		}
		//push_back
		//void push_back(const T& x)
		//{
		//	//为x创建一个节点空间
		//	Node* newnode = new Node(x);
		//	Node* tail = _head->_prev;
		//	tail->_next = newnode;
		//	newnode->_prev = tail;
		//	newnode->_next = _head;
		//	_head->_prev = newnode;
		//}
		/*using iterator = list_iterator<T>;
		using const_iterator = list_const_iterator<T>;*/

		using iterator = list_iterator<T, T&>;
		using const_iterator = list_iterator<T, const T&>;
		iterator begin()
		{
			return iterator(_head->_next);
		}
		iterator end()
		{
			return iterator(_head);
		}
		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}
		const_iterator end() const
		{
			return const_iterator(_head);
		}
		void insert(iterator pos, const T& x)
		{
			//为x创建节点空间
			Node* newnode = new Node(x);
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			newnode->_next = cur;
			newnode->_prev = prev;
			prev->_next = newnode;
			cur->_prev = newnode;
			++_size;
		}
		//erase
		//为了解决迭代器失效的问题，erase返回删除的下一个位置的迭代器
		/*void  erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* next = cur->_next;
			Node* prev = cur->_prev;
			prev->_next = next;
			next->_prev = prev;
			delete cur;
			cur = nullptr;
		}*/
		iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			prev->_next = next;
			next->_prev = prev;
			delete cur;
			cur = nullptr;
			--_size;
			return iterator(next);
		}
		//push_back 尾插
		void push_back(const T& x)
		{
			insert(end(), x);
		}
		//push_front 头插
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		//pop_back 尾删
		void pop_back()
		{
			erase(--end());
		}
		//pop_front 头删
		void pop_front()
		{
			erase(begin());
		}
		//size
		size_t size() const
		{
			/*size_t n = 0;
			for (auto e : *this)
			{
				++n;
			}
			return n;*/
			return _size;
		}
	private:
		Node* _head;//头结点（哨兵位）
		size_t _size;
	};
}
  • list.cpp
代码语言：javascript
复制
#define _CRT_SECURE_NO_WARNINGS
#include"list.h"
namespace carrot
{
	void testList1()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
		list<int>::iterator it = lt.begin();
		lt.insert(it, 10);
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
		list<int>::iterator it1 = lt.begin();
		lt.erase(it1);
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}
	void testList2()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);
		cout << lt.size() << endl;

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
		lt.push_front(0);
		lt.push_front(-1);
		lt.push_front(-2);
		cout << lt.size() << endl;

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
		lt.pop_back();
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
		lt.pop_front();
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
		cout << lt.size() << endl;
		lt.clear();
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}
	void testList3()
	{
		//list<int> lt;
		//lt.push_back(1);
		//lt.push_back(2);
		//for (auto e : lt)
		//{
		//	cout << e << " ";
		//}
		//cout << endl;
		////lt.clear();
		//list<int> lt1(lt);
		//for (auto e : lt1)
		//{
		//	cout << e << " ";
		//}
		//cout << endl;
		list<int> lt({ 1,2,3,4,5,6 });
		/*for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
		list<int> lt1(lt.begin(), lt.end());
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;*/
		list<int> lt1(lt);
		/*for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;*/
		list<int> lt2(10, 1);
		for (auto e : lt2)
		{
			cout << e << " ";
		}
		cout << endl;
		lt2 = lt1;
		for (auto e : lt2)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}
int main()
{
	carrot::testList3();
	return 0;
}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-10-26，如有侵权请联系 cloudcommunity@tencent.com 删除
c++
容器
list
数据
指针

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

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

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

c++
容器
list
数据
指针
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 一. 底层结构：List 容器的 “骨架”—— 带头双向循环链表
  • 二、架构构建：核心功能实现详解
    • 2.1 尾插数据：push_back
    • 2.2 链表迭代器实现：封装节点指针与运算符重载
      • 2.2.1 遍历的起点哨兵：begin()
      • 2.2.2 遍历的终点哨兵：end()
    • 2.3 任意位置的插入：灵活添加元素（insert）
    • 2.4 任意位置的删除：灵活删除元素（erase）
    • 2.5 链表的便捷操作：高效管理头尾元素
    • 2.6 链表的有效数据个数：size
    • 2.7 清空容器：clear 操作
    • 2.8 对象生命周期终结：析构函数
    • 2.9 深拷贝的核心：拷贝构造与赋值重载实现
      • 2.9.1 initializer_list 构造
      • 2.9.2 使用迭代区间构造
      • 2.9.3 n个val 的构造
      • 2.9.4 拷贝构造
      • 2.9.5 赋值运算符重载
  • 三、保护数据：const迭代器的设计之道
    • 3.1 分别实现：iterator与const_iterator的独立实现
    • 3.2 进阶技巧：迭代器的模板化实现
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

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

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

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

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

Copyright © 2013 - 2026 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论