面试之快速学习STL-容器适配器

1. 容器适配器

简单的理解容器适配器，其就是将不适用的序列式容器（包括 vector、deque 和 list）变得适用。
在这里插入图片描述

注意：默认使用的基础容器不代表一定只能用它，比如queue可以用deque，list。

如果你希望你的queue是list那么可以如下创建：

std::queue<int , std::list<int>> q;

可以直接通过 queue 容器适配器来初始化另一个 queue 容器适配器，只要它们存储的元素类型以及底层采用的基础容器类型相同即可。例如：

std::deque<int> values{1,2,3};
std::queue<int> my_queue1(values);
std::queue<int> my_queue(my_queue1);
//或者使用
//std::queue<int> my_queue = my_queue1;

2. priority_queue容器适配器详解

  1. priority_queue 容器适配器模拟的也是队列这种存储结构，即使用此容器适配器存储元素只能“从一端进（称为队尾），从另一端出（称为队头）”，且每次只能访问 priority_queue 中位于队头的元素。
  2. 但是，priority_queue 容器适配器中元素的存和取，遵循的并不是 “First in,First out”（先入先出）原则，而是“First in，Largest out”原则。直白的翻译，指的就是先进队列的元素并不一定先出队列，而是优先级最大的元素最先出队列。
  3. priority_queue 容器适配器中存储的元素，优先级是如何评定的呢？很简单，每个 priority_queue 容器适配器在创建时，都制定了一种排序规则。根据此规则，该容器适配器中存储的元素就有了优先级高低之分。
  4. 假设当前有一个 priority_queue 容器适配器，其制定的排序规则是按照元素值从大到小进行排序。根据此规则，自然是 priority_queue 中值最大的元素的优先级最高。
  5. priority_queue 容器适配器为了保证每次从队头移除的都是当前优先级最高的元素，每当有新元素进入，它都会根据既定的排序规则找到优先级最高的元素，并将其移动到队列的队头；同样，当 priority_queue 从队头移除出一个元素之后，它也会再找到当前优先级最高的元素，并将其移动到队头。
template <typename T, typename Container=std::vector<T>, typename Compare=std::less<T> >
class priority_queue {
//......
}
  1. 可以看到，priority_queue 容器适配器模板类最多可以传入 3 个参数，它们各自的含义如下：
  • typename T：指定存储元素的具体类型；
  • typename Container：指定 priority_queue 底层使用的基础容器，默认使用 vector 容器。
  • typename Compare：指定容器中评定元素优先级所遵循的排序规则，默认使用std::less 按照元素值从大到小进行排序，还可以使用std::greater按照元素值从小到大排序，但更多情况下是使用自定义的排序规则。
  1. 作为 priority_queue 容器适配器的底层容器，其必须包含 empty()、size()、front()、push_back()、pop_back() 这几个成员函数，STL 序列式容器中只有 vector 和 deque 容器符合条件。

创建priority_queue

//以使用普通数组或其它容器中指定范围内的数据，对 priority_queue 容器适配器进行初始化：
int values[]{4,1,3,2};
std::priority_queue<int> copy_values(values, values+4); // 4,3,2,1//使用序列式容器
std::vector<int> vec{1,5,3,4,2}
std::priority_queue<int> pq(vec.begin(), vec.end()); // 5,4,3,2,1
  1. 用来初始化的数组或容器中的数据不需要有序，priority_queue 会自动对它们进行排序。
//还可以手动指定 priority_queue 使用的底层容器以及排序规则，比如std::vector<int> vec{1,5,3,4,2};
std::priority_queue<int, std::vector<int>, std::greater<int>> pq(vec.begin(), vec.end());
  1. 注意不支持
std::priority_queue<int, std::vector<int>, std::greater<int>> pq1{2,3,4,1,5};

在这里插入图片描述

  1. 和 queue 一样，priority_queue 也没有迭代器，因此访问元素的唯一方式是遍历容器，通过不断移除访问过的元素，去访问下一个元素。
    std::vector<int> vec1{1,5,3,4,2};std::priority_queue<int, std::vector<int>, std::greater<int>> pq(vec1.begin(), vec1.end());while (!pq.empty()) {std::cout<< pq.top()<<std::endl;pq.pop();}/*12345*/

