• list的模拟实现(万字解读+由浅入深)


    先申明一下本篇总体介绍过程是按照逐步深入去写的,所以可能有些同样类型不在一块!

    前言:

      写这篇博客的时候,我是边思考边写它!自己其中感觉自己对于list的理解更加的深入,其中提出的很多问题让我明白了list为什么要这么设计,以及代码为啥要这么写!希望我的这篇博客不仅让我受益匪浅,也能对你有所帮助!若您发现了其中有什么地方有问题,希望评论区您能提出来。如果你有更好的理解思路,也希望您能不吝赐教!最后写博客不易,还望给一个赞!

     💡💡追着光,跟着光,成为光,发散光!

    目录

     一、list 介绍

     二、list 基本框架

    2.1 结点

    2.2 迭代器框架

    2.3  链表类框架

    三、模拟实现list

    3.1 先提前写好的list函数

    3.1.1 默认构造函数list() (构建哨兵结点)

     💡💡3.1.2 返回(非const)迭代器的begin() end()

    3.1.3 迭代器价值+类封装价值

    3.2 挪动数据的函数

    之前先说明如何查找位置?标准库的find()函数!

    3.2.1 insert() 任意位置插入 (往指定位置的前面插入)

    3.2.2 erase() 任意位置删除结点 ( 迭代器失效问题)

    3.2.3 push_back() 尾插

    3.2.4 pop_back() 尾删 

    3.2.5 push_front() 头插 

    3.2.5 pop_front() 头删

    3.3 构造函数

    3.3.1 迭代器区间构造

    3.3.2 拷贝构造(现代写法)

    💡💡引入const 迭代器(非常重要!)

    3.3.4 赋值拷贝(现代写法) 

    3.4 释放空间函数

    3.4.1 clear() 释放list非哨兵结点其余结点

    3.4.2 ~list() 析构函数

    四、模拟实现的list


     一、list 介绍

    1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。
    2. list的底层是带头双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。
    3. 与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好。
    4. 与其他序列式容器相比,list最大的缺陷是不支持任意位置的随机访问,比如:要访问list的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间开销;list还需要一些额外的空间,以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

    💡强调一下head是哨兵结点,本身不存储数据,作用只是指向头和尾!


     二、list 基本框架

    2.1 结点

    1. //结点
    2. template<class T>
    3. struct list_node
    4. {
    5. //结点构造函数
    6. list_node(const T& val = T())
    7. :prev(nullptr)
    8. , next(nullptr)
    9. , data(val)
    10. {}
    11. public:
    12. list_node* prev;//接前
    13. list_node* next;//接后
    14. T data;//存储数据
    15. };

    这里对于T()说明一下!这里是匿名构造,对于传来的参数类型不确定,可能是内置类型,也可能是类对象!所以不能想当然比如说默认赋值0!

    2.2 迭代器框架

    1. template<class T,class ref,class ptr>
    2. struct list_iterator
    3. {
    4. typedef list_node<T> node;
    5. typedef list_iterator<T, ref, ptr> Self;
    6. node* pnode;
    7. list_iterator(node* p)
    8. :pnode(p)
    9. {}
    10. ref operator*()
    11. ptr operator->()
    12. //前置
    13. Self& operator++()
    14. //后置
    15. Self operator++(int)
    16. //前置
    17. Self& operator--()
    18. //后置
    19. Self operator--(int)
    20. bool operator!=(const Self& it)
    21. bool operator==(const Self& it)
    22. };

    2.3  链表类框架

    1. class list
    2. {
    3. public:
    4. typedef list_node<T> node;
    5. typedef list_iterator<T,T&,T*> iterator;
    6. typedef list_iterator<T, const T&,const T*> const_iterator;
    7. iterator begin()
    8. const_iterator begin()const
    9. const_iterator end()const
    10. iterator end()
    11. void clear()
    12. ~list()
    13. void empty_initialize()
    14. list()
    15. template <class InputIterator>
    16. list(InputIterator first, InputIterator end)
    17. void swap(list<T>& lt)
    18. list(const list<T>& lt)
    19. list<T>& operator=(list<T> tmp)
    20. void push_back(const T& x)
    21. void push_front(const T& x)
    22. void pop_front()
    23. void pop_back()
    24. void insert(iterator pos,const T& x)
    25. iterator erase(iterator pos)
    26. private:
    27. node* head;//底层是一个哨兵结点
    28. };

    这里问一个问题,等你看完这篇文章理解很多的时候,回来比较这三个类的是否手动析构,手动写拷贝构造!深入自己想想为啥是上面的结果!

    三、模拟实现list

    3.1 先提前写好的list函数

    这些函数是后面写的基础!后面会频繁调用,所以先写出来!

    3.1.1 默认构造函数list() (构建哨兵结点)

    💡强调一下head是哨兵结点,本身不存储数据,作用只是指向头和尾!

    后面要多次用到这个empty_initialize()内代码 ,所以就用函数了!

    1. void empty_initialize()
    2. {
    3. head = new node;//用new对象,可以直接调用对象的构造函数
    4. head->next = head;
    5. head->prev = head;
    6. }
    7. list()
    8. {
    9. empty_initialize();
    10. }

     💡💡3.1.2 返回(非const)迭代器的begin() end()

    首先我们需要将封装的迭代器需要实现的功能函数写好!

    ❓❓首先我们要问自己一个问题,链表的迭代器能不能像vector string 那样直接单纯地用解引用和++?

    我们不妨回顾一下vector string 的迭代器,其底层是指针数组的原生指针!而它们容器的存储空间是连续的,解引用可以直接拿到数组数据,++可以直接加上类型的步长!

    而list的呢?list是不连续的!它们通过前后指针链接!直接++不能找到后一个结点解引用不是直接拿到存储数据,而是一个结点结构体!我们需要的是里面的Data!

    怎么办? 系统的* ++ 不能满足我们需要的结果!

    💡必须重载运算符!所以我们得将迭代器封装成一个类!

    现在再问自己一个问题! 他的类成员变量是谁? 联系一下我们的目的和链表容器结构!

    我们想到一个指向node 的指针就可以解决了,++不就是next,--不就是prev *不就是data!

    !这里单独将->符号拿出来说明一下! 想用->访问数据,->左边是什么? 是结构体地址! 

    也就是说如果我们list 存储的数据是结构体或者类!里面有多个变量,那么我们访问数据就不能单纯的解引用!必须使用->来访问数据!

    下面上代码~

    1. template<class T>
    2. struct list_iterator
    3. {
    4. typedef list_node<T> node;//结点类
    5. typedef list_iterator<T> Self;//迭代器类
    6. node* pnode;//成员变量
    7. //构造函数
    8. list_iterator(node* p)
    9. :pnode(p)
    10. {}
    11. T& operator*()
    12. {
    13. return pnode->data;
    14. }
    15. T* operator->()
    16. {
    17. return &pnode->data;//返回结构体地址
    18. }
    19. Self& operator++()
    20. {
    21. pnode = pnode->next;
    22. return *this;
    23. }
    24. Self& operator--()
    25. {
    26. pnode = pnode->prev;
    27. return *this;
    28. }
    29. bool operator!=(const Self& it)
    30. {
    31. return pnode != it.pnode;
    32. }
    33. };

    现在迭代器功能基本完善!我们通过链表函数构建迭代器!

    1. //再强调一下,迭代器被封装成类!!!
    2. typedef list_iterator<T> iterator;
    3. iterator begin()
    4. {
    5. //匿名对象返回!这里调用了迭代器的构造函数
    6. return iterator(head->next);
    7. }
    8. iterator end()
    9. {
    10. //这里千万记住,返回的是哨兵结点!不是尾结点!
    11. return iterator(head);
    12. }

    现在看看如何使用迭代器!

    3.1.3 迭代器价值+类封装价值

    迭代器是一种可以遍历数组的抽象接口!

    1.封装底层实现,不暴露底层实现原理

    2.有了迭代器,可以不关心底层实现原理,而是注重使用!

    我们上面用的*符号,看似简单几个字母,可底层却是返回Data!我们不需要知道它返回的具体是什么,我们只要知道*符号代表着就是获取容器数据的方式!

    类封装价值是什么?

    1.因为不同容器实现原理不同,vector,list同样是*符号,对于vector,*号是原生指针!解引用可以直接获取数据,但是对于list,解引用实现不了我们直接获取数据的方法!(前面说过)有了类封装,我们就可以重载*号,让它的意义改变!有了封装,让我们使得同样的符号,对于不同实现原理的容器,可以有同样的效果!

    2.我们可以注意到,即使是封装了迭代器,它的物理消耗内存仍只有一个指针大小!也就是说即使是类,他没有过多消耗内存!


    3.2 挪动数据的函数

    有了迭代器,它的成员变量是指向结点的指针,所以我们可以用迭代器获取结点位置!

    之前先说明如何查找位置?标准库的find()函数!

    参数为迭代器头尾和要查找的数据!

    3.2.1 insert() 任意位置插入 (往指定位置的前面插入)

    1. void insert(iterator pos, const T& x)
    2. {
    3. node* newnode = new node(x);//构造新结点
    4. node* cur = pos.pnode;//记录当前结点
    5. node* prev = cur->prev;
    6. prev->next = newnode;
    7. newnode->prev = prev;
    8. cur->prev = newnode;
    9. newnode->next = cur;
    10. }

    3.2.2 erase() 任意位置删除结点 ( 迭代器失效问题)

    1. iterator erase(iterator pos)
    2. {
    3. node* cur = pos.pnode;
    4. node* prev = cur->prev;
    5. node* next = cur->next;
    6. prev->next = next;
    7. next->prev = prev;
    8. delete[]cur;//delete会调用结点类的默认析构函数
    9. //!!!返回下一个位置的迭代器
    10. return iterator(next);
    11. }

     为什么会有迭代器失效问题? 因为结点空间被释放了,这样迭代器++也就不能找到下一个位置结点,所以返回需要返回下一个结点迭代器!

    3.2.3 push_back() 尾插

    1. void push_back(const T& x)
    2. {
    3. insert(end(), x);
    4. }

    3.2.4 pop_back() 尾删 

    这里提一嘴,注意前后两者区别,前面不--end() 因为插入是插在结点前一个!end()返回哨兵结点,插在它的前一个就是尾结点!

    这里尾删,删的是尾结点,所以--迭代器重载返回前一个结点,也就是尾结点!

    1. void pop_back()
    2. {
    3. erase(--end());
    4. }

    3.2.5 push_front() 头插 

    1. void push_front(const T& x)
    2. {
    3. insert(begin(), x);
    4. }

    3.2.5 pop_front() 头删

    1. void pop_front()
    2. {
    3. erase(begin());
    4. }


    3.3 构造函数

    3.3.1 迭代器区间构造

    1. template <class InputIterator>
    2. list(InputIterator first, InputIterator end)
    3. {
    4. empty_initialize();//构建哨兵结点
    5. while (first != end)
    6. {
    7. push_back(*first);
    8. ++first;
    9. }
    10. }

    3.3.2 拷贝构造(现代写法)

    1.先构造临时链表tmp(深拷贝!)->> 2. 临时链表与拷贝构造链表交换!

    那么如何交换两个链表? 很简单就是交换两个链表的哨兵结点

    1. //list<T> lt2(lt1)
    2. void swap(list<T>& lt)
    3. {
    4. std::swap(head, lt.head);//交换地址
    5. }
    6. list(const list<T>& lt)
    7. {
    8. empty_initialize();//注意我们必须初始化lt2的哨兵结点!这样tmp析构的时候析构的不是野指针!
    9. list<T> tmp(lt.begin(), lt.end());
    10. swap(tmp);
    11. }

    💡💡引入const 迭代器(非常重要!)

    首先说明一下,为什么从这里引入const 迭代器,因为注意一下这个拷贝构造的传参,是const list &,我们在用迭代器构造tmp的时候,传的 lt 是const的!

    所以我们要实现const 迭代器!

    首先我们得明确一下const迭代器const的作用,这个const保护的是Data!也就是说数据只可读,不可写!迭代器解引用不能算数运算!迭代器本身可以++!

    如何实现const迭代器?

    先思考一下下面这个写法能不能实现我们要的const迭代器

     现在看看这样的 rit 能干什么:

     我们看到它不能++,它可以解引用算数运算!它是const迭代器吗?当然不是!通过结果我们不难可以类比原来的内置类型 这样写法相当于 int const * 而我们需要的是 const int* !

    所以我们仍需要自己写一个const迭代器!

    我们在明确一下const 迭代器与非const 迭代器的主要区别就在* 后是可读可写,还是只可读!也就是返回值一个是const T,一个是T!

    💡💡那这就很简单了,那不就是我们在原来普通迭代器基础上重载一个*号运算符重载函数,如下:

    1. template<class T>
    2. struct list_iterator
    3. {
    4. typedef list_node<T> node;//结点类
    5. typedef list_iterator<T> Self;//迭代器类
    6. ..../之前上面写的普通迭代器函数
    7. const T& operator*()const
    8. {
    9. return pnode->data;
    10. }
    11. };

    可是这样真的行吗?这样解决了当前的问题,可是我const迭代器想要调用普通迭代器其他接口函数怎么办?有人又会说了那每一个都重载一下呗!每一个函数都弄一个const!

    比如 之前的++,写成如下:

     那么请问,如果这样写了会有什么后果!我们来看看!

    因为const 修饰了this指针,所以我们不能改变this指向的类对象成员函数 !

    可是我们const迭代器只需要对* 做修改!所以这种只在原迭代器补const重载函数,行不通!

    那么引入第三种想法(一般人),我们可以重新写一个const迭代器类封装它,类中与原来普通迭代器不同的就是*号 重载函数!

    1. //在list类中定义const迭代器
    2. typedef const_list_iterator<T> const_iterator;
    3. //const迭代器类
    4. template<class T>
    5. struct const_list_iterator
    6. {
    7. typedef list_node<T> node;//结点类
    8. typedef const_list_iterator<T> Self;//迭代器类
    9. node* pnode;//成员变量
    10. //构造函数
    11. list_iterator(node* p)
    12. :pnode(p)
    13. {}
    14. //唯一区别地方
    15. const T& operator*()
    16. {
    17. return pnode->data;
    18. }
    19. T* operator->()
    20. {
    21. return &pnode->data;//返回结构体地址
    22. }
    23. Self& operator++()
    24. {
    25. pnode = pnode->next;
    26. return *this;
    27. }
    28. Self& operator--()
    29. {
    30. pnode = pnode->prev;
    31. return *this;
    32. }
    33. bool operator!=(const Self& it)
    34. {
    35. return pnode != it.pnode;
    36. }
    37. };

    现在我们看看C++设计者大佬的写法!它们的写法就是一行代码能解决的事绝不用多行

    之前我们先引入一个问题,模板类 类型的问题!

    请问list 是类型吗?它不是!它是类明!

    什么是类型? 诸如list的list它们是类型! 区别模板类类型的关键在于T!现在再想一想const迭代器不同于普通迭代器什么?不就是重载的*号不同!那么我们是否可以多一个模板参数,区别这两个不同的类!

    list_iterator  list_iterator这两个不是同一个迭代器!!!   

    现在看看大佬写法!

    三个模板参数!! 两者区别在于第二个一个是T,一个是const T!

    1. //这里的T*是->返回时的参数
    2. typedef list_iterator<T,T&,T*> iterator;
    3. typedef list_iterator<T, const T&,const T*> const_iterator;
    4. const_iterator begin()const
    5. {
    6. return const_iterator(head->next);
    7. }
    8. const_iterator end()const
    9. {
    10. return const_iterator(head);
    11. }
    12. template<class T, class ref, class ptr>
    13. struct list_iterator
    14. {
    15. typedef list_node<T> node;
    16. typedef list_iterator<T, ref, ptr> Self;
    17. node* pnode;
    18. list_iterator(node* p)
    19. :pnode(p)
    20. {}
    21. ref& operator*()
    22. {
    23. return pnode->data;
    24. }
    25. ptr operator->()
    26. {
    27. return &pnode->data;
    28. }
    29. Self& operator++()
    30. {
    31. pnode = pnode->next;
    32. return *this;
    33. }
    34. Self& operator--()
    35. {
    36. pnode = pnode->prev;
    37. return *this;
    38. }
    39. bool operator!=(const Self& it)
    40. {
    41. return pnode != it.pnode;
    42. }
    43. };

    3.3.4 赋值拷贝(现代写法) 

    1.构造tmp--> 2.交换--> 3.出作用域,临时变量调用析构函数,释放this原空间

    1. //连等可能,所以返回链表!
    2. //出作用域,被替换的tmp会调用它的析构函数,析构this的原空间
    3. list<T>& operator=(list<T> tmp)
    4. {
    5. swap(tmp);
    6. return *this;
    7. }

    3.4 释放空间函数

    3.4.1 clear() 释放list非哨兵结点其余结点

    1. void clear()
    2. {
    3. iterator first = begin();
    4. while (first != end())
    5. {
    6. first = erase(first);//!!!注意考虑迭代器失效
    7. }
    8. }

    3.4.2 ~list() 析构函数

    1. ~list()
    2. {
    3. clear();
    4. delete head;
    5. head = nullptr;
    6. }

    这里再引入一个问题!为什么之前的迭代器类,结点类我们没有写析构函数?现在需要写呢?

    因为这两个类的成员变量都是内置类型,默认构造会自动释放成员变量。它们的任务都是单个结点!

    如果list我们这里不写,默认析构函数只会将我们的头结点释放,那些剩余结点并没有被释放,也就是说list析构任务不仅仅是单个结点,而是所有结点!所以这里我们必须手动写! 

    四、模拟实现的list

    1. namespace wyz
    2. {
    3. template<class T>
    4. struct list_node
    5. {
    6. list_node(const T& val = T())
    7. :prev(nullptr)
    8. , next(nullptr)
    9. , data(val)
    10. {}
    11. public:
    12. list_node* prev;
    13. list_node* next;
    14. T data;
    15. };
    16. template<class T, class ref, class ptr>
    17. template<class T, class ref, class ptr>
    18. struct list_iterator
    19. {
    20. typedef list_node<T> node;
    21. typedef list_iterator<T, ref, ptr> Self;
    22. node* pnode;
    23. list_iterator(node* p)
    24. :pnode(p)
    25. {}
    26. ref operator*()
    27. {
    28. return pnode->data;
    29. }
    30. ptr operator->()
    31. {
    32. return &pnode->data;
    33. }
    34. //前置
    35. Self& operator++()
    36. {
    37. pnode = pnode->next;
    38. return *this;
    39. }
    40. //后置
    41. Self operator++(int)
    42. {
    43. Self tmp(pnode);
    44. pnode = pnode->next;
    45. return tmp;
    46. }
    47. //前置
    48. Self& operator--()
    49. {
    50. pnode = pnode->prev;
    51. return *this;
    52. }
    53. //后置
    54. Self operator--(int)
    55. {
    56. Self tmp(pnode);
    57. pnode = pnode->prev;
    58. return tmp;
    59. }
    60. bool operator!=(const Self& it)
    61. {
    62. return pnode != it.pnode;
    63. }
    64. bool operator==(const Self& it)
    65. {
    66. return pnode == it.pnode;
    67. }
    68. };
    69. template<class T>
    70. class list
    71. {
    72. public:
    73. typedef list_node<T> node;
    74. typedef list_iterator<T, T&, T*> iterator;
    75. typedef list_iterator<T, const T&, const T*> const_iterator;
    76. iterator begin()
    77. {
    78. //匿名对象返回!
    79. return iterator(head->next);
    80. }
    81. const_iterator begin()const
    82. {
    83. return const_iterator(head->next);
    84. }
    85. const_iterator end()const
    86. {
    87. return const_iterator(head);
    88. }
    89. iterator end()
    90. {
    91. return iterator(head);
    92. }
    93. void clear()
    94. {
    95. iterator first = begin();
    96. while (first != end())
    97. {
    98. first = erase(first);//!!!
    99. }
    100. }
    101. ~list()
    102. {
    103. clear();
    104. delete head;
    105. head = nullptr;
    106. }
    107. void empty_initialize()
    108. {
    109. head = new node;
    110. head->next = head;
    111. head->prev = head;
    112. }
    113. list()
    114. {
    115. empty_initialize();
    116. }
    117. template <class InputIterator>
    118. list(InputIterator first, InputIterator end)
    119. {
    120. empty_initialize();
    121. while (first != end)
    122. {
    123. push_back(*first);
    124. ++first;
    125. }
    126. }
    127. void swap(list<T>& lt)
    128. {
    129. std::swap(head, lt.head);
    130. }
    131. list(const list<T>& lt)
    132. {
    133. empty_initialize();
    134. list<T> tmp(lt.begin(), lt.end());
    135. swap(tmp);
    136. }
    137. list<T>& operator=(list<T> tmp)
    138. {
    139. swap(tmp);
    140. return *this;
    141. }
    142. void push_back(const T& x)
    143. {
    144. insert(end(), x);
    145. }
    146. void push_front(const T& x)
    147. {
    148. insert(begin(), x);
    149. }
    150. void pop_front()
    151. {
    152. erase(begin());
    153. }
    154. void pop_back()
    155. {
    156. erase(--end());
    157. }
    158. void insert(iterator pos, const T& x)
    159. {
    160. node* newnode = new node(x);
    161. node* cur = pos.pnode;
    162. node* prev = cur->prev;
    163. prev->next = newnode;
    164. newnode->prev = prev;
    165. cur->prev = newnode;
    166. newnode->next = cur;
    167. }
    168. iterator erase(iterator pos)
    169. {
    170. node* cur = pos.pnode;
    171. node* prev = cur->prev;
    172. node* next = cur->next;
    173. prev->next = next;
    174. next->prev = prev;
    175. delete[]cur;
    176. return iterator(next);
    177. }
    178. private:
    179. node* head;//底层是一个哨兵结点
    180. };

  • 相关阅读:
    P95陷阱
    进程和线程【详细总结】
    金仓数据库KingbaseES数据库参考手册(服务器配置参数14. 版本和平台兼容性)
    common Vocabulary3
    【Java】成员变量与局部变量的区别
    SpringBoot——数据访问
    QGIS编译(跨平台编译)之五十七:qgis_app库在Qt Creator环境下编译的错误处理
    vscode自动添加备注及函数信息
    Java多线程-线程关键字(二)
    python字符串
  • 原文地址:https://blog.csdn.net/qq_68926231/article/details/128161960