【C++ 】list 类

1. 标准库中的list类

list 类的介绍：

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代

2. list与forward_list非常相似：最主要的不同在于forward_list是单链表

3. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好，只是不支持任意位置的随机访问

a. list 的构造函数

list() (无参构造函数)
list (const list& x) （拷贝构造）
list (InputIterator first, InputIterator last)

（用[first, last)区间中的元素构造list ）

list (size_type n, const value_type& val = value_type())

（构造的list中包含n个值为val的元素）

注意：

list 的迭代器是双向迭代器（完成 ++ , --），可以支持传单向迭代器( 完成 ++ ) 和双向迭代器

b. list 增删查改

push_back (尾插)
push_front (头插)
pop_back (尾删)
pop_front (头删)
insert (在某一位置前增加新节点)

代码举例1

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

int main()
{
	list<int> lt;
	lt.push_back(0);
	lt.push_back(10);
	lt.push_back(20);
	lt.push_back(30);
	list<int> ::iterator it = lt.begin();
	++it;
	lt.insert(it,70);
	it = lt.begin();
	while(it != lt.end())
	{
		cout << *it << endl;
		++it;
	}
}

运行结果：

earse (删除某一位置的节点)

代码举例2

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

int main()
{
	list<int> lt;
	lt.push_back(0);
	lt.push_back(10);
	lt.push_back(20);
	lt.push_back(30);
	list<int> ::iterator it = lt.begin();
	++it;
	lt.erase(it);
	it = lt.begin();
	while(it != lt.end())
	{
		cout << *it << endl;
		++it;
	}
}

运行结果：

swap ( 交换两个list中的元素 )

代码举例3

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

