list的底层与使用

devtools/2024/9/24 12:24:36/

前言：list是带头双向循环链表，物理空间不连续，导致对于迭代器的操作需要进行运算符重载，难点也在于对迭代器的使用与实现

//底层代码
#pragma once
#include<assert.h>
#include<iostream>
using namespace std;
namespace bit
{template <typename T>struct ListNode{ListNode<T>* next;ListNode<T>* prev;T data;ListNode(T x = 0)//在这里进行数据的深拷贝: next(nullptr), prev(nullptr), data(x)//初始化列表{}};template<typename T,typename ptr , typename ref>struct NodeIterator{typedef ListNode<T> Node;typedef NodeIterator<T,ptr,ref> iterator;NodeIterator(Node* tmp): _node( tmp){}ref operator*() const{return _node->data;}//++ititerator operator++(){_node = _node->next;return *this;}// it++iterator operator++(int){iterator tmp(*this);_node = _node->next;return tmp;}//it--iterator operator--(int){iterator tmp(*this);_node = _node->prev;return tmp;}iterator operator--(){_node = _node->prev;return *this;}bool operator!=(const iterator& n) const{return _node != n._node;}ptr operator->(){return &(_node->data);}Node* _node;};template<typename T>class list{public:typedef NodeIterator<T,T* , T&> iterator;typedef NodeIterator<T,const T* ,const T&> const_iterator;typedef ListNode<T> Node;list(const list& s){size = 0;phead = new Node(0);phead->prev = phead->next = phead;for (auto& e : s)push_back(e);}void clear(){auto it = begin();while (it != end())it = erase(it);}~list(){clear();delete phead;size = 0;phead = nullptr;}list(){size = 0;phead = new Node(0);phead->prev = phead->next = phead;}void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(end()._node->prev);}void pop_front(){erase(begin());}iterator begin(){return phead->next;}iterator end(){return phead;}const_iterator begin()const{return phead->next;}const_iterator end()const{return phead;}void insert(iterator position, const T& val){Node* _position = position._node;Node* tmp = new Node(val);tmp->next = _position;tmp->prev = _position->prev;_position->prev->next = tmp;_position->prev = tmp;size++;}iterator erase(iterator position){Node* _position = position._node;Node* tt = _position->next;Node* tmp = _position->prev;tmp->next = _position->next;_position->next->prev = tmp;delete _position;size--;_position = nullptr;return tt;}list& operator= ( list x ){swap(x);return *this;}bool empty(){return size == 0;}void swap(list<T> s){std::swap(size, s.size);std::swap(phead, s.phead);}list& operator= (list<T> x){swap(x);return *this;}private:Node* phead;//头结点int size;};
}

迭代器

迭代器一般需要进行如下操作

std::list<int>::iterator it = s.begin();

while( it != s.end())
{

       cout << *it <<  " ";

        it++;
}

也就是需要对运算符 * !=  ++ 对操作符重载

明确一点：链表中的迭代器是节点的指针 ， 指针是内置类型 ，但需要对内置类型的行为重新定义，则可以把内置类型转换成自定义类型（单独为迭代器写一个类）

首先 * 一般是取链表中的元素（节点中的data) ，在迭代器中需要取data，只需要将节点的指针作为迭代器类的成员变量

第二点 迭代器可以分为const 或者是 非const ，则可以将迭代器写成一个类模版

// 首先在begin函数中 分为 iterator begin()    const_iterator begin() const
// typedef NodeIterator< T ,  T& , typename T*>  iterator;
// typedef NodeIterator< T , const T& , T* > const_iterator;
// 就导致NodeIterator只生成两个类
// iterator begin 放回的是iterator（他就只会调用第一个类）
// const_iterator begin返回的是const_iterator(只会调用第二个类)
template<typename T,typename ptr , typename ref>
struct NodeIterator
{typedef ListNode<T> Node;typedef NodeIterator<T,ptr,ref> iterator;NodeIterator(Node* tmp): _node( tmp){}ref operator*() const{return _node->data;}//++ititerator operator++(){_node = _node->next;return *this;}// it++iterator operator++(int){iterator tmp(*this);_node = _node->next;return tmp;}//it--iterator operator--(int){iterator tmp(*this);_node = _node->prev;return tmp;}iterator operator--(){_node = _node->prev;return *this;}bool operator!=(const iterator& n) const{return _node != n._node;}ptr operator->(){return &(_node->data);}Node* _node;
};

构造函数

方法1：初始化链表初始化

#include<iostream>
#include<vector>
#include<list>
#include<stack>
using namespace std;
int main()
{list<int> s = { 1 , 2 , 3 , 4 , 5 };for (auto& e : s)cout << e << " ";cout << endl;
}

方法2：迭代器区间初始化

#include<iostream>
#include<vector>
#include<list>
#include<stack>
using namespace std;
int main()
{vector<int> dp = { 1 , 2 , 3 ,4 , 6 };auto it = dp.begin();list<int> s(it + 2, dp.end() - 1);for (auto& e : s)cout << e << " ";cout << endl;
}

方法3：不加任何条件

#include<iostream>
#include<vector>
#include<list>
#include<stack>
using namespace std;
int main()
{list<int> s;return 0;
}

拷贝构造与赋值重载

均为深拷贝

front与back函数

返回头和尾元素

#include<iostream>
#include<vector>
#include<list>
#include<stack>
using namespace std;
int main()
{vector<int> dp = { 1 , 2 , 3 ,4 , 6 };int f = dp.front();int t = dp.back();cout << f << " " << t << endl;}