自定义比较函数-仿函数

  1. greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数，其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了），所以调用的是fun()?
//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;
  1. 如果自己想模拟less和greater，那么使用的方法应该是这样：
    std::priority_queue<int,std::vector<int>, myFun> pq3(vec1.begin(), vec1.end());while (!pq3.empty()) {std::cout<< pq3.top()<<std::endl;pq3.pop();}/*12345*/

自定义比较函数-重载运算符

  1. 如果是个自定义类，也可以在自定义类里面自己重载运算符
    std::priority_queue<tmp1> qp2;tmp1 t1{2};tmp1 t11{3};tmp1 t111{1};tmp1 t1111{4};qp2.push(t1);qp2.push(t11);qp2.push(t111);qp2.push(t1111);while (!qp2.empty()) {std::cout<< qp2.top().x<<std::endl;qp2.pop();}/*54321*/
std::priority_queue<tmp1> qp2;

自定义比较函数-lambda

    auto cmp = [](int a, int b) -> bool { return a < b;};std::priority_queue<int, std::vector<int>, decltype(cmp)> pq4(vec1.begin(), vec1.end(),cmp);while (!pq4.empty()) {std::cout<< pq4.top()<<std::endl;pq4.pop();}/*54321*/

补充一个比较有意思的点

前面提到的自定义比较函数-lambda， 其实传入的是一个函数指针，什么意思呢？

你可以这样写效果是一样的：

    auto cmp = [](int a, int b)-> bool { return a < b; };std::priority_queue<int, std::vector<int>, std::function<bool(int,int)>> pq5(vec1.begin(), vec1.end(),  cmp);while (!pq5.empty()) {std::cout<< pq5.top()<<std::endl;pq5.pop();}

但是你不可以这样写：

    std::priority_queue<int, std::vector<int>, decltype(cmp(1,2))> pq4(vec1.begin(), vec1.end(),cmp);
//decltype(cmp(1,2))的到的是bool，而不是函数指针

小问题，好吧，是我理解的不够。

关于priority_queue的底层实现

本来准备单独用一章写，但是看了一下，其实底层实现就是一个堆，特点：

  1. heap是一颗完全二叉树：整颗树除了最底层，都是填满的，而且底层节点从左到右不存在空隙。
    在这里插入图片描述
  2. 两个操作
    • push_heap： 因为要满足完全二叉树的性质，需要将新节点放置在底层节点的最后面，也就是vector的end()，然后执行上溯操作：只要父节点比自己小，就不断调换自己和父节点的位置。
      在这里插入图片描述
    • pop_heap： 将heap的最大元素取走，也就是将根节点取走，那根据完全二叉树的性质，得把底层最后面的元素换到根节点。然后不断执行下溯操作：将自己和两个子节点中，较大的那个对调。

做完下溯操作后，可能还需做一次上溯操作

在这里插入图片描述
参考： https://blog.csdn.net/youaremyalllove/article/details/124043310

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

perl下载与安装教程【工具使用】

perl下载与安装教程【工具使用】

Perl是一个高阶程式语言&#xff0c;由 Larry Wall和其他许多人所写&#xff0c;融合了许多语言的特性。它主要是由无所不在的 C语言&#xff0c;其次由 sed、awk&#xff0c;UNIX shell 和至少十数种其他的工具和语言所演化而来。Perl对 process、档案&#xff0c;和文字有很强…
阅读更多...
【腾讯云Cloud Studio实战训练营】用Vue+Vite快速构建完成交互式3D小故事

【腾讯云Cloud Studio实战训练营】用Vue+Vite快速构建完成交互式3D小故事

&#x1f440;前置了解&#xff1a;(官网 https://cloudstudio.net/) 什么是Cloud Studio&#xff1f; Cloud Studio 是基于浏览器的集成式开发环境&#xff08;IDE&#xff09;&#xff0c;为开发者提供了一个永不间断的云端工作站。用户在使用 Cloud Studio 时无需安装&#…
阅读更多...
通讯录的实现

通讯录的实现