int main()
{
	list<int> lt;
	lt.push_back(10);
	lt.push_back(20);
	lt.push_back(30);
	list<int> llt;
	llt.push_back(4);
	llt.push_back(5);
	llt.push_back(6);
	lt.swap(llt);
	auto it = lt.begin();
	while(it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	for (auto i : llt)
	{
		cout << i << " ";
	}
}

运行结果：

clear (清除有效节点，即不包括哨兵位)

c. list 容量

d. list 获取元素

e. list 迭代器

begin + end ( 返回第一个元素的迭代器+ 返回最后一个元素下一个位置的迭代器 )

画图分析

rbegin + rend （返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的 reverse_iterator,即begin位置）

注意：

反向迭代器的模拟实现和我们理解的有偏差，图上为了理解，我们可以认为rbegin是最后一个元素，rend是第一个元素的前一个位置

但是实际上，rbegin指向的位置就是end的位置，rend指向的位置就是rbegin的位置，但是在解引用时，会运算符重载 *，得到该位置的上一个位置（详情看 list 模拟实现）

2. 迭代器失效

list 迭代器类似一个指针，指向节点的地址 (具体详情看 list 的模拟实现)

所以在发生 erase 的时候容易造成迭代器失效(即野指针)

3. list 类的模拟实现

代码

namespace lhy
{
    template<class T>
struct ListNode
{
public:
	ListNode* prev;
	ListNode* next;
	T val;
	ListNode(const T& t = T())
	{
		prev = next = nullptr;
		val = t;
	}
};
template<class T,class Ref,class Ptr>
class list_iterator
{
public:
	typedef list_iterator<T,Ref,Ptr>  self;
	list_iterator(ListNode<T>* n)
		:_node(n)
	{}
	Ptr operator->()
	{
		return &_node->val;
	}
	Ref operator*()
	{
		return _node->val;
	}
	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 list_iterator& t)
	{
		return _node != t._node;
	}
	bool operator==(const list_iterator& t)
	{
		return _node == t._node;
	}
	ListNode<T>* _node;
};

template<class iterator,class Ref,class Ptr>
	class list_converse_iterator
	{
	private:
		iterator com;
	public:
		typedef list_converse_iterator  self;
			list_converse_iterator(iterator& it)
			:com(it)
		{}
		Ptr operator->()
		{
			return &(*com);
		}
		Ref operator*()
		{
			iterator tmp = com;
			--tmp;
			return *tmp;
		}
		self& operator++()
		{
			--com;
			return *this;
		}
		self operator++(int)
		{
			self tmp = *this;
			--*this;
			return tmp;
		}
		self& operator--()
		{
			++com;
			return *this;
		}
		self operator--(int)
		{
			self tmp = *this;
			++*this;
			return tmp;
		}
		bool operator!=(const self& t)
		{
			return com != t.com;
		}
		bool operator==(const self& t)
		{
			return com == t.com;
		}
	};
	template<class T>
	class List
	{
	public:
		typedef list_iterator<T, T&, T*> iterator;
		typedef list_iterator<T, const T&, const T*>  const_iterator;
		typedef list_converse_iterator<iterator, T&, T*>  converse_iterator;
		typedef list_converse_iterator<iterator, const T&,const T*>  const_converse_iterator;
		List()
		{
			node = new ListNode<T>;
			node->next = node;
			node->prev = node;
		}
		iterator begin()
		{
			return iterator(node->next);
		}
		const const_iterator begin() const
		{
			return const_iterator(node->next);
		}
		iterator end()
		{
			return iterator(node);
		}
		const const_iterator end() const
		{
			return const_iterator(node);
		}
		converse_iterator rbegin()
		{
			return converse_iterator(end());
		}
		const_converse_iterator rbegin() const
		{
			return const_converse_iterator(end());
		}
		converse_iterator rend()
		{
			return converse_iterator(begin());
		}
		const_converse_iterator rend()
		{
			return const_converse_iterator(begin());
		}
	void push_back(const T& val)
	{
		ListNode<T>* ptail = node->prev;
		ListNode<T>* newnode = new ListNode<T>(val);
		ptail->next = newnode;
		newnode->next = node;	
		newnode->prev = ptail;
		node->prev = newnode;
	}
	void push_front(const T& x)
	{
		insert(begin(), x);
	}
	void insert(iterator pos,const T &x)
	{
		ListNode<T>* cur = pos._node;
		ListNode<T>* newnode = new ListNode<T>(x);
		newnode->next = cur;
		newnode->prev = cur->prev;
		cur->prev->next = newnode;
		cur->prev = newnode;
	}
	void earse(iterator pos)
	{
		ListNode<T>* cur = pos._node;
		assert(cur != node);
		ListNode<T>* _prev = cur->prev;
		ListNode<T>* _next = cur->next;
		_prev->next = _next;
		_next->prev = _prev;
		delete cur;
	}
private:
	ListNode<T>* node;
};
}

list 迭代器的实现

单看这一个类的实现，可能会疑惑，已经有一个 List 类了，为什么还要加一个 list_iterator 类，并且很容易发现，两个类的成员变量是一样的

如：list<int> :: iterator it;

我们希望 *it 得到的是T类型的变量（这里是int 类型）

而 it++ 得到的是下一个节点的地址

如果是只有 List 类，无法实现

因为如果 typedef ListNode* iterator

那么 *it 的类型就是 ListNode;

it++ 也不是下一个结点的地址（这是链表，开辟的空间不是连续的）

所以这里的 list_iterator 类是为了运算符重载 *和++

代码注意事项

可以和下面的对应

注意：

const iterator 修饰的是（ListNode<T>*），即指针不可以更改，但是指针所指向的内容可以更改

const_iterator 修饰的是 const ListNode<T>* ,即指针所指向的内容不可更改

注意：

对于这个运算符重载，实际写的时候只要写一个 -> 就行，编译器简化两个 ->

模板第一个传的是正向迭代器，利用正向迭代器来实现反向迭代器的功能

这里运算符重载* 让正向迭代器--再解引用，是为了得到原先T 类型的数据的前一个数据，原因如下：

这里传递是 end() ，但是对应的数据不是我们想要的

才会在解引用得到前一个数据的值