stl::list的实现原理图

#pragma once
#include <cassert>
#include <iostream>

template<typename T>
class CList
{
private:
    struct SNode
    {
        SNode() : pPrev(nullptr), pNext(nullptr) { }
        SNode(T e, SNode* p = nullptr, SNode* s = nullptr) 
            : data(e), pPrev(p), pNext(s) { }
        SNode* insertAsPred(T const& e) {
            SNode* x = new SNode(e, this->pPrev, this);
            pPrev->pNext = x;
            pPrev = x;
            return x;
        }
        SNode* insertAsSucc(T const& e) {
            SNode* x = new SNode(e, this, this->pNext);
            pNext->pPrev = x;
            pNext = x;
            return x;
        }
        T data = T();
        SNode* pPrev = nullptr;
        SNode* pNext = nullptr;
    };
public:
    class iterator
    {
    public:
        iterator(SNode* pNode = nullptr) : m_pCurr(pNode) //m_pCurr((SNode*)pNode)
        {
            m_pCurr = pNode;
        }
        inline T& operator*()
        {
            return m_pCurr->data;
        }
        inline T* operator->() const
        {
            return &m_pCurr->data;
        }
        inline operator SNode* ()
        {
            return m_pCurr;
        }
        inline iterator& operator++()
        {
            m_pCurr = m_pCurr->pNext;
            return *this;
        }
        inline iterator operator++(int)
        {
            SNode* pTmp = m_pCurr;
            m_pCurr = m_pCurr->pNext;
            return pTmp;
        }
        inline iterator& operator--()
        {
            m_pCurr = m_pCurr->pPrev;
            return *this;
        }
        inline iterator operator--(int)
        {
            SNode* pTmp = m_pCurr;
            m_pCurr = m_pCurr->pPrev;
            return pTmp;
        }

    private:
        SNode* m_pCurr;
    };
public:
    inline CList() : m_nSize(0)
    {
        m_end.pPrev = m_end.pNext = &m_end;
    }
    inline iterator begin()
    {
        return m_end.pNext;
    }
    inline iterator end()
    {
        return&m_end;
    }
    inline iterator rbegin()
    {
        return m_end.pPrev;
    }
    inline iterator rend()
    {
        return&m_end;
    }
    inline int size() const
    {
        return m_nSize;
    }
    inline bool empty() const
    {
        return m_nSize <= 0;
    }
    inline void push_front(T&& data)
    {
        ++m_nSize;
        m_end.insertAsSucc(data);  // 在头部插入始终是头节点的后继
    }
    inline void push_back(T&& data)
    {
        ++m_nSize;
        m_end.insertAsPred(data);  // 在尾部插入始终是头节点的前驱
    }
    inline void push_front(const T& data)
    {
        ++m_nSize;
        m_end.insertAsSucc(data);  // 在头部插入始终是头节点的后继
    }
    inline void push_back(const T& data)
    {
        ++m_nSize;
        m_end.insertAsPred(data);  // 在尾部插入始终是头节点的前驱
    }
    void resize(int n, const T& val = T());
    inline iterator erase(iterator it);
    inline void clear();
    void travel() const;
    void travel_reverse() const;
private:
    SNode* insertAfter(T const& e, SNode* p) {  // 在之后插入
        m_nSize++;
        return p->insertAsSucc(e);
    }
    SNode* insertBefore(T const& e, SNode* p) {  // 在之前插入
        m_nSize++;
        return p->insertAsPred(e);
    }
    int m_nSize;
    SNode m_end;  // 环形链表的哨兵节点
};

template<typename T>
inline void CList<T>::resize(int n, const T& val)
{
    assert(n >= 0);
    if (n == m_nSize)
        return;
    if (n > m_nSize)
    {
        SNode* p = m_end.pPrev;
        while (m_nSize > n)
        {
            p->pPrev->pNext = &m_end;
            m_end.pPrev = p->pPrev;
            delete p;
            p = m_end.pPrev;
            --m_nSize;
        }
    }
    if (n < m_nSize)
    {
        while (m_nSize < n)
            push_back(val);
    }
}

template<typename T>
typename inline CList<T>::iterator CList<T>::erase(CList<T>::iterator it)
{
    assert(it != &m_end);
    SNode* p = it;
    p->pNext->pPrev = p->pPrev;
    p->pPrev->pNext = p->pNext;
    auto q = p->pNext;
    delete p;
    --m_nSize;
    return q;
}


template<typename T>
inline void CList<T>::clear()
{
    auto p = m_end.pNext, p1 = p;
    while (p != &m_end)
    {
        p1 = p;
        p = p->pNext;
        delete p1;
    }
    m_nSize = 0;
    m_end.pPrev = &m_end;
    m_end.pNext = &m_end;
}

template<typename T>
inline void CList<T>::travel() const
{   // 出于运行效率考虑，在CList内部不使用迭代器
    if(!empty()) puts("正向打印");
    for (auto p = m_end.pNext; p != &m_end; p = p->pNext) 
        std::cout << p->data << " ";
    std::cout << "总共有" << size() << " 条记录" << std::endl;
}

template<typename T>
inline void CList<T>::travel_reverse() const
{   // 出于运行效率考虑，在CList内部不使用迭代器
    if (!empty()) puts("逆向打印");
    for (auto p = m_end.pPrev; p != &m_end; p = p->pPrev) 
        std::cout << p->data << " ";
    std::cout << "总共有" << size() << " 条记录" << std::endl;
}

#include "CList.h"
#include <string>

void Delete(CList<int>& t1, int x)
{
    for (auto it = t1.begin(); it != t1.end(); ) {
        if (*it == x)
            it = t1.erase(it);
        else
            ++it;
    }
}

int main()
{
    CList<int> t1;
    CList<double> t2;
    CList<std::string> t3;

    t1.push_back(1);
    t1.push_back(2);
    t1.push_back(3);
    t1.push_back(4);
    t1.push_back(5);
    t1.travel();
    t1.travel_reverse();

    t1.push_back(32);
    t1.push_front(-1);
    t1.push_front(888);
    t1.push_front(666);
    t1.travel();
    t1.resize(5);
    Delete(t1, 666);
    t1.travel();
    t1.resize(15, -1);
    t1.travel();

    t1.travel_reverse();

    t1.clear();
    t1.travel();
    return 0;
}

测试结果