C++语法（11）---- 模拟实现list

article/2023/10/1 3:37:08

1.基础元素

struct list_node
{list_node* _next;list_node* _prev;T _data;list_node(const T& x): _next(nullptr), _prev(nullptr), _data(x){}
};

list链表，基本要素就是链表的一个小块，这个小块自己带着的数据以及指向前后位置的指针组成。初始化时，赋值指定，指向就为nullptr即可

2.迭代器

1.普通和const迭代器实现

由于实现的迭代器分别是普通迭代器和const迭代器，分开写的话代码重复度过高，所以我们需要套用模板

template<class T,class Ref,class Ptr>
struct __list_iterator
{typedef list_node<T> node;typedef __list_iterator<T, Ref, Ptr> Self;node* _pnode;__list_iterator(node* p):_pnode(p){}Ref  operator*(){return _pnode->_data;}Ptr  operator->(){return &_pnode->_data;}Self& operator++(){_pnode = _pnode->_next;return *this;}Self operator++(int){Self tmp(*this);_pnode = _pnode->_next;return tmp;}Self& operator--(){_pnode = _pnode->_prev;return *this;}Self operator--(int){Self tmp(*this);_pnode = _pnode->_prev;return tmp;}bool operator!=(const Self& it) const{return _pnode != it._pnode;}bool operator==(const Self& it) const{return _pnode == it._pnode;}
};

需要介绍一下为什么这样写

首先我们实现的无论哪种迭代器都是一样的操作，差别就是const的不能修改值嘛，也就意味着迭代器函数传出的参数是const修饰的，所以差别在传出的表示。不过，那么我们就可以用模板直接替代传出变量的位置。

基本实现参数有三类

普通的迭代器表示：<T,T*,T&>

const的迭代器表示：<const T,const T*,const T&>

我们清楚，其实这三种切换就行，那么我们直接将这三种的模板套用，<class T,class Ref,class Ptr>。

那么在list的结构体实现中，我们就可以套用模板实现普通和const的迭代器

typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

2.正迭代器实现和反向迭代器实现

对比正迭代器，反向的无非就是倒着走，那么它的函数是和正迭代器实现相反，不过都是一个list中的不同功能迭代器。所以实现代码分离就可以了。

先给出我们list结构体的外壳，为了方便求总数不需要遍历，我们用空间换时间。

template<class T>
class list
{
private:node* _head;size_t _size;
};

我们将普通迭代器和const迭代器模板展开，然后将反向迭代器展开，对于我们而言反向迭代器就是把函数变一下而已。

typedef list_node<T> node;
public:
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;typedef ReverIterator<iterator, const T&, const T*> reverse_iterator;
typedef ReverIterator<const_iterator, const T&, const T*> const_reverse_iterator;const_iterator begin() const
{return const_iterator(_head->_next);
}const_iterator end() const
{return const_iterator(_head);
}iterator begin()
{return iterator(_head->_next);
}iterator end()
{return iterator(_head);
}reverse_iterator rbegin()
{return reverse_iterator(end());
}reverse_iterator rend()
{return reverse_iterator(begin());
}const_reverse_iterator rbegin() const
{return reverse_iterator(end());
}const_reverse_iterator rend() const
{return reverse_iterator(begin());
}

3.拷贝构造和赋值拷贝

void empty_initialize()
{_head = new node(T());_head->_next = _head;_head->_prev = _head;_size = 0;
}list()
{empty_initialize();
}template <class InputIterator>
list(InputIterator first, InputIterator last)
{empty_initialize();while (first != last){push_back(*first);++first;}
}void swap(list<T>& lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}list(const list<T>& lt)
{empty_initialize();list<T> tmp(lt.begin(), lt.end());swap(tmp);
}list<T>& operator=(list<T> lt)
{swap(lt);return *this;
}

4.全部实现代码