insert函数

在某一个位置之前插入一个值或一段区间

#include<iostream>
#include<vector>
#include<list>
#include<stack>
using namespace std;
int main()
{list<int> s = { 1 , 2 , 4  , 5 , 6 };auto it = s.begin();vector<int> dp = { 1 , 0 , 9 };s.insert(it, dp.begin(), dp.end());for (auto& e : s)cout << e << " ";cout << endl;s.insert(s.end(), 10);for (auto& e : s)cout << e << " ";cout << endl;}

erase函数

去除某一个位置的值，或某一段区间的值

#include<iostream>
#include<vector>
#include<list>
#include<stack>
using namespace std;
int main()
{list<int> s = { 1 , 2 , 3 , 5 , 3 };s.erase(s.begin());list<int> p = { 4 , 5 , 12 , 3 , 4 };s.erase(++p.begin(), --p.end());for (auto& e : p)cout << e << " ";cout << endl;}

push_back 与push_front函数

本质复用insert函数 尾插 头插

pop_back与pop_front函数

本质复用erase函数

assign函数

将链表中的内容重新分配

#include<iostream>
#include<vector>
#include<list>
#include<stack>
using namespace std;
int main()
{list<int> s = { 1, 2, 3, 4, 6 };list<int> k = { 9 , 1 , 0 };s.assign({ 2,3,45 });for (auto& e : s)cout << e << " ";cout << endl;s.assign(k.begin(),k.end());for (auto& e : s)cout << e << " ";cout << endl;}


http://www.ppmy.cn/devtools/30181.html

相关文章

css 居中方法

css 居中方法

行内元素水平居中: 行内元素指的是&#xff1a;text、image、超链接等。 #id {text-align: center; }块级元素水平居中 块级元素指的是&#xff1a;div、h1-h6、ul等&#xff0c;使用如下代码即可&#xff0c;必须指定宽度。 #id {margin: 0 auto;width: 100px; }
阅读更多...
贝叶斯统计实战：Python引领的现代数据分析之旅

贝叶斯统计实战：Python引领的现代数据分析之旅

贝叶斯统计这个名字取自长老会牧师兼业余数学家托马斯贝叶斯(Thomas Bayes&#xff0c;1702—1761)&#xff0c;他最先推导出了贝叶斯定理&#xff0c;该定理于其逝世后的1763年发表。但真正开发贝叶斯方法的第一人是Pierre-Simon Laplace(1749—1827)&#xff0c;因此将其称为…
阅读更多...
UI自动化与接口自动化比较

UI自动化与接口自动化比较

UI自动化与接口自动化优比较&#xff1a; 1、执行效率 接口自动化执行效率比UI自动化执行效率更高(调用接口比打开页面要快很多) 2、稳定性 UI自动化容易受设备卡顿&#xff0c;系统弹框等因素影响而导致脚本执行失败、接口自动化不存在此问题&#xff0c;因此接口自动化测试…
阅读更多...
栈（Stack）

栈（Stack）

栈（Stack）是一种特殊的线性数据结构，遵循后进先出（Last In, First Out, LIFO）原则。想象一下一叠盘子，每次只能从最上面拿取或放置盘子，这就是栈的工作原理。栈在计算机科学中有广泛应用，如函数调用栈、表达式求值、括号匹配等。 基本概念 栈顶（Top）：栈中最上面的元…
阅读更多...
WebRTC中获取当前采集设备的deviceId

WebRTC中获取当前采集设备的deviceId

在做webRTC项目离不开切换摄像头&#xff0c;但是怎么拿到当前采集的设备id就成了问题&#xff0c;查阅资料后发现官方其实有提供相关方法&#xff0c;简单记录下&#xff1b; 通用玩法获取采集设备id // 请求访问用户媒体设备 navigator.mediaDevices.getUserMedia({ video: …
阅读更多...
C++_set和map的学习

C++_set和map的学习

1. 关联式容器 STL中的容器有序列式容器和关联式容器。 其中 vector 、 list 、 deque 、 forward_list(C11)就是序列式容器&#xff0c; 因为其底层为线性序列的数据结构&#xff0c;里面 存储的是元素本身 关联式容器 也是用来存储数据的&#xff0c;与序列式容器不同的是&am…
阅读更多...
Jammy@Jetson Orin Nano - Tensorflow GPU版本安装

Jammy@Jetson Orin Nano - Tensorflow GPU版本安装

JammyJetson Orin Nano - Tensorflow GPU版本安装 1. 源由2. 问题2.1 Tensorflow跑以下示例代码的时候&#xff0c;发现jtop中6个CPU占用率都跑满了。2.2 Jetson Orin Nano运行Tensorflow示例结果不一致 3. 分析3.1 当前版本Tensorflow 2.16.13.2 GPU版本二进制安装3.3 GPU版本…
阅读更多...
uni-app中，实现页面之间传参

uni-app中，实现页面之间传参

使用场景&#xff1a; 前提条件&#xff1a;当我们从一个列表页面&#xff0c;进入新增页面&#xff0c; 情况1&#xff1a;在新增页面&#xff0c;信息添加成功后&#xff0c;返回列表页面&#xff0c;此时&#xff0c;需要更新列表数据&#xff1b; 情况2&#xff1a;在新增页…
阅读更多...
最新文章

Copyright @ 2022~2023