从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)(中)

简介: 从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)

从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)(上):https://developer.aliyun.com/article/1521883

3. deque的介绍(了解)

deque :双端队列 - double ended queue

可以发现它的接口很多,有[ ] 也有头删。

deque 是一种双开口的 "连续" 空间的数据结构,

deque 可以在头尾两端进行插入和删除操作。且时间复杂度为O(1),


与 vector 相比,头插效率高,不需要搬移元素,与 list 相比,deque 的空间利用率更高。

3.1 deque的实现原理

deque 并不是真正连续的空间,而是由一段段连续的小空间拼接而成的。

实际的 deque 类似于一个动态的二维数组,其底层结构如下所示:

双端队列底层是一个假想的连续空间,实际是分段连续的,

为了维护其 "整体连续" 、以及随机访问的假象,其重任落在了 deque 的迭代器身上。

因此 deque 的迭代器设计就尤为复杂,如下图所示:


那 deque 是如何借助其他迭代器维护其假想连续的结构的呢?

3.2 deque的缺陷和使用场景

deque 有点像 vector 和 list ,我们把 vector 和 list 也拉出来进行优缺点的对比再合适不过了:

那什么场景适合用 deque 呢?


虽然不够极致但是还是有用武之地的:大量头尾插入删除,偶尔随机访问的情况可以使用 deque。


前面说到:在 stack 和 queue 的实现上,是选择 deque 作为底层默认容器的。


为什么选择 deque 作为 stack 和 queue 的底层默认容器?


① stack 是一种后进先出的特殊线性数据结构,因此只要具有 push_back() 和 pop_back() 操作的线性结构,都可以作为 stack 的底层容器,比如 vector 和 list 都可以。


② queue 是先进先出的特殊线性数据结构,只要具有 push_back() 和 pop_front() 操作的线性结构,都可以作为 queue 的底层容器,比如 list 。


但 STL 最终选择用 deque 作为 stack 和 queue 的底层容器,其主要原因是如下:


stack 和 queue 不需要遍历(因此 stack 和 queue 没有迭代器),


只需要在固定的一端或者两端进行操作。

在 stack 中元素增长时,deque 比 vector 的效率高(扩容时不需要搬移大量数据);


queue  中的元素增长时,deque 不仅效率高,而且内存使用率高。


结合了 deque 的优点,而完美的避开了其缺陷。

4.1 priority_queue的介绍

priority_queue的底层就是以前数据结构学的堆:

数据结构与算法⑪(第四章_中)堆的分步构建_GR C的博客-CSDN博客

https://cplusplus.com/reference/queue/priority_queue/

优先队列是一种容器适配器,根据严格的弱排序标准,


它的第一个元素总是它所包含的元素中最大的。

此上下文类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素


(优先队列中位于顶部的元素)。

优先队列被实现为容器适配器,容器适配器即将特定容器类封装作为其底层容器类,


queue提供一组特 定的成员函数来访问其元素。元素从特定容器的“尾部”弹出,


其称为优先队列的顶部。

标准容器类 vector 和 deque 满足这些需求。默认情况下,


如果没有为特定的 priority_queue 类实例化指 定容器类,则使用 vector。

需要支持随机访问迭代器,以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap 和 pop_heap 来自动完成此操作。

底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。


容器应该可以通过随机访问迭代器访问,并支持以下操作:


empty():检测容器是否为空

size():返回容器中有效元素个数

front():返回容器中第一个元素的引用

push_back():在容器尾部插入元素

pop_back():删除容器尾部元素

从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)(下):https://developer.aliyun.com/article/1521890?spm=a2c6h.13148508.setting.24.712b4f0eDngT44

