【C++STL精讲】list的使用教程及其模拟实现

举报
花想云 发表于 2023/05/30 23:01:54 2023/05/30
【摘要】 本章我们将认识与学习list的使用并且参照STL源码来模拟实现list容器，需要读者具有一定的数据结构基础。通过本章的学习，我们将对类和对象、模板的运用更加熟练，同时还会实现list的重要角色——迭代器，让我们对迭代器的了解更上一层楼~

image.png

💐文章导读

本章我们将认识与学习list的使用并且参照STL源码来模拟实现list容器，需要读者具有一定的数据结构基础。通过本章的学习，我们将对类和对象、模板的运用更加熟练，同时还会实现list的重要角色——迭代器，让我们对迭代器的了解更上一层楼~

🌷list是什么？

list是C++ STL中的一个容器，是一个双向链表，可以存储任意类型的元素。list中的元素可以通过指针在链表中进行高效的插入和删除操作，因此list通常被用于需要频繁进行插入和删除操作的场合。

🌷list如何使用？

  • 使用list前需包含头文件< list >;
#include <list>
  • 🍁定义一个list容器；
	list<int> mylist; // 声明一个空的list
	list<int> mylist2(10); // 声明一个有10个默认值的list
	list<int> mylist3(5, 2); // 声明一个有5个值为2的list
  • 🍁向list中添加元素；
mylist.push_back(1); // 在list的末尾添加元素1
mylist.push_front(2); // 在list的开头添加元素2
mylist.insert(mylist.begin(), 3); // 在指定位置插入元素3
  • 🍁访问list中的元素；
	cout << mylist.front() << endl; // 访问第一个元素
	cout << mylist.back() << endl; // 访问最后一个元素
  • 🍁遍历list中的元素；
for (auto it = mylist.begin(); it != mylist.end(); ++it) {
    cout << *it << " ";
}
  • 🍁删除list中的元素；
mylist.pop_front(); // 删除第一个元素
mylist.pop_back(); // 删除最后一个元素
mylist.erase(mylist.begin()); // 删除指定位置的元素
mylist.clear(); // 删除所有元素

list的常见使用就是这些了，若想查看更多操作，还需借助STL文档来学习。

🌷list的模拟实现

🌺定义list类

为了区别于库中的list类，我们可以在自己的命名空间中定义list类。list的基本成员变量只有一个——list的头结点（head）并且头节点内不存储有效数据。

  • 🍁定义结点结构；
namespace hxy
{
	//定义结点结构
	template<class T>
	struct ListNode
	{
		struct ListNode<T>* _next; // 指向下一个结点
		struct ListNode<T>* _prev; // 指向前一个结点
		T _data; // 结点存储的数据

		ListNode(const T& data = T()) // 构造函数 // 申请一个节点 
			:_next(nullptr),
			_prev(nullptr),
			_data(data)
		{}
	};
}
  • 🍁定义list类；
namespace hxy
{
	//定义结点结构
	template<class T>
	struct ListNode
	{
		struct ListNode<T>* _next; // 指向下一个结点
		struct ListNode<T>* _prev; // 指向前一个结点
		T _data; // 结点存储的数据

		ListNode(const T& data = T()) // 构造函数 // 申请一个节点 
			:_next(nullptr),
			_prev(nullptr),
			_data(data)
		{}
	};
	// list类的定义
	template<class T>
	class list
	{
		typedef ListNode<T> node; // 简写
	
	private:
		node* _head;
	}；
}

🌺构造函数

	list()
	{
		_head = new node;
		_head->_next = _head;
		_head->_prev = _head;
	}

🌺push_back

  • 🍁对list进行尾插元素；
	void push_back(const T& data)
	{
		node* newNode = new node(data); // 申请一个结点
		node* tail = _head->_prev; // list的尾结点就是头结点的前一个

		// 链接结点
		tail->_next = newNode;
		newNode->_prev = tail;
		newNode->_next = _head;
		_head->_prev = newNode;
	}

🌺pop_back

  • 🍁对list进行尾删；
	void pop_back()
	{
		assert(_head->_next != _head);

		node* tail = _head->_prev;
		tail->_prev->_next = _head;
		_head->_prev = tail->_prev;
		
		delete tail; //释放尾结点
	}

🌷list迭代器

迭代器——作为list最精华的部分，有着及其重要的作用，且同样为list模拟实现中最难的一部分。通过本章的内容，我们对于迭代器的理解会更上一层楼!

在string与vector的学习中，我们经常使用下标+[]来访问容器的元素，非常方便。但是到了list以后的内容，[]访问元素的方法将不再适用，我们将使用迭代器。

前面的文章中曾经简单的提到过迭代器，描述它为一种像指针一样却又不单纯是指针的东西（string和vector中的迭代器在一些编译器下确实是原始指针）。接下来我们就模拟实现list的迭代器。

🌺定义list迭代器的类

迭代器本质就是对指针的封装模拟指针的行为，所以我们需要通过运算符重载来模拟实现指针的++、--以及*、->等操作。

	template<class T,class Ref,class Ptr> // 三个参数的含义分别为--数据类型T--T的引用--T的指针
	struct _list_iterator
	{
		typedef ListNode<T> node;
		typedef _list_iterator<T, Ref, Ptr> self;
		
		node* _node; //迭代器的基本成员变量

		_list_iterator(node* node)
			:_node(node)
		{}

		
		self& operator++()
		{
			//...
		}

		self operator++(int)
		{
			//...
		}

		self& operator--()
		{
				//...
		}

		self operator--(int)
		{
			//...
		}

		Ref& operator*()
		{
			//...
		}

		Ptr& operator->()
		{
			//...
		}

		bool operator==(const self& s)
		{
			//...
		}

		bool operator!=(const self& s)
		{
			//...
		}
	}

