C++之list类及模拟实现

server/2025/3/18 13:10:30/

目录

list的介绍 

list的模拟实现

定义节点

有关遍历的重载运算符

list的操作实现 

（1）构造函数

 (2)拷贝构造函数

（3）赋值运算符重载函数=

（4）析构函数和clear成员函数

（5）尾插/头插和尾删/头删

（6)size成员函数

（7）在任意位置插入 (insert)

（8）任意位置删除（erase）

（9）迭代器 

完整代码展示

vector和list的比较

1.排序

(1)list和vector排序

（2）list copy vector sort copy list sort和list

2.总结

 

list的介绍 

 （1）list类其实就是链表，但是它是双向链表。在数据结构中我们了解过双向链表的特点。下面我们回忆一下。

1.节点中具有两个指针。一个指针指向该节点的前一个节点，另一个指针指向该节点的下一个节点。

2.存在哨兵位。初始化的时候节点里的下一个节点和上一个节点都指向自己。

 （2）STL中list的底层结构

 list的模拟实现

定义节点

我们先定义双向链表的节点并初始化。

template <class T>struct list_node{list_node* _next;list_node* _prev;T _data;list_node(const T& x = T()):_next(nullptr), _prev(nullptr), _data(x){}};

有关遍历的重载运算符

list容器有迭代器，那么就可以进行遍历，因此我们要可以++，--等运算符重载。而且在插入删除操作中我们常常需要 ‘.’    '->'对链表进行遍历。因为普通迭代器和const迭代器中只有operator*和operator->的返回值有区别，所以我们就在模板上多增加了两个模板参数。

代码如下： 

template<class T,class Ref,class Ptr>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;Node* _node;list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}//C++规定后缀调用需要有一个int型参数作为区分前缀与后缀调用的区别Self& operator++()//前置++，先++再取值{_node=_node->_next;return *this;} Self operator++(int)//后置++，先取值再++{Self tmp(*this);//取值_node = _node->_next;return tmp;//返回被取的值}Self operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator==(const Self& lt){return _node == lt._node;//结构体变量用「.」来访问成员，而结构体指针用「->」来访问。}bool operator!=(const Self& lt){return _node != lt._node;}};

list的操作实现 

（1）构造函数

创建节点并把节点中的指针全部指向自己。

list()
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}

 (2)拷贝构造函数

先构造a1,再把lt中的资源尾插给a1。

      void empty_Init(){_head = new node;_head->_next = _head;_head->_prev = _head;}   //a1(a2)，a1是新建的list(const list<T>& lt){empty_Init();for (auto& e : lt){push_back(e);}}//initializer_list<T>list(std::initializer_list<T> lt){empty_Init();for (auto& e : lt){push_back(e);}}

两种拷贝构造的区别： 

（3）赋值运算符重载函数=

        void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}//lt1=ltlist<T>& operator=(list<T>& lt){swap(lt);return *this;}

 看到这个代码我们就会想为什么运算符重载中的形参不加const呢？如果加了const就像 void swap(*this,const list<T>& y)一样，这样是会报错的，两边类型不同，swap函数是一个函数模板，只有一个模板参数，那么有人会说把这个改成类型相同的不就行了。但是我们知道const list<T>& lt中const修饰list<T> 类型，则lt 引用的对象（即 list<T>）是常量对象，不能通过 lt 修改它的内容。它的值在初始化后就不能改变，而在swap函数中需要交换它们的资源，那么lt就需要改变。

（4）析构函数和clear成员函数

clear的作用只是清理链表的节点，只剩下哨兵位，并不会释放空间。

       ~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}

（5）尾插/头插和尾删/头删

        void push_back(const T&x){insert(end(), x);}void push_front(const T&x){insert(begin(), x);}void pop_back(){erase(--end());//end()是哨兵位}void pop_front(){erase(begin());}

（6)size成员函数

        size_t size()const{return _size;}

（7）在任意位置插入 (insert)

         typedef list_iterator<T,T&,T*> iterator;   void insert(iterator pos, const T& x){node* newnode = new node(x);node*pre = pos._node;node* prev = pre->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = pre;pre->_prev = newnode;_size++;}

注意：pos的类型是list_iterator<T,T&,T*>,这个类中的成员变量只有_node,而_node的类型才是list_node,类型为list_node才有节点的成员变量。所以我们要node*pre = pos._node，而不能直接使用pos。

（8）任意位置删除（erase）

list中的erase也会有迭代器失效，所以我们需要返回下一个迭代器。

         typedef list_iterator<T,T&,T*> iterator; iterator erase(iterator pos){assert(pos != end());node* pre = pos._node;node* prev = pre->_prev;node* next = pre->_next;delete pre;prev->_next = next;next->_prev = prev;_size--;return iterator(next);}

