C++：list模拟实现

hello，各位小伙伴，本篇文章跟大家一起学习《c++：list模拟实现》，感谢大家对我上一篇的支持，如有什么问题，还请多多指教 ！
如果本篇文章对你有帮助，还请各位点点赞！！！

话不多说，开始进入正题

🍁list的逻辑结构以及节点代码

是一个双指针带头链表，所以我选择用一个结构体listnode来维护节点，如下：

// list的节点类
template<class t>
struct listnode
{
    listnode(const t& val = t())
        :_val(val)
        ,_ppre(nullptr)
        ,_pnext(nullptr)
    {}
    listnode<t>* _ppre;// 指向前一个结点
    listnode<t>* _pnext;// 指向后一个节点
    t _val;// 该结点的值
};

我对listnode<t>改一个名字：node：

typedef listnode<t> node;
typedef node* pnode;

🍁list类

🍃私有成员变量_phead和私有成员函数createhead()

private:
    void createhead()// 创建头节点并且初始化
    {
        _phead = new node();
        _phead->_pnext = _phead;
        _phead->_ppre = _phead;
    }

    pnode _phead;

🍃尾插函数和插入函数

尾插只是插入的其中一种方式，所以实现了插入函数，就能够实现尾插函数。
插入思路图解：在pos位置前插入值为val的节点

创建新节点值为value后；
使prev节点的_pnext指针指向newnode，newnode的节点的_ppre指向prev；
使cur节点的_ppre指针指向newnode，newnode的节点的_pnext指向cur；
最后返回iterator(newnode);

itearator为迭代器，后面会实现

• 插入

// 在pos位置前插入值为val的节点
iterator insert(iterator pos, const t& val)
{
    node* cur = pos._pnode;
    node* newnode = new node(val);
    node* prev = cur->_ppre;

    // prev  newnode  cur
    prev->_pnext = newnode;
    newnode->_ppre = prev;
    newnode->_pnext = cur;
    cur->_ppre = newnode;
    
    return iterator(newnode);
}

• 尾插

void push_back(const t& val)
{
	insert(end(), val); 
}

🍃构造函数

• 无参构造

list(const pnode& phead = nullptr)
{
    createhead();
    /*_phead = new node();
    _phead->_pnext = _phead;
    _phead->_ppre = _phead;*/
}

• 带参构造（数值）

list(int n, const t& value = t())
{
    createhead();
    for (int i = 0; i < n; ++i)
        push_back(value);
}

• 带参构造（迭代器）

template <class iterator>
list(iterator first, iterator last)
{
    createhead();
    while (first != last)
    {
        push_back(*first);
        ++first;
    }
}

• 拷贝构造

list(const list<t>& l)
{
    createhead();
    
    // 复用带参构造（迭代器）
    list<t> temp(l.cbegin(), l.cend());

	// 与*this的头节点phead交换指向
    swap(temp);
}

🍃析构函数

clear()为其中的成员函数，功能：清理list中的数据

~list()
{
    clear();
    delete _phead;
    _phead = nullptr;

    /*node* cur = _phead->_pnext;
    node* tmp = cur->_pnext;
    while (cur != _phead)
    {
        delete cur;
        cur = tmp;
        tmp = tmp->_pnext;
    }
    tmp = cur = nullptr;
    _phead->_pnext = _phead;
    _phead->_ppre = _phead;*/
}

🍃迭代器模拟

逻辑上并不难，也许难理解于模板

//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*()
    {
        assert(_pnode != _pnode->_pnext);
        return _pnode->_val;
    }

    t* operator->()
    {
        return &(*this);
    }

    self& operator++()
    {
        _pnode = _pnode->_pnext;
        return *this;
    }

    self operator++(int)
    {
        pnode* tmp = _pnode;
        _pnode = _pnode->_pnext;
        return tmp;
    }

    self& operator--()
    {
        _pnode = _pnode->_ppre;
        return *this;
    }

    self& operator--(int)
    {
        pnode* tmp = _pnode;
        _pnode = _pnode->_ppre;
        return tmp;
    }

    bool operator!=(const self& l)
    {
        return _pnode != l._pnode;
    }

    bool operator==(const self& l)
    {
        return !(*this != l);
    }
    pnode _pnode;
};

这段代码定义了一个模板结构 listiterator，用于表示list类的迭代器。让我们来解释模板声明部分：

template<class t, class ref, class ptr>;

这一行是模板声明，定义了一个模板类 listiterator，它有三个模板参数：t、ref 和 ptr。让我们逐个解释这些参数的作用：

