＜C++＞ STL_容器适配器

1.容器适配器

适配器是一种设计模式，该种模式是将一个类的接口转换成客户希望的另外一个接口。

容器适配器是STL中的一种重要组件，用于提供不同的数据结构接口，以满足特定的需求和限制。容器适配器是基于其他STL容器构建的，通过改变其接口和行为，使其适应不同的应用场景。

STL中有三种常见的容器适配器：stack、queue和priority_queue。

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque，比如：

在这里插入图片描述

在这里插入图片描述

而priority_queue默认使用vector

在这里插入图片描述

2.stack的介绍和使用

stack的介绍

  1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。

  2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。

  3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：

    • empty：判空操作

    • back：获取尾部元素操作

    • push_back：尾部插入元素操作

    • pop_back：尾部删除元素操作

  4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器， 默认情况下使用deque。

在这里插入图片描述

stack的使用

当你使用 std::stack 时，你可以使用以下一些重要的成员函数：

  1. push(const T& value): 将元素 value 压入栈顶。
  2. pop(): 弹出栈顶元素，不返回其值。
  3. top(): 返回栈顶元素的引用，但不将其从栈中移除。
  4. size(): 返回栈中元素的数量。
  5. empty(): 检查栈是否为空，返回布尔值。
  6. swap(stack& other): 将当前栈与另一个栈 other 进行交换。
#include <iostream>
#include <stack>int main() {std::stack<int> myStack;// 将元素压入栈顶myStack.push(10);myStack.push(20);myStack.push(30);std::cout << "栈顶元素: " << myStack.top() << std::endl; // 输出：30std::cout << "栈的大小: " << myStack.size() << std::endl; // 输出：3myStack.pop(); // 弹出栈顶元素if (!myStack.empty()) {std::cout << "弹出元素后的栈顶元素: " << myStack.top() << std::endl; // 输出：20}std::stack<int> anotherStack;anotherStack.push(50);myStack.swap(anotherStack); // 交换两个栈的内容std::cout << "交换后 myStack 的大小: " << myStack.size() << std::endl; // 输出：1return 0;
}

stack的模拟实现

#pragma once
#include <deque>namespace phw {template<class T, class Container = std::deque<T>>class stack {public:void push(const T &x) {_con.push_back(x);}void pop() {_con.pop_back();}T &top() {return _con.back();}const T &top() const {return _con.back();}size_t size() const {return _con.size();}bool empty() const {return _con.empty();}void swap(stack<T, Container> &st) {_con.swap(st._con);}private:Container _con;};
}// namespace phw

3.queue的介绍和使用

queue的介绍

  1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端 提取元素。

  2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的 成员函数来访问其元素。元素从队尾入队列，从队头出队列。

  3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

    • empty：检测队列是否为空

    • size：返回队列中有效元素的个数

    • front：返回队头元素的引用

    • back：返回队尾元素的引用

    • push_back：在队列尾部入队列

    • pop_front：在队列头部出队列

  4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标 准容器deque。

queue的使用

  1. push(const T& value): 将元素 value 添加到队列的尾部。
  2. pop(): 弹出队列的头部元素，不返回其值。
  3. front(): 返回队列头部元素的引用。
  4. back(): 返回队列尾部元素的引用。
  5. size(): 返回队列中元素的数量。
  6. empty(): 检查队列是否为空。
  7. swap(queue& other): 交换两个队列的内容。

示例：

#include <iostream>
#include <queue>int main() {std::queue<int> myQueue;// 向队列尾部添加元素myQueue.push(10);myQueue.push(20);myQueue.push(30);std::cout << "队列头部元素: " << myQueue.front() << std::endl; // 输出：10std::cout << "队列尾部元素: " << myQueue.back() << std::endl;  // 输出：30std::cout << "队列大小: " << myQueue.size() << std::endl;     // 输出：3myQueue.pop(); // 弹出队列头部元素std::cout << "弹出元素后的队列头部元素: " << myQueue.front() << std::endl; // 输出：20std::queue<int> anotherQueue;anotherQueue.push(50);myQueue.swap(anotherQueue); // 交换两个队列的内容std::cout << "交换后 myQueue 的大小: " << myQueue.size() << std::endl; // 输出：1return 0;
}

