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

【C++精华铺】12.STL list模拟实现

news 来源：原创 2024/9/20 2:48:16

1.序言

        STL (Standard Template Library)是C++标准库中的一个重要组件，提供了许多通用的数据结构和算法。其中，STL list是一种带头双向链表容器，可以存储任意类型的元素。

list的特点包括：

  1. 双向性：list中的元素可以根据需要在前向和后向方向上进行遍历和访问。

  2. 动态大小：list的大小可以根据需要动态增长和收缩，不像数组需要预先定义大小。

  3. 高效的插入和删除：在list中插入或删除元素的操作非常高效，时间复杂度为常数时间。

  4. 不支持随机访问：由于list的实现是基于链表的，所以不支持随机访问，只能通过遍历来访问指定位置的元素。

list提供了一系列的成员函数来操作元素，包括：

  1. push_back()和push_front()：分别在list的尾部和头部插入一个元素。

  2. pop_back()和pop_front()：分别删除list的尾部和头部的元素。

  3. insert()：在指定位置插入一个或多个元素。

  4. erase()：删除指定位置的一个或多个元素。

  5. size()：返回list中元素的个数。

  6. empty()：判断list是否为空。

        值得注意的是，由于list是双向链表，所以在内存上的开销相对较大，而且无法通过下标直接访问元素。因此，在选择容器时需要根据实际需求进行权衡。

2.list整体结构

template<class T>
struct list_node
{list_node<T>* _next;list_node<T>* _prev;T _Data;list_node(const T& x = T()):_next(nullptr), _prev(nullptr), _Data(x){}
};template<class T,class Ref,class Ptr>
struct __list_iterator
{typedef list_node<T> node;typedef __list_iterator<T, Ref, Ptr> iterator;     node* _node; //···········
};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;};

3.list迭代器

3.1 operator*()

        operator*() 返回的是list某节点存储的数据，并且返回时要能修改数据，所以返回类型是T&（Ref：是个模板参数，兼顾 T& 和 const T &，用哪个传那个 ）。

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

3.2 operator->()

        operator->() 用于取list存储的数据对象里面的属性，也是模拟指针的行为，返回数据对象的地址。

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

        需要注意的是如果我们使用这个 -> 的运算符重载，假设一迭代器对象 it ：it.operator->()->(某属性) 等价于 it->->(某属性) ，这里实际上有俩个 -> ,为了增加代码的可读性，这里进行了特殊处理，优化成了一个 -> ：it->(某属性) 。

3.3 operator++() 和 operator++(int)、operator--() 和 operator--(int)

        operator++()（operator--()）是前置++（--），返回++（--）后的值，operator++(int)（operator--()）是后置++（--），返回++前的值（--）。

iterator& operator++()
{_node = _node->_next;return *this;
}
iterator operator++(int)
{ iterator tmp(*this);_node = _node->_next;return tmp;
}
iterator& operator--()
{_node = _node->_prev;return *this;
}
iterator operator--(int)
{iterator tmp(*this);_node = _node->_prev;return tmp;
}

 3.4 operator==() 和 operator!=()

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

3.5 迭代器完整代码

template<class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _Data;
list_node(const T& x = T()):_next(nullptr), _prev(nullptr), _Data(x)
{}
};template<class T,class Ref,class Ptr>
struct __list_iterator
{
typedef list_node<T> node;
typedef __list_iterator<T, Ref, Ptr> iterator;
__list_iterator(node* n):_node(n)
{}
Ref operator*()
{return _node->_Data;
}
Ptr operator->()
{return &_node->_Data;
}iterator& operator++()
{_node = _node->_next;return *this;
}
iterator operator++(int)
{ iterator tmp(*this);_node = _node->_next;return tmp;
}
iterator& operator--()
{_node = _node->_prev;return *this;
}
iterator operator--(int)
{iterator tmp(*this);_node = _node->_prev;return tmp;
}bool operator==(const iterator& it)
{return _node == it._node;
}
bool operator!=(const iterator& it)
{return _node != it._node;
}
node* _node; 
};

4.list接口

4.1构造函数

