C++之list容器介绍及使用方式

目录
  • 一、list底层结构
  • 二、构造方法
    • 构造函数
    • 拷贝构造函数
  • 三、元素访问和迭代器
    • back&front
    • 三种遍历方式
  • 四、元素修改
    • 尾插、头插、尾删、头删
    • insert、erase
    • swap
    • resize
  • 五、特殊操作
    • remove
    • remove_if
    • unique、sort
    • reverse
  • 六、list迭代器失效问题
  • 七、vector与list对比
  • 总结

一、list底层结构

list底层是带头节点的双向循环链表

  • 双向：可以从前往后，也可以从后往前遍历
  • 循环：找尾节点的时间复杂度为O( 1 )
  • 带头节点：代码实现简单，不用考虑链表为空等特殊情况，可令end()迭代器指向头节点的位置

二、构造方法

构造函数

list<int> l1;
list<int> l2(5, 3);
//迭代器
vector<int> v{ 1,2,3,4,5 };
list<int> l3(v.begin(), v.end());
//C++11
list<int> l4{ 1,2,3,4,5 };

拷贝构造函数

利用l1拷贝构造l2

list<int> l1{ 1,2,3,4,5 };
list<int> l2(l1);

三、元素访问和迭代器

back&front

list<int> l1{ 1,2,3,4,5 };
cout << l1.front() << endl;
cout << l1.back() << endl;

三种遍历方式

list<int> l1{ 1,2,3,4,5 };

采用下面三种方式对下面这个list<int>类型的对象进行遍历打印：

1.迭代器

list<int>::iterator it = l1.begin();
for (it; it != l1.end(); it++)
{
	cout << *it << " ";
}
cout << endl;

打印结果：

2.范围for

注意这里e是int类型，不用再进行解引用

//范围for
for (auto e : l1)
{
	cout << e << " ";
}
cout << endl;

打印结果：

3.反向迭代器

list<int>::reverse_iterator rit = l1.rbegin();
for (rit; rit != l1.rend(); rit++)
{
	cout << *rit << " ";
}
cout << endl;

打印结果：

四、元素修改

尾插、头插、尾删、头删

insert、erase

list支持任意位置的插入，注意list对象的迭代器不支持加减数字，因为其底层空间不连续，如图：

如果要往一个位置进行插入，可以通过find函数返回位置进行，find是一个通用的函数模板，返回值是传入参数的迭代器类型，

list<int> l1{ 1,2,3,4,5 };
l1.insert(find(l1.begin(), l1.end(), 3), 10);//任意位置插入
l1.erase(find(l1.begin(), l1.end(), 10), l1.end());//任意位置的删除

swap

list内置的交换函数

list<int> l1{ 1,2,3,4,5 };
list<int> l2{ 5,6,7,8,9 };
l1.swap(l2);

resize

resize改变有效元素的个数，多的元素用第resize二个参数填充，如果没有给第二个参数，则默认用T()。

list<int> l1{ 0,1,2 };
l1.resize(5, 3);

五、特殊操作

remove

删除值为value的元素

list<int> l1{ 3,0,1,3,2,3 };
l1.remove(3);

remove_if

remove_if的参数是一个判断条件，可以是函数指针或者函数对象

//判断5的倍数
bool MultipleFive(int n)
{
	return 0 == n % 5;
}

void Test10()
{
	//此处传递函数指针
	list<int> l1{ 10,0,1,3,5,7,20 };
	l1.remove_if(MultipleFive);
}

unique、sort

unique，去重，删除所有重复元素，使用unique之前要先调用sort进行排序，这里的sort是list内置的sort，不是标准库中的sort

void Test()
{
	list<int> l1{ 1,3,3,5,4,0,2,5,4 };
	l1.sort();//默认升序
	l1.unique();//删除重复元素
}

结果：

对于sort的使用，还可以自定义函数，并将函数指针作为参数传递给sort函数进行排序：

reverse

对链表进行逆置

void Test()
{
	list<int> l1{ 1,3,5,7,9 };
	l1.reverse();
}

结果：

六、list迭代器失效问题

list底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

erase导致的迭代器失效

如图所示，it迭代器所指向的位置被删除后，迭代器失效：

改正方法：

while (it != l1.end())
{
	//it=l1.erase(it);
	l1.erase(it++);
}

这里 l1.erase(it++)语句也能达到效果，因为后置++会将自增后的结果保存在临时变量中，而前置则不可以。

resize导致的迭代器失效

resize减少有效元素个数也会导致迭代器失效：

list<int> l1{ 1,3,5,7,9 };
auto it = l1.end();
l1.resize(3);

上面这个程序中，reseze减少有效元素个数后，it指向的位置元素已经被删除，迭代器失效，如果再使用该迭代器，则会出错。

七、vector与list对比

vector（动态顺序表）

list（带头结点的双向循环链表）

