【C++】详解STL的容器之一：list

ops/2024/9/24 17:30:59/

目录

简介

list-toc" style="margin-left:0px;">初识list

模型

list%E5%AE%B9%E5%99%A8%E7%9A%84%E4%BC%98%E7%BC%BA%E7%82%B9-toc" style="margin-left:40px;">list容器的优缺点

list%E7%9A%84%E8%BF%AD%E4%BB%A3%E5%99%A8-toc" style="margin-left:40px;">list的迭代器

常用接口介绍

获取迭代器

begin

end

empty

size

front

back

insert

push_front

pop_front

push_back

pop_back

clear

源代码思路

节点设计

迭代器的设计

list%E7%9A%84%E8%AE%BE%E8%AE%A1-toc" style="margin-left:40px;">list的设计

 begin()

end()

空构造

insert()

push_back

模拟实现

节点设计

迭代器设计

list%E8%AE%BE%E8%AE%A1-toc" style="margin-left:40px;">list设计

框架

获取迭代器

空构造

insert

erase

赋值重载

其他接口

简介

C++的STL有六大组件：仿函数， 空间配置器， 算法， 容器， 迭代器，配接器。list属于容器的一种。

list的设计使用了模板，是一种泛型编程。

list">初识list

模型

list是带哨兵位的双向循环链表。

链表是由一个一个的节点通过指针链接起来的。list的节点设计：prev指针指向前一个节点，next指针指向下一个节点，data储存数据。如下图

而list想要实现双向循环链表，只需用一个指针指向不储存数据的节点——哨兵位节点或头节点。让哨兵位节点将整条链表首尾相连。哨兵位的next是链表的头节点，哨兵位的prev是链表的尾节点，如下图

list%E5%AE%B9%E5%99%A8%E7%9A%84%E4%BC%98%E7%BC%BA%E7%82%B9">list容器的优缺点

优点：头部插入，头部删除，尾部插入，尾部删除的时间复杂度位O(1)。list的指针是一直指向哨兵位节点的，通过哨兵位节点能找到链表的头节点和尾节点，从而实现头插，头删，尾插，尾删操作。

缺点：对链表中的数据进行排序的时间复杂度会很高。找链表中的某一个数据时，需要遍历链表。

list%E7%9A%84%E8%BF%AD%E4%BB%A3%E5%99%A8">list的迭代器

list的每个节点在内存中储存不是连续的。

普通的指针不能完成对链表的遍历——加加指针不能使指针指向下一个节点，减减指针不能使指针指向上一个节点。指针的解引用不能完成对数据存取——普通指针解引用是整个节点，而不是节点里存的数据。

所以不能用普通指针做list的迭代器。应该对普通指针进行封装，将封装之后的普通指针作为list的迭代器。该迭代器能完成链表的遍历，数据的存取等操作。

具体怎样封装，下面介绍源代码思路和模拟实现时会详细讲解

迭代器失效：把迭代器指向的节点删除掉，会让该迭代器失效，类似于野指针的问题。在迭代器指向节点的前面或后面插入节点，不会使迭代器失效。

常用接口介绍

获取迭代器

begin

返回哨兵位前一个节点的位置

end

返回哨兵位节点的位置

empty

检测list是否为空，是返回true，否则返回false

size

返回list中有效节点的个数

front

返回list的第一个节点中值的引用

back

返回list的最后一个节点中值的引用

insert

在list的 position 迭代器指向的节点之前插入值为val的节点,返回新插入节点的迭代器

push_front

在链表的头部插入一个值为val的节点

pop_front

删除头部位置的节点

erase

删除position迭代器指向的节点，或删除从first到last迭代器区间的节点，返回下一个位置的迭代器

push_back

在链表的尾部插入值为val的节点

pop_back

删除最后一个节点

clear

删除所有有效节点

源代码思路

下面内容参考侯捷老师的《STL源码剖析》

源代码中涉及空间配置器的部分不做重点讲解，只需知道空间配置器是为了给节点list申请空间的即可。

小编摘抄部分源码，带大家了解list设计的大概框架。具体实现的细节在模拟实现时讲解

节点设计

template <class T>
struct __list_node 
{typedef void* void_pointer;void_pointer* prev;void_pointer* next;T data;}

struct在C语言中是结构体，在C++中是类。用struct封装不加访问限定符默认成员是公有的。迭代器和链表需要访问节点的数据，设计成共有是为了方便访问。设计成私有需要声明友元。

prev和next的指针是void*类型是因为不知道数据的类型，源码在实现其他接口时会把void*进行强转。和下面代码的设计是等价的

__list_node<T>* prev;   __list_node<T>* next；

data是用来储存数据的

迭代器的设计