🌺迭代器运算符重载的实现

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

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

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

	bool operator==(const self& s)
	{
		return _node == s._node;
	}

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

🌷list其它接口的实现

有了迭代器，我们才能更好的实现多种接口。

🌺迭代器相关函数

	template<class T>
	class list
	{
		typedef ListNode<T> node;
	public:
		typedef _list_iterator<T,T&,T*> iterator; // 类型重命名——普通迭代器
		typedef _list_iterator<T, const T&,const T*> const_iterator; // 类型重命名——const迭代器
		
		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);
		}
		//...
	}

🌺insert——插入

list模拟实现时，主要完成insert与erase（删除）函数实现即可，其它的头插、尾删等函数可以复用这两个函数。

	void insert(iterator pos,const T& data)
	{
		node* newNode = new node(data);

		node* cur = pos._node;
		node* prev = cur->_prev;

		newNode->_prev = prev;
		prev->_next = newNode;
		newNode->_next = cur;
		cur->_prev=newNode;
	}

🌺erase——删除

	iterator erase(iterator pos)
	{
		assert(pos != end());
		node* prev = pos._node->_prev;
		node * next = pos._node->_next;

		prev->_next = next;
		next->_prev = prev;
		delete pos._node;

		return iterator(next); // 返回删除位置的下一个迭代器位置
	}

🌺其它删除及插入操作

	void push_back(const T& data)
	{
		insert(end(),data);
	}

	void pop_back()
	{
		erase(--end());
	}

	void push_front(const T& data)
	{
		insert(begin(), data);
	}

	void pop_front()
	{
		erase(begin());
	}
	
	void clean() // 清空list
	{
		iterator it = begin();
		while (it != end())
		{
			//it = erase(it);
			erase(it++);
		}
	}

🌺迭代器区间构造

	// 迭代器区间构造
	template<class Iterator>
	list(Iterator begin, Iterator end)
	{
		//初始化
		_head = new node;
		_head->_next = _head;
		_head->_prev = _head;

		while (begin != end)
		{
			push_back(*begin);
			++begin;
		}
	}

🌺拷贝构造

	//拷贝构造
	list(const list<T>& lt)
	{
		//初始化
		_head = new node;
		_head->_next = _head;
		_head->_prev = _head;

		//复用区间构造
		list<T> tmp(lt.begin(), lt.end());
		swap(tmp);
	}

🌺赋值重载

	//赋值重载
	list<T>& operator=(list<T> lt)
	{
		swap(lt);
		return *this;
	}

🌺析构函数

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

🌷完整源码

#include<iostream>
#include<assert.h>
using namespace std;
namespace hxy
{
	//定义结点结构
	template<class T>
	struct ListNode
	{
		struct ListNode<T>* _next; // 指向下一个结点
		struct ListNode<T>* _prev; // 指向前一个结点
		T _data; // 结点存储的数据

		ListNode(const T& data = T()) // 构造函数 // 申请一个节点 
			:_next(nullptr),
			_prev(nullptr),
			_data(data)
		{}
	};
	//迭代器的定义
	template<class T, class Ref, class Ptr> // 三个参数的含义分别为--数据类型T--T的引用--T的指针
	struct _list_iterator
	{
		typedef ListNode<T> node;
		typedef _list_iterator<T, Ref, Ptr> self;
		node* _node;

		_list_iterator(node* node)
			:_node(node)
		{}

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

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

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

		bool operator==(const self& s)
		{
			return _node == s._node;
		}

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


	// list类的定义
	template<class T>
	class list
	{
		typedef ListNode<T> node;
	public:
		typedef _list_iterator<T, T&, T*> iterator;
		typedef _list_iterator<T, const T&, const T*> const_iterator;

		list()
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		// 迭代器区间构造
		template<class Iterator>
		list(Iterator begin, Iterator end)
		{
			//初始化
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;

			while (begin != end)
			{
				push_back(*begin);
				++begin;
			}
		}
		void swap(list<T>& tmp)
		{
			std::swap(_head, tmp._head);
		}
		//拷贝构造
		list(const list<T>& lt)
		{
			//初始化
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;

			//复用区间构造
			list<T> tmp(lt.begin(), lt.end());
			swap(tmp);
		}

		//赋值重载
		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}

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

		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 push_back(const T& data)
		{
			insert(end(),data);
		}

		void pop_back()
		{
			erase(--end());
		}

		void push_front(const T& data)
		{
			insert(begin(), data);
		}

		void pop_front()
		{
			erase(begin());
		}

		void insert(iterator pos, const T& data)
		{
			node* newNode = new node(data);

			node* cur = pos._node;
			node* prev = cur->_prev;

			newNode->_prev = prev;
			prev->_next = newNode;
			newNode->_next = cur;
			cur->_prev = newNode;
		}

		iterator erase(iterator pos)
		{
			assert(pos != end());
			node* prev = pos._node->_prev;
			node* next = pos._node->_next;

			prev->_next = next;
			next->_prev = prev;
			delete pos._node;

			return iterator(next); // 返回删除位置的下一个迭代器位置
		}

		void clean()
		{
			iterator it = begin();
			while (it != end())
			{
				//it = erase(it);
				erase(it++);
			}
		}
	private:
		node* _head;
	};
}
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
C++ 容器 数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入