1. list的介绍及使用
1.1 list的介绍

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

2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指其前一个元素和后一个元素。

3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。

4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。

5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

1.2 list的使用

list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口：

1.2.1 list的构造
 

1.2.2 list iterator的使用

list迭代器可以理解成一个指针，该指针指向list中的某个节点。实际它是指针的封装。

void testlist1()
	{
		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();
		cout << *it++ << endl;
		while (it != lt.end())
		{
			cout << *it << " ";
			it++;
		}

		cout << endl;

	}

1.2.3 list capacity

1.2.4 list element access

int main()
{

	//list<int> lt(3);
	vector<int> v{ 4,5 };

    vector<string> tokens{ "4","13","5","/","+" };
    cout<<evalRPN(tokens)<<endl;

    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_back(5);
    //这里可以直接修改里面第一个元素的值
    lt.front() = 10;  
    for (auto e : lt)
    {
        cout << e << " ";
    }
    cout << endl;
    
	return 0;
}

1.2.5 list modifiers

以下代码对部分接口进行测试：

	void testlist3()
	{
		list<int> lt;
		lt.push_front(1);
		lt.push_front(2);
		lt.push_front(3);
		lt.push_front(4);
		lt.push_front(5);
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
		list<int> lt1;
		lt1.push_front(10);
		lt1.push_front(20);
		lt1.push_front(30);
		lt1.push_front(40);
		lt.swap(lt1);
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl<<"头删后："<<endl;

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

1.2.6 list的迭代器失效

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

删除list容器的所有值 正确写法：

void TestListIterator()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> l(array, array + sizeof(array) / sizeof(array[0]));
    for (auto e : l)
    {
        cout << e <<" ";
    }
    auto it = l.begin();
    while (it != l.end())
    {
        //此时it已经指向原来it的下一个迭代器位置
        l.erase(it++); // it = l.erase(it);

        //下面两行为错误写法

        //l.erase(it);
        //++it;
    }
    for (auto e : l)
    {
        cout << e <<endl;
    }
}

2. list的模拟实现

2.1 模拟实现list

要模拟实现list，必须要熟悉list的底层结构以及其接口的含义，通过上面的学习，这些内容已基本掌握，现在我们来模拟实现list。

namespace xwy {
	template<typename T>
	struct listNode
	{
		T _data;
		listNode<T>* _pre;
		listNode<T>* _next;
		//单参数构造函数
		listNode(const T& val = T())
			:_data(val),
			_pre(nullptr),
			_next(nullptr)
		{

		}

		
	};
	template<typename T, class Ref, class Ptr>
	struct _list_iterator
	{
		//  受类域的限制
		typedef listNode<T> Node;
		typedef _list_iterator<T,Ref,Ptr> self;
		Node* _node;
		_list_iterator(Node *node=nullptr):
			_node(node)
		{

		}
		//操作符重载
		Ref operator*()
		{
			return _node->_data;
		}
		Ptr operator->()
		{
			return &(_node->_data);
		}

		self& operator--()
		{
			_node = _node->_pre;
			return *this;
		}
		self operator-(int a)
		{
			Node* ptr = _node;

			while (a--&&ptr)
			{
				ptr = ptr->_pre;
			}
			return ptr;
		}

		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		self operator++(int)
		{
			//  self tmp(*this)  拷贝构造自己
			Node* tmp = _node;
			_node = _node->_next;
			return tmp;
			
		}

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

	};
	// 适配器 -- 复用
	template<class Iterator, class Ref, class Ptr>
	struct Reverse_iterator
	{
		Iterator _it;
		typedef  Reverse_iterator<Iterator, Ref, Ptr> self;
		Reverse_iterator(const Iterator &it):
			_it(it)
		{

		}
		//操作符重载
		Ref operator*()
		{
			return *_it;
		}
		self& operator--()
		{
			++_it;
			return *this;
		}

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

		self& operator++()
		{
			--_it;
			return *this;
		}
		self operator++(int)
		{
			//  self tmp(*this)  拷贝构造自己
			Iterator it = _it;
			--_it;
			return it;

		}

