首页
学习
活动
专区
工具
TVP
发布

STLlist的使用

2、list的数据结构 list本身与list节点,这两个是完全不同的结构,是需要分开来设计的,对于一个list节点来说,由于list是双向环状链表(双向带头循环链表),所以需要提供两个指针,一个指向前一个元素...如下所示为SGI版本的list底层(稍作修改,便于学习): //list节点 template struct _list_node { _list_node* _prev;//...这里我们先了解其使用即可: 3、list的使用 在使用前,需要包含头文件 3.1、构造相关 3.1.1、构造一个空容器 list l;//构造一个存储元素为int类型的空list...这里,begin与end分别指向list中第一个有效元素,以及最后一个有效元素的下一个位置,而我们的begin与end区间,通常都是左闭右开,对于环状的链表来说,只需要在尾端加入一个空白节点,便符合STL...这里list由于不像vector那样,vector的插入操作可能会引起扩容,从而导致迭代器失效,而list则不会,因为list的底层结构为带头结点的双向循环链表,因此在list中进行插入时是不会导致list

14330
您找到你想要的搜索结果了吗?
是的
没有找到

走近STL -- 你好,List

1、你好,List 从实现层面看,相较于Vector的线性空间,List的实现要复杂的多。 List的优势在于每次插入或删除一个元素,就分配或释放一个位置。...因此,List对于空间的把控有绝对的精准。 而且,对于从任何节点增删数据,List消耗的永远是常数时间。 List和Vector的使用应该视元素的多寡、元素的构造复杂度、元素的存取频繁度而定。...List优在存取,Vector优在查询。 2、List节点 每一个自己写过链表的人都知道,链表的节点和链表本身是分开设计的。...那我们来看一下List的节点设计: template struct __list_node { typedef void* void_pointer; void_pointer...3、List基本函数使用 创 #include typedef struct rect { ··· }Rect; listtest; //声明一个链表,用于存放结构体数据

34230

【C++】STL---list

STL---list 一、list 的介绍 list 是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。...list 与 forward_list 非常相似:最主要的不同在于 forward_list 是单链表,只能朝前迭代,已让其更简单高效。...与其他序列式容器相比,list 和 forward_list 最大的缺陷是不支持任意位置的随机访问,比如:要访问 list 的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间开销...首先我们先创建一个自己的命名空间,把 list 节点的类,list 迭代器的类,list 类都放进去; 1. list 节点类 list 节点类如下,因为是双向链表,所以应该有一个数据,两个指针;...3. list 反向迭代器类 list 的反向迭代器可以复用 list 的正向迭代器,就不需要我们重新写一个反向迭代器的类了。

3710

STL源码解析--list揭秘

1 list简介 list也是最经常使用的一个容器,尤其是在对容器中的元素进行频繁的插入和删除时,通过指针操作使得list的插入和删除在常数时间内即可完成。...1.1 list数据节点 list是通过指针将不同的节点进行串联得到,因此在设计list的时候需要对节点进行单独定义,在新的STL list容器中对节点进行如下定义: //节点基类 struct _...List_node_base { _List_node_base* _M_next; _List_node_base* _M_prev; } //节点模板,继承基类 template<typename...1.2 list的迭代器 list管理的不是连续的内存空间,不能通过下标索引的方式访问,但是通过list提供的迭代器可以对list中的节点进行正确的访问。...STL的迭代器是双向链表,迭代器通过加或者减能够进行正确的访问list中的元素。在对迭代器进行操作时,同样会产生迭代器失效的问题,但是list的迭代器时候只指针对删除操作时指向被删除节点的迭代器失效。

13610

STLlist的模拟实现

放在专栏【C++知识总结】,会持续更新,期待支持 1、list数据结构 list是一个带有头节点的双向链表,list主要是由以下部分组成:list节点类、迭代器类、list本身 1.1、list节点类...关于list节点类,由于list本身是一个双向的链表,所以节点内必须包含指向前一个节点的指针、指向后一个节点的指针、用来存储数据的data。...如下所示,为list的节点设计: 1.2、迭代器类 list不能像vector那样以一个原生指针作为迭代器,这是因为list中各个节点并不是连续的,但是list中的迭代器必须要能够像“原生指针”那样,...=重载忘记填参数了,在后面实现时才发现,这里前面就懒得改了)  1.3、list本身 对于list本身来说,成员变量只需要一个头节点的指针,即可表示出整个双向链表,同时list还要提供插入、删除等相关函数接口...,以及多个形式构造函数的实现、同时链表节点的释放也是在list析构函数中实现的,并且list还要提供迭代器相关的一些函数,如下所示,为其list基本结构: 接下来,我们对这些接口一一进行模拟实现。