list()
{_head = new node;_head->_next = _head->_prev = _head;
}~list()
{while (end() != _head){erase(end());}delete _head;_head = nullptr;
}
template<class Iterator>
list(Iterator first, Iterator last)
{_head = new node;_head->_next = _head->_prev = _head;while (first != last){push_back(*first);first++;}
}void swap(list<T>& tmp)
{std::swap(_head, tmp._head);
}list(const list<T>& l)
{_head = new node;_head->_next = _head->_prev = _head;list<T> tmp(l.begin(), l.end());swap(tmp);
}

4.2 push_back() push_front() pop_back() pop_front()

void push_back(const T& x)
{node* tail = _head->_prev;node* newnode = new node(x);newnode->_prev = tail;newnode->_next = tail->_next;tail->_next = newnode;_head->_prev = newnode;
}void push_front(const T& x)
{node* head = _head->_next;node* newnode = new node(x);newnode->_prev = _head;newnode->_next = head;_head->_next = newnode;head->_prev = newnode;}
void pop_back()
{node* tail = _head->_prev;_head->_prev = tail->_prev;tail->_prev->_next = _head;delete tail;
}
void pop_front()
{node* head = _head->_next;_head->_next = head->_next;head->_next->_prev = _head;delete head;
}

 4.3迭代器

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

 4.4 insert() 和 erase()

        注意erase的迭代器失效，需要更新pos

void insert(iterator pos, const T& x)
{node* cur = pos._node;node* newnode = new node(x);newnode->_next = cur;newnode->_prev = cur->_prev;cur->_prev->_next = newnode;cur->_prev = newnode;
}iterator erase(iterator pos)
{assert(pos != end());node* prev = pos._node->_prev;node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;return iterator(next);
}

5. list完整代码