> 作者简介&#xff1a;დ旧言~&#xff0c;目前大一&#xff0c;现在学习Java&#xff0c;c&#xff0c;c&#xff0c;Python等 > 座右铭&#xff1a;松树千年终是朽&#xff0c;槿花一日自为荣。 > 望小伙伴们点赞&#x1f44d;收藏✨加关注哟&#x1f495;&#x1…
阅读更多...
谷歌推出首款量子弹性 FIDO2 安全密钥

谷歌推出首款量子弹性 FIDO2 安全密钥

谷歌在本周二宣布推出首个量子弹性 FIDO2 安全密钥&#xff0c;作为其 OpenSK 安全密钥计划的一部分。 Elie Bursztein和Fabian Kaczmarczyck表示&#xff1a;这一开源硬件优化的实现采用了一种新颖的ECC/Dilithium混合签名模式&#xff0c;它结合了ECC抵御标准攻击的安全性和…
阅读更多...
Tomcat 一次请求的生命周期

Tomcat 一次请求的生命周期

在使用 Tomcat 的时候&#xff0c;我们只需要在 Servlet 实现类中写我们的业务逻辑代码即可&#xff0c;不需要管 Socket 连接、协议处理要怎么实现&#xff0c;因为这部分作为不经常变动的部分&#xff0c;被封装到了 Tomcat 中&#xff0c;程序员只需要引入 Tomcat 中即可&am…
阅读更多...
【LeetCode-中等题】49. 字母异位词分组

【LeetCode-中等题】49. 字母异位词分组

题目 题解一:排序哈希表 思路:由于互为字母异位词的两个字符串包含的字母相同&#xff0c;因此对两个字符串分别进行排序之后得到的字符串一定是相同的&#xff0c;故可以将排序之后的字符串作为哈希表的键。 核心api: //将字符串转换为字符数组char[] ch str.toCharArray();…
阅读更多...
页面滑动到可视区域加载更多内容思维流程

页面滑动到可视区域加载更多内容思维流程

页面滑动到可视区域加载更多内容思维流程
阅读更多...
GEEMAP 中如何拉伸图像

GEEMAP 中如何拉伸图像

图像拉伸是最基础的图像增强显示处理方法&#xff0c;主要用来改善图像显示的对比度&#xff0c;地物提取流程中往往首先要对图像进行拉伸处理。图像拉伸主要有三种方式&#xff1a;线性拉伸、直方图均衡化拉伸和直方图归一化拉伸。 GEE 中使用 .sldStyle() 的方法来进行图像的…
阅读更多...
Android岗位技能实训室建设方案

Android岗位技能实训室建设方案

一 、系统概述 Android岗位技能作为新一代信息技术的重点和促进信息消费的核心产业&#xff0c;已成为我国转变信息服务业的发展新热点&#xff1a;成为信息通信领域发展最快、市场潜力最大的业务领域。互联网尤其是移动互联网&#xff0c;以其巨大的信息交换能力和快速渗透能力…
阅读更多...
机器学习编译系列---张量程序抽象

机器学习编译系列---张量程序抽象

机器学习编译系列---张量程序抽象 1. 张量函数概念的引入与抽象的必要性 1. 张量函数概念的引入与抽象的必要性 在文章机器学习编译系列—概述中提到&#xff0c;机器学习编译的一个很重要操作是做等价变换来减少内存或者提高运行效率。变换是以“元张量函数”(private tensor …
阅读更多...
Viewpager2+Fragment+指示器

Viewpager2+Fragment+指示器

Viewpager2Fragment指示器 效果展示&#xff1a; MainActivity.java package com.huawei.myviewpager;import androidx.appcompat.app.AppCompatActivity; import androidx.fragment.app.Fragment; import androidx.viewpager2.widget.ViewPager2;import android.os.Bundle; …
阅读更多...
小白到运维工程师自学之路 第七十五集 （Kubernetes 企业级高可用部署）2

小白到运维工程师自学之路 第七十五集 （Kubernetes 企业级高可用部署）2

