[数据结构与算法]＜C++＞详解list类

1. list介绍

list的文档

简单来说：list就是数据结构里的双向循环带头链表
如果对双向循环带头链表不熟悉，可以看看我写过的这篇博文＜数据结构＞你敢信？带头双向循环链表其实很简单

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

2. list使用

2.1 list构造

2.2 list iterator的使用

现在可以暂时把iterator理解为一个指向节点的指针，稍后我们再模拟实现它

用法跟string和vector的一样

2.3 list内存管理

2.4 list元素访问

2.5 list增删查改

2.6 list的迭代器失效

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

// 插入时迭代器不失效
void test1()
{
	tyyg::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	lt.push_back(6);

	// 在偶数前面插入这个偶数*10
	auto it1 = lt.begin();
	while (it1 != lt.end())
	{
		if (*it1 % 2 == 0)
		{
			lt.insert(it1, (*it1) * 10);// it1还是指向该偶数，没有迭代器失效问题
		}
		++it1;
	}
	for (auto v : lt)
	{
		cout << v << " ";
	}
	cout << endl;
}

// 删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响
void test2()
{
	tyyg::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	lt.push_back(6);

	// 删除偶数
	auto it1 = lt.begin();
	while (it1 != lt.end())
	{
		if (*it1 % 2 == 0)
		{
			// 删除之后出现野指针，迭代器失效。
			it1 = lt.erase(it1);// erase返回删除节点的下一个节点的地址，不用自己++了
		}
		else
		{
			++it1;
		}
	}
	for (auto v : lt)
	{
		cout << v << " ";
	}
	cout << endl;
}

3. list的模拟实现

3.1 模拟实现list

#pragma once
#include <iostream>
#include <assert.h>
#include "ReverseIterator.h"
using namespace std;

namespace tyyg
{
	// 把节点封装起来
	template<class T>
	struct list_node
	{
		list_node<T>* _next;
		list_node<T>* _prev;
		T _data;

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

	};

	// 把迭代器封装起来
	template<class T, class Ref, class Ptr>// 为了支持const迭代器
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self;
		Node* _node;

		__list_iterator(Node* node)// 用节点的指针初始化迭代器
			: _node(node)
		{}

		// 析构 不需要（节点不属于迭代器），默认生成的函数会去调用Node的析构
		// 拷贝构造、赋值重载 默认生成的浅拷贝就可以

		Ref operator*()
		{
			return _node->_data;// _data所在的Node是new出来的，可以引用返回
		}

		Ptr operator->()
		{
			return &_node->_data;// 使用中会变成it.operator->()->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 self& it)
		{
			return _node != it._node;
		}

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

		
	};

	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;// T前面不能加const，否则list_node<T>和list_node<const T>之间无法赋值
		// 反向迭代器适配支持
		typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
		typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;

		iterator begin()
		{
			//return iterator(_head->_next);// 返回匿名对象，不能引用返回
			return _head->_next;// 隐式类型转换，如果不想这样可以在iterator构造函数前加explicit
		}

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

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

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

		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}

		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}

		const_reverse_iterator rbegin() const
		{
			return const_reverse_iterator(end());
		}

		const_reverse_iterator rend() const
		{
			return const_reverse_iterator(begin());
		}

		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 empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		template<class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			empty_init();

			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

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

		list(const list<T>& lt)
		{
			empty_init();
			list<T> tmp(lt.begin(), lt.end());
			swap(tmp);
		}

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

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

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

		void push_back(const T& x)
		{
			//Node* tail = _head->_prev;
			//Node* newnode = new Node(x);// 要记得new

			//tail->_next = newnode;
			//newnode->_prev = tail;
			//newnode->_next = _head;
			//_head->_prev = newnode;
			insert(end(), x);
		}

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

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

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

		// 在pos位置之前插入
		iterator insert(iterator pos, const T& x)
		{
			Node* newnode = new Node(x);
			Node* cur = pos._node;
			Node* prev = cur->_prev;

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

			return iterator(newnode);// 虽然不会迭代器失效，但库里有返回值
		}

		iterator erase(iterator pos)
		{
			assert(pos != end());

			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

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

			return iterator(next);// 解决野指针导致的迭代器失效问题
		}

	private:
		Node* _head;
	};

}
// ReverseIterator.h
// 反向迭代器封装
namespace tyyg
{
	template<class Iterator, class Ref, class Ptr>
	struct Reverse_iterator
	{
		typedef Reverse_iterator<Iterator, Ref, Ptr> Self;
		Iterator _it;

		Reverse_iterator(Iterator it)
			: _it(it)
		{}

		Ref operator*()
		{
			Iterator tmp = _it;
			return *(--tmp);
		}

		Ptr operator->()
		{
			return &(operator*());
		}

		Self operator++()
		{
			--_it;
			return *this;
		}

		Self operator--()
		{
			++_it;
			return *this;
		}

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

	};
}

3.2 list的反向迭代器

通过前面例子知道，反向迭代器的++就是正向迭代器的–，反向迭代器的–就是正向迭代器的++，因此反向迭代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口进行包装即可

模拟实现的里面有反向迭代器的封装、和const迭代器的封装。

4. vector和list的区别