STL中list的模拟

在 C++ 的 STL（标准模板库）中，list 是一个十分重要的容器，它就像一个灵活的弹簧，可以在任意位置快速地插入和删除元素。今天，就让我们一起走进 list 的世界，去探索它的奥秘。

list 的节点 —— ListNode

    template<class T>struct ListNode{ListNode(const T& val = T()):_pPre(nullptr),_pNext(nullptr),_val(val){}ListNode<T>* _pPre;ListNode<T>* _pNext;T _val;};

list 的基础是节点，就像一串项链上的珠子。代码中的 ListNode 就承载着这样的角色。每个节点都有一个前驱指针 _pPre、一个后继指针 _pNext 和一个存储数据的 _val。它们就像是珠子的连接线，将一个个数据串联起来，构成了 list 的主体。当我们创建一个节点时，它就像一颗独立的珠子，等待被加入到项链中。

list 的 “导览员” —— ListIterator

 //List的迭代器类template<class T, class Ref, class Ptr>struct ListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;//成员函数ListIterator(PNode pNode = nullptr):_pNode(pNode){}ListIterator(const Self& l)//怎么实现拷贝{_pNode = l._pNode;}T& operator*(){return _pNode->_val;}//T* operator->()//存疑//{//    return  &_pNode->_val;//}Self& operator++(){_pNode= _pNode->_pNext;return *this;}Self operator++(int){Self tmp(*this);_pNode = _pNode->_pNext;return tmp;}Self& operator--(){_pNode = _pNode->_pPre;return *this;}Self& operator--(int){Self tmp(*this);_pNode = _pNode->_pPre;return tmp;}bool operator!=(const Self& l){return _pNode != l._pNode;}bool operator==(const Self& l){return _pNode == l._pNode;}//成员对象PNode _pNode;};

有了节点，我们还需要一个 “导览员” 来带我们游览整个 list，这就是迭代器 ListIterator。它就像是我们手中的一根细棒，可以指向 list 中的任意一个节点，让我们能够方便地访问和操作元素。
构造函数 ：它接受一个节点指针作为参数，默认指向空。这就像我们在开始游览之前，先确定了出发点。
拷贝构造函数 ：当遇到一个已经存在的迭代器时，我们可以通过拷贝它的方式，快速地获得一个指向相同节点的迭代器。这就好比看到朋友手中有一个很好的导览路线，我们直接复制过来一样。
解引用操作符（operator*） ：通过这个操作符，我们可以轻松地获取当前节点所存储的值。这相当于在游览过程中，我们停下脚步，仔细观察手中的珠子。
自增自减操作符（operator++、operator–） ：这两个操作符就像是我们的双脚，可以带着我们在 list 的项链上向前或向后移动，指向下一个或前一个节点。
比较操作符（operator!=、operator==） ：它们可以帮助我们判断两个迭代器是否指向同一个节点。这就好比在不同的游览路线中，我们可以比较是否来到了同一个景点。

list 的核心 —— list 类

现在，我们迎来了主角 —— list 类。它就像是一个精心编织的项链，将众多节点串联起来，并提供了一系列方法让我们能够灵活地操作它。

//list类template<class T>class list{typedef ListNode<T> Node;typedef Node* PNode;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T&> const_iterator;public:///// List的构造list(){CreateHead(); }list(int n, const T& value = T()){CreateHead();PNode cur = _pHead;while (n--){PNode next = new Node(value);cur->_pNext = next;next->_pPre = cur;cur = next;_size++;}cur->_pNext = _pHead;_pHead->_pPre = cur;}template <class Iterator>list(Iterator first, Iterator last){CreateHead();PNode cur = _pHead;while (first != last){PNode next = new Node(*first);cur->_pNext = next;next->_pPre = cur;cur = next;first++;_size++;}cur->_pNext = _pHead;_pHead->_pPre = cur;}list(const list<T> &l){CreateHead();for(auto &a:l){push_back(a);}}list<T>& operator=(const list<T> l){CreateHead();swap(l);return *this;}~list(){clear();delete _pHead;_pHead = nullptr;}///// List Iteratoriterator begin(){return _pHead->_pNext;}iterator end(){return _pHead;}const_iterator begin()const{return _pHead->_pNext;}const_iterator end()const{return _pHead;}///// List Capacitysize_t size()const{return _size;}bool empty()const{return _size == 0;}//// List AccessT& front(){return _pHead->_pNext->_val;}const T& front()const{return _pHead->_pNext->_val;}T& back(){return _pHead->_pPre->_val;}const T& back()const{return _pHead->_pPre->_val;}// List Modifyvoid 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){PNode n = new Node(val);PNode pre = pos._pNode->_pPre;pre->_pNext = n;n->_pPre = pre;n->_pNext = pos._pNode;pos._pNode->_pPre = n;_size++;return n;}// 删除pos位置的节点，返回该节点的下一个位置iterator erase(iterator pos){PNode pre = pos._pNode->_pPre;PNode next = pos._pNode->_pNext;delete pos._pNode;pre->_pNext = next;next->_pPre = pre;_size--;return next;}void clear(){PNode cur = _pHead->_pNext;while (cur != _pHead){PNode next = cur->_pNext;delete cur;cur = next;}_pHead->_pNext = _pHead;_pHead->_pPre = _pHead;_size = 0;}void swap(list<T>& l){std::swap(_pHead, l._pHead);std::swap(_size, l._size);}//void print()//{//    for (auto c : *this)//    {//        cout << c << " ";//    }//    cout << endl;//}private:void CreateHead(){_pHead = new Node;_pHead->_pNext = _pHead;_pHead->_pPre = _pHead;_size = 0;}PNode _pHead;size_t _size;};
};

