C++ 简单模拟实现 STL 中的 list 与 queue

目录

一，list

1， list 的节点与迭代器

2，list 的数据结构、一些简单的功能、构造函数

3，list 的对元素操作

4，C++ 11 的一些功能

5，完整代码：

二，queue

一，list

std::list 是 C++ 标准模板库 (STL) 中提供的一个容器模板，它被实现为环状双向链表。list 和 vector 是两个最常被使用的容器。相较于 vector 的连续线性空间，list 的非连续存储就显得复杂许多，它的好处是每次插人或删除一个元素，就配置或释放一个元素空间。因此，list 对空间的使用一点也不浪费。而且，对于任何位置的插入或移除元素，list 永远是常数时间。

关于 list 的各种接口的用法这里就不介绍了，此文主要是模拟实现。
 

1， list 的节点与迭代器

list 本身和 list 的节点是不同的结构，是需要分开设计的。list 中会包含 list 节点结构。节点结构：

template<class T>
struct list_node {list_node<T>* next, * pre;	// next 指向下一个节点，pre 指向前一个节点T data;list_node(const T& data_ = T()):next(nullptr),pre(nullptr),data(data_){}
};

如果不清楚迭代器是什么或者是不清楚要怎么设计一个容器专属的迭代器可以看看这个：C++ 迭代器与反向迭代器-CSDN博客

如果对 vector 的实现细节感兴趣可以看看这个：C++ 简单模拟实现 STL 中的 vector 与 stack-CSDN博客

list 不再能够像 vector 一样以普通指针作为迭代器，因为其节点不保证在储存空间中连续存在。所以 list 迭代器必须有能力指向 list 的节点，并且能够进行正确的递增（++）、递减（--）、取值（*）、成员存取（->）等操作。这里要注意，取值时取的是节点的数据值，不是节点本身，成员取用时取用的是节点的成员。例如：

mySTL::list<int> lt = { 1,2,3,4,5 };
for (auto it = lt.begin();it != lt.end();++it) {cout << *it << " ";    // 输出的是 1 2 3 4 5;
}
mySTL::list<pair<int, int>> lt2 = { {1,2},{3,4},{5,6} };
for (auto it = lt2.begin();it != lt2.end();++it) {cout << it->first << "," << it->second << " # ";	// 输出的是 1,2 # 3,4 # 5,6 #
}

list 迭代器的设计：