#pragma once
#include<iostream>
#include<assert.h>
using namespace std; 
namespace zy
{template<class T>struct list_node{list_node<T>* _next;list_node<T>* _prev;T _Data;list_node(const T& x = T()):_next(nullptr), _prev(nullptr), _Data(x){}};template<class T,class Ref,class Ptr>struct __list_iterator{typedef list_node<T> node;typedef __list_iterator<T, Ref, Ptr> iterator;__list_iterator(node* n):_node(n){}Ref operator*(){return _node->_Data;}Ptr operator->(){return &_node->_Data;}iterator& operator++(){_node = _node->_next;return *this;}iterator operator++(int){ iterator tmp(*this);_node = _node->_next;return tmp;}iterator& operator--(){_node = _node->_prev;return *this;}iterator operator--(int){iterator tmp(*this);_node = _node->_prev;return tmp;}bool operator==(const iterator& it){return _node == it._node;}bool operator!=(const iterator& it){return _node != it._node;}node* _node; };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;list(){_head = new node;_head->_next = _head->_prev = _head;}~list(){while (end() != _head){erase(end());}delete _head;_head = nullptr;}template<class Iterator>list(Iterator first, Iterator last){_head = new node;_head->_next = _head->_prev = _head;while (first != last){push_back(*first);first++;}}void swap(list<T>& tmp){std::swap(_head, tmp._head);}list(const list<T>& l){_head = new node;_head->_next = _head->_prev = _head;list<T> tmp(l.begin(), l.end());swap(tmp);}list<T>& operator=(list<T> lt){swap(lt);return *this;}void push_back(const T& x){node* tail = _head->_prev;node* newnode = new node(x);newnode->_prev = tail;newnode->_next = tail->_next;tail->_next = newnode;_head->_prev = newnode;}void push_front(const T& x){node* head = _head->_next;node* newnode = new node(x);newnode->_prev = _head;newnode->_next = head;_head->_next = newnode;head->_prev = newnode;}void pop_back(){node* tail = _head->_prev;_head->_prev = tail->_prev;tail->_prev->_next = _head;delete tail;}void pop_front(){node* head = _head->_next;_head->_next = head->_next;head->_next->_prev = _head;delete head;}iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin() const{return iterator(_head->_next);}const_iterator end() const{return iterator(_head);}void insert(iterator pos, const T& x){node* cur = pos._node;node* newnode = new node(x);newnode->_next = cur;newnode->_prev = cur->_prev;cur->_prev->_next = newnode;cur->_prev = newnode;}iterator erase(iterator pos){assert(pos != end());node* prev = pos._node->_prev;node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;return iterator(next);}private:node* _head;};
}

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • 【低照度图像增强系列（8）】URetinex-Net算法详解与代码实现（2022|CVPR）
  • 手机和电脑通过TCP传输（一）
  • 第一节Linux常见指令
  • CV11_模型部署pytorch转ONNX
  • 前端练习小项目——方向感应名片
  • Open-TeleVision——通过VR沉浸式感受人形机器人视野：兼备远程控制和深度感知能力
  • Base64文件流查看下载PDF方法-CSDN
  • python-矩阵加法（赛氪OJ）
  • BERT架构的深入解析
  • c# 依赖注入-服务的生命周期
  • 如何恢复电脑上删除的文件？快速恢复被删除文件的技巧【5个实用方法】
  • css的三大特性
  • MATLAB quiver矢量图 设置colorbar
  • R语言学习笔记6-数据框
  • 2024黑马AI+若依框架项目开发 个人心得、踩坑和bug记录 全网最快最全 基础功能认识篇
  • 《Java编程思想》读书笔记-对象导论
  • 【407天】跃迁之路——程序员高效学习方法论探索系列（实验阶段164-2018.03.19）...
  • 【跃迁之路】【519天】程序员高效学习方法论探索系列（实验阶段276-2018.07.09）...
  • axios 和 cookie 的那些事
  • co.js - 让异步代码同步化
  • CSS魔法堂：Absolute Positioning就这个样
  • Spring Security中异常上抛机制及对于转型处理的一些感悟
  • Twitter赢在开放，三年创造奇迹
  • ubuntu 下nginx安装 并支持https协议
  • vue+element后台管理系统，从后端获取路由表，并正常渲染
  • 阿里研究院入选中国企业智库系统影响力榜
  • 爬虫进阶 -- 神级程序员：让你的爬虫就像人类的用户行为！
  • d²y/dx²； 偏导数问题 请问f1 f2是什么意思
  • ​直流电和交流电有什么区别为什么这个时候又要变成直流电呢？交流转换到直流（整流器）直流变交流（逆变器）​
  • #免费 苹果M系芯片Macbook电脑MacOS使用Bash脚本写入(读写)NTFS硬盘教程
  • #我与Java虚拟机的故事#连载12：一本书带我深入Java领域
  • $con= MySQL有关填空题_2015年计算机二级考试《MySQL》提高练习题(10)
  • （k8s）Kubernetes 从0到1容器编排之旅
  • （补充）IDEA项目结构
  • (读书笔记)Javascript高级程序设计---ECMAScript基础
  • （附源码）php投票系统 毕业设计 121500
  • （附源码）spring boot校园拼车微信小程序 毕业设计 091617
  • （附源码）SSM环卫人员管理平台 计算机毕设36412
  • （附源码）ssm基于微信小程序的疫苗管理系统 毕业设计 092354
  • （论文阅读30/100）Convolutional Pose Machines
  • (强烈推荐)移动端音视频从零到上手（下）
  • (原創) 如何讓IE7按第二次Ctrl + Tab時，回到原來的索引標籤? (Web) (IE) (OS) (Windows)...
  • (转)h264中avc和flv数据的解析
  • (转)真正的中国天气api接口xml，json（求加精） ...
  • (轉貼) 蒼井そら挑戰筋肉擂台 (Misc)
  • ..回顾17，展望18
  • .NET 5.0正式发布，有什么功能特性(翻译)
  • .NET COER+CONSUL微服务项目在CENTOS环境下的部署实践
  • .NET Micro Framework 4.2 beta 源码探析
  • .NET 的静态构造函数是否线程安全？答案是肯定的！
  • .NET 中小心嵌套等待的 Task，它可能会耗尽你线程池的现有资源，出现类似死锁的情况
  • .NetCore 如何动态路由
  • .NET委托：一个关于C#的睡前故事
  • @antv/g6 业务场景：流程图
  • @JSONField或@JsonProperty注解使用