queue的模拟实现

#pragma once
#include <deque>namespace phw//防止命名冲突
{template<class T, class Container = std::deque<T>>class queue {public://队尾入队列void push(const T &x) {_con.push_back(x);}//队头出队列void pop() {_con.pop_front();}//获取队头元素T &front() {return _con.front();}const T &front() const {return _con.front();}//获取队尾元素T &back() {return _con.back();}const T &back() const {return _con.back();}//获取队列中有效元素个数size_t size() const {return _con.size();}//判断队列是否为空bool empty() const {return _con.empty();}//交换两个队列中的数据void swap(queue<T, Container> &q) {_con.swap(q._con);}private:Container _con;};
}// namespace phw

4.priority_queue的介绍和使用

priority_queue的介绍

std::priority_queue 用于实现优先队列数据结构。优先队列是一种特殊的队列，其中的元素按照一定的优先级顺序进行排列，而不是按照插入的顺序。

std::priority_queue 使用堆（heap）数据结构来维护元素的顺序，通常用于需要按照一定规则获取最高优先级元素的场景。在默认情况下，std::priority_queue 会以降序排列元素，即最大的元素会被放置在队列的前面。你也可以通过提供自定义的比较函数来改变排序顺序。

priority_queue的使用

构造函数

默认构造函数： 创建一个空的优先队列。

std::priority_queue<T> pq;  // 创建一个空的优先队列，T 是元素类型

带有比较函数的构造函数： 可以指定一个自定义的比较函数，用于确定元素的优先级顺序。

std::priority_queue<T, Container, Compare> pq;
  • T 是元素类型。
  • Container 是底层容器类型，默认情况下使用 std::vector。
  • Compare 是比较函数类型，用于确定元素的顺序。默认情况下，使用 operator< 来比较元素。

示例：

#include <iostream>
#include <queue>int main() {// 构造一个默认的优先队列，元素类型为 int，使用默认比较函数 operator<std::priority_queue<int> pq1;// 构造一个优先队列，元素类型为 int，使用自定义的比较函数 greater，实现最小堆std::priority_queue<int, std::vector<int>, std::greater<int>> pq2;// 构造一个优先队列，元素类型为 std::string，使用默认比较函数 operator<std::priority_queue<std::string> pq3;// 构造一个优先队列，元素类型为 double，使用 lambda 表达式作为比较函数，实现最大堆auto cmp = [](double a, double b) { return a < b; };std::priority_queue<double, std::vector<double>, decltype(cmp)> pq4(cmp);return 0;
}

成员函数

  1. push()： 向优先队列中插入元素。

    pq.push(value);  // 插入元素 value

  2. pop()： 移除队列顶部的元素（即最高优先级元素）。

    pq.pop();  // 移除队列顶部元素

  3. top()： 获取队列顶部的元素（即最高优先级元素）。

    T highestPriority = pq.top();  // 获取最高优先级元素

  4. empty()： 检查队列是否为空。

    bool isEmpty = pq.empty();  // 如果队列为空则返回 true，否则返回 false

  5. size()： 获取队列中的元素数量。

    int numElements = pq.size();  // 获取队列中的元素数量

示例：

#include <iostream>
#include <functional>
#include <queue>
using namespace std;
int main(){priority_queue<int> q;q.push(3);q.push(6);q.push(0);q.push(2);q.push(9);q.push(8);q.push(1);while (!q.empty()){cout << q.top() << " ";q.pop();}cout << endl; //9 8 6 3 2 1 0return 0;
}

自定义比较函数

你可以通过提供自定义的比较函数来改变元素的排序顺序。比较函数应该返回 true，如果第一个参数应该排在第二个参数之前。