template<class T,class Ref,class Ptr>
struct list_iterator {typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> self;typedef list_iterator<T, T&, T*> iterator;// 迭代器内部的一个普通指针类型，指向对应的 list 节点Node* _node;// 迭代器相应类型的定义typedef T	value_type;typedef Ref reference;typedef Ptr pointer;// 迭代器的构造list_iterator(Node* node):_node(node){}					// 用节点构造当前迭代器list_iterator(const iterator& iter):_node(iter._node){}	// 用普通迭代器构造当前迭代器// 注意, 对迭代器解引用, 取出来的是节点里面的数据值reference operator*()const { return _node->data; }// &(operator*()), 这是一个标准的做法pointer operator->()const { return &(operator*()); }self& operator++() { _node = _node->next; return *this;}self operator++(int){Node* tmp = _node;_node = _node->next;return tmp;}self& operator--() { _node = _node->pre; return *this;}self operator--(int) {Node* tmp = _node;_node = _node->pre;return tmp;}bool operator==(const self& iter)const { return _node == iter._node; }bool operator!=(const self& iter)const { return not operator==(iter); }};

2，list 的数据结构、一些简单的功能、构造函数

list 是一个带有头节点的环状双向链表，它只需要一个指针就可以完整的表示整个链表，为了方便操作，我们也可以来额外来维护一个 size 变量来表示节点的个数（不包括头节点）。

template<class T>
class list {// ...
private:typedef list_node<T> Node;typedef list<T> self;private:Node* _head = nullptr;  //头节点size_t _size = 0;void initialize() {		//初始化头节点_head = new Node;_head->pre = _head->next = _head;}// ...
};

list 中有关迭代器的操作与一些简单的基础功能：

template<class T>
class list {// ...
public://迭代器/*正向迭代器*/typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;iterator begin() { return _head->next; }iterator end() { return _head; }const_iterator begin()const { return _head->next; }const_iterator end()const { return _head; }/*反向迭代器*/typedef Reverse_Iterator<iterator> reverse_iterator;typedef Reverse_Iterator<const_iterator> const_reverse_iterator;reverse_iterator rbegin() { return end(); }reverse_iterator rend() { return begin(); }const_reverse_iterator rbegin()const { return end(); }const_reverse_iterator rend()const { return begin(); }public:// 简单的基础功能size_t size() { return _size; }bool empty() { return _size == 0; }void clear() {while (not empty()) pop_back();}void swap(list& lt) {std::swap(_head, lt._head);std::swap(_size, lt._size);}// 对首尾元素的访问T& back() { return *(--end()); }const T& back()const { return *(--end()); }T& front() { return *begin(); }const T& front()const { return *begin(); }// ...
};

list 的构造函数：

template<class T>
class list {// ...
public://构造list() { initialize(); }list(size_t n, const T& data = T()) {initialize();while (n--) { push_back(data); }}list(int n, const T& data = T()) {initialize();while (n--) { push_back(data); }}/*使用迭代器构造*/template<class input_iterator>						list(input_iterator begin, input_iterator end) {initialize();while (begin != end) {push_back(*(begin++));}}//拷贝list(const list& lt) {initialize();for (const auto& data : lt) {push_back(data);}}self& operator=(list lt) {swap(lt);return *this;}//析构~list() {clear();delete _head;_head = nullptr;_size = 0;}// ...
};

3，list 的对元素操作

std::list 里面提供的元素操作有很多，这里就只挑几种重要的函数来实现。我们把 insert 与 erase 操作实现之后就可以很轻松的实现 push_back()、push_front()（尾插，头插） 与 pop_back() 、pop_front() （尾删，头删）操作了。

template<class T>
class list {// ...
public://增void push_front(const T& data) { insert(begin(), data); }	// 头插新节点void push_back(const T& data) { insert(end(), data); }		// 尾插新节点// 在 pos 位置的前面插入一个值为 data 的新节点, 返回新插入的节点的迭代器iterator insert(iterator pos, const T& data) {Node* node = pos._node;Node* newNode = new Node(data);newNode->next = node;newNode->pre = node->pre;node->pre->next = newNode;node->pre = newNode;++_size;return newNode;}//删void pop_front() { erase(begin()); }	// 头删void pop_back() { erase(--end()); }		// 尾删// 删掉迭代器 pos 所指向的节点, 返回删掉的节点的位置的新节点迭代器iterator erase(iterator pos) {assert(pos != end());Node* tmp = pos._node;tmp->pre->next = tmp->next;tmp->next->pre = tmp->pre;Node* res = tmp->next;delete tmp;--_size;return res;}// ...
};

4，C++ 11 的一些功能

这里主要实现的功能是 initializer_list 初始化 与 右值引用，如果对这两个东西不了解的话可以看看这两篇博客：

C++11 一些常用的功能-CSDN博客

C++ 左值引用与右值引用-CSDN博客

template<class T>
class list {// ...
public://C++ 11 //initializer_list构造list(const std::initializer_list<T>& lt) {initialize();for (const T& data : lt) {push_back(data);}}//右值引用相关//移动构造与移动赋值list(list&& lt) :_head(lt._head), _size(lt._size) {initialize();lt._head = nullptr;lt._size = 0;}self& operator=(list&& lt) {delete* this;std::swap(_head, lt._head);std::swap(_size, lt._size);}//插入void push_front(T&& data) { insert(begin(), std::forward<T>(data)); }void push_back(T&& data) { insert(end(), std::forward<T>(data)); }iterator insert(iterator pos, T&& data) {Node* node = pos._node;Node* newNode = new Node(std::forward<T>(data));newNode->next = node;newNode->pre = node->pre;node->pre->next = newNode;node->pre = newNode;++_size;return newNode;}// ...
};

5，完整代码：

namespace mySTL {// list 节点类template<class T>struct list_node {list_node<T>* next, * pre;	// next 指向下一个节点，pre指向前一个节点T data;list_node(const T& data_ = T()):next(nullptr),pre(nullptr),data(data_){}};// list 迭代器类template<class T,class Ref,class Ptr>struct list_iterator {typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> self;typedef list_iterator<T, T&, T*> iterator;// 迭代器内部的一个普通指针类型，指向对应的 list 节点Node* _node;// 迭代器相应类型的定义typedef T	value_type;typedef Ref reference;typedef Ptr pointer;// 迭代器的构造list_iterator(Node* node):_node(node){}					// 用节点构造当前迭代器list_iterator(const iterator& iter):_node(iter._node){}	// 用普通迭代器构造当前迭代器// 注意, 对迭代器解引用, 取出来的是节点里面的数据值reference operator*()const { return _node->data; }// &(operator*()), 这是一个标准的做法pointer operator->()const { return &(operator*()); }self& operator++() { _node = _node->next; return *this;}self operator++(int){Node* tmp = _node;_node = _node->next;return tmp;}self& operator--() { _node = _node->pre; return *this;}self operator--(int) {Node* tmp = _node;_node = _node->pre;return tmp;}bool operator==(const self& iter)const { return _node == iter._node; }bool operator!=(const self& iter)const { return not operator==(iter); }};// list 类template<class T>class list {private:typedef list_node<T> Node;typedef list<T> self;private:Node* _head = nullptr;  //头节点size_t _size = 0;void initialize() {		//初始化头节点_head = new Node;_head->pre = _head->next = _head;}public://迭代器/*正向迭代器*/typedef list_iterator<T, T&, T*> iterator;					typedef list_iterator<T, const T&, const T*> const_iterator;iterator begin() { return _head->next; }iterator end() { return _head; }const_iterator begin()const { return _head->next; }const_iterator end()const { return _head; }/*反向迭代器*/typedef Reverse_Iterator<iterator> reverse_iterator;		typedef Reverse_Iterator<const_iterator> const_reverse_iterator;reverse_iterator rbegin() { return end(); }reverse_iterator rend() { return begin(); }const_reverse_iterator rbegin()const { return end(); }const_reverse_iterator rend()const { return begin(); }public:// 简单的基础功能size_t size() { return _size; }bool empty() { return _size == 0; }void clear() { while (not empty()) pop_back();}void swap(list& lt) {std::swap(_head, lt._head);std::swap(_size, lt._size);}// 对首尾元素的访问T& back() { return *(--end()); }const T& back()const { return *(--end()); }T& front() { return *begin(); }const T& front()const { return *begin(); }// 在迭代器 start 与 finish 构成的范围内查找值为 target 的节点iterator find(const iterator& start, const iterator& finish, const T& target) {for (iterator it = start;it != finish;++it) {if (*it == target) return it;}return finish;}public://构造list() { initialize(); }list(size_t n, const T& data = T()) {initialize();while (n--) { push_back(data); }}list(int n, const T& data = T()) {initialize();while (n--) { push_back(data); }}template<class input_iterator>						/*使用迭代器构造*/list(input_iterator begin, input_iterator end) {initialize();while (begin != end) {push_back(*(begin++));}}//拷贝list(const list& lt) {initialize();for (const auto& data : lt) {push_back(data);}}self& operator=(list lt) {swap(lt);return *this;}//析构~list() {clear();delete _head;_head = nullptr;_size = 0;}public://增void push_front(const T& data) { insert(begin(), data); }	// 头插新节点void push_back(const T& data) { insert(end(), data); }		// 尾插新节点// 在 pos 位置的前面插入一个值为 data 的新节点, 返回新插入的节点的迭代器iterator insert(iterator pos,const T& data) {Node* node = pos._node;Node* newNode = new Node(data);newNode->next = node;newNode->pre = node->pre;node->pre->next = newNode;node->pre = newNode;++_size;return newNode;}//删void pop_front() { erase(begin()); }	// 头删void pop_back() { erase(--end()); }		// 尾删// 删掉迭代器 pos 所指向的节点, 返回删掉的节点的位置的新节点迭代器iterator erase(iterator pos) {assert(pos != end());Node* tmp = pos._node;tmp->pre->next = tmp->next;tmp->next->pre = tmp->pre;Node* res = tmp->next;delete tmp;--_size;return res;}public://C++ 11 //initializer_list构造list(const std::initializer_list<T>& lt) {initialize();for (const T& data : lt) {push_back(data);}}//右值引用相关//移动构造与移动赋值list(list&& lt) :_head(lt._head), _size(lt._size) {initialize();lt._head = nullptr;lt._size = 0;}self& operator=(list&& lt) {delete *this;std::swap(_head, lt._head);std::swap(_size, lt._size);}//插入void push_front(T&& data) { insert(begin(), std::forward<T>(data)); }void push_back(T&& data) { insert(end(), std::forward<T>(data)); }iterator insert(iterator pos, T&& data) {Node* node = pos._node;Node* newNode = new Node(std::forward<T>(data));newNode->next = node;newNode->pre = node->pre;node->pre->next = newNode;node->pre = newNode;++_size;return newNode;}};}

二，queue

queue 是一种先进先出（First In First Out，FIFO）的数据结构，它有两个出口。queue 允许新增元素、移除元素、从最底端加人元素取得最顶端元素。但除了最底端可以加入、最顶端可以取出外，没有任何其它方法可以存取 queue 的其它元素。也就是说，queue 不允许有遍历行为。将元素推人queue 的操作称为 push，将元素推出 queue 的操作称为 pop。

queue 与 stack 一样，都是容器适配器（container adapters），他们的底层都是其他的容器，STL 中的 stack 与 queue 实际上都是对其他容器的封装，其都不支持迭代器。

我们可以选择用 list 也可以选择用 deque 来当作 queue 的底层容器。

namespace mySTL {template<class T, class Container = list<T>>class queue {private:Container _cont;	// 底层使用的容器public:void push(const T& data) { _cont.push_back(data); }void push(T&& data) { _cont.push_back(std::forward<T>(data)); }void pop() { _cont.pop_front(); }T& back() { return _cont.back(); }const T& back()const { return _cont.back(); }T& front() { return _cont.front(); }const T& front()const { return _cont.front(); }size_t size() { return _cont.size(); }bool empty() { return _cont.empty(); }};}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/286349.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

目前国内体验最佳的AI问答助手：kimi.ai

目前国内体验最佳的AI问答助手：kimi.ai

文章目录 简介图片理解长文档解析 简介 kimi.ai是国内初创AI公司月之暗面推出的一款AI助手&#xff0c;终于不再是四字成语拼凑出来的了。这是一个非常存粹的文本分析和对话工具&#xff0c;没有那些东拼西凑花里胡哨的AIGC功能&#xff0c;实测表明&#xff0c;这种聚焦是对的…
阅读更多...
『Apisix入门篇』从零到一掌握Apache APISIX：架构解析与实战指南

『Apisix入门篇』从零到一掌握Apache APISIX：架构解析与实战指南

&#x1f4e3;读完这篇文章里你能收获到&#xff1a; &#x1f310; 深入Apache APISIX架构&#xff1a; 从Nginx到OpenResty&#xff0c;再到etcd&#xff0c;一站式掌握云原生API网关的构建精髓&#xff0c;领略其层次化设计的魅力。 &#x1f50c; 核心组件全解析&#xff…
阅读更多...
Ubuntu deb文件 安装 MySQL

Ubuntu deb文件 安装 MySQL

更新系统软件依赖 sudo apt update && sudo apt upgrade下载安装包 输入命令查看Ubuntu系统版本 lsb_release -a2. 网站下载对应版本的安装包 下载地址. 解压安装 mkdir /home/mysqlcd /home/mysqltar -xvf mysql-server_8.0.36-1ubuntu20.04_amd64.deb-bundle.tar# …
阅读更多...
判断a是否大于b operator.gt(a, b) 判断a是否大于等于b operator.ge(a, b)

判断a是否大于b operator.gt(a, b) 判断a是否大于等于b operator.ge(a, b)

【小白从小学Python、C、Java】 【计算机等考500强证书考研】 【Python-数据分析】 判断a是否大于b operator.gt(a, b) 判断a是否大于等于b operator.ge(a, b) [太阳]选择题 请问执行以下程序的结果是&#xff1a; import operator print("【执行】2>2") print(2…
阅读更多...
hbase启动错误-local host is“master:XXXX“ destination is:master

hbase启动错误-local host is“master:XXXX“ destination is:master

博主的安装前提&#xff1a; zookeeper安装完成&#xff0c;且启动成功 hdfs高可用安装&#xff0c;yarn高可用安装&#xff0c;且启动成功 报错原因&#xff1a;端口配置不对 解决方案&#xff1a; 输入&#xff1a;hdfs getconf -confKey fs.default.name 然后把相应的…
阅读更多...
影视文件数字指纹签名检验系统的用户操作安全大多数

影视文件数字指纹签名检验系统的用户操作安全大多数

国内网盘服务大规模出现版权问题。 一些个人或团体会通过云存储客户端将主要由电影、电视、音乐组成的文件上传到网盘&#xff0c;然后在圈子里分享。 可供下载。 大量受版权保护的视频音乐就是通过这种特殊的盗版方式传播的&#xff0c;而这种传播方式暂时不受监管。 一些云存…
阅读更多...
开发者的瑞士军刀：DevToys

开发者的瑞士军刀：DevToys

DevToys&#xff1a; 一站式开发者工具箱&#xff0c;打造高效创意编程体验&#xff0c;让代码生活更加得心应手&#xff01;—— 精选真开源&#xff0c;释放新价值。 概览 不知道大家是否在windows系统中使用过PowerToys&#xff1f;这是微软研发的一项免费实用的系统工具套…
阅读更多...
iMazing2024功能强大的iPhone和iPad管理工具

iMazing2024功能强大的iPhone和iPad管理工具

iMazing是一款功能强大的iPhone和iPad管理工具&#xff0c;确实可以作为iTunes的替代品进行数据备份。以下是一些关于iMazing的主要特点和功能&#xff1a; 设备备份&#xff1a;iMazing可以备份iOS设备上的所有数据&#xff0c;包括照片、视频、音乐、应用程序等。与iTunes相比…
阅读更多...
【元胞自动机】MATLAB界面聚合的元胞自动机模拟完整实现运行

【元胞自动机】MATLAB界面聚合的元胞自动机模拟完整实现运行

文末有完整代码分享链接 文件介绍 automain 为元胞自动机主函数 choosedirection 选择方向函数&#xff0c;主函数调用 judgedirection 判断位置函数&#xff0c;主函数调用 neighbor 求每个元胞的邻居函数&#xff0c;主函数调用 surfaceness 求表面粗糙度 porosity 求孔隙率…
阅读更多...
机器学习作业二之KNN算法

机器学习作业二之KNN算法

KNN&#xff08;K- Nearest Neighbor&#xff09;法即K最邻近法&#xff0c;最初由 Cover和Hart于1968年提出&#xff0c;是一个理论上比较成熟的方法&#xff0c;也是最简单的机器学习算法之一。该方法的思路非常简单直观&#xff1a;如果一个样本在特征空间中的K个最相似&…
阅读更多...
Arduino IDE工程代码多文件编程和中文设置

Arduino IDE工程代码多文件编程和中文设置

一、esp8266模块信息 二、中英文切换 点击文件( File )–选择首选项( Preference )—选择语言( Language )—选择中文–点击确定( OK ) 三、多文件编程 在Arduino编程中&#xff0c;将代码分割成多个文件是一种很好的做法&#xff0c;特别是项目变得越来越大和复杂时。这样…
阅读更多...
【微服务】Eureka（服务注册，服务发现）

【微服务】Eureka（服务注册，服务发现）

文章目录 1.基本介绍1.学前说明2.当前架构分析1.示意图2.问题分析 3.引出Eureka1.项目架构分析2.上图解读 2.创建单机版的Eureka1.创建 e-commerce-eureka-server-9001 子模块2.检查父子pom.xml1.子 pom.xml2.父 pom.xml 3.pom.xml 引入依赖4.application.yml 配置eureka服务5.…
阅读更多...
【牛客】SQL142 对试卷得分做min-max归一化

【牛客】SQL142 对试卷得分做min-max归一化

描述 现有试卷信息表examination_info&#xff08;exam_id试卷ID, tag试卷类别, difficulty试卷难度, duration考试时长, release_time发布时间&#xff09;&#xff1a; idexam_idtagdifficultydurationrelease_time19001SQLhard602020-01-01 10:00:0029002Chard802020-01-0…
阅读更多...
huawei 华为 交换机 配置 LACP 模式的链路聚合示例 （交换机之间直连）

huawei 华为 交换机 配置 LACP 模式的链路聚合示例 （交换机之间直连）

组网需求 如 图 3-22 所示&#xff0c; SwitchA 和 SwitchB 通过以太链路分别都连接 VLAN10 和 VLAN20 的网络&#xff0c;且SwitchA 和 SwitchB 之间有较大的数据流量。用户希望 SwitchA 和 SwitchB 之间能够提供较大的链路带宽来使相同VLAN 间互相通信。在两台 Switch 设备上…
阅读更多...
【SpringBoot】实现一个简单的图片上传

【SpringBoot】实现一个简单的图片上传

前端上传表单 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Title</title> </head> <body> <form enctype"multipart/form-data" method"post" action&q…
阅读更多...
纯前端调用本机原生Office实现Web在线编辑Word/Excel/PPT，支持私有化部署

纯前端调用本机原生Office实现Web在线编辑Word/Excel/PPT，支持私有化部署

在日常协同办公过程中&#xff0c;一份文件可能需要多次重复修改才能确定&#xff0c;如果你发送给多个人修改后再汇总&#xff0c;这样既效率低又容易出错&#xff0c;这就用到网页版协同办公软件了&#xff0c;不仅方便文件流转还保证不会出错。 但是目前一些在线协同Office…
阅读更多...
【考研数学】张宇最新全年学习包

【考研数学】张宇最新全年学习包

考研数学冲高分必备&#xff0c;张宇老师肯定榜上有名&#xff01; 考研数学&#xff0c;其实就像一场没有硝烟的战斗。基础题是常规武器&#xff0c;中难题就是重型火炮&#xff0c;而压轴题呢&#xff0c;那就是核弹级别的存在&#xff01;考研的战场&#xff0c;关键就在那…
阅读更多...
Vulnhub：DR4G0N B4LL: 1

Vulnhub：DR4G0N B4LL: 1

目录 信息收集 1、arp 2、nmap WEB web信息收集 gobuster 隐藏目录发现 图片隐写 ssh登录 提权 get user 系统信息收集 get root 信息收集 1、arp ┌──(root㉿ru)-[~/kali/vulnhub] └─# arp-scan -l …
阅读更多...
iOS - Runtime-isa详解（位域、union（共用体）、位运算）

iOS - Runtime-isa详解（位域、union（共用体）、位运算）

文章目录 iOS - Runtime-isa详解&#xff08;位域、union&#xff08;共用体&#xff09;、位运算&#xff09;前言1. 位域介绍1.1 思路1.2 示例 - 结构体1.3 示例 - union&#xff08;共用体&#xff09;1.3.1 说明 1.4 结构体 对比 union&#xff08;共用体&#xff09; 2. a…
阅读更多...
Github多账号共存

Github多账号共存

在开发阶段&#xff0c;如果同时拥有多个开源代码托管平台的账户&#xff0c;在代码的管理上非常麻烦。那么&#xff0c;如果同一台机器上需要配置多个账户&#xff0c;怎样才能确保不冲突&#xff0c;不同账户独立下载独立提交呢&#xff1f; 我们以两个github账号进行演示 …
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023