C++ List （带你一篇文章搞定C++中的List类）

感谢大佬的光临各位，希望和大家一起进步，望得到你的三连，互三支持，一起进步

数据结构习题_LaNzikinh篮子的博客-CSDN博客

初阶数据结构_LaNzikinh篮子的博客-CSDN博客

收入专栏：C++_LaNzikinh篮子的博客-CSDN博客

其他专栏：c语言基础_LaNzikinh篮子的博客-CSDN博客

个人主页：LaNzikinh-CSDN博客

前言

经过前面两个容器的讲解，其实已经对很多接口的使用都了解的差不多了，容器之间接口的使用真的都是大体相同的，但是底层的实现是不同的，今天我们来看看列表是如何实现这个功能的，在讲解列表的实现之前，我们先要再次来讲解这个迭代器

一.迭代器

迭代器的功能分为四种迭代器，反向迭代器，常数迭代器，反向常数迭代器，他的性质有三种，单向迭代器，双向迭代器和随机迭代器，性质的意思就是底层结构，底层结构可以决定可以用哪些算法

举个例子来说，比如说我们之前学过的排序算法，他在库里面就一个专门这样子的函数sort，他支持的就是随机的代替其他不支持，所以说在list创建的类就不能用这个库里面的算法，只能自己实现一个，又比如说逆置算法reverse（需要++/--）他支持双向迭代器，所以说随机的也可以，但是单向的就不行

我们的list就是双向迭代器，我们之前学过的vector和string就是随机迭代器，那我们后面的栈和队列是什么呢？

答案是根本不支持迭代,栈的特性是先进后出，队列的特性是先进先出，如果都满足了迭代器的遍历，那这些特性就不存在了，你支持了迭代器，那你的特性的意义在什么地方呢

二.list的底层实现

我们之前讲过了库函数的使用，直接看文档即可，在这里就不做多的了解了，和之前的使用string，vector是大致相同的，主要还是来看list的底层，他是一个带头双向循环列表，不是我们以前C语言学过的单链表

接下来了，我们先要来定义两个结构体，一个就是节点本身，还有一个就是指向节点的指针，即便它是一个带头双向循环列表，这两个也是必不可少的

2.1定义两个结构体

结点

const T& data = T()；利用缺省参数来进行初始化

template<class T>
struct list_node
{
	T _data;
	list_node<T>* _next;
	list_node<T>* _prev;

	list_node(const T& data = T())
		:_data(data)
		, _next(nullptr)
		, _prev(nullptr)
	{}
};

指向节点的指针

注意：这里获取的迭代器，就是一个节点的指针

因为他是一个指针，所以说我们要用函数重载来定义它的加加减减和判断等于，还有解引用

template<class T>
struct list_iterator
{
	typedef list_node<T> Node;
	typedef list_iterator<T> Self;
	Node* _node;

	list_iterator(Node* node)
		:_node(node)
	{}

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

	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}

	Self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}

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

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

2.2insert（）和 erase（）

迭代器失效问题

前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

insert（）

void insert(iterator pos, const T& x)
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;

	Node* newnode = new Node(x);

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

	++_size;
}

erase（）

只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响

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

	--_size;
}

所以要用返回值来改正，防止迭代器失效

int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array+sizeof(array)/sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{
l.erase(it++); // it = l.erase(it);
}

2.3头插尾插一个数据

直接复用就可以了

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

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

2.4析构函数和迭代器函数

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

iterator end()
{
	return _head;
}

list()
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
	_size = 0;
}

2.4成员对象

private:
	Node* _head;
	size_t _size;

三.list使用和细节

还是补充几个list一些独特的函数使用方式和一些使用它的细节

emplace：构造和插入元素

他是支持直接传构造函数对象的参数的

list<A> lt;
A a1(1,1);
lt.push_back(3,3);//不合理，不存在
lt.emplace_back(3,3);//可以

unique：删除重复值

注意：前提要有序不然删不完全

merge：合并排序列表

注意：合并排序列表，v1会被滞空

it.merge(v1);

补：

如果要在pos的位置插入一个30大小的元素

auto it = lt.begin();
int k = 3;
while (k--)
{
	++*it;
}
it.insert(it, 30);

因为他的迭代器只支持++

总结

链表容器结构到这里就结束了，下一章，我们将引入一个适配器的概念去完成栈与队列的知识