template <class T, class Ref, class Ptr> 
struct __list_iterator  
{typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, Ref, Ptr> self;typedef T value_type;typedef Ptr pointer;typedef Ref reference;typedef __list_node<T>* link_type;link_type node; //节点指针  核心数据//运算符重载，为了让node能像普通指针一样//解引用重载reference operator*()const //Ref{return (*node).data;}//->运算符重载pointer operator->() const  //Ptr{return &(operator*());}//++运算符重载.....//--运算符重载....//==运算符重载....//......
}

成员全部共有，方便list访问

Ref和Ptr两个模板参数是为了区分普通迭代器和const迭代器，如下代码

typedef __list_iterator<T, T&, T*>  iterator;   //迭代器别名   
typedef __list_iterator<T, const T&, const T*>  const_iterator; //const迭代器别名

如下图

node是节点的指针，是核心数据。在迭代器这个类中，重载了*  ->  ++  --  ==  != 运算符是为了让结点指针能像普通指针一样，完成对链表的遍历和对数据的存取。这便是封装的魅力。

list%E7%9A%84%E8%AE%BE%E8%AE%A1">list的设计

template <class T, class Alloc = alloc>
class list
{
protected:typedef __list_node<T> list_node;public:typedef list_node* link_type;protected:link_type node;
}

上文已经提到，只需用一个节点指针node指向哨兵位节点，便可以通过迭代器对整条链表增删查改。

 begin()

iterator begin()
{
return (link_type)((*node).next);
}

获取哨兵位节点的下一个指针next，但next是void*类型的指针，需要强转成节点类型的指针

end()

iterator end()
{
return node;
}

获取尾节点的下一个节点的指针——哨兵位节点指针

空构造

