【C++】学习笔记——list

八、list

list链接

1. list的介绍

是的， list 就是带头双向循环链表。

2. list的使用

通过 string 和 vector 的学习，我们差不多已经很了解容器的使用了，接下来要非常快速的过一遍了。

#include<iostream>
#include<list>
using namespace std;

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);

	list<int>::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	return 0;
}

简简单单。

链表嘛，有头插、头删、尾插、尾删。也非常好使用，跟 push_back() 和 pop_back() 一样的用法。看到了 insert 和 erase ，我们知道，vector 的 insert 和 erase 可能会发生迭代器失效的问题，那 list 会出现吗？答案是不会发生，毕竟是链表嘛。
list 的大部分接口我们都了解了，我们就来看看一些之前没见过的东西。

首先我们来看看 reverse 。注意！是 reverse ，不是 reserve ，前者是逆置的意思，后者是保留，扩容的意思。sort 是排序的意思。

非常的简洁明了啊。

#include<iostream>
#include<list>
using namespace std;

int main()
{
	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.reverse();

	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	lt.sort();
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	return 0;
}

sort 默认排的都是升序，若是想要排降序，需要用到 仿函数 ，这里先不过多介绍。list 的 sort 效率比较低，当数据量大的时候，经量不要用 list 的 sort 排序。

merge 是合并的意思，用的比较少。

unique 的作用是去重，去除重复元素，要求是必须先有序。

#include<iostream>
#include<list>
using namespace std;

int main()
{
	list<int> lt;
	lt.push_back(2);
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(5);
	lt.push_back(1);
	lt.push_back(5);
	lt.push_back(4);
	lt.push_back(4);
	lt.push_back(4);
	lt.push_back(5);
	lt.push_back(1);
	lt.push_back(2);

	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	
	// 先排序
	lt.sort();
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	
	// 再去重
	lt.unique();
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	return 0;
}

remove 相当于 find + erase ，给你一个值，找到了就删，找不到就不删。

splice 这个接口很怪，它的作用是 转移 。

它可以将某一个链表，或者某个链表的某个值，或者某个链表的某一块区间转移到 position 位置 。也可以自己转移自己。

#include<iostream>
#include<list>
using namespace std;

int main()
{
	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 链表的 begin() 转移到 lt 链表的 end()
	lt.splice(lt.end(), lt, lt.begin());

	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	return 0;
}

确实将头部的 1 转移到 尾部的 5 后面了。转移的本质是改变节点的指向，并不是删除或创建节点 。

3. list的模拟实现

我们快速的搭一个 list 框架出来， 这个框架大致基于 STL库里的 list 。注意理解。

#pragma once

#include<assert.h>

namespace my
{
	// struct 成员默认全公开   节点结构体
	template<class T>
	struct ListNode
	{
		// 后继指针
		ListNode<T>* _next;
		// 前驱指针
		ListNode<T>* _prev;
		// 数据域
		T _data;
		
		// 构造函数
		ListNode(const T& x = T())
			:_next(nullptr)
			,_prev(nullptr)
			,_data(x)
		{}
	};

	template<class T>
	class list
	{
		typedef ListNode<T> Node;
	public:
		// 默认构造
		list()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}
	private:
		// 指向头节点的指针
		Node* _head;
	};
}

写一个尾插操作：

// list类的 public域
void push_back(const T& x)
{
	// 实例化新节点
	Node* newnode = new Node(x);
	// 尾部节点
	Node* tail = _head->_prev;

	// 修改新节点的指向
	newnode->_next = _head;
	newnode->_prev = tail;

	// 修改指向新节点的指针
	tail->_next = newnode;
	_head->_prev = newnode;
}

有了尾插，我们就想去测试一下，但是测试需要访问，list 本身不支持 下标 + [] 访问，只能通过迭代器访问。我们之前说过 迭代器是一个行为像指针的东西，但不一定是指针 。那么 list 这里的迭代器可以使用原生指针吗，我们发现，链表本身是不连续的，我们 ++指针 无法访问到到下一个元素，解引用指针 也访问不到元素的数据。
因此，这里的迭代器并不能使用原生指针来代替。我们知道，可以通过重载一系列运算符来改变类的行为 ，就像日期类一样，++日期 可以得到下一天的日期，那么我们也可以将迭代器封装成一个类，然后通过重载运算符来改变其行为。

// my命名空间内
// 迭代器模板
template<class T>
struct ListIterator
{
	typedef ListNode<T> Node;