		bool operator!=(const self& lt) const   //const和const比较 ，非const和const比较
		{
			return lt._it != _it;   //不支持那两种类型的比较，是因为不存在那两种类型比较的重载
		}


	};

	template<typename T>
	class list
	{
	public:
		typedef listNode<T> Node;
		typedef _list_iterator<T,T&,T*> iterator;   
		typedef _list_iterator<T, const T&, const T*> const_iterator;
		typedef Reverse_iterator<iterator,T&,T*> reverse_iterator;
		typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
		//无参构造函数
		list()
		{
			empty_init();
			
		}
		template<class iterator>
		list(iterator first,iterator last)
		{
			empty_init();
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}
		//拷贝构造
		list(const list& lt)
		{
			empty_init();
			auto it = lt.begin();
			while (it != lt.end())
			{
				push_back(*it);
				it++;
			}

		}

		//迭代器的实现
		iterator begin() 
		{
			return _head->_next;
		}

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

		const_iterator end() const
		{
			return _head;
		}


		//反向迭代器
		reverse_iterator rbegin()
		{
			return --end();
		}
		reverse_iterator rend()
		{
			return --begin();
		}

		const_reverse_iterator rbegin() const
		{
			return --end();
		}
		const_reverse_iterator rend() const
		{
			return --begin();
		}

		

		void push_back(const T& val)
		{
			Node* newnode = new Node(val);
			newnode->_next = _head;
			_head->_pre->_next = newnode;
			newnode->_pre = _head->_pre;
			_head->_pre = newnode;
		}


		iterator erase(iterator pos) //在pos位置删除
		{
			Node* cur = pos._node;
			Node* prev = cur->_pre;
			Node* next = cur->_next;
			delete cur;
			prev->_next = next;
			next->_pre = prev;
		
			return next;
		}
		// 在pos位置前插入值为val的节点
		iterator insert(iterator pos, const T& val)
		{
			Node* cur = pos._node;
			Node* newNode = new Node(val);
			newNode->_next = cur;
			newNode->_pre = cur->_pre;
			cur->_pre->_next = newNode;
			cur->_pre = newNode;
			return pos;
		}
		/*void push_back(const T& val)
		{
			insert(_head, val);
		}*/
		void push_front(const T& val)
		{
			insert(_head->_next, val);
		}


		void swap(list<T>& l)
		{
			std::swap(l._head, _head);
		}
	
		void clear()
		{
			//清理数据,不清头节点
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);//it就是下一个位置
			}
		}

		~list()
		{
			clear();
			delete _head;		// 只有节点是new出来，需要delete，但这个只delete 了一个节点
		}

	private:
		void empty_init()
		{
			_head = new Node();
			_head->_next = _head->_pre = _head;
		}
		Node* _head;  
	};

2.2 list的反向迭代器

反向迭代器的++就是正向迭代器的--，反向迭代器的--就是正向迭代器的++，因此反向迭代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口进行包装即可.

template<class Iterator>
class ReverseListIterator
{
    // 注意：此处typename的作用是明确告诉编译器，Ref是Iterator类中的类型，而不是静态成员变量
    // 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
    // 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
public:
    typedef typename Iterator::Ref Ref;
    typedef typename Iterator::Ptr Ptr;
    typedef ReverseListIterator<Iterator> Self;
public:
//
    // 构造
    ReverseListIterator(Iterator it): _it(it){}
    //
    // 具有指针类似行为
    Ref operator*(){
    Iterator temp(_it);
    --temp;
    return *temp;
}
Ptr operator->(){ return &(operator*());}
//
// 迭代器支持移动
Self& operator++(){
--_it;
return *this;
}
Self operator++(int){
Self temp(*this);
--_it;
return temp;
}
Self& operator--(){
++_it;
return *this;
}
Self operator--(int)
{
Self temp(*this);
++_it;
return temp;
}
//
// 迭代器支持比较
bool operator!=(const Self& l)const{ return _it != l._it;}
bool operator==(const Self& l)const{ return _it != l._it;}
Iterator _it;
};

3. list与vector的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下: