【STL】map和set的原理及其使用

文章目录

  • 关联容器
  • 键值对
  • set
    • set的介绍
    • set的使用
    • set的构造
      • 函数声明1:
      • 函数声明2:
      • 函数声明3:
    • set的迭代器
      • begin和end
      • rbegin和rend
    • set的容量
      • empty()
      • size()
    • set的修改操作
      • insert
      • erase
      • clear
      • find
      • count
  • map
    • map的介绍
    • map的构造
      • 函数声明1
      • 函数声明2
      • 函数声明3
    • map的迭代器
      • begin和end
      • rbegin和rend
    • map的[]访问
    • map的修改操作
  • multiset
  • multimap

关联容器

关联容器是c++中的一种数据结构,提供了一种通过键来访问值的方式。根据使用场景的不同,STL的关联容器有两种结构,树型结构哈希结构。常见树形结构的关联容器有:mapset。map是一种键值对容器,里面存储的结构是<key,value>.set是一种集合容器,有序且唯一。常见的哈希结构的关联容器有unordered_mapunordered_set

键值对

键值对用来表示具有一一对应关系的一种结构,该结构中包含两个成员变量keyvalue,key表示键值,value表示与key对应的值。我们常用的pair<key,value> 就是键值对。
下面观察STL源码中是如何定义pair的:

template <class T1, class T2>
struct pair 
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(): first(T1()), second(T2())
{}
 
pair(const T1& a, const T2& b): first(a), second(b)
{}
};

所以pair其实就是一个类模板,根据<>里的两个参数来实例化类,第一个参数表示key,第二个表示value。
pair的两个成员变量first表示key,second表示value。

set

set的介绍

在c++文档中是这么定义set的:
在这里插入图片描述

  1. set是按照一定次序存储元素的容器,其中class Compare控制比较逻辑,默认是小于。可以是一个仿函数,也可以是一个函数指针。
  2. set中的key必须是唯一的。不能修改key但是可以删除或者插入一个key。
  3. 在内部,set中的元素总是按照其内部比较对象(类型比较)所指定的特定严格强弱排序准则进行排序。
  4. set访问元素的平均时间复杂度为O(logn).
  5. set的底层是通过二叉搜索树(红黑树)来实现的

与map等容器不同,set存储的元素其实只有value,在底层是<value,value>.所以在插入元素时,只需要提供value即可,不需要构造键值对。使用set的迭代器进行遍历set时,会得到一个有序的序列。这是因为遍历的方式其实是二叉搜索树的中序遍历

set的使用

set的模板参数列表有三个:
在这里插入图片描述

  • T:元素类型
  • Compare:用于控制set的比较逻辑,默认是小于
  • Alloc:控制set的空间管理方式,使用STL提供的空间管理配置器.

set的构造

函数声明1:

explicit set (const key_compare& comp = key_compare(),
              const allocator_type& alloc = allocator_type());

构造一个空的set,里面没有元素

函数声明2:

template <class InputIterator>
  set (InputIterator first, InputIterator last,
       const key_compare& comp = key_compare(),
       const allocator_type& alloc = allocator_type());

根据提供的范围[InputIterator,InputIerator last)里的值来一一构造。

函数声明3:

set (const set& x);

拷贝构造,根据提供的一个set对象去构造一个一模一样的另一个set对象。

set的迭代器

begin和end

分别指向set第一个元素和最后一个元素的下一个位置。
rbegin和rend表示const修饰的begin和end。

rbegin和rend

方向迭代器,分别指向set最后一个元素的下一个位置和第一个元素的位置。
crbegin和crend表示被const修饰的 rbegin和rend。
注意,const迭代器并不是指迭代器本身不能被修改,而是指向的元素不能被修改。

set的容量

empty()

检测set中的元素是否为空,空返回true,否则false.

size()

返回set中有效元素的个数

set的修改操作

下面讲一些比较常用的修改操作

insert

pair<iterator,bool> insert ( const value_type& x )

在set中插入元素x,实际上插入的是<x,x>构成的键值对,如果插入成功,返回一个迭代器和true构成的键值对。该迭代器指向插入set后的x。如果插入失败,说明x已经存在,返回一个迭代器和false构成的键值对。

erase

void erase ( iterator position )
void erase ( iterator first, iterator last )
  1. 删除set中position位置上的元素。
  2. 删除[first,last)这个区间的所有元素

clear

void clear ( ) 

清空set中的所有元素

find

iterator find ( const key_type& x ) const

返回指向元素x的迭代器

count

size_type count ( const key_type& x ) const

返回set中值为x的元素的个数.

map

map的介绍

map的文档介绍:
在这里插入图片描述

  1. 键值对映射 :map中的元素是一对键值对,每一个key都有一个value对应。
  2. 自动排序:与set类似,mao中的元素在插入的同时会进行排序,默认情况下是key小的排在前面。
  3. 唯一键:每个键在map中都是唯一的。
  4. map查找的时间复杂度是O(logn).
  5. 迭代器支持:支持使用迭代器来遍历map中的元素。本质上是搜索二叉树的中序遍历。
  6. 底层是用二叉搜索树(红黑树)实现的。
  7. 可以使用[key]访问对应的value