	// 指向节点的指针
	Node* _node;
	
	// 构造函数
	ListIterator(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;
}

接着是迭代器的解引用：迭代器解引用我们要得到什么？得到节点的值，所以要返回数据

// 可读可写
T& operator*()
{
	return _node->_data;
}

判断相等：

bool operator!=(const Self& it)
{
	return _node != it._node;
}

bool operator==(const Self& it)
{
	return _node == it._node;
}

现在我们要实现 begin 和 end 。请问这两个函数在哪里实现？在迭代器类里面实现吗？不对，迭代器类根本不知道链表的组成，这俩函数只能在 list类 里面实现。

// list类里面
iterator begin()
{
	// 匿名对象
	return iterator(_head->_next);
}

iterator end()
{
	// 匿名对象 _head是最后一个节点的下一个节点
	return iterator(_head);
}

完事儿，迭代器的行为也写完了，我们把当前的完整代码给出来：

#pragma once

#include<assert.h>

namespace my
{
	// struct 成员默认全公开   节点结构体
	template<class T>
	struct ListNode
	{
		// 后继指针
		ListNode<T>* _next;
		// 前驱指针
		ListNode<T>* _prev;
		// 数据域
		T _data;

		ListNode(const T& x = T())
			:_next(nullptr)
			,_prev(nullptr)
			,_data(x)
		{}
	};

	// 迭代器模板
	template<class T>
	struct ListIterator
	{
		typedef ListNode<T> Node;
		// self : 自己
		typedef ListIterator<T> Self;

		// 指向节点的指针
		Node* _node;

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

		// 可读可写，引用返回
		T& operator*()
		{
			return _node->_data;
		}

		bool operator!=(const Self& it)
		{
			return _node != it._node;
		}

		bool operator==(const Self& it)
		{
			return _node == it._node;
		}
	};

	// 链表类
	template<class T>
	class list
	{
		typedef ListNode<T> Node;
	public:
		typedef ListIterator<T> iterator;

		iterator begin()
		{
			// 匿名对象
			return iterator(_head->_next);
		}

		iterator end()
		{
			// 匿名对象
			return iterator(_head);
		}

		// 默认构造
		list()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		void push_back(const T& x)
		{
			// 实例化新节点
			Node* newnode = new Node(x);
			// 尾部节点
			Node* tail = _head->_prev;

			// 修改新节点的指向
			newnode->_next = _head;
			newnode->_prev = tail;

			// 修改指向新节点的指针
			tail->_next = newnode;
			_head->_prev = newnode;
		}
	private:
		// 指向头节点的指针
		Node* _head;
	};
	// 测试区
}

我们来测试一下：

// 测试区
void test01()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);

	list<int>::iterator it = lt.begin();
	while (it != lt.end())
	{
		std::cout << *it << " ";
		++it;
	}
	std::cout << std::endl;
}

// test.cpp
#include<iostream>
#include"list.h"

int main()
{
	my::test01();
	return 0;
}

成功运行，我们的最基础的 list 框架可算是搭建好了。
接下来是 insert 。在 pos 位置前插入 val 。

void insert(iterator pos, const T& val)
{
	// 目标节点
	Node* cur = pos._node;
	// 待插入的节点
	Node* newnode = new Node(val);
	// 目标节点的上一个节点
	Node* prev = cur->_prev;

	newnode->_prev = prev;
	newnode->_next = cur;

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

还有 erase 。

iterator erase(iterator pos)
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;

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

	delete cur;
	// 返回下一个节点的迭代器，避免迭代器失效
	return iterator(next);
}

有了 insert 和 erase ，我们就可以把 push_back 给复用一下，然后我们再将其他插入删除给顺便完成了。

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

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

void pop_back()
{
	// 必须是 -- ，不能是 - 1，因为迭代器不支持 - ，支持 --
	erase(--end());
}

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

来测试一下：

// 测试区
void test02()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_front(3);
	lt.push_front(4);
	lt.push_back(5);

	list<int>::iterator it = lt.begin();
	while (it != lt.end())
	{
		std::cout << *it << " ";
		++it;
	}
	std::cout << std::endl;

	lt.pop_back();
	lt.pop_front();

	for (auto e : lt)
	{
		std::cout << e << " ";
	}
	std::cout << std::endl;
}

#include<iostream>
#include"list.h"

int main()
{
	my::test02();
	return 0;
}

同样符合预期。
size ：遍历一遍即可。

