list简介

1，list是可以在常数时间复杂度任何位置随意插入的序列式容器，可以双向迭代
2，底层是双向链表结构，每个节点都是独立的，通过前后指针链接
3，相比vector，list随机插入更快，但是要访问随机元素更复杂，需要线性时间开销；还需要额外空间开销（保存前后指针）；

list接口

和前文的string，vector接口一致，这里就不赘述了，无非多了头插头删
vector讲解

迭代器失效

与前文的vector一样，如果指针指向当前位置被释放，再访问就会崩溃

#include <iostream>
#include <list>
using namespace std;
int main()
{int a[] = {4, 5, 6};list<int> l1(a, a + sizeof(a) / sizeof(int));auto it = l1.begin();while(it!=l1.end()){cout << *it;//l1.erase(it);//it++;//错误it = l1.erase(it);//正确}return 0;
}

🚩模拟实现

#include <iostream>
namespace jib {template<class T>struct ListNode{ListNode(const T& val = T()):_prev(nullptr),_next(nullptr),_val(val){}ListNode<T>* _prev;ListNode<T>* _next;T _val;};template<class T, class Ref, class Ptr>struct ListIterator{typedef ListNode<T> Pnode;typedef ListIterator<T, Ref, Ptr> self;Pnode* _node;ListIterator(Pnode* pnode = nullptr):_node(pnode){}ListIterator(const self& l):_node(l._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!=(self& l) const{return _node != l._node;}bool operator==(self& l) const{return !(*this!=l);}};template<class T>class list {typedef ListNode<T> Node;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;list(){CreateNode();}list(int n, const T& value = T()){CreateNode();for(int i=0;i<n;i++){push_back(value);}}template <class Iterator>list(Iterator first, Iterator last){CreateNode();while (first != last){push_back(*first);++first;}}list(const list<T>& l){CreateNode();list<T> tmp(l.begin(),l.end());this->swap(tmp);}list<T>& operator=(const list<T> l){this->swap(l);return *this;}~list(){clear();delete _phead;_phead = nullptr;}///////////////////////////////////////////////////////////////// List Iteratoriterator begin(){return iterator(_phead->_next);}iterator end(){return iterator(_phead);}const_iterator begin() const{return const_iterator(_phead->_next);}const_iterator end() const{return const_iterator(_phead);}///////////////////////////////////////////////////////////////// List Capacitysize_t size()const{size_t sz = 0;Node* p = _phead->_next;while (p != _phead){sz++;p = p->_next;}return sz;}bool empty()const{return size() == 0;}////////////////////////////////////////////////////////////// List AccessT& front(){access(!empty());return _phead->_next->_val;}const T& front()const{access(!empty());return _phead->_next->_val;}T& back(){access(!empty());return _phead->_prev->_val;}const T& back()const{access(!empty());return _phead->_prev->val;}////////////////////////////////////////////////////////////// List Modifypublic:void push_back(const T& val) { insert(end(), val); }void pop_back() { erase(--end()); }void push_front(const T& val){ insert(begin(), val); }void pop_front() { erase(begin()); }// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T& val){Node* newnode = new Node(val);Node* cur=pos._node;newnode->_prev = cur->_prev;newnode->_next = cur;cur->_prev->_next = newnode;cur->_prev = newnode;return iterator(newnode);}iterator erase(iterator pos){Node* cur = pos._node;Node* curnext = cur->_next;curnext->_prev = cur->_prev;cur->_prev->_next = curnext;delete cur;cur = nullptr;return iterator(curnext);}void clear(){iterator p = begin();while (!empty()){p = erase(p);}_phead->_next = _phead;_phead->_prev = _phead;}void swap(list<T>& l){std::swap(_phead, l._phead);}private:void CreateNode(){_phead = new Node;_phead->_next = _phead;_phead->_prev = _phead;}Node* _phead;};
}

先开辟节点类，再开辟迭代器类，再创建list类
注意 it用法：

struct Person {std::string name;int age;void print() { std::cout << name << ", " << age; }
};jib::list<Person> people;
people.push_back(Person{"Alice", 30});auto it = people.begin();
std::cout << it->name;  // 输出 "Alice"
it->age = 31;           // 修改年龄
it->print();            // 调用成员函数

调用 it.operator->()，返回 &_node->_val
编译器自动对结果应用 ->，变成== (&_node->_val)->name==

编译器自动省略了一个->