12440

STL list源码分析以及实现

STL list实现的三个模块节点__list_node,迭代器__list_iterator以及list本身(使用一个__list_node*代表整个链表)的介绍。 2....重点分析list的几个核心函数,理解STL list的实现原理,核心函数如下: list 的构造函数 基本的迭代器操作 插入操作 size, 析构函数等 3....STL list实现的三个模块 1.1 STL list节点 节点定义如下: template struct __list_node{ typedef __list_node...//为了更清晰的看list的定义,先省略其他的函数 } 2.2 list的构造函数 在给出list的构造函数之前,先给出,list内部的向空间配置申请节点的内存分配,以及在节点上面构造对象(...size_type n, const T& value){ fill_initialize(n, value); } 如下这个构造函数有点小问题,会创建一个临时对象,然后调用对象的copy构造函数,实际上STL

1.4K30

【C++】STL 模拟实现之 list

文章目录 一、list 的常用接口及其使用 1、list 一般接口 2、list 特殊接口 3、list 排序的性能分析 二、list 迭代器的实现 1、迭代器的分类 2、list 迭代器失效问题...除了上述 STL 容器基本都有的一般接口外,list 还提供一些独有的特殊操作接口,如下: -函数声明 -接口说明 splice 将 list1 中的元素转移到 list2 中 remove 移除 list...const_iterator; //STL源码中大佬的写法,利用多个模板参数来避免副本造成的代码冗余问题 template struct __list_iterator...; //typedef __list_iterator const_iterator; //STL源码中大佬的写法,利用多个模板参数来避免副本造成的代码冗余问题... iterator; //typedef __list_iterator const_iterator; //STL源码中大佬的写法

34900

STL vector list deque区别与实现

STL内部实现时,首先分配一个非常大的内存空间预备进行存储,即capacituy()函数返回的大小,当超过此分配的空间时再整体重新放分配一块内存存储,这给人以vector可以不指定vector即一个连续内存的大小的感觉...(3) 当动态添加的数据超过vector默认分配的大小时要进行整体的重新分配、拷贝与释放 2 list     双向链表     每一个结点都包括一个信息快Info、一个前驱指针Pre、一个后驱指针Post...vector.at()             (2) 相对于verctor占用内存多 3 deque    双端队列 double-end queue    deque是在功能上合并了vector和list...   缺点:(1) 占用内存多 使用区别:      1 如果你需要高效的随即存取,而不在乎插入和删除的效率,使用vector      2 如果你需要大量的插入和删除,而不关心随即存取,则应使用list...Cplusplus - Deque Cplusplus - Vector STL提供了三个最基本的容器:vector,list,deque

80540

C++ STL学习之【list的使用】

---- 前言 STL 中的 vector 存在头部及中部操作效率低的缺陷,需要另一种容器来弥补其短板,此时 list 就应运而生,list 是一个双向带头循环链表,是链表的终极形态,除了不支持下标的随机访问外...,其他方面效率都是极高的,本文将带大家认识、使用 list 容器 list 的结构示意图(双向带头循环链表) 出自 《STL源码剖析》 ---- ️正文 学习使用容器首先需要从 默认成员函数...入手 1、默认成员函数 1.1、构造 list 支持三种构造方式:默认构造、带参构造及迭代器区间构造 默认构造:生成一个 list 对象,此时只有一个头节点(哨兵位节点) 带参构造:初始化对象,内含... l1; //默认构造 list l2(10, 1); //带参构造 list l3(arr.begin(), arr.end()); //迭代器区间构造 cout...《list》 ---- 总结 以上就是本次关于 STL 中的 list 容器学习使用的全部内容了,list 相对于前两种容器来说比较特殊,值得细细研究,list 的核心内容在于其迭代器类的设计,将在下篇文章

13620

【C++修行之道】STL(初识list、stack)

一、list 1.1list的定义和结构 list的使用频率不高,在做题时极少遇到需要使用list的情景。 ist是一种双向链表容器,它是标准模板库(STL)提供的一种序列容器。...list容器的定义和结构如下: template >class list; list容器模板接受两个参数: T:...list与其他标准序列容器(array,vector和deque)相比,list通常可以在容器内的任何位置插入、提取和移动元素。...list与其他标准序列容器(array,vector和deque)相比,list和forward_list(单链表实现)的主要缺点是他们不能通过位置直接访问元素;例如,要访问列表中的第五个元素,必须从已知位置...以下是一个示例,展示如何使用list容器: #include #include using namespace std; int main() { list<int

13510
领券