文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >【c++】STL-容器 list 的实现

【c++】STL-容器 list 的实现

作者头像
mosheng
发布于 2026-01-14 18:29:42
发布于 2026-01-14 18:29:42
700
举报
文章被收录于专栏：c++c++

hello~ 很高兴见到大家! 这次带来的是C++中关于list容器这部分的一些知识点,如果对你有所帮助的话,可否留下你的三连呢? 个 人 主 页: 默|笙

接上次的博客<list的使用>

一、做好实现list前的准备工作

由于模板的特殊，声明和定义不分离,即把它们放在一个文件里(.h)。

模板的实例化需要看到完整定义，而分文件编译机制导致无法让编译器在使用模板的地方获取定义，导致无法生成实例代码，链接失败。

1.1 节点

  1. 与底层为数组的vector不同，list这个模板的底层是链表，是由一个一个的节点组成的，我们首先要实现的就是节点。
  2. 我们可以将节点所需变量打包成一个类，其包含一个存储数据的变量和两个指针。由于我们需要经常访问这个类的成员变量，我们用struct实现。
  3. 同时不要忘了用模板实现。
代码语言：javascript
复制
template<class T>
struct list_node//节点
	{
		T _data;
		list_node<T>* _next;//指向前一个节点的指针
		list_node<T>* _prev;//指向后一个节点的指针

		list_node(const T& x = T())//构造节点
			:_data(x)
			,_next(nullptr)
			,_prev(nullptr)
		{}
	};
  1. 关于节点构造函数里的 const T& x = T()：c++规定，T()，若T为自定义类型，则会调用默认构造函数，若为内置类型，则会进行零初始化，将值设置为0 或 nullptr。
  2. 为了在任何时候节点都能被初始化（无论是设置头节点还是push_back一个节点），我们用全缺省默认构造函数。

1.2 实现iterator迭代器

1.实现基本框架（普通迭代器）

  1. 在之前vector的实现里，我们直接将指针重命名为迭代器iterator（vector博客）。这是因为vector的底层是数组，*解引用能直接拿到数据，++能移动到后一个位置，- -能移动到前一个位置，运用指针就能达到预期目的。
  2. 但在list里，我们能够直接接触的只有节点，节点的指针解引用，拿到的不会是我们想要的数据，而是节点本身，++与- -也不会达到预期效果，节点指针不能成为我们的迭代器。
  3. 那么我们可以类封装节点指针来实现迭代器，通过重载运算符来控制迭代器的行为（重载++与- -实现跳转到前一个或后一个节点，重载*实现访问数据）。

则有：

代码语言：javascript
复制
template<class T>
struct __list_iterator
{
	typedef list_node<T> Node;

	Node* _node;
	__list_iterator(Node* node)
		:_node(node)
	{}

	T& operator*()
	{
		return _node->_data;
	}
	//前置++
	__list_iterator<T>& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	//后置++
	__list_iterator<T> operator++(int)
	{
		__list_iterator<T> tmp(*this);
		_node = _node->_next;
		return tmp;
	}
	//前置--
	__list_iterator<T>& operator--()
	{
		_node = _node->_prev;
		return *this;
	}
	//后置--
	__list_iterator<T> operator--(int)
	{
		__list_iterator<T> tmp(*this);
		_node = _node->_prev;
		return tmp;
	}

	//!=
	bool operator!=(const __list_iterator<T>& it)const
	{
		return _node != it._node;
	}
	//==
	bool operator==(const __list_iterator<T>& it)const
	{
		return _node == it._node;
	}
};

注：这里的 this 是迭代器指针，也就是__list_iterator*，而*this是迭代器。

  1. *重载：我们的预期是解引用直接得到数据，重载*函数让其被调用时返回数据便可，这里返回数据的引用）。
  2. 前置++与前置- -重载：改变迭代器的指向然后返回迭代器的引用（避免拷贝）就行。
  3. 后置++与后置- -重载：由于需要返回的是改变之前的迭代器，需要先把所指节点改变之前的迭代器拷贝存一份，这里迭代器变量名称设置为tmp，迭代器所指节点改变之后再返回tmp。这里不能返回引用，因为tmp离开这个作用域就会销毁。

迭代器这个类不需要实现析构函数，拷贝构造函数和赋值重载函数。前者是因为它没有资源需要释放，它只是目前指向/管理这个节点，这个节点并不属于它；后面两个是因为我们需要的就是浅拷贝，指向同一块空间，不需要进行深拷贝。

  1. != 与 ==：分辨两个迭代器所指向的节点是否是不同或相同节点便可。
2. 常量迭代器的添加

  1. 在一些场景比如创建Print函数时，仅仅是遍历，我们不能允许改变迭代器所指的节点的值，这需要我们使用到常量迭代器。
  2. 常量迭代器如何实现？只需要修改*重载函数的返回值就行，加上const修饰。
  3. 常量迭代器不是本身不可修改，而是它指向的数据不能被修改。
