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==

編譯器自動省略了一個->