0
0

【C++】list模拟实现

💗个人主页💗
⭐个人专栏——C++学习⭐
💫点击关注🤩一起学习C语言💯💫

导读

我们刚刚学习了list的一些基本的使用，现在我们来尝试着模拟实现一下。

需要注意的是，我们需要写三个类来进行模拟实现。

1. vector与list的区别

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不 同，其主要不同如下：
vectorlist底 层 结 构动态顺序表，一段连续空间带头结点的双向循环链表随 机 访 问支持随机访问，访问某个元素效率O(1）不支持随机访问，访问某个元素 效率O(N)插 入 和 删 除任意位置插入和删除效率低，需要搬移元素，时间复杂 度为O(N)，插入时有可能需要增容，增容：开辟新空 间，拷贝元素，释放旧空间，导致效率更低任意位置插入和删除效率高，不 需要搬移元素，时间复杂度为 O(1）空 间 利 用 率底层为连续空间，不容易造成内存碎片，空间利用率 高，缓存利用率高底层节点动态开辟，小节点容易 造成内存碎片，空间利用率低， 缓存利用率低迭 代 器原生态指针对原生态指针(节点指针)进行封装迭 代 器 失 效在插入元素时，要给所有的迭代器重新赋值，因为插入 元素有可能会导致重新扩容，致使原来迭代器失效，删 除时，当前迭代器需要重新赋值否则会失效插入元素不会导致迭代器失效， 删除元素时，只会导致当前迭代 器失效，其他迭代器不受影响使 用 场 景需要高效存储，支持随机访问，不关心插入删除效率大量插入和删除操作，不关心随 机访问

2. 模拟实现

2.1 三个基本类

真正实现list，我们需要完成三个类：

  1. 节点类
  2. 迭代器类
  3. list功能类

为什么要写三个类？

我们在上面与vector的对比中了解到，list的空间不是连续的，节点类是好理解的，因为每个节点都有前驱指针、后驱指针以及数据，设定节点类更方便我们进行管理。也正是因为list每个节点空间并不是连续的，所以它的迭代器并不像vector或是string那样可以直接使用，而是需要我们自己来实现它，以便于让它++或是--能访问到下一个节点。

2.2 节点类实现

在节点类中，有三个成员变量：

  1. _prev：指向前一个节点的指针。
  2. _next：指向后一个节点的指针。
  3. _data：节点的数据。

节点类有一个默认构造函数，默认参数为

T()

，其中

T

是模板类型。构造函数初始化了成员变量，将

_prev

和

_next

指针置为

nullptr

，

_data

置为给定的值（默认为类型

T

的默认值）。

当 

T

被具体化为 

int

时，

ListNode<int>*

就是指向 

ListNode<int>

类型对象的指针，类似于 

int*

是指向 

int

类型对象的指针。

    //节点类实现
    template<class T>
    struct ListNode
    {
        ListNode<T>* _prev;//C++中可省略了struct
        ListNode<T>* _next;
        T _data;

        //构造函数
        ListNode(const T& x = T())
            :_next(nullptr)
            ,_prev(nullptr)
            ,_data(x)
        {}
    };

2.3 迭代器类实现

2.3.1基础实现及构造函数

代码中定义了三个模板参数：

T

表示节点中存储的数据类型，

Ref

表示引用类型，

Ptr

表示指针类型。

Node* _node

是指向当前节点的指针。

ListIterator(Node* node)

是构造函数，用于初始化迭代器对象。它接受一个参数 

node

，表示要遍历的节点。

//迭代器类实现
    template<class T, class Ref, class Ptr>
    struct ListIterator
    {
        typedef ListNode<T> Node;
        typedef ListIterator<T, Ref, Ptr> Self;
        Node* _node;
        ListIterator(Node* node)
            :_node(node)
        {}
    }

通过使用模板参数，可以实现在不同类型的节点上使用相同的迭代器类。例如，可以用 

ListIterator<int, int&, int*>

来遍历存储 

int

类型数据的链表，或者用 

ListIterator<string, string&, string*>

来遍历存储 

string

类型数据的链表。

2.3.2 operator*

        //*it（调用的是函数，返回节点中的值）
        //T& operator*()
        Ref operator*()
        {
            return _node->_data;
        }

2.3.3 operator->

这个重载是服务于自定义类型的，比如Date类，如果需要访问Date类中的元素则需

list<Date>::iterator it;   
it->Date->data;

        //it->           自定义类型需要
        //T* operator->()
        //list<Date>::iterator it;   it->Date->data;
        Ptr operator->()
        {
            return &_node->_data;
        }

2.3.4 operator前置++和后置++

        //++it 迭代器++本质就是指针往后移，加完后还应是个迭代器
        Self& operator++()
        {
            _node = _node->_next;
            return *this;
        }

        //it++
        Self operator++(int)//加参数方便区分前置++和后置++
        {
            Self tmp(*this);//拷贝构造，记录当前节点
            _node = _node->_next;
            return tmp;//因为是先使用再++，所以返回原先节点方便使用
        }

2.3 5 operator前置--和后置--

        //--it
        Self& operator--()
        {
            _node = _node->_prev;
            return *this;
        }

        //it--
        Self operator--(int)
        {
            Self tmp(*this);
            _node = _node->_prev;
            return tmp;
        }

2.3.6 operator!=和operator==

        //it != end()
        bool operator!=(const Self& it)
        {
            return _node != it._node;
        }

        bool operator==(const Self& it)
        {
            return _node == it._node;
        }

2.4 list功能类实现

2.4.1 基础实现

    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;
    private:
        Node* _head;//头节点
        size_t _size;
    };

2.4.2 构造函数

对哨兵位的头结点_head进行初始化

        void empty_init()
        {
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;

            _size = 0;
        }
        //构造函数
        list()
        {
            empty_init();
        }

2.4.3 begin()和end()

begin的作用是返回第一个位置的结点的迭代器，而第一个结点就是哨兵位头结点的下一个结点。

end的作用就是返回最后一个有效数据的下一个位置的迭代器，而这里对于list指的就是头结点_head的位置。

        iterator begin()
        {
            return _head->_next;
        }

        iterator end()
        {
            return _head;
        }

        const_iterator begin() const
        {
            return _head->_next;
        }

        const_iterator end() const
        {
            return _head;
        }

2.4.4 拷贝构造函数

        // lt2(lt1)拷贝构造
        list(const list<T>& lt)
        {
            empty_init();
            //遍历lt1，把lt1的元素push_back到lt2里头
            for (auto& e : lt)
            {
                push_back(e);
            }
        }

2.4.5 赋值运算符重载

        void swap(list<T>& lt)
        {
            std::swap(_head, lt._head);
            std::swap(_size, lt._size);
        }

        //lt1 = lt2
        list<T>& operator=(list<T> lt)
        {
            swap(lt);
            return *this;
        }

2.4.6 insert（）

  1. 获取要插入位置的迭代器pos所指向的节点cur。
  2. 创建一个新的节点newnode，并将其数据值初始化为传入的参数val。
  3. 获取当前节点cur的前一个节点prev。
  4. 将新节点newnode插入到当前位置： - 将前一个节点的下一个节点指针_next指向新节点newnode。- 将新节点的前一个节点指针_prev指向前一个节点。- 将新节点的下一个节点指针_next指向当前节点cur。- 将当前节点的前一个节点指针_prev指向新节点newnode。
  5. 增加链表的大小_size。
        void insert(iterator pos, const T& val)
        {
            Node* cur = pos._node;
            Node* newnode = new Node(val);
            Node* prev = cur->_prev;

            prev->_next = newnode;
            newnode->_prev = prev;
            newnode->_next = cur;
            cur->_prev = newnode;
            _size++;
        }

2.4.7 push_back（）

法一：

  1. 创建一个新的节点newnode，并将其数据值初始化为传入的参数x。
  2. 获取链表的尾节点tail，即链表头节点的前一个节点。
  3. 将新节点newnode插入到链表尾部： - 将尾节点的下一个节点指针_next指向新节点newnode。- 将新节点的前一个节点指针_prev指向尾节点。- 将新节点的下一个节点指针_next指向链表头节点。- 将链表头节点的前一个节点指针_prev指向新节点newnode。
        void push_back(const T& x)
        {
            Node* newnode = new Node(x);
            Node* tail = _head->_prev;

            tail->_next = newnode;
            newnode->_prev = tail;
            newnode->_next = _head;
            _head->_prev = newnode;
        }

法二：

直接调用insert（）函数

        void push_back(const T& x)
        {
            insert(end(), x);
        }

2.4.8 push_front（）

        void push_front(const T& x)
        {
            insert(begin(), x);
        }

2.4.9 erase（）

  1. 首先判断传入的迭代器pos是否指向链表的末尾，如果是，则抛出异常。
  2. 获取要删除位置的迭代器pos所指向的节点cur。
  3. 获取当前节点cur的前一个节点prev和后一个节点next。
  4. 将前一个节点的下一个节点指针_next指向后一个节点。
  5. 将后一个节点的前一个节点指针_prev指向前一个节点。
  6. 删除当前节点cur。
  7. 减少链表的大小_size。
  8. 返回一个指向下一个节点的迭代器。
        iterator erase(iterator pos)
        {
            assert(pos != end());
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* next = cur->_next;

            prev->_next = next;
            next->_prev = prev;

            delete cur;
            _size--;
            return iterator(next);
        }

2.4.10 pop_back（）

直接复用erase函数

        void pop_back()
        {
            erase(--end());
        }

2.4.11 pop_front（）

        void pop_front()
        {
            erase(begin());
        }

2.4.12 clear（）

复用erase函数，遍历每个节点。

        void clear()
        {
            iterator it = begin();
            while (it != end())
            {
                it = erase(it);
            }
        }

2.4.13 析构函数

调用clear函数，并释放哨兵节点。

        //析构函数
        ~list()
        {
            clear();
            delete _head;
            _head = nullptr;
        }

2.4.14 size（）

        size_t size() const
        {
            return _size;
        }

2.4.15 empty（）

判断size是否等于0。

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

3. 代码整理

3.1 list.h

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

namespace mylist
{
    //节点类实现
    template<class T>
    struct ListNode
    {
        ListNode<T>* _prev;//C++中可省略了struct
        ListNode<T>* _next;
        T _data;

        //构造函数
        ListNode(const T& x = T())
            :_next(nullptr)
            ,_prev(nullptr)
            ,_data(x)
        {}
    };

    //迭代器类实现
    template<class T, class Ref, class Ptr>
    struct ListIterator
    {
        typedef ListNode<T> Node;
        typedef ListIterator<T, Ref, Ptr> Self;
        Node* _node;
        ListIterator(Node* node)
            :_node(node)
        {}

        //*it（调用的是函数，返回节点中的值）
        //T& operator*()
        Ref operator*()
        {
            return _node->_data;
        }

        //it->           自定义类型需要
        //T* operator->()
        //list<Date>::iterator it;   it->Date->data;
        Ptr operator->()
        {
            return &_node->_data;
        }

        //++it 迭代器++本质就是指针往后移，加完后还应是个迭代器
        Self& operator++()
        {
            _node = _node->_next;
            return *this;
        }

        //it++
        Self operator++(int)//加参数方便区分前置++和后置++
        {
            Self tmp(*this);//拷贝构造，记录当前节点
            _node = _node->_next;
            return tmp;//因为是先使用再++，所以返回原先节点方便使用
        }

        //--it
        Self& operator--()
        {
            _node = _node->_prev;
            return *this;
        }

        //it--
        Self operator--(int)
        {
            Self tmp(*this);
            _node = _node->_prev;
            return tmp;
        }

        //it != end()
        bool operator!=(const Self& it)
        {
            return _node != it._node;
        }

        bool operator==(const Self& it)
        {
            return _node == it._node;
        }
    };

    //链表类
    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;
        
        iterator begin()
        {
            return _head->_next;
        }

        iterator end()
        {
            return _head;
        }

        const_iterator begin() const
        {
            return _head->_next;
        }

        const_iterator end() const
        {
            return _head;
        }

        void empty_init()
        {
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;

            _size = 0;
        }
        //构造函数
        list()
        {
            empty_init();
        }

        // lt2(lt1)拷贝构造
        list(const list<T>& lt)
        {
            empty_init();
            for (auto& e : lt)
            {
                push_back(e);
            }
        }

        void swap(list<T>& lt)
        {
            std::swap(_head, lt._head);
            std::swap(_size, lt._size);
        }

        //lt1 = lt2
        list<T>& operator=(list<T> lt)
        {
            swap(lt);
            return *this;
        }

        //析构函数
        ~list()
        {
            clear();
            delete _head;
            _head = nullptr;
        }

        void clear()
        {
            iterator it = begin();
            while (it != end())
            {
                it = erase(it);
            }
        }

        /*void push_back(const T& x)
        {
            Node* newnode = new Node(x);
            Node* tail = _head->_prev;

            tail->_next = newnode;
            newnode->_prev = tail;
            newnode->_next = _head;
            _head->_prev = newnode;
        }*/

        void push_back(const T& x)
        {
            insert(end(), x);
        }
        void push_front(const T& x)
        {
            insert(begin(), x);
        }
        void insert(iterator pos, const T& val)
        {
            Node* cur = pos._node;
            Node* newnode = new Node(val);
            Node* prev = cur->_prev;

            prev->_next = newnode;
            newnode->_prev = prev;
            newnode->_next = cur;
            cur->_prev = newnode;
            _size++;
        }

        void pop_back()
        {
            erase(--end());
        }

        void pop_front()
        {
            erase(begin());
        }
        iterator erase(iterator pos)
        {
            assert(pos != end());
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* next = cur->_next;

            prev->_next = next;
            next->_prev = prev;

            delete cur;
            _size--;
            return iterator(next);
        }
         
        size_t size() const
        {
            return _size;
        }

        bool empty()
        {
            return size == 0;
        }
    private:
        Node* _head;//头节点
        size_t _size;
    };

    void test1()
    {
        list<int> lt;
        lt.push_back(1);
        lt.push_back(2);
        lt.push_back(3);
        lt.push_back(4);
        cout << "尾插" << endl;
        list<int>::iterator it = lt.begin();
        while (it != lt.end())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;

        lt.push_front(10);
        lt.push_front(20);
        lt.push_front(30);
        cout << "头插" << endl;
        for (auto e : lt)
        {
            cout << e << " ";
        }
        cout << endl;

        lt.pop_back();
        lt.pop_back();
        lt.pop_front();
        lt.pop_front();
        cout << "头删尾删" << endl;
        for (auto e : lt)
        {
            cout << e << " ";
        }
        cout << endl;
    }

    struct Date
    {
        int _year = 0;
        int _month = 1;
        int _day = 1;
    };

    void test2()
    {
        Date* p2 = new Date;
        *p2;//取到的是Date
        p2->_year;//取到的是Date类中的成员变量

        list<Date>lt;
        lt.push_back(Date());
        lt.push_back(Date());
        //list存了个日期类(自定义类型)的类型
        list<Date>::iterator it = lt.begin();
        while (it != lt.end())
        {
            //cout << *it << " ";
            cout << it->_year << "-" << it->_month << "-" << it->_day << endl;
            ++it;
        }
        cout << endl;

    }

}

3.2 test.cpp

#include "list.h"

int main()
{
    //mylist::test1();
    mylist::test2();

    return 0;
}
标签： c++ 开发语言
本文转载自: https://blog.csdn.net/qq_64818885/article/details/139527729
版权归原作者 流浪者与猴 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【C++】list模拟实现”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

项目符合行业安全标准的必要步骤与实用建议

Nginx location 和 proxy_pass 配置详解

Python自动化测试实战：Selenium页面切换技术详解

van-picker级联设置默认选择

前端请求后端接口报错(blocked:mixed-content)，以及解决办法

功能安全实战系列-DFA(Dependent Failure Analysis)分析

Apifox接口项目搭建、管理优化方案报告

文章导航