1.t: 这是一个模板参数，表示迭代器指向的元素类型。在使用 listiterator 时，你需要提供实际的类型作为 t 的值。
2.ref: 这也是一个模板参数，表示迭代器的引用类型。通常情况下，当你通过迭代器解引用（使用 * 运算符）时，你希望得到的是元素的引用类型。所以 ref 通常被设定为 t&，表示引用类型为 t 的元素。
3.ptr: 这是迭代器的指针类型。与 ref 类似，当你通过迭代器解引用（使用 -> 运算符）时，你希望得到的是元素的指针类型。因此，通常情况下 ptr 被设定为 t*，表示指针类型为 t 的元素。

通过将这些参数设定为模板参数，listiterator 类可以适用于不同类型的元素，同时也可以提供不同的引用和指针类型。这样做使得 listiterator 类更加灵活，能够适用于不同的使用场景。

• 封装的意义
  将迭代器的实现从 list 类中分离出来，有几个重要的意义和优势：

1. 模块化设计：通过将迭代器封装为单独的类，可以实现更模块化的设计。这意味着 list 类的实现与迭代器的实现可以分开，每个类都专注于自己的职责。这样的设计使得代码更易于理解、维护和测试。
2. 可重用性：通过将迭代器设计为独立的类，可以在不同的容器类中重复使用相同的迭代器实现。例如，如果你有另一个类似于 list 的容器类，也需要迭代器来遍历其中的元素，你可以直接重用相同的迭代器实现，而无需重新编写。
3. 灵活性：将迭代器设计为独立的类使得它们的实现更加灵活。你可以在迭代器类中添加额外的功能或改变迭代器的行为，而不会影响到容器类的实现。这样的设计使得容器和迭代器的职责分离，每个类可以独立地演化和改进。
4. 通用性：独立的迭代器类可以设计成通用的，适用于多种容器类型。这意味着你可以为不同的容器类实现相同的迭代器接口，使得用户在使用不同的容器时无需学习不同的迭代器接口，提高了代码的一致性和可用性。

总的来说，将迭代器封装为独立的类使得代码更加模块化、可重用、灵活和通用，提高了代码的可维护性、可扩展性和可读性。

🍃list类中迭代器的使用

public:
    typedef listiterator<t, t&, t*> iterator;
    typedef listiterator<t, const t&, const t&> const_iterator;

• begin()和end()

// list iterator
iterator begin()
{
    return _phead->_pnext;
}

iterator end()
{
    return _phead;
}

const_iterator begin() const
{
    return _phead->_pnext;
}

const_iterator end() const
{
    return _phead;
}

• erase
  删除pos位置的节点，返回该节点的下一个位置

iterator erase(iterator pos)
{
    assert(pos._pnode != _phead);
    node* prev = pos._pnode->_ppre;
    node* next = pos._pnode->_pnext;

    delete pos._pnode;
    prev->_pnext = next;
    next->_ppre = prev;

    return iterator(next);
}

🍃list modify

void push_back(const t& val) { insert(end(), val); }
void pop_back() { erase(--end()); }
void push_front(const t& val) 
{ 
    assert(!empty());
    insert(begin(), val); 
}
void pop_front() { erase(begin()); }

🍁全部代码

#pragma once
#include<assert.h>
#include<iostream>
using namespace std;

namespace my_list
{
    // list的节点类
    template<class t>
    struct listnode
    {
        listnode(const t& val = t())
            :_val(val)
            ,_ppre(nullptr)
            ,_pnext(nullptr)
        {}
        listnode<t>* _ppre;
        listnode<t>* _pnext;
        t _val;
    };


    //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*()
        {
            assert(_pnode != _pnode->_pnext);
            return _pnode->_val;
        }

        t* operator->()
        {
            return &(*this);
        }

        self& operator++()
        {
            _pnode = _pnode->_pnext;
            return *this;
        }

        self operator++(int)
        {
            pnode* tmp = _pnode;
            _pnode = _pnode->_pnext;
            return tmp;
        }

        self& operator--()
        {
            _pnode = _pnode->_ppre;
            return *this;
        }

        self& operator--(int)
        {
            pnode* tmp = _pnode;
            _pnode = _pnode->_ppre;
            return tmp;
        }

        bool operator!=(const self& l)
        {
            return _pnode != l._pnode;
        }