map和set的特性其实很像,只不过map中的元素更像是一个键值对。

map的构造

函数声明1

explicit map (const key_compare& comp = key_compare(),
              const allocator_type& alloc = allocator_type());

构造一个空的map对象,没有元素。

函数声明2

template <class InputIterator>
  map (InputIterator first, InputIterator last,
       const key_compare& comp = key_compare(),
       const allocator_type& alloc = allocator_type());

迭代器范围构造map,根据[first,last)范围内的元素一一构造出与其对应的map元素。

函数声明3

map (const map& x);

拷贝构造

map的迭代器

begin和end

begin:首元素的位置,end最后一个元素的下一个位置

cbegin和cend:与begin和end意义相同,但cbegin和cend所指向的元素不能修改

rbegin和rend

反向迭代器,rbegin在end位置,rend在begin位置,其++和–操作与begin和end操作移动相反

crbegin和crend:与rbegin和rend意义相同,但crbegin和crend所指向的元素不能修改

map的[]访问

在这里插入图片描述
当访问的key不存在,[key]操作会先将key插入到map中,返回默认的value.否则直接返回其value值。

map的修改操作

在这里插入图片描述

multiset

multiset的文档介绍:
在这里插入图片描述multiset和set的区别就在于multiset可以存相同的元素。因此我们可以使用multiset对数组进行排序。
其内部结构和set都是一样的,都是用二叉搜索树(红黑树)实现的。

multimap

multimap的文档介绍:
在这里插入图片描述
multimap和map的区别就在于multimap可以存重复的key。此外,multimap不支持[key]操作
其内部结构和map都是一样的,都是用二叉搜索树(红黑树)实现的。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

拼多多怎么推广才有效果

拼多多店铺的有效推广需要综合考虑多个方面&#xff0c;包括优化店铺信息、商品详情、参与平台活动、利用社交媒体、精准营销和客户服务等。具体如下&#xff1a; 拼多多推广可以使用3an推客。3an推客&#xff08;CPS模式&#xff09;给商家提供的营销工具&#xff0c;由商家自…

Go Web 开发【Gin 框架快速开发】

1、Gin Web 快速开发 1.1、环境准备 1.1.1、导入 gin 依赖 这里就叫 gin 依赖了&#xff0c;在 Goland 命令行中输入下面的命令&#xff1a; go get -u github.com/gin-gonic/gin 1.1.2、设置代理 如果下载失败&#xff0c;最好设置一下代理&#xff0c;在 cmd 命令行中输…

功能测试_分类_用例_方法

总结 测试分类 按阶段分类 是否查看源代码分类 是否运行分类 是否自动化 其他分类 软件质量模型 开发模型-瀑布模型 测试过程模型 v w 测试用例八大要素 用例编号 用例标题 …

海外仓系统:为什么对小型海外仓企业尤为重要,该怎么看待wms系统

相对于大型海外仓企业来说&#xff0c;小型海外仓受到资金和规模的限制&#xff0c;在库存管理、订单处理能力上面临的问题尤其大。而这正是海外仓系统擅长的地方&#xff0c;现代的海外仓系统逐渐发展以云端部署方式为主&#xff0c;这也为小型海外仓企业提供了很多便利。 1、…

基于Pytorch深度学习——GPU安装/使用

本文章来源于对李沐动手深度学习代码以及原理的理解&#xff0c;并且由于李沐老师的代码能力很强&#xff0c;以及视频中讲解代码的部分较少&#xff0c;所以这里将代码进行尽量逐行详细解释 并且由于pytorch的语法有些小伙伴可能并不熟悉&#xff0c;所以我们会采用逐行解释小…

Java中的Lambda表达式

Lambda表达式的标准格式 格式&#xff1a;&#xff08;形式参数&#xff09;->{代码块} 形式参数&#xff1a;如果有多个参数&#xff0c;参数之间用逗号隔开 如果没有参数&#xff0c;留空即可 ->&#xff1a;由英文中画线和大于符号组成&#xff0c;固定写法。代表着…

学习中遇到的问题

1.UFUNCTION() 不是所有函数都能加UFUNCTION()修饰&#xff0c;涉及UE反射机制。 2.初始化用{} 初始化列表 3.创建C文件时修改了路径 这时.cpp文件会报错&#xff0c;只需删掉前面多余路径即可 4.函数的移除 1.虚幻5.1 UUserWidget不再包含OnLevelRemovedFromWorld() 转而使用…

微信CRM管理系统、企业个人微信号管理对接接口

接口地址&#xff1a; POST/login/getLoginQrCode appId参数为设备ID&#xff0c;首次登录传空&#xff0c;会自动触发创建设备&#xff0c;掉线后重新登录则必须传接口返回的appId&#xff0c;注意同一个号避免重复创建设备&#xff0c;以免触发官方风控 取码时传的appId需要…

python邮件发送

