目录
list的介绍
list的使用
list的构造
list iterator的使用
list capacity
list modifiers
list的迭代器失效
list模拟实现
list的介绍
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3.与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
list的使用
list的构造
1.list(size_t n,const T& lt = T())
说明：构造的list中包含n个值为val的元素
2.list()
说明：构造空的list
3.list(const list& x)
说明：拷贝构造函数
4.list(InputIterator first,InputIterator last)
说明：用[first,last)区间中的元素构造list
list iterator的使用
此时，我们暂且将迭代器理解成一个指针，该指针指向list中的某个节点。
begin+end：返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin+rend：返回第一个元素的reverse_iterator，即end位置，返回最后一个元素下一个位置的reverse_iterator，即begin位置
注意：
1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
list capacity
empty：检测list是否为空，是返回true，否则返回false
size：返回list中有效节点个数
list modifiers
push_front：在list首元素前插入值为val的元素
pop_front：删除list中的第一个元素
push_back：在list尾部插入值为val的元素
pop_back：删除list中的最后一个元素
insert：在pos位置插入值为val的元素
erase：删除pos位置的元素
swap：交换两个list中的元素
clear：清空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]));auto it = l.begin();while (it != l.end()){//错误示范 //erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值//l.erase(it);//++it;//正确it = l.erase(it);}}list模拟实现
namespace ghs{template<class T>struct ListNode{ListNode(const T& x = T()):_next(nullptr),_prev(nullptr),_data(x){}ListNode<T>* _next;ListNode<T>* _prev;T _data;};template<class T, class Ref, class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator Self;Node* _node;ListIterator(Node* node):_node(node){}//*it//不能传值返回，*it只能传引用返回，因为除了读还有写的功能//T& operator*()Ref operator*(){return _node->_data;}//++itSelf& operator++(){_node = _node->_next;return *this;}//it++Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}//--itSelf& operator--(){_node = _node->_prev;return *this;}//it--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;}//T* operator->()Ptr operator->(){return &_node->_data;}};//template<class T>//struct ListConstIterator//{//typedef ListNode<T> Node;//typedef ListConstIterator Self;//Node* _node;//ListConstIterator(Node* node)//:_node(node)//{}////*it////不能传值返回，*it只能传引用返回，因为除了读还有写的功能//const T& operator*()//{//return _node->_data;//}////++it//Self& operator++()//{//_node = _node->_next;//return *this;//}////it++//Self operator++(int)//{//Self tmp(*this);//_node = _node->_next;//return tmp;//}////--it//Self& operator--()//{//_node = _node->_prev;//return *this;//}////it--//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;//}//const T* operator->()//{//return &_node->_data;//}//};template<class T>class list{typedef ListNode<T> Node;public:/*typedef ListIterator<T> iterator;typedef ListConstIterator<T> const_iterator;*/typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;//iterator begin()//{////匿名对象 //return iterator(_head->_next);//}iterator begin(){return _head->_next;}iterator end(){return _head;}//如果返回值类型是const iterator，那表示迭代器本身不能被修改，而不是迭代器指向的内容不能被修改//我们需要的是迭代器指向的内容不能被修改，const iterator不是我们需要的迭代器const_iterator begin()const{return _head->_next;}const_iterator end()const{return _head;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}//lt2(lt1)list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}//需要析构，一般就需要自己写深拷贝//不需要析构，一般就不需要自己写深拷贝，默认浅拷贝就可以void swap(list<T> lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>& operator=(list<T> lt)//()里调用了拷贝构造{swap(lt);return *this;}//void push_back(const T& x)//{//Node* newnode = new Node(x);//Node* tail = _head->_prev;//tail->_next = newnode;//newnode->_prev = tail;//newnode->_next = _head;//_head->_prev = newnode;//}void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}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;prev->_next = newnode;newnode->_prev = prev;_size++;}iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;_size--;return iterator(next);}size_t size()const{return _size;}bool empty(){return _size == 0;}//不清除头结点，只是把数据清掉void clear(){iterator it = begin();while (it != end()){it = erase(it);}}~list(){clear();delete _head;_head = nullptr;}private:Node* _head;size_t _size;};}
