当前位置： 首页 > backend >正文

【C++初阶】--- list容器功能模拟实现

backend 2025/5/22 10:38:18

1.什么是list容器

在 C++ 标准模板库（STL）中，std::list 是一个非常有用的容器，它是双向链表的实现std::list 是一种序列式容器，它允许在序列内的任意位置进行高效的插入和删除操作。与数组和 std::vector 不同，std::list 中的元素在内存中并不是连续存储的，而是通过指针相互连接，形成一个双向链表。

2.需要创建的三个必要类模板

// 1.节点模板
template<class T>
struct list_node
{//成员变量T _data;list_node<T>* _next;list_node<T>* _prev;
};// 2.迭代器模板
template<class T, class Ref, class Ptr>
struct list_iterator
{typedef list_node<T> Node;typedef list_iterator<T, Ref ,Ptr> Self;//成员变量Node* _node;
};// 3.链表模板
template<class T>
class list
{typedef list_node<T> Node;
public:typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;private://成员变量包括哨兵位和链表长度Node* _head;size_t _size;
};

3.节点类模板

list容器底层是一个双向带头循环链表，所以节点类模板中有三个成员变量：data用于存储数据，next是指向下一个节点的指针，prev是指向前一个节点的指针。
节点类模板我们只需要实现一个默认构造用于构造出一个哨兵位即可，后续插入删除等操作在链表类模板中实现

template<class T>
struct list_node
{//成员变量T _data;list_node<T>* _next;list_node<T>* _prev;
};

3.1默认构造

//默认构造
list_node(const T& data = T())//T()匿名对象，内置类型一样有:_data(data), _next(nullptr), _prev(nullptr)
{}

4.迭代器类模板

我们模拟实现的迭代器底层是一个指向节点指针，所以有一个成员变量Node* _node

template<class T, class Ref, class Ptr>
struct list_iterator
{typedef list_node<T> Node;typedef list_iterator<T, Ref ,Ptr> Self;//成员变量Node* _node;
};

我们参考一下以下代码，我们要实现迭代器模板的原因是因为我们要对迭代器变量it进行++、–、*(解引用)、==、!=等操作，我们对it进行++操作的时候我们希望的是it能够指向下一个节点，对it进行解引用操作时我们希望能够取到节点中的数据，但因为链表中的数据不是连续存储的,所以这些操作符达到的实际效果与我们预期效果不符，所以我们要对这些运算符进行重载，使其能够达到我们实际的预期效果。

auto it = con.begin();
while (it != con.end())
{cout << *it << " ";it++;
}
cout << endl;

4.1operator*

这里的Ref我们之后传T&，即返回引用

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

4.2operator->

Ptr后续传的是T*

//返回的是指针
Ptr operator->()
{return &(_node->_data);
}

重载这个运算符的原因是我们可以进行以下操作：

struct AA
{int _a1;int _a2;
};
list<AA> lta;
lta.push_back(AA());
lta.push_back(AA());
lta.push_back(AA());
lta.push_back(AA());list<AA>::iterator ita = lta.begin();
while (ita != lta.end())
{//特殊处理，本来应该是两个->才合理，为了可读性，省略了一个->//cout << ita.operator->()->_a1 << ":" << ita.operator->()->_a2 << endl;cout << ita->_a1 << ":" << ita->_a2 << endl;ita++;
}

4.3前置++、–

//前置
Self& operator++()
{_node = _node->_next;return *this;//即返回节点
}Self& operator--()
{_node = _node->_prev;return *this;
}

4.4后置++、–

后置++、–返回的是临时变量，但实际值会改变

//后置
Self& operator++(int)
{Node* tmp(_node);_node = _node->_next;return *this;
}Self& operator--(int)
{Node* tmp(_node);_node = _node->_prev;return *this;
}

4.5operator==/operator!=

是否相同比较的是地址

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

5.链表类模板

链表类模板有两个成员变量：_head是指向链表哨兵位的指针，_size用于记录链表的长度。

// 3.链表模板
template<class T>
class list
{typedef list_node<T> Node;
public:typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;private://成员变量包括哨兵位和链表长度Node* _head;size_t _size;
};

5.1迭代器

begin()返回的是指向链表哨兵位后一个节点的迭代器，end()返回的是指向哨兵位的迭代器。

iterator begin()
{//有名对象/*iterator it(_head->_next);return it;*///匿名对象//return iterator(_head->_next);//单参数构造函数支持隐式类型转换return _head->_next;
}iterator end()
{return _head;
}

5.2const迭代器

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

const迭代器给const对象使用，如以下模板可以使用

//打印数据通用模板
template<class Container>
void print_Container(const Container& con)
{//去未实例化的类里面取东西，不知道是类型还是变量，加上typename说明是类型//typename Container::const_iterator it = con.begin();auto it = con.begin();while (it != con.end()){//*it += 10;cout << *it << " ";it++;}cout << endl;
}

5.3空初始化empty_init()

空初始化即初始化一个空链表，空链表只包含一个哨兵位。

//空初始化
void empty_init()
{_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;
}

5.4在pos位置插入节点insert()

在pos尾插插入数据需要传pos位置的迭代器，然后我们构造一个值位x的节点，改变相关节点前后指针的指向实现pos位置的插入