代码语言：javascript
复制
const T& operator*()
{
	return _node->_data;
}

接下来，我们来看一段加上常量迭代器过后的代码：

代码语言：javascript
复制
	template<class T>
	struct __list_iterator
	{
		typedef list_node<T> Node;

		Node* _node;
		__list_iterator(Node* node)
			:_node(node)
		{}

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

	template<class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		typedef __list_iterator<T> iterator; 
		//1
		typedef const __list_iterator<T> const_iterator;

	private:

	};

这里省略了很多代码，留下了主要的部分。这个代码里存在着两处问题。

  1. 1处的错误：将 const __list_iterator类型重定义为 const_iterator，也就是常量迭代器。注意，const这里修饰的是 __list_iterator这个类型本身，意思是这个迭代器它本身不能修改，而不是说迭代器它所指向的数据不能被修改，这不符合我们的预期。
  2. 假如没有上面的错误，仅有2处，也存在着问题：这里虽然两个*重载函数构成重载，但是只有被const修饰的迭代器才能够调用上面的const *函数，然后又回到了上面的问题，这也是迭代器本身不可修改，做不到迭代器的基本功能遍历。
  3. 正确方法应该是再创建一个常量迭代器的类，与上面普通迭代器的类区别开来。

如下：

代码语言：javascript
复制
	//普通迭代器
	template<class T>
	struct __list_iterator
	{
		typedef list_node<T> Node;

		Node* _node;
		__list_iterator(Node* node)
			:_node(node)
		{}

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

		//前置++
		__list_iterator<T>& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		//后置++
		__list_iterator<T> operator++(int)
		{
			__list_iterator<T> tmp(*this);
			_node = _node->_next;
			return tmp;
		}
		//前置--
		__list_iterator<T>& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		//后置--
		__list_iterator<T> operator--(int)
		{
			__list_iterator<T> tmp(*this);
			_node = _node->_prev;
			return tmp;
		}

		//!=
		bool operator!=(const __list_iterator<T>& it)const
		{
			return _node != it._node;
		}
		//==
		bool operator==(const __list_iterator<T>& it)const
		{
			return _node == it._node;
		}
	};

	//常量迭代器
	template<class T>
	struct __list_const_iterator
	{
		typedef list_node<T> Node;

		Node* _node;
		__list_iterator(Node* node)
			:_node(node)
		{}

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

		//前置++
		__list_iterator<T>& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		//后置++
		__list_iterator<T> operator++(int)
		{
			__list_iterator<T> tmp(*this);
			_node = _node->_next;
			return tmp;
		}
		//前置--
		__list_iterator<T>& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		//后置--
		__list_iterator<T> operator--(int)
		{
			__list_iterator<T> tmp(*this);
			_node = _node->_prev;
			return tmp;
		}

		//!=
		bool operator!=(const __list_iterator<T>& it)const
		{
			return _node != it._node;
		}
		//==
		bool operator==(const __list_iterator<T>& it)const
		{
			return _node == it._node;
		}
	};
	template<class T>
	class list
	{
		typedef list_node Node;
	public:
		typedef __list_iterator iterator;
		//重命名常量迭代器
		typedef __list_const_iterator const_iterator;

	private:

	};
  1. 但上面的代码稍微有些冗长，且两个迭代器几乎完全一样，这里我们可以增加一个模板参数，将它们整合为同一个模板类，最终使得这两个迭代器变成这个模板类的不同实例。

如下：

代码语言：javascript
复制
template<class T, class Ref>
struct __list_iterator
{
	typedef list_node<T> Node;
	typedef __list_iterator<T, Ref> Self;

	Node* _node;
	__list_iterator(Node* node)
		:_node(node)
	{}
	//*重载
	Ref operator*()
	{
		return _node->_data;
	}

	//前置++
	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	//后置++
	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& it)const
	{
		return _node != it._node;
	}
	//==
	bool operator==(const Self& it)const
	{
		return _node == it._node;
	}
};
template<class T>
class list
{
	typedef list_node Node;
public:
	typedef __list_iterator<T, T&> iterator;
	typedef __list_iterator<T, const T&> const_iterator;

private:

};
  1. 这里通过增加Res模板参数来实现迭代器模板类，除此之外，在模板类里，还将__list_iterator<T, Ref> 重命名为Self，这样可以方便以后代码的维护，比如增加一个模板参数时，只用动这里一个地方就行了。
在这里插入图片描述
在这里插入图片描述

3.->重载函数

接下来看一段代码：

代码语言：javascript
复制
//这是一个类：
struct Pos
	{
		int _row;
		int _col;

		Pos(int row = 0, int col = 0)
			:_row(row)
			, _col(col)
		{}
	};