第一种方式 一&#xff1a;发送的邮件要设置授权码&#xff0c;通过邮箱邮箱授权码去验证&#xff0c;让邮件服务器帮我们去转发邮件到要接收的邮件&#xff0c;代码中的授权码&#xff0c;是需要登录126邮箱&#xff08;我这里是以126邮件发送的&#xff0c;具体的以自己为准…

stm32f103c8t6学习笔记(学习B站up江科大自化协)-PWR电源控制

PWR简介 PVD可用在电池供电或安全要求比较高的设备&#xff0c;如果供电电压在逐渐下降&#xff0c;在电压过低的情况下可能会导致内外电路出现不确定的错误。为了避免不必要的错误&#xff0c;可以在电源电压过低的情况下&#xff0c;提前发出警告并关闭较为危险的设备 关闭的…

循环神经网络模块介绍(Pytorch 12)

到目前为止&#xff0c;我们遇到过两种类型的数据&#xff1a;表格数据和图像数据。对于图像数据&#xff0c;我们设计了专门的卷积神经网络架构(cnn)来为这类特殊的数据结构建模。换句话说&#xff0c;如果我们拥有一张图像&#xff0c;我们 需要有效地利用其像素位置&#xf…

专业渗透测试 Phpsploit-Framework(PSF)框架软件小白入门教程(三)

本系列课程&#xff0c;将重点讲解Phpsploit-Framework框架软件的基础使用&#xff01; 本文章仅提供学习&#xff0c;切勿将其用于不法手段&#xff01; 继续接上一篇文章内容&#xff0c;讲述如何进行Phpsploit-Framework软件的基础使用和二次开发。 当我们点击 submit 提…

【JavaEE 初阶(一)】初识线程

❣博主主页: 33的博客❣ ▶️文章专栏分类:JavaEE◀️ &#x1f69a;我的代码仓库: 33的代码仓库&#x1f69a; &#x1faf5;&#x1faf5;&#x1faf5;关注我带你了解更多线程知识 目录 1.前言2.进程3.线程4.线程和进程的区别5.Thread创建线程5.1继承Thread创建线程5.2实现R…

非平衡数据处理-SMOTE Tomek算法(互联网最全)

作者Toby&#xff0c;来源公众号&#xff1a;Python风控模型&#xff0c;非平衡数据处理-SMOTE Tomek算法 之前Toby老师讲了非平衡数据处理相关知识&#xff0c;具体内容和链接如下。 imbalanced data机器学习非平衡数据处理 Python非平衡数据处理_SMOTE-ENN 方法 非平衡数…

【SSM进阶学习系列丨分页篇】PageHelper 分页插件导入集成实践

文章目录 一、说明什么是分页PageHelper介绍 二、导入依赖三、集成Spring框架中四、编写Service五、编写Controller六、编写queryAllByPage页面展示数据 一、说明 什么是分页 ​ 针对分页&#xff0c;使用的是PageHelper分页插件&#xff0c;版本使用的是5.1.8 。 ​ 参考文档…

虚拟机网络实现桥接模式

虚拟机网络实现桥接模式 虚拟化软件&#xff1a;VMware 17 Linux&#xff1a;rocky8_9 主机&#xff1a;Win10 文章目录 虚拟机网络实现桥接模式1. 桥接模式介绍2. 查看Win本机的网络信息&#xff08;以笔记本电脑以WiFi联网为例&#x…

【Canvas与艺术】录王昌龄出塞诗“秦时明月汉时关”

【成图】 【代码】 <!DOCTYPE html> <html lang"utf-8"> <meta http-equiv"Content-Type" content"text/html; charsetutf-8"/> <head><title>使用HTML5/Canvas绘制秦时明月汉时关</title><style type&q…

【论文阅读】Sparse is Enough in Scaling Transformers

Sparse is Enough in Scaling Transformers 论文地址摘要1 介绍2 相关工作模型压缩。模型修剪模型蒸馏。稀疏注意力。张量分解。稀疏前馈。 3 Sparse is Enough3.1 稀疏前馈层3.2 稀疏 QKV 层3.3 稀疏损失层。 4 长序列的稀疏性4.1 长序列架构4.2 内存效率的可逆性4.3 泛化的循…

# 从浅入深 学习 SpringCloud 微服务架构(七)Hystrix(4)

从浅入深 学习 SpringCloud 微服务架构&#xff08;七&#xff09;Hystrix&#xff08;4&#xff09; 一、hystrix&#xff1a;使用 turbine 聚合所有的 hytrix 的监控数据测试。创建父工程 spring_cloud_hystrix_demo&#xff0c;导入相关依赖坐标。并在父工程 spring_cloud_…

C++校招八股

c类的访问权限与继承方式 公有成员在任何地方都可以被访问&#xff0c;包括类的外部和派生类。受保护成员在类的内部和派生类中可以被访问&#xff0c;但在类的外部不可访问。 私有成员只能在类的内部访问&#xff0c;包括类的成员函数和友元函数&#xff0c;不允许在类的外部…