C++——STL（list类）

1.list的介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。

4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。

5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问。

2.list的使用

2.1 list的构造

(constructor)

  • list():无参构造，构造空的list
  • list (size_type n, const value_type& val = value_type())：构造的list中包含n个值为val的元素
  • list (const list& x)：拷贝构造函数
  • list (InputIterator first, InputIterator last)：用[first, last)区间中的元素构造list

list构造函数模拟实现：

//无参构造
List()
{CreateHead();
}
//构造
List(int n, const T& val = T())
{CreateHead();for (int i = 0; i < n; i++){push_back(val);}
}
//参数为迭代器的构造
template<class iterator>
List(iterator first, iterator last)
{CreateHead();iterator it = first;while (it != last){push_back(*it);++it;}
}
//拷贝构造
List(const List<T>& l)
{CreateHead();List<T> tmp(l.begin(), l.end());this->swap(tmp);
}//析构
~List()
{clear();delete _head;_head = nullptr;
}

2.2 list iterator的使用

begin  + end ：返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器

rbegin +  rend ：返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置

注意：

1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动 

 list iterator的模拟实现：

template<class T,class Ref,class Ptr>
struct ListIterator
{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;//构造ListIterator(Node* node=nullptr):_node(node){}//迭代器的解引用Ref operator*(){return _node->_val;}Ptr operator->(){return &(_node->_val);}//迭代器的移动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& it) const{return _node != it._node;}bool operator==(const Self& it) const{return _node == it._node;}Node* _node; //迭代器本质是节点指针
};

2.3 list capacity

  • empty ：检测list是否为空，是返回true，否则返回false
  • size ：返回list中有效节点的个数

模拟实现：

// 容量相关
//size
size_t size() const
{Node* cur = _head->_next;size_t count = 0;while (cur != _head){++count;cur = cur->_next;}return count;
}bool empty() const
{return _head->_next == _head;
}

 2.4 list element access

  • front ：返回list的第一个节点中值的引用
  • back ：返回list的最后一个节点中值的引用

模拟实现：

//元素访问
T& front()
{return _head->_next->_val;
}const T& front()const
{return _head->_next->_val;
}T& back()
{return _head->_prev->_val;
}const T& back()const
{return _head->_prev->_val;
}

 2.5 list Modifiers

  • push_front  :在list首元素前插入值为val的元素
  • pop_front :删除list中第一个元素
  • push_back :在list尾部插入值为val的元素
  • pop_back :删除list中最后一个元素
  • insert :在list position 位置中插入值为val的元素
  • erase :删除list position位置的元素
  • swap :交换两个list中的元素
  • clear :清空list中的有效元素
  • resize :改变list的size

 模拟实现：

//插入删除
void push_back(const T& data)
{insert(end(), data);
}void pop_back()
{erase(--end());
}void push_front(const T& data)
{insert(begin(), data);
}void pop_front()
{erase(begin());
}//insert
iterator insert(iterator pos, const T& val)
{Node* newnode = new Node(val);Node* cur = pos._node;newnode->_prev = cur->_prev;newnode->_next = cur;newnode->_prev->_next = newnode;cur->_prev = newnode;return iterator(newnode);
}//erase
iterator erase(iterator pos)
{Node* cur = pos._node;Node* Ret = cur->_next;cur->_prev->_next = cur->_next;cur->_next->_prev = cur->_prev;delete cur;return iterator(Ret);
}//swap
void swap(bit::List<T>& l)
{std::swap(_head, l._head);
}//clear
void clear()
{Node* cur = _head->_next;while (cur != _head){Node* next = cur->_next;delete cur;cur = next;}_head->_prev = _head->_next = _head;
}//resize
void resize(size_t newsize, const T& data = T())
{int oldsize = size();if (newsize > oldsize){while (oldsize < newsize){push_back(data);++oldsize;}}else{while (oldsize > newsize){pop_back();--oldsize;}}
}

2.6 list迭代器失效问题

大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节
点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

 3.list与vector的对比

vector链接

vector

list

底

层

结

构

动态顺序表，一段连续空间

带头结点的双向循环链表

随

机

访

问

支持随机访问，访问某个元素效O(1)

不支持随机访问，访问某个元素效率O(N)

插

入

和

删

除

任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低

任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1)

空

间

利

用

率

底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高

底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低

迭

代

器

原生态指针

对原生态指针(节点指针)进行封装

迭

代

器

失

效

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

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

插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响

使

用

场

景

需要高效存储，支持随机访问，不关心插入删除效率

大量插入和删除操作，不关心随机访问

4.模拟实现源码 

list.h