目录
相关文章
|
1天前
|
存储 缓存 C++
C++ 容器全面剖析:掌握 STL 的奥秘,从入门到高效编程
C++ 标准模板库(STL)提供了一组功能强大的容器类,用于存储和操作数据集合。不同的容器具有独特的特性和应用场景,因此选择合适的容器对于程序的性能和代码的可读性至关重要。对于刚接触 C++ 的开发者来说,了解这些容器的基础知识以及它们的特点是迈向高效编程的重要一步。本文将详细介绍 C++ 常用的容器,包括序列容器(`std::vector`、`std::array`、`std::list`、`std::deque`)、关联容器(`std::set`、`std::map`)和无序容器(`std::unordered_set`、`std::unordered_map`),全面解析它们的特点、用法
C++ 容器全面剖析:掌握 STL 的奥秘,从入门到高效编程
|
3月前
|
存储 设计模式 C++
【C++】优先级队列(容器适配器)
本文介绍了C++ STL中的线性容器及其适配器,包括栈、队列和优先队列的设计与实现。详细解析了`deque`的特点和存储结构,以及如何利用`deque`实现栈、队列和优先队列。通过自定义命名空间和类模板,展示了如何模拟实现这些容器适配器,重点讲解了优先队列的内部机制,如堆的构建与维护方法。
63 0
|
6天前
|
Ubuntu API 网络虚拟化
ubuntu22 编译安装docker,和docker容器方式安装 deepseek
本脚本适用于Ubuntu 22.04,主要功能包括编译安装Docker和安装DeepSeek模型。首先通过Apt源配置安装Docker,确保网络稳定(建议使用VPN)。接着下载并配置Docker二进制文件,创建Docker用户组并设置守护进程。随后拉取Debian 12镜像,安装系统必备工具,配置Ollama模型管理器,并最终部署和运行DeepSeek模型,提供API接口进行交互测试。
131 15
|
1月前
|
Ubuntu NoSQL Linux
《docker基础篇:3.Docker常用命令》包括帮助启动类命令、镜像命令、有镜像才能创建容器,这是根本前提(下载一个CentOS或者ubuntu镜像演示)、容器命令、小总结
《docker基础篇:3.Docker常用命令》包括帮助启动类命令、镜像命令、有镜像才能创建容器,这是根本前提(下载一个CentOS或者ubuntu镜像演示)、容器命令、小总结
160 6
《docker基础篇:3.Docker常用命令》包括帮助启动类命令、镜像命令、有镜像才能创建容器,这是根本前提(下载一个CentOS或者ubuntu镜像演示)、容器命令、小总结
|
1月前
|
Kubernetes Linux 虚拟化
入门级容器技术解析:Docker和K8s的区别与关系
本文介绍了容器技术的发展历程及其重要组成部分Docker和Kubernetes。从传统物理机到虚拟机,再到容器化,每一步都旨在更高效地利用服务器资源并简化应用部署。容器技术通过隔离环境、减少依赖冲突和提高可移植性,解决了传统部署方式中的诸多问题。Docker作为容器化平台,专注于创建和管理容器;而Kubernetes则是一个强大的容器编排系统,用于自动化部署、扩展和管理容器化应用。两者相辅相成,共同推动了现代云原生应用的快速发展。
208 11
|
2月前
|
Ubuntu Linux 开发工具
docker 是什么?docker初认识之如何部署docker-优雅草后续将会把产品发布部署至docker容器中-因此会出相关系列文章-优雅草央千澈
Docker 是一个开源的容器化平台,允许开发者将应用程序及其依赖项打包成标准化单元(容器),确保在任何支持 Docker 的操作系统上一致运行。容器共享主机内核,提供轻量级、高效的执行环境。本文介绍如何在 Ubuntu 上安装 Docker,并通过简单步骤验证安装成功。后续文章将探讨使用 Docker 部署开源项目。优雅草央千澈 源、安装 Docker 包、验证安装 - 适用场景:开发、测试、生产环境 通过以上步骤,您可以在 Ubuntu 系统上成功安装并运行 Docker,为后续的应用部署打下基础。
96 8
docker 是什么?docker初认识之如何部署docker-优雅草后续将会把产品发布部署至docker容器中-因此会出相关系列文章-优雅草央千澈
|
2月前
|
存储 Kubernetes 开发者
容器化时代的领航者:Docker 和 Kubernetes 云原生时代的黄金搭档
Docker 是一种开源的应用容器引擎,允许开发者将应用程序及其依赖打包成可移植的镜像,并在任何支持 Docker 的平台上运行。其核心概念包括镜像、容器和仓库。镜像是只读的文件系统,容器是镜像的运行实例,仓库用于存储和分发镜像。Kubernetes(k8s)则是容器集群管理系统,提供自动化部署、扩展和维护等功能,支持服务发现、负载均衡、自动伸缩等特性。两者结合使用,可以实现高效的容器化应用管理和运维。Docker 主要用于单主机上的容器管理,而 Kubernetes 则专注于跨多主机的容器编排与调度。尽管 k8s 逐渐减少了对 Docker 作为容器运行时的支持,但 Doc
178 5
容器化时代的领航者:Docker 和 Kubernetes 云原生时代的黄金搭档
|
2月前
|
关系型数据库 应用服务中间件 PHP
实战~如何组织一个多容器项目docker-compose
本文介绍了如何使用Docker搭建Nginx、PHP和MySQL的环境。首先启动Nginx容器并查看IP地址,接着启动Alpine容器并安装curl测试连通性。通过`--link`方式或`docker-compose`配置文件实现服务间的通信。最后展示了Nginx配置文件和PHP代码示例,验证了各服务的正常运行。
85 3
实战~如何组织一个多容器项目docker-compose
|
2月前
|
监控 NoSQL 时序数据库
《docker高级篇(大厂进阶):7.Docker容器监控之CAdvisor+InfluxDB+Granfana》包括:原生命令、是什么、compose容器编排,一套带走
《docker高级篇(大厂进阶):7.Docker容器监控之CAdvisor+InfluxDB+Granfana》包括:原生命令、是什么、compose容器编排,一套带走
303 78
|
2月前
|
数据建模 应用服务中间件 nginx
docker替换宿主与容器的映射端口和文件路径
通过正确配置 Docker 的端口和文件路径映射,可以有效地管理容器化应用程序,确保其高效运行和数据持久性。在生产环境中,动态替换映射配置有助于灵活应对各种需求变化。以上方法和步骤提供了一种可靠且易于操作的方案,帮助您轻松管理 Docker 容器的端口和路径映射。
180 3

热门文章

最新文章