IT评测·应用市场-qidao123.com技术社区

标题: 【C++】深度解析：用 C++ 模拟实现 list 类，探索其底层实现细节 [打印本页]

---

作者: 光之使者    时间: 2024-7-30 04:26
标题: 【C++】深度解析：用 C++ 模拟实现 list 类，探索其底层实现细节

 

目录
list先容
list模拟实现
list 节点类
list 的迭代器
定义 
构造函数
解引用
operator前置++和--与后置++和--
operator==与operator!=
list 类
构造函数
 begin()和end()
 拷贝构造
erase()
clear()
析构函数
insert
 push_back 和 push_front
pop_back 和 pop_front
完备代码

---

 

⭐list先容

• list是可以在常数范围内在任意位置进行插入和删除的序列式容器，而且该容器可以前后双向迭代。
  
• list的底层是双向链表布局，双向链表中每个元素存储在互不相干的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
  
• list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
  
• 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
  
• 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list 的第6个元素，必须从已知的位置(比如头部大概尾部)迭代到该位置，在这段位置上迭代须要线性的时间开销；list还须要一些额外的空间，以保存每个节点的相干联信息(对于存储范例较小元素的大list来说这大概是一个告急的因素)。
  

⭐list模拟实现

   

• list的底层是双向链表布局，包含有一个哨兵节点。
  
• 模拟实现list，要实现下列三个类：
  

  

•         ①list节点类
  
•         ②迭代器的类
  
•         ③list主要功能的类(size()，empty()...)
  

  模拟实现list的类的基本功能（增删等操作）要创建在迭代器类和节点类均已实现好的情况下才得以完成。
  ✨list 节点类

• 定义list中的节点ListNode，包含前驱指针，后驱指针和数据变量；
  
• 使用struct而不使用class定义类，是为了方便访问每个一个节点 ，struct默认是pbulic，而class中成员变量要定义为private，不方便访问。
  

1.         template<class T>
2.         struct ListNode
3.         {
4.                 ListNode<T>* _next;
5.                 ListNode<T>* _prev;
6.                 T _data;
8.                 ListNode(const T& x = T())
9.                         :_next(nullptr)
10.                         ,_prev(nullptr)
11.                         ,_data(x)
12.                 {}
13.         };

复制代码

✨list 的迭代器

迭代器有两种实现方式，具体应根据容器底层数据布局实现：
1. 原生态指针，比如：vector
2. 将原生态指针进行封装，因迭代器使用形式与指针完全雷同，因此在自定义的类中必须实现以下方法：

• 指针可以解引用，迭代器的类中必须重载operator*()
  
• 指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()
  
• 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)
  
• 至于operator--()/operator--(int)释放须要重载，根据具体的布局来决议，双向链表可以向前移动，以是须要重载，如果是forward_list就不须要重载--
  
• 迭代器须要进行是否相等的比力，因此还须要重载operator==()与operator!=()
  

---

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)

Powered by Discuz! X3.4