        bool operator==(const self& l)
        {
            return !(*this != l);
        }
        pnode _pnode;
    };


    //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(const pnode& phead = nullptr)
        {
            createhead();
            /*_phead = new node();
            _phead->_pnext = _phead;
            _phead->_ppre = _phead;*/
        }

        list(int n, const t& value = t())
        {
            createhead();
            for (int i = 0; i < n; ++i)
                push_back(value);

            /*int cnt = 0;
            while (cnt < n)
            {
                pnode _first = new node(value);
                pnode tmp = _phead->_ppre;
                tmp->_pnext = _first;
                _first->_ppre = tmp;
                _first->_pnext = _phead;
                _phead->_ppre = _first;
                ++cnt;
            }*/
        }

        template <class iterator>
        list(iterator first, iterator last)
        {
            createhead();
            while (first != last)
            {
                push_back(*first);
                ++first;
            }

            /*while (first != last)
            {
                pnode _first = new node(*first);
                pnode tmp = _phead->_ppre;
                tmp->_pnext = _first;
                _first->_ppre = tmp;
                _first->_pnext = _phead;
                _phead->_ppre = _first;
                ++first;
            }*/
        }

        list(const list<t>& l)
        {
            createhead();
            list<t> temp(l.cbegin(), l.cend());
            swap(temp);

            /*iterator first = l._phead->_pnext;
            iterator last = l._phead;
            while (first != last)
            {
                pnode _first = new node(*first);
                pnode tmp = _phead->_ppre;
                tmp->_pnext = _first;
                _first->_ppre = tmp;
                _first->_pnext = _phead;
                _phead->_ppre = _first;
                ++first;
            }*/
        }

        list<t>& operator=(const list<t> l)
        {
            createhead();

            swap(l);
            return *this;
            /*iterator first = l._phead->_pnext;
            iterator last = l._phead;
            while (first != last)
            {
                pnode _first = new node(*first);
                pnode tmp = _phead->_ppre;
                tmp->_pnext = _first;
                _first->_ppre = tmp;
                _first->_pnext = _phead;
                _phead->_ppre = _first;
                ++first;
            }
            return *this;*/
        }

        ~list()
        {
            clear();
            delete _phead;
            _phead = nullptr;

            /*node* cur = _phead->_pnext;
            node* tmp = cur->_pnext;
            while (cur != _phead)
            {
                delete cur;
                cur = tmp;
                tmp = tmp->_pnext;
            }
            tmp = cur = nullptr;
            _phead->_pnext = _phead;
            _phead->_ppre = _phead;*/
        }


        ///
        // list iterator
        iterator begin()
        {
            return _phead->_pnext;
        }

        iterator end()
        {
            return _phead;
        }

        const_iterator begin() const
        {
            return _phead->_pnext;
        }

        const_iterator end() const
        {
            return _phead;
        }


        ///
        // list capacity
        size_t size()const
        {
            node* cur = _phead->_pnext;
            size_t cnt = 0;
            while (cur != _phead)
            {
                ++cnt;
                cur = cur->_pnext;
            }
            return cnt;
        }

        bool empty()const
        {
            return size() == 0;
        }


        
        // list access
        t& 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 modify
        void push_back(const t& val) { insert(end(), val); }
        void pop_back() { erase(--end()); }
        void push_front(const t& val) 
        { 
            assert(!empty());
            insert(begin(), val); 
        }
        void pop_front() { erase(begin()); }
        // 在pos位置前插入值为val的节点
        iterator insert(iterator pos, const t& val)
        {
            node* cur = pos._pnode;
            node* newnode = new node(val);
            node* prev = cur->_ppre;

            // prev  newnode  cur
            prev->_pnext = newnode;
            newnode->_ppre = prev;
            newnode->_pnext = cur;
            cur->_ppre = newnode;
            
            return iterator(newnode);
        }

        // 删除pos位置的节点，返回该节点的下一个位置
        iterator erase(iterator pos)
        {
            assert(pos._pnode != _phead);
            node* prev = pos._pnode->_ppre;
            node* next = pos._pnode->_pnext;

            delete pos._pnode;
            prev->_pnext = next;
            next->_ppre = prev;

            return iterator(next);
        }

        void clear()
        {
            iterator cur = begin();
            while (cur != end())
            {
                cur = erase(cur);
            }
            _phead->_pnext = _phead;
            _phead->_ppre = _phead;
        }

        void swap(list<t>& l)
        {
            /*list<t> tmp = l;
            l = *this;
            *this = tmp;*/

            pnode tmp = _phead;
            _phead = l._phead;
            l._phead = tmp;
        }

    private:
        void createhead()
        {
            _phead = new node();
            _phead->_pnext = _phead;
            _phead->_ppre = _phead;
        }

        pnode _phead;
    };
};

你学会了吗？
好啦，本章对于《c++：list模拟实现》的学习就先到这里，如果有什么问题，还请指教指教，希望本篇文章能够对你有所帮助，我们下一篇见！！！

如你喜欢，点点赞就是对我的支持，感谢感谢！！！