list的使用
list的底层是我们所说的双向带头循环链表，因此它的空间分配和vector不一样，它在内存中不是连续存放的。我们只讲常用的。
构造函数
我们现阶段可以不用管那个alloc，我们可以看到，可以用n个val来初始化list，也可以用一段迭代器区间来初始化，也可以用一个list来拷贝构造。
void test() { list<int> ls(10, 1); list<int> ls1(ls); list<int> ls2(ls1.begin(),ls1.end()); }
迭代器
我们可以看到list也是支持迭代器的，所以我们可以用迭代器进行访问。
void test() { list<int> ls(10, 1); list<int>::iterator it = ls.begin(); while (it != ls.end()) { cout << *it << " "; it++; } cout << endl; }
插入删除数据
1. push_back
尾插一个数据。
2. pop_back
尾删一个数据。
3. push_front
头插一个数据。
4. pop_front
头删一个数据。
5. insert
在某个迭代器的位置的前面插入一个数据，这个有个返回值，返回的是插入后的那个数据的迭代器。在某个迭代器的位置前面插入n个val，在某个迭代器的位置的前面插入一段迭代器区间。insert不会导致迭代器失效。
6. erase
删除某个迭代器位置的值，删除一段迭代器区间，erase会导致迭代器失效，因此删除后需要返回删除后，那个位置的数据的迭代器。
void test() { list<int> ls; //尾插 ls.push_back(1); ls.push_back(2); ls.push_back(3); //头插 ls.push_front(2); ls.push_front(3); //头删 ls.pop_front(); //尾删 ls.pop_back(); ls.insert(ls.begin(), 5); ls.erase(--ls.end()); list<int>::iterator it = ls.begin(); while (it != ls.end()) { cout << *it << " "; it++; } cout << endl; }
reverse和sort
1. reverse
逆置链表。
2. sort
因为库里面的sort只能用来排序一段连续的空间的数据，所以链表就不能用，所以针对链表有一个专门的sort，但是比较慢，不推荐使用。
void test() { list<int> ls; //尾插 ls.push_back(1); ls.push_back(2); ls.push_back(3); ls.reverse(); ls.sort(); list<int>::iterator it = ls.begin(); while (it != ls.end()) { cout << *it << " "; it++; } cout << endl; }
list模拟实现
我们说list是双向带头循环链表，所以它的结构接很清晰了。
结构
template <class T> struct ListNode { T _date; ListNode<T>* _next; ListNode<T>* _prev; ListNode(const T& x = T()) : _date(x) , _next(nullptr) , _prev(nullptr) {} };
因为我们在申请节点的时候会用一个初始值来初始化，所以我们可以给ListNode来一个构造函数。
list构造函数
为了修改方便我们会把结构typedef一下。
typedef ListNode Node;
我们开始需要申请一个节点，让他的前后指针都指向它自己。这里我们为了记录数量，我们添加了一个_size来记录容器中的数量。
list() { _head = new Node; _head->_next = _head; _head->_prev = _head; _size = 0; }
迭代器
我们说迭代器是一种类似指针的东西，对于vector来说，它的底层是数组，可以++和–，但是对于我们链表来说，他是不支持++和–的，所以，我们的迭代器可以说是一个全新的类，我们要对这个类加入运算符重载，然后让他实现我们想要的操作。
但是我们迭代器分为迭代器和const迭代器，所以我们可以加两个模板参数，这样可以减少代码的冗余。
然后我们在list中定义的时候可以直接传T&和const T&就可以了。
这样我们就可以减少代码的冗余。
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 = nullptr) :_node(node) {} bool operator!=(const self& s ) { return _node != s._node; } bool operator==(const self& s) { return _node == s._node; } //解引用 Ref operator*() { return _node->_date; } //为了以后对自定义类型使用 Ptr operator->() { return &(_node->_date); } //前置++ self operator++() { _node = _node->_next; return *this; } //前置-- self operator--() { _node = _node->_prev; return *this; } //后置++ self operator++(int) { self tmp(*this); _node = _node->_next; return tmp; } //后置-- self operator--(int) { self tmp(*this); _node = _node->_prev; return tmp; } };
有了这个以后我们就可以在list里面开始完成迭代器相关的接口了。
iterator begin() { return _head->_next; } iterator end() { return _head; } const_iterator begin() const { return _head->_next; } const_iterator end() const { return _head; }
插入和删除数据
插入和删除我们又6个接口，但是我们实现一个insert和erase后上下来直接来复用这两个接口就可以了。
- insert
我们需要申请一个新节点，从迭代器中拿到需要插入的节点，然后记录一下前一个节点，然后改变链接关系，最后返回插入后的那个节点就可以了。
iterator insert(iterator pos, const T& x) { Node* cur = pos._node; Node* newnode = new Node(x); Node* prev = cur->_prev; prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; _size++; return newnode; }
- erase
我们拿到迭代器中的当前节点，然后拿到前一个节点和后一个节点，释放当前节点，改变链接关系，返回下一个节点就可以了。
iterator erase(iterator pos) { Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; delete cur; _size--; prev->_next = next; next->_prev = prev; return next; }
头插头删尾插尾删
头插就是在_head节点前插入，头删就是删除_head的下一个节点，尾删就是删除_head的前一个节点，尾插就是在_head的前面插入。
void pop_back() { erase(--end()); } void push_front(const T& x) { insert(begin(), x); } void pop_front() { erase(begin()); } void push_back(const T& x) { insert(end(), x); }
clear
clser可以用迭代器来清，遍历的同时删除。
void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } }
拷贝构造析构和赋值重载
拷贝构造先初始化一下，然后遍历需要拷贝的list，依次尾插。
list(const list& ls) { _head = new Node; _head->_next = _head; _head->_prev = _head; _size = 0; for (auto e : ls) { push_back(e); } }
析构可以先clear一下，然后把哨兵位的头结点释放了就可以了。
~list() { clear(); delete _head; }
赋值拷贝
我们可以直接让原数据拷贝给tmp，然后和this交换，就可以了，等这个函数结束，编译器会帮我们调用析构。
void swap(list& s) { std::swap(_head, s._head); std::swap(_size, s._size); } list& operator=(list ls) { swap(ls); return *this; }
今天的分享就到这里，感谢大家的关注和支持。