对比 vector list
底层结构 动态顺序表，连续空间 带头结点的双向循环链表
访问 支持随机访问，首地址+下标 不能随机访问，可通过find查找，访问随即元素时间复杂度O(N)
插入删除 任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低 任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1)
空间利用率 底层为连续空间，不容易造成内存碎片，空间利用率较高，缓存利用率高。可以一次将一个数据附近的空间都加载到缓存，不用频繁地从内存读取数据 底层节点动态开辟，容易造成内存碎片，空间利用率低，缓存利用率低
迭代器 原生态指针 对指针进行了封装
迭代器失效 容量相关的操作都有可能导致迭代器失效，如插入引起的扩容，删除元素等 插入元素不会导致迭代器失效，删除节点会导致，且只影响当前迭代器，其他迭代器不受影响
使用场景 不关心插入和删除效率，支持随机访问 大量插入和删除操作，不关心随机访问的场景

总结

以上为个人经验，希望能给大家一个参考，也希望大家多多支持我们。

赞 (0)

相关推荐

  • 利用C++模拟实现STL容器:list

    目录 一.list的介绍 二.list的排序 三.迭代器 1.list的迭代器失效问题 2.迭代器的功能分类 3.list迭代器的模拟实现 4.迭代器价值 5.迭代器operator->的重载 四.模拟实现时遇到的困惑及注意点 五.vector和list的优缺点 1.vector 2.list 六.模拟实现list整体代码 一.list的介绍 列表是一种顺序容器,它允许在序列中的任何位置执行常量时间插入和删除操作,并允许在两个方向上进行迭代. 它的底层是一个带头双向循环链表.附一篇博主用C语言写

  • C++语言 STL容器list总结

    在使用std::list<>链表时,难免会对数据进行添加删除操作.而遍历链表则有两种方式:通过索引访问,象数组一样处理:通过std::list<>::iterator链表遍历器进行访问 STL 中的list 就是一 双向链表,可高效地进行插入删除元素. list不支持随机访问.所以没有 at(pos)和operator[]. list 对象list1, list2 分别有元素list1(1,2,3),list2(4,5,6) .list< int>::iterator

  • c++ STL容器总结之:vertor与list的应用

    STL提供六大组件,彼此可以组合套用 1.容器(containers):各种数据结构,如vertor,list,deque,set,map.从实现的角度来看,STL容器是一种class template 2.算法(algorithms):各种算法如sort,search,copy,earse.STL算法是一种 function template. 3.迭代器(iterators):扮演容器与算法之间的胶合剂,是所谓的"泛型指针".所有STL容器都有自己的专属的迭代器. 4.仿函数(fu

  • C++List容器常用函数接口刨析

    目录 一.基本结构 二.list的迭代器的构造 三.迭代器的实现 四.insert,erase 五.push_back,push_front,pop_back,pop_front 六.构造函数与赋值重载 七.析构与清空 一.基本结构 由源代码可知,list容器是有一个带头双向循环链表实现,所以我们模拟实现也需要实现一个带头双向循环链表的数据结构. template<class T> struct list_node { list_node<T>* _next; list_node&

  • C++顺序容器(vector、deque、list)的使用详解

    目录 一:STL(Standard Template Library),即标准模板库,是一个高效的C++程序库 二:STL组件 三:容器 四:类型成员 五:迭代器 六:顺序容器 七:顺序容器--向量(vector) 八:顺序容器--双端队列--deque 九:顺序容器 --列表--list 一:STL(Standard Template Library),即标准模板库,是一个高效的C++程序库 1.从实现层次看,整个STL是以一种类型参数化(type parameterized)的方式实现的,基

  • c++容器list、vector、map、set区别与用法详解

    c++容器list.vector.map.set区别 list 封装链表,以链表形式实现,不支持[]运算符. 对随机访问的速度很慢(需要遍历整个链表),插入数据很快(不需要拷贝和移动数据,只需改变指针的指向). 新添加的元素,list可以任意加入. vector 封装数组,使用连续内存存储,支持[]运算符. 对随机访问的速度很快,对头插元素速度很慢,尾插元素速度很快 新添加的元素,vector有一套算法. map 采用平衡检索二叉树:红黑树 存储结构为键值对<key,value> set 采用

  • C++之list容器介绍及使用方式

    目录 一.list底层结构 二.构造方法 构造函数 拷贝构造函数 三.元素访问和迭代器 back&front 三种遍历方式 四.元素修改 尾插.头插.尾删.头删 insert.erase swap resize 五.特殊操作 remove remove_if unique.sort reverse 六.list迭代器失效问题 七.vector与list对比 总结 一.list底层结构 list底层是带头节点的双向循环链表 双向:可以从前往后,也可以从后往前遍历 循环:找尾节点的时间复杂度为O(

  • 基于spring三方包类注入容器的四种方式小结

    如果引用第三方jar包,肯定是不能直接使用常用注解@Controller.@Service.@Repository.@Component将类的实例注入到spring容器中.以下四种方法可以向spring容器中导入三方包中类实例 . 1 xml配置 这种情况大家用的比较多,就是在spring的xml文件中配置需要导入的bean.在springweb项目工程web.xml中 ContextLoaderListener或者DispatcherServlet的初始参数contextConfigLocat

  • Java并发容器介绍

    Java并发容器介绍

    目录 1.原子类 2.锁 3.并发容器 4.List接口下 5.Map接口下 6.Set接口下 7.Queue接口下 Java并发包(concurrent)是Java用来处理并发问题的利器,该并发包中主要有原子类,锁(lock),并发容器类等等.本系列博客主要就是介绍并发包中一些常用的并发容器,常用的类.那么就让我们一起来揭开并发包的面纱吧. 环境: 基于JDK1.8 1.原子类 首先登场的就是我们的原子类.啥是原子类?原子类用啥用? 第一个问题,啥是原子类:操作具有原子性的类,我们称之为原子类

  • WPF布局及布局容器介绍

    WPF布局及布局容器介绍

    WPF布局基础 WPF布局原则 一个窗口中只能包含一个元素 不应显示设置元素尺寸 不应使用坐标设置元素的位置 可以嵌套布局容器 WPF布局容器 StackPanel: 水平或垂直排列元素.Orientation属性分别: Horizontal / Vertical WrapPanel : 水平或垂直排列元素.针对剩余空间不足会进行换行或换列进行排列 DockPanel : 根据容器的边界.元素进行Dock.Top.Left.Right.Bottom设置 Grid : 类似table表格.可灵活设

  • MySQL索引介绍及优化方式

    MySQL索引介绍及优化方式

    目录 一.导致sql执行慢的原因 二.分析原因时,一定要找切入点 三.什么是索引? 四.Explain分析 1.id 2.select_type 3.table 4.type(★) 5.possible_key 6.key(★) 7.key_len 8.ref(★) 9.rows(★) 10.extra 五.优化案例 六.是否需要创建索引? 一.导致sql执行慢的原因 硬件条件限制: io吞吐量小,形成瓶颈(读取磁盘数据) 网络传输速度慢 内存不足(读取磁盘数据加载到内存) 程序设计方面: 没有

  • SpringBoot AOP AspectJ切面技术介绍与实现方式

    目录 AspectJ简介 什么是AspectJ 实现AOP的方式 原生使用切面 通过注解使用切面 AspectJ简介 它不属于spring: AspectJ是一个AOP的框架: 定义了AOP语法: 有一个专门的编译器用来生成遵守Java字节编码规范的Class文件 Spring AOP 回顾 什么是AspectJ AspectJ是使用面向切面的一个框架 它扩展了Java语言(它本身也是一种语言) 支持原生Java代码 有自己的编译器 将代码翻译成Java字节码文件 是为了方便编写AOP代码而出现

  • 简单介绍HTTP请求方式中8种请求方法

    简单介绍 HTTP是超文本传输协议,其定义了客户端与服务器端之间文本传输的规范.HTTP默认使用80端口,这个端口指的是服务端的端口,而客户端使用的端口是动态分配的.当我们没有指定端口访问时,浏览器会默认帮我们添加80端口.我们也可以自己指定访问端口如:http://www.ip138.com:80. 需要注意的是,现在大多数访问都使用了HTTPS协议,而HTTPS的默认端口为443,如果使用80端口访问HTTPS协议的服务器可能会被拒绝. HTTP请求的方法:HTTP/1.1协议中共定义了八种

  • WPF中常用的布局容器介绍

    WPF中常用的布局容器介绍

    目录 一.简介 二.代码案例 1.Border 2.StackPanel 3.WrapPanel 4.DockPanel 5.Grid 6.UniformGrid 7.Canvas 8.ScrollViewer 一.简介 所有的WPF布局容器都派生自System.Windows.Controls.Panel.Panel继承自FrameworkElement. 在Panel中有一个比较重要的属性是UIElementCollection 类型的Children属性,UIElementCollecti

  • docker入门之容器介绍

    docker概述 docker是一个开源的软件部署解决方案: docker也是轻量级的应用容器框架: docker可以打包.发布.运行任何的应用,这个也是docker的产品理念:Docker - Build, Ship, and Run Any App, Anywhere docker采用的是LXC(Namespace+CGroups),即在Linux内核的Namespace[资源隔离]和CGroups[资源控制]技术的基础上通过镜像管理机制来实现轻量化设计. docker组成 docker的组

  • c#中WebService的介绍及调用方式小结

    c#中WebService的介绍及调用方式小结

    前言 之前做移动端开发,都不清楚WebService是啥东东,现在接触c#,项目中有三处WebService调用,就不得不与其打交道了,最近碰上第三方接口地址更换,而自己项目因功能也需要增加WebService方法,所以了解了下WebService及其调用. C-sharp in itlao5.com 一.概念 Web Service也叫XML Web Service WebService是一种可以接收从Internet或者Intranet上的其它系统中传递过来的请求,轻量级的独立的通讯技术.是

随机推荐