namespace MY
{template<class T>struct list_node{list_node* _next;list_node* _prev;T _data;list_node(const T& x): _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> Self;node* _pnode;__list_iterator(node* p):_pnode(p){}Ref  operator*(){return _pnode->_data;}Ptr  operator->(){return &_pnode->_data;}Self& operator++(){_pnode = _pnode->_next;return *this;}Self operator++(int){Self tmp(*this);_pnode = _pnode->_next;return tmp;}Self& operator--(){_pnode = _pnode->_prev;return *this;}Self operator--(int){Self tmp(*this);_pnode = _pnode->_prev;return tmp;}bool operator!=(const Self& it) const{return _pnode != it._pnode;}bool operator==(const Self& it) const{return _pnode == it._pnode;}};/*template<class T>struct __list_const_iterator{typedef list_node<T> node;node* _pnode;__list_const_iterator(node* p):_pnode(p){}const T& operator*(){return _pnode->_data;}__list_const_iterator<T>& operator++(){_pnode = _pnode->_next;return *this;}__list_const_iterator<T>& operator--(){_pnode = _pnode->_prev;return *this;}bool operator!=(const __list_const_iterator<T>& it){return _pnode != it._pnode;}};*/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;//typedef __list_const_iterator<T> const_iterator;typedef ReverIterator<iterator, const T&, const T*> reverse_iterator;typedef ReverIterator<const_iterator, const T&, const T*> const_reverse_iterator;const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rbegin() const{return reverse_iterator(end());}const_reverse_iterator rend() const{return reverse_iterator(begin());}void empty_initialize(){_head = new node(T());_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_initialize();}/*list(const list<T>& lt){empty_initialize();for (const auto& e : lt){push_back(e);}}*/template <class InputIterator>list(InputIterator first, InputIterator last){empty_initialize();while (first != last){push_back(*first);++first;}}void swap(list<T>& lt)//void swap(list& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list(const list<T>& lt)//list(const list& lt){empty_initialize();list<T> tmp(lt.begin(), lt.end());swap(tmp);}/*list<T>& operator=(const list<T>& lt){if (this != &lt){clear();for (const auto& e : lt){push_back(e);}}return *this;}*/list<T>& operator=(list<T> lt)//list& operator=(list lt){swap(lt);return *this;}size_t size() const{return _size;}bool empty() const{return _size == 0;}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}void push_back(const T& x){/*node* newnode = new node(x);node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;*/insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}iterator insert(iterator pos, const T& x){node* newnode = new node(x);node* cur = pos._pnode;node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return iterator(newnode);}iterator erase(iterator pos){assert(pos != end());node* prev = pos._pnode->_prev;node* next = pos._pnode->_next;prev->_next = next;next->_prev = prev;delete pos._pnode;--_size;return iterator(next);}private:node* _head;size_t _size;};
}

5.list和vector的比较

vectorlist
底层结构动态顺序表，一段连续空间带头结点的双向循环链表
随机访问支持随机访问，访问某个元素效率O(1)不支持随机访问，访问某个元素 效率O(N)
插入和删除任意位置插入和删除效率低，需要搬移元素，时间复杂 度为O(N)，插入时有可能需要增容任意位置插入和删除效率高，不 需要搬移元素，时间复杂度为 O(1)
空间利用率缓存利用率高空间利用率低， 缓存利用率低
迭代器原生态指针对原生态指针(节点指针)进行封装，即前一个后一个位置都要知道
迭代器失效在插入元素时，要给所有的迭代器重新赋值，因为插入 元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效插入元素不会导致迭代器失效， 删除元素时，只会导致当前迭代 器失效，其他迭代器不受影响
使用场景需要高效存储，支持随机访问，不关心插入删除效率大量插入和删除操作，不关心随机访问


http://www.ngui.cc/article/show-1007549.html

相关文章

关于VUE3的数据

接口请求出来的数据一般为对象类型的这里有三种方法存储数据&#xff1a;refreactive([])不太推荐reactive&#xff08;[]&#xff09;嵌套一个对象去存储&#xff0c;推荐1、ref<template><van-swipe :autoplay"3000"lazy-render><van-swipe-itemv-f…
阅读更多...
2023-03-25 Android app 通过蓝牙（BLE低功耗蓝牙）实现设备间通讯的一个可用实例

2023-03-25 Android app 通过蓝牙（BLE低功耗蓝牙）实现设备间通讯的一个可用实例