size_t size() const
{
	Node* begin = _head;
	size_t num = 0;
	while (begin->_next != _head)
	{
		++num;
		begin = begin->_next;
	}
	return num;
}

list类 实现的差不多了，我们接着完善 迭代器类 。
我们新增一个自定义类型 A 。

struct A
{
	int _a1;
	int _a2;

	A(int a1 = 0, int a2 = 0)
		:_a1(a1)
		,_a2(a2)
	{}
};

//测试区
void test03()
{
	list<A> lt;
	A aa1(1, 1);
	// 有名对象
	lt.push_back(aa1);
	// 匿名对象
	lt.push_back(A(2, 2));
	// 多参数的隐式类型转换 {}
	lt.push_back({ 3,3 });

	for (auto e : lt)
	{
		std::cout << e << " ";
	}
	std::cout << std::endl;
}

我们会发现不能运行。

因为内置类型可以使用流插入，自定义类型没写重载流插入就用不了，所以该怎么遍历呢？由于这里的成员变量都是共有的，所以直接访问成员变量就可以了。

// 测试区
void test03()
{
	list<A> lt;
	A aa1(1, 1);
	// 有名对象
	lt.push_back(aa1);
	// 匿名对象
	lt.push_back(A(2, 2));
	// 多参数的隐式类型转换 {}
	lt.push_back({ 3,3 });

	list<A>::iterator it = lt.begin();
	while (it != lt.end())
	{
		std::cout << (*it)._a1 << (*it)._a2 << " ";
		++it;
	}
	std::cout << std::endl;
}

#include<iostream>
#include"list.h"

int main()
{
	my::test03();
	return 0;
}

就可以遍历了。但是，既然可以 (*it)._a1 那就要可以 it->_a1 。所以我们还需要给迭代器类再重载一个运算符。

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

有人会说，欸？这里怎么返回的是data的地址啊，那咋能访问到 _a1 啊？

void test04()
{
	list<A> lt;
	A aa1(1, 1);
	// 有名对象
	lt.push_back(aa1);
	// 匿名对象
	lt.push_back(A(2, 2));
	// 多参数的隐式类型转换 {}
	lt.push_back({ 3,3 });

	list<A>::iterator it = lt.begin();
	while (it != lt.end())
	{
		std::cout << it->_a1 << it->_a2 << " ";
		++it;
	}
	std::cout << std::endl;
}

但确实能跑了。其实是这里编译器做了相关的优化。咱们写的 it->_a1 编译器自动识别成 it->->_a1 ，也就是 it.operator->()->_a1 ，就是 &_data->_a1 。这下终于理解了，原理编译器帮我们省略了一个 -> 。
我们来实现一个 const迭代器 。最简单粗暴的方式就是 再定义一个const迭代器类 然后将其 解引用重载函数 和 ->重载函数 前面加上 const 就能够完成任务，但是如果就这两处不同的话，那普通迭代器和const迭代器代码相似度也太高了，有点冗余，该怎么合并呢？可以用类模板。

// Ref就是引用返回，Ptr就是指针返回
template<class T, class Ref, class Ptr>
struct ListIterator
{
	//
};

// list类里
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;

这就相当于：我们写了一个类模板，编译器帮我们实例化生成了普通迭代器类和const迭代器类 。

list 到这里基本差不多了，我们最后收尾一下。
list 的清理：

void clear()
{
	iterator it = begin();
	while (it != end())
	{
		it = erase(it);
	}
}

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

判空：

bool empty()
{
	return size() == 0;
}

拷贝构造：

list(const list<T>& lt)
{
	// 初始的头结点
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;

	for (auto& e : lt)
	{
		push_back(e);
	}
}

复制重载：

void swap(list<T> lt)
{
	std::swap(_head, lt._head);
}

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

现在大部分接口都已经手到擒来了。

4. list模拟实现的代码整合

1. list.h

#pragma once

#include<assert.h>

namespace my
{
	// struct 成员默认全公开   节点结构体
	template<class T>
	struct ListNode
	{
		// 后继指针
		ListNode<T>* _next;
		// 前驱指针
		ListNode<T>* _prev;
		// 数据域
		T _data;

		ListNode(const T& x = T())
			:_next(nullptr)
			,_prev(nullptr)
			,_data(x)
		{}
	};

	// 迭代器模板
	template<class T, class Ref, class Ptr>
	struct ListIterator
	{
		typedef ListNode<T> Node;
		// self : 自己
		typedef ListIterator<T, Ref, Ptr> Self;