#pragma once#include<iostream>using namespace std;namespace bit
{template<class T>struct ListNode{ListNode(const T& val=T()):_prev(nullptr),_next(nullptr),_val(val){}ListNode* _prev;ListNode* _next;T _val;};template<class T,class Ref,class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;//构造ListIterator(Node* node=nullptr):_node(node){}//迭代器的解引用Ref operator*(){return _node->_val;}Ptr operator->(){return &(_node->_val);}//迭代器的移动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& it) const{return _node != it._node;}bool operator==(const Self& it) const{return _node == it._node;}Node* _node; //迭代器本质是节点指针};template<class Iterator>struct ReverseListIterator{typedef typename Iterator::Ref Ref;typedef typename Iterator::Ptr Ptr;typedef ReverseListIterator<Iterator> Self;//构造ReverseListIterator(Iterator it):_it(it){}//迭代器的解引用Ref operator*(){Self tmp(_it);--tmp;return *tmp;}Ptr operator->(){Self tmp(_it);--tmp;return &(operator*());}//迭代器的移动Self operator++(){--_it;return *this;}Self operator++(int){Self tmp(_it);--_it;return tmp;}Self operator--(){++_it;return *this;}Self operator--(int){Self tmp(_it);++_it;return tmp;}//反向迭代器的比较bool operator!=(const Self& rit) const{return _it != rit._it;}bool operator==(const Self& rit) const{return _it == rit._it;}Iterator _it;};template<class T>class List{typedef ListNode<T> Node;public://迭代器typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;//反向迭代器typedef ReverseListIterator<iterator> reverse_iterator;typedef ReverseListIterator<const_iterator> const_reverse_iterator;//无参构造List(){CreateHead();}//构造List(int n, const T& val = T()){CreateHead();for (int i = 0; i < n; i++){push_back(val);}}//参数为迭代器的构造template<class iterator>List(iterator first, iterator last){CreateHead();iterator it = first;while (it != last){push_back(*it);++it;}}//拷贝构造List(const List<T>& l){CreateHead();List<T> tmp(l.begin(), l.end());this->swap(tmp);}//析构~List(){clear();delete _head;_head = nullptr;}/// 迭代器iterator begin(){return iterator(_head->_next);}const_iterator begin()const{return const_iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator end()const{return const_iterator(_head);}//反向迭代器reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rbegin()const{return const_reverse_iterator(end());}const_reverse_iterator rend()const{return const_reverse_iterator(begin());}//// 容量相关//sizesize_t size() const{Node* cur = _head->_next;size_t count = 0;while (cur != _head){++count;cur = cur->_next;}return count;}bool empty() const{return _head->_next == _head;}void resize(size_t newsize, const T& data = T()){int oldsize = size();if (newsize > oldsize){while (oldsize < newsize){push_back(data);++oldsize;}}else{while (oldsize > newsize){pop_back();--oldsize;}}}///元素访问T& front(){return _head->_next->_val;}const T& front()const{return _head->_next->_val;}T& back(){return _head->_prev->_val;}const T& back()const{return _head->_prev->_val;}////插入删除void push_back(const T& data){insert(end(), data);}void pop_back(){erase(--end());}void push_front(const T& data){insert(begin(), data);}void pop_front(){erase(begin());}//insertiterator insert(iterator pos, const T& val){Node* newnode = new Node(val);Node* cur = pos._node;newnode->_prev = cur->_prev;newnode->_next = cur;newnode->_prev->_next = newnode;cur->_prev = newnode;return iterator(newnode);}//eraseiterator erase(iterator pos){Node* cur = pos._node;Node* Ret = cur->_next;cur->_prev->_next = cur->_next;cur->_next->_prev = cur->_prev;delete cur;return iterator(Ret);}void clear(){Node* cur = _head->_next;while (cur != _head){Node* next = cur->_next;delete cur;cur = next;}_head->_prev = _head->_next = _head;}void swap(bit::List<T>& l){std::swap(_head, l._head);}private:void CreateHead(){_head = new Node;_head->_next = _head;_head->_prev = _head;}Node* _head;};
}

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

音视频入门基础：AAC专题（5）——FFmpeg源码中，判断某文件是否为AAC裸流文件的实现

音视频入门基础：AAC专题（5）——FFmpeg源码中，判断某文件是否为AAC裸流文件的实现

一、引言 通过FFmpeg命令&#xff1a; ./ffmpeg -i XXX.aac 可以判断出某个文件是否为AAC裸流文件&#xff1a; 所以FFmpeg是怎样判断出某个文件是否为AAC裸流文件呢&#xff1f;它内部其实是通过adts_aac_probe函数来判断的。从《FFmpeg源码&#xff1a;av_probe_input_for…
阅读更多...
TCP socket

