【C++】STL--list
目录
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;};
}