网站导航
> 技术文档 > C++之list类的代码及其逻辑详解 （中）

C++之list类的代码及其逻辑详解 （中）

网友: 技术文档 2025-09-02 19:09:42

接下来我会依照前面所说的一些接口以及list的结构来进行讲解。

1. list_node的结构

1.1 list_node结构体

list由于其结构为双向循环链表，所以我们在这里要这么初始化

  • _next：指向链表中下一个节点的指针
  • _prev：指向链表中上一个节点的指针
  • _val：存储节点的值

list_node(const T& val = T()) 用于初始化节点，将 _next 和 _prev 指针默认设置为 nullptr，并将 _val 初始化为传入的值

struct list_node{list_node* _next;list_node* _prev;T _val; list_node(const T& val = T()):_next(nullptr), _prev(nullptr), _val(val) {}};

  1. typedef list_node Node;

    • 将list_node（链表节点类型）简化定义为Node
    • 在类内部可以直接使用Node来表示链表节点类型，无需重复写list_node

  2. typedef _list_iterator iterator;

    • 定义了普通迭代器类型iterator
    • 这里的_list_iterator应该是一个迭代器模板类，三个模板参数分别表示：
      • 存储的数据类型T
      • 迭代器解引用后返回的引用类型T&
      • 迭代器解引用后返回的指针类型T*

  3. typedef _list_iterator const_iterator;

    • 定义了常量迭代器类型const_iterator
    • 与普通迭代器的区别是，解引用后返回的是const类型的引用和指针
    • 用于对const list对象进行遍历，保证不能通过迭代器修改元素值
class list{ public:typedef list_node Node;typedef _list_iterator iterator;typedef _list_iterator const_iterator;};

1.2 list和list_node分离设计原因 

将list_node结构体和list类分离设计，是一种典型的 \"数据存储\" 与 \"逻辑管理\" 分离的思想。

1. 职责分离，符合单一职责原则
  • list_node结构体：仅负责存储单个节点的数据和连接关系（前驱_prev、后继_next指针），它的职责非常单一 —— 就是作为链表的 \"最小数据单元\"。
  • list类：负责管理整个链表的逻辑，包括节点的创建 / 销毁、插入 / 删除、遍历、容量管理等操作。它不直接存储数据，而是通过操作list_node对象来实现链表的整体功能。

这种分离让代码更清晰：节点只关心自身数据和连接，链表类只关心整体逻辑，便于维护和扩展。

2. 封装性更好，隐藏实现细节
  • list_node通常是list类的内部私有类型（或通过typedef限定在类内部使用），外部用户不需要知道节点的具体结构（比如_prev、_next指针的存在）。
  • 用户只需通过list类提供的接口（如push_back、erase、迭代器等）操作链表，无需直接接触节点，避免了误操作节点指针导致的内存问题（如野指针、内存泄漏）。
3. 便于迭代器设计和容器适配
  • 链表的迭代器需要通过节点的_next/_prev指针实现遍历，将节点封装为list_node后，迭代器可以统一通过节点指针操作，无需关心具体数据类型。
  • 符合 STL 容器的设计规范：STL 中所有容器都需要将 \"元素存储\" 和 \"容器管理\" 分离，这样才能统一迭代器接口。
  • list_node可以被视为一个通用的 \"双向节点模板\"，如果未来需要实现其他基于双向节点的结构（如循环链表、队列等），可以复用list_node的设计。
  • 当需要扩展链表功能时，只需修改list类的管理逻辑，无需改动list_node的结构。

2. list迭代器

2.1 三个可变参数的原因

我们在这里之所以要设置三个，是因为在list的迭代器里面需要不同的类型。同时一个可变参数在一个类里面只会推导一次，所以我们在这里是需要是三个。

  • T：链表中存储的元素类型（如 int、string 等）。
  • Ref：迭代器解引用后返回的引用类型（普通迭代器用 T&，常量迭代器用 const T&）。
  • Ptr：迭代器通过 -> 运算符返回的指针类型（普通迭代器用 T*，常量迭代器用 const T*）。
templatestruct _list_iterator{typedef list_node Node;typedef _list_iterator self;Node* _node;};

2.2 构造函数

我们在这里又会有构造函数，是因为我们在list中实际上写了三个类，一个list_iterator，一个list_node和一个list，这三者构成了完整的list。

这个就是在给list的迭代器进行初始化。因为是通过节点去访问所以怎么写。

_list_iterator(Node* node):_node(node){}

2.3 operator*()

返回对元素的引用（Ref），模拟指针的解引用操作（如 *p 获取指针指向的对象）。所以在这里要使用Ref。

Ref operator*(){return _node->_val;}

2.4 operator->() 

这边的Ptr更多是为了结构体这种设计的，简单来说这样设计就是为了先进入结构体然后再访问其内部成员。

那为什么要加&呢？这是因为operator要返回一个指针，然后我们通过这个指针来访问结构体的内部成员。

Ptr operator->(){return &_node->_val;}

2.5 前置++

因为是前置的，所以是先++再return。

self 是迭代器类型本身（_list_iterator），它是一个 “指向元素的迭代器”，负责管理节点指针、提供遍历能力。

self& operator++(){_node = _node->_next;return *this;}

2.6 后置++

这边（）里面的int是特殊处理，是为了和前置++构成函数重载。

又因为是后置++，所以我们让迭代器向后走并返回走之前的值。

self operator++(int){self tmp(*this);_node = _node->next;return tmp;}

2.7 前置--

因为是前置--，所以先返回上一个节点在return。

self& operator--(){_node = _node->_prev;return *this;}

2.8 后置--

因为是后置--，所以先保存节点在--。

int是为了和前置--构成函数重载。

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

2.9 operator！=

这个加const是防止修改指向和被指向的内容。

因为是bool类型的，所以直接比较两个指针的地址值是否一样即可。

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

2.10 operator==

这个加const是防止修改指向和被指向的内容。

因为是bool类型的，所以直接比较两个指针的地址值是否一样即可。

bool operator==(const self& it) const{return _node == it._node;}
网络标签：

相关问题