8、添加master节点 在k8s-master2和k8s-master3节点创建文件夹 mkdir -p /etc/kubernetes/pki/etcd在k8s-master1节点执行 从k8s-master1复制密钥和相关文件到k8s-master2和k8s-master3 scp /etc/kubernetes/admin.conf root192.168.77.15:/etc/kubernetes scp /etc/kubernet…
阅读更多...
jmap（Memory Map for Java）Java内存映像工具

jmap（Memory Map for Java）Java内存映像工具

jmap&#xff08;Memory Map for Java&#xff09;Java内存映像工具 jmap&#xff08;Memory Map for Java&#xff09;命令用于生成堆转储快照&#xff08;一般称为heapdump或dump文件&#xff09; 如果不使用jmap命令&#xff0c;要想获取Java堆转储快照也还有一些比较“暴…
阅读更多...
RabbitMq:Topic exchange(主题交换机)的理解和使用

RabbitMq:Topic exchange(主题交换机)的理解和使用

RabbitMq:Topic exchange(主题交换机)的理解和使用 在RabbitMq中&#xff0c;生产者的消息都是通过交换机来接收&#xff0c;然后再从交换机分发到不同的队列中去&#xff0c;在分发的过程中交换机类型会影响分发的逻辑&#xff0c;下面主要讲解一下主题交换机。 ​ 主题交换…
阅读更多...
2023面试八股文 ——Java基础知识

2023面试八股文 ——Java基础知识

Java基础知识 一.Java概述何为编程什么是Javajdk1.5之后的三大版本JVM、JRE和JDK的关系什么是跨平台性&#xff1f;原理是什么Java语言有哪些特点什么是字节码&#xff1f;采用字节码的大好处是什么什么是Java程序的主类&#xff1f;应用程序和小程序的主类有何不同&#xff1f…
阅读更多...
数据结构之并查集

数据结构之并查集

并查集 1. 并查集原理2. 并查集实现3. 并查集应用3.1 省份数量3.2 等式方程的可满足性 4. 并查集的优缺点及时间复杂度 1. 并查集原理 并查表原理是一种树型的数据结构&#xff0c;用于处理一些不相交集合的合并及查询问题。并查集的思想是用一个数组表示了整片森林&#xff0…
阅读更多...
微服务中间件--微服务保护

微服务中间件--微服务保护

微服务保护 微服务保护a.sentinelb.sentinel限流规则1) 流控模式1.a) 关联模式1.b) 链路模式 2) 流控效果2.a) 预热模式2.b) 排队等待 3) 热点参数限流 c.隔离和降级1) Feign整合Sentinel2) 线程隔离2.a) 线程隔离&#xff08;舱壁模式&#xff09; 3) 熔断降级3.a) 熔断策略-慢…
阅读更多...
21-注意点说明:scoped样式冲突 / data

21-注意点说明:scoped样式冲突 / data

组件的三大组成部分 - 注意点说明 组件的样式冲突 scoped 默认情况:写在组件中的样式会 全局生效 -> 因此很容易造成多个组件之间的样式冲突问题 1.全局样式: 默认组件中的样式会作用到全局 2.局部样式: 可以给组件加上 scoped 属性,可以让样式只作用于当前组件 scoped原理…
阅读更多...
构建去中心化微服务集群，满足高可用性和高并发需求的实践指南！

构建去中心化微服务集群，满足高可用性和高并发需求的实践指南！

随着互联网技术的不断发展&#xff0c;微服务架构已经成为了开发和部署应用程序的一种主流方式。然而&#xff0c;当应用程序需要满足高可用性和高并发需求时&#xff0c;单一中心化的微服务架构可能无法满足性能和可靠性的要求。因此&#xff0c;构建一个去中心化的微服务集群…
阅读更多...
岩土工程安全监测隧道中使用振弦采集仪注意要点？

岩土工程安全监测隧道中使用振弦采集仪注意要点？

岩土工程安全监测隧道中使用振弦采集仪注意要点&#xff1f; 岩土工程的安全监测是非常重要的&#xff0c;它可以帮助工程师及时发现可能存在的问题&#xff0c;并及时解决&#xff0c;保障施工进度以及施工质量&#xff0c;保障工程的安全运行。其中&#xff0c;振弦采集仪是…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023