（9）迭代器 

        iterator begin(){iterator it(_head->_next);//调用了list_iterator类模板的构造函数return it;}iterator end(){iterator it(_head);return it;}const_iterator begin()const{const_iterator it(_head->_next);return it;}const_iterator end()const{const_iterator it(_head);return it;}

完整代码展示

#include<assert.h>
namespace slm
{//创建节点template <class T>struct list_node{list_node* _next;list_node* _prev;T _data;list_node(const T& x = T()):_next(nullptr), _prev(nullptr), _data(x){}};//实现运算符重载template<class T,class Ref,class Ptr>//template<class T,class T&,class T*>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;Node* _node;list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}//C++规定后缀调用需要有一个int型参数作为区分前缀与后缀调用的区别Self& operator++()//前置++，先++再取值{_node=_node->_next;return *this;} Self operator++(int)//后置++，先取值再++{Self tmp(*this);//取值_node = _node->_next;return tmp;//返回被取的值}Self operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator==(const Self& lt){return _node == lt._node;//结构体变量用「.」来访问成员，而结构体指针用「->」来访问。}bool operator!=(const Self& lt){return _node != lt._node;}};template<class T>class list{typedef list_node<T> node;typedef list_iterator<T,T&,T*> iterator;typedef list_iterator<T,const T&,const T*> const_iterator;public:iterator begin(){iterator it(_head->_next);return it;}iterator end(){iterator it(_head);return it;}const_iterator begin()const{const_iterator it(_head->_next);return it;}const_iterator end()const{const_iterator it(_head);return it;}void empty_Init(){_head = new node;_head->_next = _head;_head->_prev = _head;}list(){empty_Init();}//a1(a2)list(const list<T>& lt){empty_Init();for (auto& e : lt){push_back(e);}}list(std::initializer_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=ltlist<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);}}size_t size()const{return _size;}void push_back(const T&x){insert(end(), x);}//在pos前插入void insert(iterator pos, const T& x){node* newnode = new node(x);node*pre = pos._node;node* prev = pre->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = pre;pre->_prev = newnode;_size++;}iterator erase(iterator pos){assert(pos != end());node* pre = pos._node;node* prev = pre->_prev;node* next = pre->_next;delete pre;prev->_next = next;next->_prev = prev;_size--;return iterator(next);}void push_front(const T&x){insert(begin(), x);}void pop_back(){erase(--end());//end()是哨兵位}void pop_front(){erase(begin());}private:node* _head;size_t _size;};
}

vector和list的比较

1.排序

(1)list和vector排序

#include<iostream>
#include<list>
#include<vector>
#include<algorithm>
using namespace std;
void test_op1()
{srand(time(0));const int N = 1000000;list<int> lt1;vector<int> v;for (int i = 0; i < N; ++i){auto e = rand() + i;lt1.push_back(e);v.push_back(e);}int begin1 = clock();// vector排序sort(v.begin(), v.end());int end1 = clock();//list排序int begin2 = clock();lt1.sort();int end2 = clock();printf("vector sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}
int main()
{
test_op1();
return 0;
}

从结果中我们发现list排序比vector排序快了两倍多。

（2）list copy vector sort copy list sort和list

那如果我们先把list类资源拷贝构造给vector排序，排完序后又拷贝回list类，那结果会是如何呢？

#include<iostream>
#include<list>
#include<vector>
#include<algorithm>
using namespace std;
void test_op2()
{srand(time(0));const int N = 10000;list<int> lt1;list<int> lt2;for (int i = 0; i < N; ++i){auto e = rand() + i;lt1.push_back(e);lt2.push_back(e);}int begin1 = clock();// 拷贝vectorvector<int> v(lt2.begin(), lt2.end());// 排序sort(v.begin(), v.end());// 拷贝回lt2lt2.assign(v.begin(), v.end());int end1 = clock();int begin2 = clock();lt1.sort();int end2 = clock();printf("list copy vector sort copy list sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}int main()
{test_op2();return 0;
}

我们发现上面list先拷贝构造成vector类在排序，排完序后再拷贝回list的效率还是比直接list排序慢。

2.总结

 vectorlist
底
层
结
构		动态顺序表，一段连续空间带头结点的双向循环链表
随
机
访
问		支持随机访问，访问某个元素效率O(1)不支持随机访问，访问某个元
素效率O(N)
插
入
和
删
除		任意位置插入和删除效率低，需要搬移元素，时间
复杂度为O(N)，插入时有可能需要增容，增容：
开辟新空间，拷贝元素，释放旧空间，导致效率更
低
任意位置插入和删除效率高，
不需要搬移元素，时间复杂度
为O(1)
空
间
利
用
率
 		底层为连续空间，不容易造成内存碎片，空间利用
率高，缓存利用率高		底层节点动态开辟，小节点容
易造成内存碎片，空间利用率
低，缓存利用率低
迭
代
器

 		原生态指针对原生态指针(节点指针)进行
封装
迭
代
器
失
效

在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效.

删除时，当前迭代器需要重新赋值否则会失效

插入元素不会导致迭代器失
效，删除元素时，只会导致当
前迭代器失效，其他迭代器不
受影响
使
用
场
景		需要高效存储，支持随机访问，不关心插入删除效率大量插入和删除操作，不关心
随机访问

 

 

 

 


http://www.ppmy.cn/server/175965.html

相关文章

C# ManualResetEvent‌的高级用法

C# ManualResetEvent‌的高级用法

一、ManualResetEvent 的核心作用‌ ManualResetEvent 是 C# 中用于 ‌线程同步‌ 的类&#xff08;位于 System.Threading 命名空间&#xff09;&#xff0c;通过信号机制控制线程的等待与执行。其核心功能包括&#xff1a; 阻塞线程‌&#xff1a;调用 WaitOne() 的线程会等…
阅读更多...
【实测闭坑】LazyGraphRAG利用本地ollama提供Embedding model服务和火山引擎的deepseek API构建本地知识库

【实测闭坑】LazyGraphRAG利用本地ollama提供Embedding model服务和火山引擎的deepseek API构建本地知识库

LazyGraphRAG 2024年4月&#xff0c;为解决传统RAG在全局性的查询总结任务上表现不佳&#xff0c;微软多部门联合提出Project GraphRAG&#xff08;大模型驱动的KG&#xff09;&#xff1b;2024年7月&#xff0c;微软正式开源GraphRAG项目&#xff0c;引起极大关注&#xff0c…
阅读更多...
【前端面试题】宏任务与微任务的区别

【前端面试题】宏任务与微任务的区别

宏任务与微任务的区别 JavaScript采用单线程模型&#xff0c;通过 事件循环&#xff08;Event Loop&#xff09; 机制处理异步操作。 类比于厨师上菜的过程&#xff0c;顾客点的菜可能存在容易处理的 “软菜” 与难处理的 “硬菜” &#xff0c;以及要加米饭酒水这些立马可以上…
阅读更多...
Java常用设计模式

Java常用设计模式

设计模式是软件开发中解决常见问题的模板或指南。Java中的23种设计模式通常被分为三大类&#xff1a;创建型模式&#xff08;Creational Patterns&#xff09;、结构型模式&#xff08;Structural Patterns&#xff09;和行为型模式&#xff08;Behavioral Patterns&#xff09…
阅读更多...
python脚本实现服务器内存和cpu使用监控，并记录日志，可以设置阈值和采样频率

python脚本实现服务器内存和cpu使用监控，并记录日志，可以设置阈值和采样频率

Python 脚本&#xff0c;实现以下功能&#xff1a; 按日期自动生成日志文件&#xff08;例如 cpu_mem_20231001.csv&#xff09;当 CPU 或内存超过阈值时触发记录独立记录报警事件&#xff08;保存到 alert.log&#xff09;支持自定义阈值和监控间隔 脚本代码 import psutil …
阅读更多...
HCIA-PPP

HCIA-PPP

一、基本概念 1、定义&#xff1a;PPP 协议是一种数据链路层协议&#xff0c;在两点之间建立直接通信连接。常用于拨号上网、宽带接入、路由器间通信等。 2、核心功能&#xff1a; ①链路控制&#xff1a;建立、配置和测试数据链路连接。 ②网络层协议支持&#xff1a;支持…
阅读更多...
【密码学——基础理论与应用】李子臣编著 第四章 SM4分组密码算法 课后习题

【密码学——基础理论与应用】李子臣编著 第四章 SM4分组密码算法 课后习题

免责声明 这里都是自己搓或者手写的。 里面不少题目感觉有问题或者我的理解有偏颇&#xff0c;请大佬批评指正&#xff01; 不带思考抄作业的请自动退出&#xff0c;我的并非全对&#xff0c;仅仅提供思维&#xff01; SM4的python实现 基于AI生成的SM4加密算法-CSDN博客 题…
阅读更多...
【云原生技术】容器技术的发展史

【云原生技术】容器技术的发展史

一、Jail 时代 容器不是一个新概念或者新技术&#xff0c;很早就有了&#xff0c;只是近几年遇到了云计算&#xff0c;整个技术 被彻底引爆了。 1.1 1979年 贝尔实验室发明 chroot chroot系统调用是在 1979 年开发第 7 版 Unix 期间引入的。贝尔实验室在 Unix V7 的 开发过程…
阅读更多...
最新文章

Copyright @ 2022~2023