void empty_initialize()
{node = get_node(); //为哨兵位开空间node->next = node; //没有有效节点，首尾指针都指向自己node->prev = node;}list()//构造函数，构造空链表
{
empty_initialize();}

list是允许构造空链表的

详解构造函数：http://t.csdnimg.cn/Iu0t4

insert()

iterator insert (iterator position, const T& x)
{link_type tmp = create_node(x);tmp->next = position.node;
tmp->prev =  position.node->prev;
(link_type(position.node->prev))->net = tmp;
position.node->prev = tmp;return tmp;}

上述代码中有经过封装的函数。但大致思路如下图

隐式类型转换：http://t.csdnimg.cn/jBT7I

push_back

void push_back(const T& x)
{
insert(end(), x);}

复用insert

模拟实现

目的：源代码的变量经过了嵌套的typedef，函数经过层层封装。用源代码理解list的实现细节和运行机制并不容易。用源代码的的框架和实现思路实现一个简易的list，帮助我们更好的理解list。

模拟实现是用new和delete，管理list的内存。详见内存管理一文：http://t.csdnimg.cn/byO3P

节点设计

template <class T>
struct __list_node
{T* prev;//指向前一个节点T* next;//指向后一个节点T data;//储存数据__list_node(const T& val = T()) //构造函数:prev(nullptr), next(nullptr)  //参数列表, data(val){}
};

迭代器设计

template <class T, class Ref, class Ptr>  //封装指针
struct __list_iterator
{typedef __list_iterator<T, Ref, Ptr>  self;   //迭代器别名 typedef __list_node<T>  list_node; //节点别名别名  list_node* p_node;   //节点指针 __list_iterator(list_node* val)  :p_node(val)        {};     T operator*()//解引用重载{return  p_node->data;        }; Ref operator*()//解引用重载 {return  p_node->data;};T operator->(){return &p_node->data;}Ptr operator->()     {return &p_node->data;}self& operator++()//加加运算符重载 {return p_node->next; };bool operator!=(const self val)//不等于运算符重载{return p_node != val.p_node;};bool operator==(const self val)//等于运算符重载  {return p_node == val.p_node; };};

list%E8%AE%BE%E8%AE%A1">list设计

框架

template <class T>
class list
{typedef __list_node<T>  list_node; //节点指针别名typedef __list_iterator<T, T&, T*>  iterator;   //迭代器别名   typedef __list_iterator<T, const T&, const T*>  const_iterator;   //const迭代器别名    public://接口......private:list_node* head_node;//头节点，只要一个指针便可代表整个链表 };

获取迭代器

iterator begin() 
{return head_node->next;}
const_iterator begin()
{return head_node->next;
}iterator end()
{return head_node; 
}const_iterator end()  
{return head_node;
}

空构造

void empty_init()
{head_node = new list_node;head_node->_prev = head_node;head_node->_next = head_node;}
list()
{empty_init();
}

insert

iterator insert(iterator pos, const T& x)//指定位置插入
{list_node* cur = pos.p_node;  //用临时指针指向迭代器位置的节点list_node* prev = cur->prev; //用临时指针指向该节点的下一个节点list_node* newnode = new list_node(x); //构造新节点prev->next = newnode; //改变指向newnode->next = cur;cur->prev = newnode;newnode->prev = prev; return newnode; //返回新节点的迭代器
}

代码思路如下图

erase

iterator erase(iterator pos)//指定位置删除
{assert(pos != end());  //不能删哨兵位list_node* cur = pos.p_node; //用临时指针指向前中后三个节点list_node* prev = cur->prev;list_node* next = cur->next;prev->next = next; //改变指向next->prev = prev;delete cur;//删除该节点return next; //返回下一个位置的节点的迭代器}

赋值重载

现在写法

void swap(list<T>& lt)   
{std::swap(head_node, lt.head_node);   
}list<T>& operator=(list<T> lt)  
{swap(lt);return *this;
}

其他接口

void push_back(const T& x)
{insert(end(), x); 
}void push_front(const T& x)
{insert(begin(), x); 
}void pop_back()
{erase(--end()); 
}void pop_front()
{erase(begin()); 
}

本篇内容到此结束啦


http://www.ppmy.cn/ops/33479.html

相关文章

【DevOps】Jenkins 集成Docker

【DevOps】Jenkins 集成Docker

目录 1. 安装 Docker 和 Jenkins 2. 在 Jenkins 中安装 Docker 插件 3. 配置 Docker 连接 4. 创建 Jenkins Pipeline 5. 示例 Pipeline 脚本 6. 运行 Jenkins Job 7. 扩展功能 8、docker配置测试连接的时候报错处理 将 Docker 与 Jenkins 集成可以实现持续集成和持续交…
阅读更多...
Transformer中的数据输入构造

Transformer中的数据输入构造

文章目录 1. 文本内容2. 字典构造2.1 定义一个类用于字典构造2.2 拆分文本2.3 构造结果 3. 完整代码 1. 文本内容 假如我们有如下一段文本内容&#xff1a; Optics It is the branch of physics that studies the behaviour and properties of light . Optical Science 这段…
阅读更多...
室外巡检机器人——A2型高防护轮式巡检机器人

室外巡检机器人——A2型高防护轮式巡检机器人

在科技日新月异的时代&#xff0c;室外巡检机器人犹如一位无畏的守护者&#xff0c;悄然出现在我们的视野之中。它迈着坚定的步伐&#xff0c;穿梭于各种复杂的室外环境&#xff0c;承担着重要的巡检任务。它是科技与智慧的结晶&#xff0c;是保障安全与稳定的前沿力量。让我们…
阅读更多...
XXL-JOB定时任务

XXL-JOB定时任务

1. xxl-job初识 1.1 xxl-job介绍 xxl-job 是大众点评大佬徐雪里开源的一款分布式任务调度框架&#xff0c;具有简单易用、轻量级、可扩展的特点。相比于Spring Task, Quartz&#xff0c;xxl-job有记录执行日志和运行大盘&#xff0c;方便开发人员和运维人员更好的管理任务。 …
阅读更多...
机器学习Sklean基础教程

机器学习Sklean基础教程

Scikit-learn&#xff08;也称为 sklearn&#xff09;是一个使用 python 语言的机器学习模块&#xff0c;内置了大量的监督和无监督学习算法&#xff0c;主要用于数据挖掘和数据分析。 以下是一个简单关于如何使用 sklearn 进行机器学习的指导&#xff1a; 安装: 首先&#…
阅读更多...
MySQL-创建数据表

MySQL-创建数据表

1.选择数据库 USE database_name;2.定义数据类型 设计表的结构&#xff0c;包括表名、列名、数据类型以及任何需要的约束 3.使用SQL语句创建数据表 使用CREATE TABLE语句来创建表 CREATE TABLE table_name(column1_name column1_data_type column1_constraints;column2_name …
阅读更多...
AtCoder Beginner Contest 352 G. Socks 3（期望线性性+分治NTT板子题）

AtCoder Beginner Contest 352 G. Socks 3（期望线性性+分治NTT板子题）

题目 一盒抽屉&#xff0c;里面有n(n<3e5)种袜子&#xff0c;第i种有ai(2<ai<3000)只 每次抽一只袜子不放回&#xff0c;直到凑齐一双袜子后结束&#xff0c; 求结束时抽取的次数的期望&#xff0c;答案对998244353取模 思路来源 元老群全月&starsilk&pro…
阅读更多...
eve 导入linux

eve 导入linux

mkdir /opt/unetlab/addons/qemu/linux-centos7 cd /opt/unetlab/addons/qemu/linux-centos7 上传hda.qcow2 /opt/unetlab/wrappers/unl_wrapper -a fixpermissions Linux images - (eve-ng.net) Due to very high demand of this section and problems with how to crea…
阅读更多...
最新文章

Copyright @ 2022~2023