//我们尝试打印一下存储这个Pos类型的list<Pos>,假设list已经实现
int main()
{
	mosheng::list<Pos> lt1;
	lt1.push_back({1,1});//隐式类型转换
	lt1.push_back({2,2});
	lt1.push_back({3,3});
	lt1.push_back({4,4});

	auto it = lt1.begin();
	while (it != lt1.end())
	{
		//cout << (*it)._row << ":" << (*it)._col << endl;
		cout << it->_row << ":" << it->_col << endl;
		++it;
	}
	cout << endl;			
	return 0;
}
  1. 会出现（其中mosheng是list实现所在的命名空间）：
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
  1. 这是因为我们重载了*，但是还没有重载->，所以我们无法成功打印。接下来让我们来进行实现：
代码语言：javascript
复制
//operator->() 的返回类型必须是 T* 或迭代器，无论 T 是否为指针类型
T* operator->()
{
	return &_node->_data;
}
  1. 将其放入迭代器类模板里，代码能够正常运行。
在这里插入图片描述
在这里插入图片描述
  1. 我们能够发现一个有趣现象：根据重载函数，返回的应该是Pos*，而上面代码的 it->_row，它少了一个->，实际应该是it->->row（写的时候不能写两个）。第一个箭头是迭代器运算符重载得到Pos*，第二个取Pos里的row。省略一个->是编译器的特殊处理，为了增强可读性。
  2. 为了实例化常量迭代器，我们再增添一个模板参数。
代码语言：javascript
复制
template<class T, class Ref, class Ptr>
struct __list_iterator
{
	typedef list_node<T> Node;
	typedef __list_iterator<T, Ref, Ptr> Self;

	Node* _node;
	__list_iterator(Node* node)
		:_node(node)
	{}

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

	Ptr operator->()
	{
		return &_node->_data;
	}
}
class list
{
	typedef list_node<T> Node;
public:
	typedef __list_iterator<T, T&, T*> iterator;
	typedef __list_iterator<T, const T&, const T*> const_iterator;
}
//省略中间一部分

二、实现list

由于链表的实现比较简单没有什么需要单独拿出来讲的内容，这里就跳过了。

代码语言：javascript
复制
		template<class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;

		//创造头节点函数
		void empty_Init()
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
		}
		//默认构造函数
		list()
		{
			empty_Init();
		}
		//拷贝构造函数
		list<T> (const list<T>& lt)
		{
			empty_Init();

			for (const auto& e : lt)
			{
				push_back(e);
			}
		}
		//初始化列表构造函数
		list(initializer_list<T> il)
		{
			empty_Init();
			for (const auto& e : il)
			{
				push_back(e);
			}
		}
		//清除链表节点，留下头节点
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
			_size = 0;
		}
		//析构函数
		~list()
		{
			clear();//清除所有节点
			delete _head;//清除头节点
			_head = nullptr;
		}
		//交换
		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}
		//赋值重载函数（现代写法）
		list<T>& operator=(list lt)
		{
			swap(lt);

			return *this;
		}

		//begin()
		iterator begin()
		{
			return iterator(_head->_next);
		}
		const_iterator begin()const
		{
			return cosnt_iterator(_head->_next);
		}
		//end()
		iterator end()
		{
			return iterator(_head);
		}
		const_iterator end()const
		{
			return const_iterator(_head);
		}
		//在指定位置插入
		iterator insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;
			Node* newnode = new Node(x);
			Node* prev = cur->_prev;
			
			prev->_next = newnode;
			newnode->_next = cur;
			newnode->_prev = prev;
			cur->_prev = newnode;

			_size++;
			return iterator(newnode);
		}
		//删除指定位置
		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;

			_size--;
			return iterator(next);
		}
		//尾插
		void push_back(const T& x)
		{
			insert(end(), x);
		}
		//头插
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		//尾删
		void pop_back()
		{
			erase(--end());
		}
		//头删
		void pop_front()
		{
			erase(begin());
		}
		//节点个数
		size_t size()
		{
			return _size;
		}

	private:
		Node* _head;
		size_t _size = 0;
	};
}

今天的分享就到此结束啦,如果对读者朋友们有所帮助的话,可否留下宝贵的三连呢~~ 如果可以, 那就让我们共同努力, 一起走下去!

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2026-01-13，如有侵权请联系 cloudcommunity@tencent.com 删除
list
stl
函数
c++
容器

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

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

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

list
stl
函数
c++
容器
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 一、做好实现list前的准备工作
    • 1.1 节点
    • 1.2 实现iterator迭代器
      • 1.实现基本框架（普通迭代器）
      • 2. 常量迭代器的添加
    • 3.->重载函数
  • 二、实现list
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

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. 腾讯云 版权所有

登录 后参与评论