struct MyComparator {bool operator()(const T& a, const T& b) {// 自定义比较逻辑}
};std::priority_queue<T, Container, MyComparator> pq;

priority_queue的模拟实现

priority_queue的底层实际上就是堆结构，实现priority_queue之前，我们先认识两个重要的堆算法。（下面这两种算法我们均以大堆为例）

堆的向上调整算法

在这里插入图片描述

以大堆为例，堆的向上调整算法就是在大堆的末尾插入一个数据后，经过一系列的调整，使其仍然是一个大堆。

调整的基本思想如下：

1、将目标结点与其父结点进行比较。
2、若目标结点的值比父结点的值大，则交换目标结点与其父结点的位置，并将原目标结点的父结点当作新的目标结点继续进行向上调整；若目标结点的值比其父结点的值小，则停止向上调整，此时该树已经是大堆了。

例如，现在我们在该大堆的末尾插入数据88。

在这里插入图片描述

我们先将88与其父结点54进行比较，发现88比其父结点大，则交换父子结点的数据，并继续进行向上调整。

在这里插入图片描述

此时将88与其父结点87进行比较，发现88还是比其父结点大，则继续交换父子结点的数据，并继续进行向上调整。

在这里插入图片描述

这时再将88与其父结点89进行比较，发现88比其父结点小，则停止向上调整，此时该树已经就是大堆了。

在这里插入图片描述

堆的向上调整算法代码：

void AdjustUp(int child) {int parent = (child - 1) / 2;while (child > 0) {// 默认less ，也就是parent<childif (_comp(_con[parent], _con[child]))// 通过所给比较方式确定是否需要交换结点位置{// 将父结点与孩子结点交换swap(_con[child], _con[parent]);// 继续向上进行调整child = parent;parent = (child - 1) / 2;} else// 已成堆{break;}}
}

堆的向下调整算法

以大堆为例，使用堆的向下调整算法有一个前提，就是待向下调整的结点的左子树和右子树必须都为大堆。

在这里插入图片描述

调整的基本思想如下：

1、将目标结点与其较大的子结点进行比较。
2、若目标结点的值比其较大的子结点的值小，则交换目标结点与其较大的子结点的位置，并将原目标结点的较大子结点当作新的目标结点继续进行向下调整；若目标结点的值比其较大子结点的值大，则停止向下调整，此时该树已经是大堆了。

例如，将该二叉树从根结点开始进行向下调整。（此时根结点的左右子树已经是大堆）

在这里插入图片描述

将60与其较大的子结点88进行比较，发现60比其较大的子结点小，则交换这两个结点的数据，并继续进行向下调整。

在这里插入图片描述

此时再将60与其较大的子结点87进行比较，发现60比其较大的子结点小，则再交换这两个结点的数据，并继续进行向下调整。

在这里插入图片描述

这时再将60与其较大的子结点54进行比较，发现60比其较大的子结点大，则停止向下调整，此时该树已经就是大堆了。

在这里插入图片描述

堆的向下调整算法代码：

void AdjustDown(int n, int parent) {int child = 2 * parent + 1;while (child < n) {//_comp(_con[child], _con[child + 1])表示child<child+1if (child + 1 < n && _comp(_con[child], _con[child + 1])) {child++;}// parent<childif (_comp(_con[parent], _con[child]))// 通过所给比较方式确定是否需要交换结点位置{// 将父结点与孩子结点交换swap(_con[child], _con[parent]);// 继续向下进行调整parent = child;child = 2 * parent + 1;} else// 已成堆{break;}}
}

模拟实现代码：

// 优先级队列使用vector作为其底层存储数据的容器，priority_queue就是堆
// 默认情况是大堆#include <iostream>
#include <vector>
using namespace std;
namespace phw {// 仿函数less(使内部结构为大堆)template<class T>struct less {bool operator()(const T &x, const T &y) {return x < y;}};// 仿函数greater(使内部结构为小堆)template<class T>struct greater {bool operator()(const T &x, const T &y) {return x > y;}};// 优先级队列template<class T, class Container = vector<T>, class Compare = greater<T>>class priority_queue {public:// 堆的向上调整void AdjustUp(int child) {int parent = (child - 1) / 2;while (child > 0) {// 默认less ，也就是parent<childif (_comp(_con[parent], _con[child]))// 通过所给比较方式确定是否需要交换结点位置{// 将父结点与孩子结点交换swap(_con[child], _con[parent]);// 继续向上进行调整child = parent;parent = (child - 1) / 2;} else// 已成堆{break;}}}// 堆的向下调整void AdjustDown(int n, int parent) {int child = 2 * parent + 1;while (child < n) {//_comp(_con[child], _con[child + 1])表示child<child+1if (child + 1 < n && _comp(_con[child], _con[child + 1])) {child++;}// parent<childif (_comp(_con[parent], _con[child]))// 通过所给比较方式确定是否需要交换结点位置{// 将父结点与孩子结点交换swap(_con[child], _con[parent]);// 继续向下进行调整parent = child;child = 2 * parent + 1;} else// 已成堆{break;}}}// 插入元素到队尾（并排序）void push(const T &x) {_con.push_back(x);AdjustUp(_con.size() - 1);// 将最后一个元素进行一次向上调整}// 弹出队头元素（堆顶元素）void pop() {swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(_con.size(), 0);// 将第0个元素进行一次向下调整}// 访问队头元素（堆顶元素）T &top() {return _con[0];}const T &top() const {return _con[0];}// 获取队列中有效元素个数size_t size() const {return _con.size();}// 判断队列是否为空bool empty() const {return _con.empty();}private:Container _con;// vector容器Compare _comp; // 比较方式};
}// namespace phw
(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(_con.size(), 0);// 将第0个元素进行一次向下调整}// 访问队头元素（堆顶元素）T &top() {return _con[0];}const T &top() const {return _con[0];}// 获取队列中有效元素个数size_t size() const {return _con.size();}// 判断队列是否为空bool empty() const {return _con.empty();}private:Container _con;// vector容器Compare _comp; // 比较方式};
}// namespace phw

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

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

相关文章

【算法】经典的八大排序算法

【算法】经典的八大排序算法

点击链接 可视化排序 动态演示各个排序算法来加深理解&#xff0c;大致如下 一&#xff0c;冒泡排序&#xff08;Bubble Sort&#xff09; 原理 冒泡排序&#xff08;Bubble Sort&#xff09;是一种简单的排序算法&#xff0c;它通过多次比较和交换相邻元素的方式&#xff0c;将…
阅读更多...
基于神经网络的3D地质模型

基于神经网络的3D地质模型

地球科学家需要对地质环境进行最佳估计才能进行模拟或评估。 除了地质背景之外&#xff0c;建立地质模型还需要一整套数学方法&#xff0c;如贝叶斯网络、协同克里金法、支持向量机、神经网络、随机模型&#xff0c;以在钻井日志或地球物理信息确实稀缺或不确定时定义哪些可能是…
阅读更多...
视频汇聚/视频监控管理平台EasyCVR接入海康SDK协议后无法播放该如何解决？

视频汇聚/视频监控管理平台EasyCVR接入海康SDK协议后无法播放该如何解决？

开源EasyDarwin视频监控/安防监控/视频汇聚EasyCVR能在复杂的网络环境中&#xff0c;将分散的各类视频资源进行统一汇聚、整合、集中管理&#xff0c;在视频监控播放上&#xff0c;视频安防监控汇聚平台可支持1、4、9、16个画面窗口播放&#xff0c;可同时播放多路视频流&#…
阅读更多...
[Linux]命令行参数和进程优先级

[Linux]命令行参数和进程优先级

[Linux]命令行参数和进程优先级 文章目录 [Linux]命令行参数和进程优先级命令行参数命令行参数的概念命令函参数的接收编写代码验证 进程优先级进程优先级的概念PRI and NI使用top指令修改nice值 命令行参数 命令行参数的概念 命令行参数是指用于运行程序时在命令行输入的参数…
阅读更多...
Python之动态规划

Python之动态规划

序言 最近在学习python语言&#xff0c;语言有通用性&#xff0c;此文记录复习动态规划并练习python语言。 动态规划&#xff08;Dynamic Programming&#xff09; 动态规划是运筹学的一个分支&#xff0c;是求解决策过程最优化的过程。20世纪50年代初&#xff0c;美国数学家…
阅读更多...
ospf不规则区域划分和数据库表

ospf不规则区域划分和数据库表

华子目录 ospf不规则区域1.远离骨干的非骨干区域2.不连续骨干 不规则区域解决方案1.tunnel-点到点GRE2.ospf虚链路3.多进程双向重发布&#xff08;推荐&#xff09; ospf的数据库表 ospf不规则区域 1.远离骨干的非骨干区域 图示 2.不连续骨干 图示 不规则区域解决方案 …
阅读更多...
成都瀚网科技有限公司：抖店精选联盟企业是什么？

成都瀚网科技有限公司：抖店精选联盟企业是什么？

我很高兴为您提供有关如何加入抖店特色联盟企业以及加入的好处的信息。在这篇文章中&#xff0c;我将为大家详细介绍如何申请加入抖店精选的关联公司&#xff0c;并讲解加入的好处。希望能够帮助您更好地了解和使用抖店精选联盟企业平台。 1、如何加入抖店精选联盟企业&#xf…
阅读更多...
Docker基础入门：容器数据卷与Dockerfile构建镜像（发布）

Docker基础入门：容器数据卷与Dockerfile构建镜像（发布）

Docker基础入门&#xff1a;容器数据卷与Dockerfile构建镜像&#xff08;发布&#xff09; 一、docker容器数据卷1.1、使用docker容器数据卷1.2、具名挂载、匿名挂载1.3、如何确定是具名挂载还是匿名挂载 二、使用dockerfile2.1 初识Dockerfile2.2 Dockerfile构建过程2.3 Docke…
阅读更多...
Ansible学习笔记2

Ansible学习笔记2

Ansible是Python开发的自动化运维工具&#xff0c;集合了众多运维工具&#xff08;Puppet、cfengine、chef、func、fabric&#xff09;的优点&#xff0c;实现了批量系统配置&#xff0c;批量程序部署、批量运行命令等功能。 特点&#xff1a; 1&#xff09;部署简单&#xff…
阅读更多...
Kafka3.0.0版本——Leader故障处理细节原理

Kafka3.0.0版本——Leader故障处理细节原理

目录 一、服务器信息二、服务器基本信息及相关概念2.1、服务器基本信息2.2、LEO的概念2.3、HW的概念 三、Leader故障处理细节 一、服务器信息 三台服务器 原始服务器名称原始服务器ip节点centos7虚拟机1192.168.136.27broker0centos7虚拟机2192.168.136.28broker1centos7虚拟机…
阅读更多...
Spring——Spring Boot基础

Spring——Spring Boot基础

文章目录 第一个helloword项目新建 Spring Boot 项目Spring Boot 项目结构分析SpringBootApplication 注解分析新建一个 Controller大功告成,运行项目 简而言之&#xff0c;从本质上来说&#xff0c;Spring Boot 就是 Spring&#xff0c;它做了那些没有它你自己也会去做的 Spri…
阅读更多...
【Unity】终极移动指南-注解【理解移动到抓钩，再到贪吃蛇的实现】

【Unity】终极移动指南-注解【理解移动到抓钩，再到贪吃蛇的实现】

文章目录 【Unity】终极移动指南-注解&#xff08;从移动、抓钩到贪吃蛇&#xff09;观前提醒链接地址&#xff1a; 内容一、 transform移动操作【1】transform.position变换位置【2】transform.Translate平移【3】transform.position 类似平移的操作【4】定向矢量【5】停在指定…
阅读更多...
IP 地址追踪工具

IP 地址追踪工具

IP 地址跟踪工具是一种网络实用程序&#xff0c;允许您扫描、跟踪和获取详细信息&#xff0c;例如 IP 地址的 MAC 和接口 ID。IP 跟踪解决方案通过使用不同的网络扫描协议来检查网络地址空间来收集这些详细信息。一些高级 IP 地址跟踪器软件&#xff08;如 OpUtils&#xff09;…
阅读更多...
RT-Thread 时钟管理

RT-Thread 时钟管理

时钟节拍 任何操作系统都需要提供一个时钟节拍&#xff0c;以供系统处理所有和时间有关的事件&#xff0c;如线程的延时、时间片的轮转调度以及定时器超时等。 RTT中&#xff0c;时钟节拍的长度可以根据RT_TICK_PER_SECOND的定义来调整。rtconfig.h配置文件中定义&#xff1a…
阅读更多...
自然语言处理(一)：词嵌入

自然语言处理(一)：词嵌入

词嵌入 词嵌入&#xff08;Word Embedding&#xff09;是自然语言处理&#xff08;NLP&#xff09;中的一种技术&#xff0c;用于将文本中的单词映射到一个低维向量空间中。它是将文本中的单词表示为实数值向量的一种方式。 在传统的文本处理中&#xff0c;通常使用独热编码&…
阅读更多...
Python Opencv实践 - Canny边缘检测

Python Opencv实践 - Canny边缘检测

import cv2 as cv import numpy as np import matplotlib.pyplot as pltimg cv.imread("../SampleImages/pomeranian.png", cv.IMREAD_GRAYSCALE) print(img.shape)#图像Canny边缘检测 #cv.Canny(image, threshold1, threshold2[, edges[, apertureSize[, L2gradien…
阅读更多...
GitHub 标星 15w，如何用 Python 实现所有算法？

GitHub 标星 15w，如何用 Python 实现所有算法？

学会了 Python 基础知识&#xff0c;想进阶一下&#xff0c;那就来点算法吧&#xff01;毕竟编程语言只是工具&#xff0c;结构算法才是灵魂。 新手如何入门 Python 算法&#xff1f; 几位印度小哥在 GitHub 上建了一个各种 Python 算法的新手入门大全。从原理到代码&#xf…
阅读更多...
助力网络管理的利器：企业办公网络中的VLAN划分策略

助力网络管理的利器：企业办公网络中的VLAN划分策略

企业办公网络的性能和安全性对员工的高效工作和信息安全具有重要意义。在实现这一目标时&#xff0c;VLAN&#xff08;Virtual Local Area Network&#xff09;划分在网络设计中发挥着至关重要的作用。通过将办公网络划分为多个虚拟局域网&#xff0c;VLAN划分可以实现网络资源…
阅读更多...
Web服务器-Tomcat详细原理与实现

Web服务器-Tomcat详细原理与实现

Tomcat 安装与使用 &#xff1a;MAC 安装配置使用Tomcat - 掘金 安装后本计算机就相当于一台服务器了&#xff01;&#xff01;&#xff01; 方式一&#xff1a;使用本地安装的Tomcat 1、将项目文件移动到Tomcat的webapps目录下。 2、启动Tomcat 3、在浏览器输入想要加载的…
阅读更多...
ELK日志分析系统概述及部署

ELK日志分析系统概述及部署

ELK 平台是一套完整的日志集中处理解决方案&#xff0c;将 ElasticSearch、Logstash 和 Kibana 三个开源工具配合使用&#xff0c;完成更强大的用户对日志的查询、排序、统计需求。 一、ELK概述 1、组件说明 ①ElasticSearch ElasticSearch是基于Lucene&#xff08;一个全文…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023