构造函数

默认构造函数会创建一个头节点 _pHead，它是一个特殊的节点，不存储实际数据，但起到了标记项链开头和结尾的作用。这就像我们在开始制作项链时，先打了个结。
可以指定元素个数和初始值来构造 list。这就像我们已经有了设计图，知道要制作多少颗珠子以及它们的颜色，于是按照这个设计直接把珠子串起来。
还可以从一个范围（通过迭代器指定开始和结束位置）来构造 list。这就像是我们从一个现成的珠子堆中，挑选
出一部分珠子，按照顺序串成项链。
拷贝构造函数能够复制一个已有的 list。这就好比看到了一件精美的项链作品，我们想模仿着制作一个一模一样的。
赋值操作符（operator=） ：它通过 “拷贝 - 交换” 技术，先创建一个临时的 list，再与当前 list 进行交换。这就像我们先按照别人的项链样式做好一个新项链，然后把自己的旧项链换掉。
析构函数 ：在 list 不再被需要时，析构函数会负责清理内存，删除所有节点，并释放头节点。这是在我们结束了项链的使用后，把它拆解，回收材料的过程。

迭代器相关操作

begin() 和 end() 方法分别返回指向 list 第一个节点和头节点（代表结束位置）的迭代器。这就像我们在游览项链时，确定了起点和终点。
const_iterator 版本的 begin() 和 end() 方法可以让我们在不修改 list 的情况下进行遍历，就像是我们戴着白手套，小心翼翼地观察项链上的珠子，而不去改变它们。

容量相关操作

size() 方法能够返回 list 当前的元素个数。这让我们可以清楚地知道项链上有多少颗珠子。
empty() 方法用于判断 list 是否为空，返回一个布尔值。这就像在检查项链是否已经断开，里面是否还有珠子。
元素访问操作
front() 和 back() 方法分别返回 list 第一个和最后一个元素的引用。这相当于我们直接拿起项链的开端或末端的珠子，查看它的模样。
修改操作
push_back() 和 pop_back() 方法用于在 list 的尾部添加或删除元素。这就像我们在项链的末端添加或取下一颗珠子。
push_front() 和 pop_front() 方法则是在 list 的头部进行添加或删除操作。这类似于我们在项链的开头位置进行珠子的增减。
insert() 方法可以在指定位置前插入一个元素。这就好比我们在项链的某个特定位置插入一颗新的珠子，需要调整相邻珠子的连接关系。
erase() 方法用于删除指定位置的元素，并返回下一个元素的位置。这就像我们在项链上取下一颗珠子后，要把剩下的珠子重新连接起来，并且告诉我们接下来的位置在哪里。
clear() 方法会清除 list 中的所有元素，将项链完全拆解，只剩下头节点。这通常在我们想要重新利用这条项链，重新设计样式时使用。
swap() 方法可以快速地交换两个 list 的内容。这就像我们把两条项链的珠子序列互换，但项链本身的结构（如头节点）保持不变。

结尾

通过以上对 list 的各个组成部分以及其成员函数的详细介绍（虽然这里的代码实现可能与 STL 中的 list 有些许不同，只是起到模拟作用），我们对 list 的工作原理和使用方法有了更深入的理解。它就像是我们手中的一条神奇项链，可以根据我们的需求，在任何位置灵活地添加或删除珠子，为我们处理数据提供了极大的便利。希望这次的 list 之旅能够让你对 C++ STL 有更进一步的认识，让我们在编程的世界里继续探索，发现更多宝藏！