TCP socket

TCP的socket和UDP大同小异&#xff0c;基本的代码结构都是相同的。一些相同的接口本文就不赘述了&#xff0c;例如&#xff0c;socket,bind&#xff0c;有需要看这篇文章UDP socket 服务端server 两步&#xff1a;初始化服务端&#xff0c;运行服务端 初始化服务端 创建soc…
阅读更多...
物品识别——基于python语言

物品识别——基于python语言

目录 1.物品识别 2.模型介绍 3.文件框架 4.代码示例 4.1 camera.py 4.2 interaction.py 4.3 object_detection.py 4.4 main.py 4.5 运行结果 5.总结 1.物品识别 该项目使用Python&#xff0c;OpenCV进行图像捕捉&#xff0c;进行物品识别。我们将使用YOLO&#xff08…
阅读更多...
人工智能——猴子摘香蕉问题

人工智能——猴子摘香蕉问题

一、实验目的 求解猴子摘香蕉问题&#xff0c;根据猴子不同的位置&#xff0c;求解猴子的移动范围&#xff0c;求解对应的过程&#xff0c;针对不同的目标状态进行求解。 二、实验内容 根据场景有猴子、箱子、香蕉&#xff0c;香蕉挂天花板上。定义多种谓词描述位置、状态等…
阅读更多...
Vue生命周期；Vue路由配置；vue网络请求；vue跨域处理

Vue生命周期；Vue路由配置；vue网络请求；vue跨域处理

一&#xff0c;Vue生命周期 <template><div > <h1 click"changeText">{{ info }}</h1></div> </template><script> export default {name: HelloWorld,data(){return{info:"介绍组件生命周期"}},methods:{chang…
阅读更多...
CenterNet官方代码—目标检测模型推理部分

CenterNet官方代码—目标检测模型推理部分

CenterNet模型推理部分解析 CenterNet官方代码环境部署 CenterNet作为2019年CVPR推出的论文&#xff0c;论文中给出了官方代码所在的github仓库地址。https://github.com/xingyizhou/CenterNet。 整个代码的代码量并不是特别大&#xff0c;但整个项目的难点在于使用了老版本的…
阅读更多...
Djourney新手入门基础，AI摄影+AI设计+AI绘画-AIGC作图

Djourney新手入门基础，AI摄影+AI设计+AI绘画-AIGC作图

人工智能技术的飞速发展&#xff0c;AI正逐渐渗透进创意领域&#xff0c;特别是在摄影、设计和绘画方面&#xff0c;AIGC&#xff08;Artificial Intelligence for Generative Content&#xff09;技术正在重塑我们的创作方式。本文将深入探讨Djourney这款创新工具&#xff0c;…
阅读更多...
XML_Tomcat_HTTP

XML_Tomcat_HTTP

第四章 XML_Tomcat10_HTTP 一 XML XML是EXtensible Markup Language的缩写&#xff0c;翻译过来就是可扩展标记语言。所以很明显&#xff0c;XML和HTML一样都是标记语言&#xff0c;也就是说它们的基本语法都是标签。 可扩展 三个字表面上的意思是XML允许自定义格式。但这不代…
阅读更多...
推荐这款神器：Perplexity

推荐这款神器：Perplexity

今天推荐是一款AI搜索引擎&#xff0c;还支持gpt-4模型的使用&#xff0c;虽然4小时只能使用5次&#xff0c;但是相比于常规的搜索引擎&#xff0c;在某些方面还是很强的&#xff0c;个人感觉优于newbing。 页面简洁&#xff0c;没有广告&#xff0c;内容丰富&#xff0c;功能…
阅读更多...
LinkedHashMap 如何实现排序

LinkedHashMap 如何实现排序

目录 一、LinkedHashMap二、排序实现三、代码片段分析 一、LinkedHashMap LinkedHashMap 是 Java 中的一个集合类&#xff0c;它是 HashMap 的一个子类&#xff0c;继承了 HashMap 的所有特性&#xff0c;并且在此基础上增加了一个双向链表来维护元素的插入顺序或者访问顺序。L…
阅读更多...
Day26_0.1基础学习MATLAB学习小技巧总结（26）——数据插值

Day26_0.1基础学习MATLAB学习小技巧总结（26）——数据插值

利用空闲时间把碎片化的MATLAB知识重新系统的学习一遍&#xff0c;为了在这个过程中加深印象&#xff0c;也为了能够有所足迹&#xff0c;我会把自己的学习总结发在专栏中&#xff0c;以便学习交流。 参考书目&#xff1a; 1、《MATLAB基础教程 (第三版) (薛山)》 2、《MATL…
阅读更多...
C++ STL中sort函数