//在pos位置之前插入数据
void insert(iterator pos, const T& x)
{//申请新节点Node* newnode = new Node(x);Node* cur = pos._node;Node* prev = cur->_prev;//cur->prev、newnode、curnewnode->_next = cur;newnode->_prev = prev;cur->_prev = newnode;prev->_next = newnode;++_size;
}

5.5删除pos维持节点erase()

删除pos位置节点需要传pos位置得迭代器，注意不能删除哨兵位，然后我们改变相关节点前后指针的指向实现删除。

//删除pos位置数据
iterator erase(iterator pos)
{//不能删除哨兵位assert(pos != end());//pos->prev、pos->nextNode* next = pos._node->_next;Node* prev = pos._node->_prev;prev->_next = next;next->_prev = prev;delete pos._node;--_size;return next;
}

5.6尾插push_back()

往链表中尾插一个节点我们可以选择先构造一个新节点，然后改变相关节点前后指针的指向实现尾插，也可以选择复用insert传尾节点的迭代器实现尾插。

//尾插
//方法1
void push_back(const T& x)
{//申请新节点,用x构造一个节点Node* newnode = new Node(data);Node* tail = _head->_prev;//tail、newnode、tail->next(_head)tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;++_size;
}//方法2
void push_back(const T& x)
{insert(end(), x);
}

5.7头插push_front()

头插是插入至哨兵位后面。头插可以选择直接复用insert传头节点的迭代器实现，也可以想上面的尾插一样改变相关节点前后指针的指向实现头插

//头插
void push_front(const T& x)
{//_head、newnode、_head->nextinsert(begin(), x);
}

5.8尾删pop_back()

尾删我们直接复用erase，传尾节点的迭代器实现删除

//尾删
void pop_back()
{erase(--end());
}

5.9头删pop_front()

头删我们直接复用erase，传头节点的迭代器实现删除

//头删
void pop_front()
{erase(begin());
}

5.10size()和empty()

size()用于返回链表的长度，empty()用于判断链表是否为空

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

5.11构造函数

5.11.1默认构造

默认构造即构造一个哨兵位，我们可以复用空初始化。

//默认构造(哨兵位)
list()
{empty_init();
}

5.11.2拷贝构造

拷贝构造我们可以复用空初始化先给个哨兵位，然后使用范围for将节点一个一个尾插至链表中

//拷贝构造
list(const list<T>& lt)
{//先给个哨兵位empty_init();for (auto e : lt){push_back(e);}
}

6.打印数据的通用模板

通用模板我们传的是const对象，会调用const迭代器。
这里有一点需要注意，就是模板有个特性：按需实例化，即如果我们没有将这个模板实例化的话，如果这个模板中没有明显的语义错误，编译器是不会报错的，比如下面的打印模板，我们打印的是const对象，我们对const对象只有读的权限，我们不能对其进行修改,比如*it += 10，正常这样是会报错的，但因为这是在模板中写的，也就是说只有当模板被实例化后，编译器才会报错。

//按需实例化
template<class Container>
void print_Container(const Container& con)
{//去未实例化的类里面取东西，不知道是类型还是变量，加上typename说明是类型//typename Container::const_iterator it = con.begin();auto it = con.begin();while (it != con.end()){//*it += 10;cout << *it << " ";it++;}cout << endl;
}
http://www.xdnf.cn/news/29.html

相关文章：

  • 基于flask+vue框架的灯饰安装维修系统u49cf（程序+源码+数据库+调试部署+开发环境）带论文文档1万字以上，文末可获取，系统界面在最后面。
  • 【Unity】JSON数据的存取
  • 燕山大学计算机网络之Java实现TCP数据包结构设计与收发
  • 有什么工具可以在家连接到公司内网？局域网址提供异地公网访问的那些常用方法
  • 一台 Master 多节点玩转 Kubernetes：sealos 一键部署实践
  • MahApps.Metro：专为 WPF 应用程序设计的 UI 框架
  • 【数据结构】AVL树
  • 自动驾驶系列—GLane3D: Detecting Lanes with Graph of 3D Keypoints
  • android liveData observeForever 与 observe对比
  • CS144 Lab0实战记录：搭建网络编程基础
  • 游戏引擎学习第231天
  • 02、GPIO外设(一)：基础知识
  • Windows平台使用Docker部署Neo4j
  • 从零上手GUI Guider学习LVGL——Button
  • 【Windows本地部署n8n工作流自动平台结合内网穿透远程在线访问】
  • SAP HANA使用命令行快速导出导入
  • 【HFP】深入解析蓝牙 HFP 协议中呼叫转移、呼叫建立及保持呼叫状态的机制
  • 在 Kali Linux 上安装 Java OpenJDK 8（详细指南）
  • 在Pycharm配置stable diffusion环境（使用conda虚拟环境）
  • Mac idea WordExcel等文件git modify 一直提示修改状态
  • 深度剖析：GPT-3.5与GPT-4的主要区别及架构解析
  • 消除异步的传染性(代数效应)
  • Java八种常见的设计模式
  • 【python画图】：从入门到精通绘制完美柱状图
  • 2025华中杯B题——AI实现
  • C++23 新特性：std::size_t 字面量后缀 Z/z
  • 台式机 thingsboard 部署 MQTT服务器端口查询及公开本地站点到公网，MQTT客户端配置
  • 循环队列的实现