		// 指向节点的指针
		Node* _node;

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

		// 可读可写
		//T& operator*()
		Ref operator*()
		{
			return _node->_data;
		}

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

		bool operator!=(const Self& it)
		{
			return _node != it._node;
		}

		bool operator==(const Self& it)
		{
			return _node == it._node;
		}
	};

	template<class T>
	class list
	{
		typedef ListNode<T> Node;
	public:
		typedef ListIterator<T, T&, T*> iterator;
		typedef ListIterator<T, const T&, const T*> const_iterator;

		iterator begin()
		{
			// 匿名对象
			return iterator(_head->_next);
		}

		iterator end()
		{
			// 匿名对象
			return iterator(_head);
		}

		// 迭代器指向的内容不能修改，const iterator不是我们要的const迭代器

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

		const_iterator end() const
		{
			return iterator(_head);
		}

		// 默认构造
		list()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		list(const list<T>& lt)
		{
			// 初始的头结点
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;

			for (auto& e : lt)
			{
				push_back(e);
			}
		}

		void swap(list<T> lt)
		{
			std::swap(_head, lt._head);
		}

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

		bool empty()
		{
			return size() == 0;
		}

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

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

		//void push_back(const T& x)
		//{
		//	// 实例化新节点
		//	Node* newnode = new Node(x);
		//	// 尾部节点
		//	Node* tail = _head->_prev;

		//	// 修改新节点的指向
		//	newnode->_next = _head;
		//	newnode->_prev = tail;

		//	// 修改指向新节点的指针
		//	tail->_next = newnode;
		//	_head->_prev = newnode;
		//}

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

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

		void pop_back()
		{
			// 必须是 -- ，不能是 - 1，因为迭代器不支持 - ，支持 --
			erase(--end());
		}

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

		iterator insert(iterator pos, const T& val)
		{
			// 目标节点
			Node* cur = pos._node;
			// 待插入的节点
			Node* newnode = new Node(val);
			// 目标节点的上一个节点
			Node* prev = cur->_prev;

			newnode->_prev = prev;
			newnode->_next = cur;

			prev->_next = newnode;
			cur->_prev = newnode;

			return iterator(newnode);
		}

		iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev; 
			Node* next = cur->_next;

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

			delete cur;
			// 返回下一个节点的迭代器，避免迭代器失效
			return iterator(next);
		}

		size_t size() const
		{
			Node* begin = _head;
			size_t num = 0;
			while (begin->_next != _head)
			{
				++num;
				begin = begin->_next;
			}
			return num;
		}
	private:
		// 指向头节点的指针
		Node* _head;
	};

	struct A
	{
		int _a1;
		int _a2;

		A(int a1 = 0, int a2 = 0)
			:_a1(a1)
			,_a2(a2)
		{}
	};

	void test01()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);

		list<int>::iterator it = lt.begin();
		while (it != lt.end())
		{
			std::cout << *it << " ";
			++it;
		}
		std::cout << std::endl;
	}

	void test02()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_front(3);
		lt.push_front(4);
		lt.push_back(5);

		list<int>::iterator it = lt.begin();
		while (it != lt.end())
		{
			std::cout << *it << " ";
			++it;
		}
		std::cout << std::endl;

		lt.pop_back();
		lt.pop_front();

		for (auto e : lt)
		{
			std::cout << e << " ";
		}
		std::cout << std::endl;

		std::cout << lt.size();
	}

	void test03()
	{
		list<A> lt;
		A aa1(1, 1);
		// 有名对象
		lt.push_back(aa1);
		// 匿名对象
		lt.push_back(A(2, 2));
		// 多参数的隐式类型转换 {}
		lt.push_back({ 3,3 });

		list<A>::iterator it = lt.begin();
		while (it != lt.end())
		{
			std::cout << (*it)._a1 << (*it)._a2 << " ";
			++it;
		}
		std::cout << std::endl;
	}

	void test04()
	{
		list<A> lt;
		A aa1(1, 1);
		// 有名对象
		lt.push_back(aa1);
		// 匿名对象
		lt.push_back(A(2, 2));
		// 多参数的隐式类型转换 {}
		lt.push_back({ 3,3 });

		list<A>::iterator it = lt.begin();
		while (it != lt.end())
		{
			std::cout << it->_a1 << it->_a2 << " ";
			++it;
		}
		std::cout << std::endl;
	}
}

2. test.cpp

#include<iostream>
#include"list.h"

int main()
{
	my::test03();
	return 0;
}

未完待续