一、两台android 手机之间的ble 蓝牙通信&#xff0c;不要蓝牙匹配&#xff0c;也是可以互传数据。 二、主要代码参考下面的文章&#xff1a; 1、主要参考 Android通过蓝牙&#xff08;BLE低功耗蓝牙&#xff09;实现设备间通讯 | 客户端 | 服务端_蓝牙beaon server_Code-Por…
阅读更多...
TiDB K8S

TiDB K8S

1、 命名空间 k create ns ti k create namespace tidb-admin k create namespace tidb-clusteralias kkubectl alias tik -n tidb alias tiak -n tidb-admin alias tick -n tidb-cluster2、 Helm安装 tidb-operator helm repo add pingcap https://charts.pingcap.org/ helm…
阅读更多...
论文解读：PP-LiteSeg: A Superior Real-Time Semantic Segmentation Model

论文解读：PP-LiteSeg: A Superior Real-Time Semantic Segmentation Model

发表时间&#xff1a;2022 论文地址&#xff1a;https://arxiv.org/abs/2204.02681 项目地址&#xff1a;https://github.com/PaddlePaddle/PaddleSeg PP-LiteSeg&#xff0c;一个新的轻量级实时语义分割任务模型&#xff0c;在分割精度和推理速度之间实现了一种最先进的权衡…
阅读更多...

考研复试——概率论(2)

文章目录概率论1. 什么是概率&#xff1f;请给出定义并解释它。2. 什么是条件概率&#xff1f;请举一个例子并解释。3. 什么是贝叶斯定理&#xff1f;请举一个例子并解释。4. 什么是期望值和方差&#xff1f;请解释这些概念及其在统计学和概率论中的应用。5. 什么是随机变量&am…
阅读更多...

Netty进阶《ChannelPoolMap源码分析》

ChannelPoolMap是用来存储ChannelPool和指定key的一个集合Map&#xff0c;实际的应用场景就是服务器端是一个分布式集群服务&#xff0c;拥有多个配置地址&#xff0c;这样我们就可以配置多个服务地址&#xff0c;减轻单台服务器的压力&#xff1b;Netty框架提供了ChannelPoolM…
阅读更多...
从零开始学习目标检测：YOLO算法详解

从零开始学习目标检测：YOLO算法详解

从零开始学习目标检测&#xff1a;YOLO算法详解 文章目录从零开始学习目标检测&#xff1a;YOLO算法详解1. &#x1f31f;什么是目标检测?2.&#x1f31f;传统的目标检测与基于深度学习的目标检测3.&#x1f31f;目标检测算法的工作流程4.&#x1f31f;目标检测可以干什么&…
阅读更多...

【华为OD机试 2023最新 】 最优资源分配（C++）

文章目录 题目描述输入描述输出描述备注用例题目解析C++题目描述 某块业务芯片最小容量单位为1.25G，总容量为M*1.25G，对该芯片资源编号为1，2，…，M。该芯片支持3种不同的配置，分别为A、B、C。 配置A：占用容量为 1.25 * 1 = 1.25G配置B：占用容量为 1.25 * 2 = 2.5G配置C…
阅读更多...
车机娱乐系统

车机娱乐系统

BYD哪吒理想蔚来小鹏埃安吉利(魅族)大众 MQB大众MEB奥迪娱乐主机内置TboxYes生产商惠州比亚迪电子有限公司惠州市德赛西威汽车电子股份有限公司惠州市德赛西威汽车电子股份有限公司伟创力电脑&#xff08;苏州&#xff09;有限公司比亚迪汽车工业有限公司铁将军汽车电子股份有限…
阅读更多...
数据结构与算法二 算法分析

数据结构与算法二 算法分析

一 算法分析 前面我们已经介绍了&#xff0c;研究算法的最终目的就是如何花更少的时间&#xff0c;如何占用更少的内存去完成相同的需求&#xff0c;并且也通过案例演示了不同算法之间时间耗费和空间耗费上的差异&#xff0c;但我们并不能将时间占用和空间占用量化&#xff0c…
阅读更多...
最新文章

Copyright @ 2022~2023