C++ STL中sort函数

STL的sort算法&#xff0c;数据量大时采用QuickSort快排算法&#xff0c;分段归并排序。一旦分段后的数据量小于某个门槛&#xff08;16&#xff09;&#xff0c;为避免QuickSort快排的递归调用带来过大的额外负荷&#xff0c;就改用Insertion Sort插入排序。如果递归层次过深&…
阅读更多...
C++入门基础知识69（高级）——【关于C++ 动态内存】

C++入门基础知识69（高级）——【关于C++ 动态内存】

成长路上不孤单&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a; 【14后&#x1f60a;///C爱好者&#x1f60a;///持续分享所学&#x1f60a;///如有需要欢迎收藏转发///&#x1f60a;】 今日分享关于C 动态内存的相关内容&#xff01; 目录…
阅读更多...
[产品管理-19]：NPDP新产品开发 - 17 - 产品设计与开发工具 - 实体化设计工具：联合分析、功能分析、FAST技术图和逆向工程

[产品管理-19]：NPDP新产品开发 - 17 - 产品设计与开发工具 - 实体化设计工具：联合分析、功能分析、FAST技术图和逆向工程

目录 前言&#xff1a; 一、什么是实体化设计 1.1 什么是实体化设计 1、定义与概述 2、设计流程 3、关键要素 4、应用领域 5、举例说明 1.2 实体化设计与概念设计的区别 实体化设计 概念设计 区别归纳 1.3 实体化设计与初步设计、规格设计的区别 1、定义与目的 …
阅读更多...
51单片机-LCD1602（液晶显示屏）- 写驱动

51单片机-LCD1602（液晶显示屏）- 写驱动

时间永远是检验真理唯一标准&#xff01;Whappy&#xff01; 主要简单写出几个驱动 初始化、显示字符、显示字符串、显示整形数据、有符号数据、十六进制、二进制&#xff01; void LCD_Init(); void LCD_ShowChar(unsigned char Line,unsigned char Column,char Char); vo…
阅读更多...
平安养老险阜阳中心支公司开展金融教育宣传专项活动

平安养老险阜阳中心支公司开展金融教育宣传专项活动

为全面深入开展“金融教育宣传月”的各项工作&#xff0c;不断完善金融惠民利民举措&#xff0c;提升金融服务质效&#xff0c;帮助基层群众增强维权意识、防非反诈的自我保护能力。近日&#xff0c;平安养老保险股份有限公司&#xff08;以下“平安养老险”&#xff09;阜阳中…
阅读更多...
【Node.js】RabbitMQ 延时消息

【Node.js】RabbitMQ 延时消息

概述 在 RabbitMQ 中实现延迟消息通常需要借助插件&#xff08;如 RabbitMQ 延迟队列插件&#xff09;&#xff0c;因为 RabbitMQ 本身不原生支持延迟消息。 延迟消息的一个典型场景是&#xff0c;当消息发布到队列后&#xff0c;等待一段时间再由消费者消费。这可以通过配置…
阅读更多...
带你0到1之QT编程：十一、掌握Containers容器艺术，一网打尽开发利器

带你0到1之QT编程：十一、掌握Containers容器艺术，一网打尽开发利器

此为QT编程的第十一谈&#xff01;关注我&#xff0c;带你快速学习QT编程的学习路线&#xff01; 每一篇的技术点都是很很重要&#xff01;很重要&#xff01;很重要&#xff01;但不冗余&#xff01; 我们通常采取总-分-总和生活化的讲解方式来阐述一个知识点&#xff01; …
阅读更多...
npm install报错，gyp verb `which` failed Error: not found: python

npm install报错，gyp verb `which` failed Error: not found: python

主要错误 gyp verb which failed Error: not found: python2 gyp ERR! configure error gyp ERR! stack Error: Cant find Python executable "python", you can set the PYTHON env variable. npm ERR! node-sass4.14.1 postinstall: node scripts/build.js 全部错…
阅读更多...
几分钟学会搭建一个自己的外卖霸王餐系统

几分钟学会搭建一个自己的外卖霸王餐系统

大家好&#xff0c;我是鲸天科技千千&#xff0c;大家都知道我是做小程序开发的&#xff0c;平时会给大家分享一些互联网相关的创业项目&#xff0c;感兴趣的可以跟我关注一下。 搭建一个首先就是要搭建一个自己的霸王餐小程序&#xff0c;我们自己的工作就是把这个小程序推广…
阅读更多...
最新文章

Copyright @ 2022~2023