关于list

1、什么是list

list是一个带头结点的双向循环链表模版容器，可以存放任意类型，需要显式定义

2、list的使用

有了前面学习string和vector的基础，学习和使用list会方便很多，因为大部分的内容依然是高度重合的。

与顺序表不同，链表是以结点形式进行链接和存储，其地址并不是连续的，因此进行插入和删除操作不需要进行大量的数据挪动，只需要改变指针的指向即可，方便很多。

使用push_back()和push_front()可以分别实现尾插和头插

    list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(5);lt.push_front(6);for (auto e : lt){cout << e << " ";}cout << endl;

也可以使用insert实现在某一位置的插入，erase实现在某一位置的删除

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

然而由于迭代器的失效问题，erase会返回被删除元素的下一个位置，因此，当进行连续删除时，我们可以使用迭代器来直接对此返回值进行接收来实现

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

同时，由于list底层结构的不同，不能像string和vector一样去实现迭代器，因为string和vector在底层结构中是连续的，可以直接用指针去访问得到相应位置的元素内容，对指针进行++或者--操作又可以直接到达下一位置或者前一位置，list中存放的是一个一个不连续的结点，对迭代器的实现时需要进行相应的重载，使用也会受限，比如在上述代码中就无法使用lt.begin()+3等，更多内容在进行list的模拟实现中可以得到更多的体会

reverse()用于逆置，库里有实现公用的reverse，不过list里面也有提供自己的逆置，如果使用公用的则需要使用两个参数指定逆置的范围，如果使用的是自己的逆置则不需要传参

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

对于排序，之前的vector可以直接调用库中的sort()函数实现排序，实际sort()排序使用的是快排进行排序，而对于数组这种结构来说快排会很方便，而对于链表来说则比较困难，代价较高，因此库中的排序函数并不能对list进行排序，list内部自己有实现一个排序，可以进行使用并完成排序。不过对于list来说，排序始终代价较大，如果需要频繁使用排序应该使用其他的结构来存放数据，所以库里的sort()函数实质上也是对程序员的一种约束。

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

find()函数是库里实现的公用函数，list也可以使用，同时会返回寻找元素的位置

	auto it=find(lt.begin(), lt.end(), 3);cout << *it;

splice()可以用于将某一部分的内容转移至其他list中，也可以转移给自身的其他地方

	list<int> lt2 = { 10,20,30 };//全部转移//lt2.splice(lt2.begin(), lt);//部分转移//lt2.splice(lt2.begin(), lt, ++lt.begin());//转移某一位置的内容lt2.splice(lt2.begin(), lt,++lt.begin(),--lt.end());//转移某一段位置的内容//lt2.splice(++lt2.begin(), lt2, lt2.begin(), lt2.end());for (auto e : lt){cout << e << " ";}cout << endl;for (auto e : lt2){cout << e << " ";}cout << endl;lt2.splice(lt2.begin(), lt2, ++lt2.begin(), lt2.end());for (auto e : lt2){cout << e << " ";}cout << endl;

以上就是list的一些较常用的使用，那么在对list及其使用都有了解后就可以进行模拟实现

3、list的模拟实现

不得不说，我觉得list的实现比前面的string和vector的实现难很多，主要是迭代器的原因会上很大难度，很难以理解，所以直到勉强实现出来以后也还是处于一个似懂非懂的状态里，希望后面能继续加强自己的技术，实现轻松手撕

#include<iostream>
#include<list>
#include<algorithm>
using namespace std;namespace bit
{template<class T>struct ListNode{ListNode(const T& val = T()):_prev(nullptr),_next(nullptr),_val(val){}ListNode* _prev;ListNode* _next;T _val;};template<class 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):_node(node){}Ref operator*(){return _node->_val;}Ptr 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 Self& it){return _node != it._node;}bool operator==(const Self& it){return _node == it._node;}};template<class 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;iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const {return _head->_next;}const_iterator end() const{return _head;}List(){empty_init();}//list(const list<T>& lt)//{//	empty_init();//	for (auto& e : lt)//	{//		push_back(e);//		_size++;//	}//}size_t size(){return _size;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_head->_val = 0;_size = 0;}void push_back(const T& x){insert(end(), x);//Node* newnode = new Node;//_head->_prev->_next = newnode;//newnode->_prev = _head->_prev;//newnode->_next = _head;//_head->_prev = newnode;//newnode->_val = x;//_size++;}void push_front(const T& x){insert(++end(), x);//Node* newnode = new Node;//_head->_next->_prev = newnode;//newnode->_next = _head->_next;//_head->_next = newnode;//newnode->_prev = _head;//newnode->_val = x;//_size++;}void pop_back(){erase(--end());}void pop_front(){erase(++end());}void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}iterator insert(iterator pos,const T& x){Node* newnode = new Node;Node* cur = pos._node;newnode->_prev = cur->_prev;cur->_prev->_next = newnode;cur->_prev = newnode;newnode->_next = cur;newnode->_val = x;_size++;return newnode;}iterator erase(iterator pos){Node* cur = pos._node;cur->_next->_prev = cur->_prev;cur->_prev->_next = cur->_next;pos._node = cur->_next;delete cur;_size--;return pos;}void swap(List<T> tmp){std::swap(_head, tmp._head);std::swap(_size, tmp._size);}List<T>& operator=(List<T> tmp){swap(tmp);return *this;}List(const List<T>& lt){empty_init();//const_iterator it = lt.begin();//while (it != lt.end())//{//	push_back(*(it));//	it++;//}//_size = lt._size;for (auto& e : lt){push_back(e);}}~List(){clear();delete _head;_head = nullptr;}private:Node* _head;size_t _size;};
}