STL——map set

文章将解决一下几个问题:
1.什么是set
2.什么是map
3.set应用场景
4.map应用场景

序列式容器和关联式容器

数据结构有序列式容器和关联式容器,序列式容器一般有vector,list,deque…,但关联式容器中就有map,关联式容器也是用来存储数据的,与序列式容器不同的是,其里面存储的是<key,value>结构的键值对,在数据检索时比序列式容器效率高。

键值对

它是用来表示具有一一对应关系的一种结构,该结构一般只包含了两个成员变量key和value,key代表了键值,value表示与key对应的信息。 如果字典,每个单词都有对应的关系,英文单词和其对应的含义就是一一对应的关系,通过该单词就可以找到对应的意思。

下面是STL中关于键值对的定义:

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)
{}
};

树形结构的关联式容器

STL总共实现了两种不同结构的管理师容器:树形结构和哈希结构。
树形结构的关联式容器有map、set、multimap、multiset。这四种容器的底层就是红黑树。

set

  1. set是按照一定次序存储元素的容器
  2. 在set中,元素的value也标识了它(value,T类型),并且每个value都只有一个,set中的元素不能在容器中修改,但是可以从容器中插入和删除
  3. 在内部,set中的元素总是按照其内部比较对象,所指示的特定严格若排序准则进行排序
  4. set容器通过key访问单个元素的速度通常比unordered_set容器慢,但它们可以根据顺序子集进行直接迭代
  5. 底层是红黑树
    在这里插入图片描述

T是set中元素的类型实际存储的是<key,value>的键值对
Compare是仿函数,默认是升序的,可以根据需求改写仿函数
Alloc:set中元素空间的管理方式,使用STL的空间配置器来管理

set的构造

在这里插入图片描述

set的迭代器

在这里插入图片描述

下面是实例:

#include <set>
void TestSet()
{
	int arr[] = {1,3,5,7,9,2,4,6,8,0};
	set<int> s(arr,arr+sizeof(arr) / sizeof(arr));
	cout << s.size() <<endl;
	
	//用C++11的auto 遍历set
	for(auto& e : s)
	{
		cout <<e << " "; // 0 1 2 3 4 5 6 7 8 9 
	}
	cout <<endl;
	for(auto it = s.rbegin(); it != s.rend(); it++)
	{
		cout << *it<<" ";//9 8 7 6 5 4 3 2 1 0
	}
	cout <<endl;
}

map

1.map是关联式容器,它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素
2.在map中,键值key通常用于排序和唯一的标识元素,而值value中存储与此键值key关联的内容。 在map中key和value是绑定的,通常用pair来表示
在这里插入图片描述
3. 在内部,map中的元素总是按照键值key进行比较排序的。
4. map支持下标访问符,即在[]中放入key,就可以找到与key对应的value。
5. 底层也是红黑树

在这里插入图片描述
key:键值对中key的类型
T:键值对value的类型
Compare:是仿函数,缺省情况是按照升序的方式来排序
Alloc:通过空间配置器来管理map申请的空间,不需要用户来传递,一般用标准库中的

map的迭代器

在这里插入图片描述

map的operator[]

在这里插入图片描述

下面是实例

#include <map>
#include <string>

void TestMap()
{
	map<string,string> m;
	m.insert(pair<string,string>("peach","桃子"));
	m.insert(pair<make_pair<"banan","香蕉");
	// 将键值对<"peach","桃子">插入map中,用make_pair函数来构造键值对
 	m.insert(make_pair("banan", "香蕉"));
 
 // 借用operator[]向map中插入元素
    /*
 operator[]的原理是:
  用<key, T()>构造一个键值对,然后调用insert()函数将该键值对插入到map中
  如果key已经存在,插入失败,insert函数返回该key所在位置的迭代器
  如果key不存在,插入成功,insert函数返回新插入元素所在位置的迭代器
  operator[]函数最后将insert返回值键值对中的value返回
 */
    // 将<"apple", "">插入map中,插入成功,返回value的引用,将“苹果”赋值给该引
用结果,
 m["apple"] = "苹果";
 // key不存在时抛异常
  //m.at("waterme") = "水蜜桃";
 cout << m.size() << endl;
 // 用迭代器去遍历map中的元素,可以得到一个按照key排序的序列
 for (auto& e : m)
 cout << e.first << "--->" << e.second << endl;
 cout << endl;
 // map中的键值对key一定是唯一的,如果key存在将插入失败
 auto ret = m.insert(make_pair("peach", "桃色"));
 if (ret.second)
 cout << "<peach, 桃色>不在map中, 已经插入" << endl;
 else
 cout << "键值为peach的元素已经存在:" << ret.first->first << "--->"
<< ret.first->second <<" 插入失败"<< endl;
 // 删除key为"apple"的元素
 m.erase("apple");
 if (1 == m.count("apple"))
 cout << "apple还在" << endl;
 else
 cout << "apple被吃了" << endl;
}

总结:

  • map中的元素使键值对
  • map中的key是唯一的,并且是不能被修改的
  • 默认按照 小于的方式对key来进行比较
  • 支持operator[]

multiset

multiset和set最大的区别就是multiset可以允许有重复元素

下面是示例

#include <set>
void TestSet()
{
  int array[] = { 2, 1, 3, 9, 6, 0, 5, 8, 4, 7,7 };
 
 // 注意:multiset在底层实际存储的是<int, int>的键值对
 multiset<int> s(array, array + sizeof(array)/sizeof(array[0]));
 for (auto& e : s)
 cout << e << " "; // 0 1 2 3 4 5 6 7 7 8 9
 cout << endl;
 return 0;
}

multimap

  1. multimap中的key是可以重复的。
  2. multimap中的元素默认将key按照小于来比较
  3. multimap中没有重载operator[]操作(同学们可思考下为什么?)。
  4. 使用时与map包含的头文件相同:

底层结构

这几个容器有个共同点是:其底层都是按照二叉搜索树来实现的,但是二叉搜索树有其自身的缺陷**,假如往树中插入的元素有序或者接近有序,二叉搜索树就会退化成单支树**,时间复杂度会退化成O(N),因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理,即采用平衡树来实现。

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

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

相关文章

Java实现知乎热点小时榜爬虫

1.效果演示 1.1 热点问题列表 启动程序后&#xff0c;自动展示热点问题&#xff0c;并等待终端输入 1.2 根据序号选择想看的热点问题 输入问题序号&#xff0c;展示回答内容 1.3 退出 输入q即可退出程序 2.源码 2.1 pom.xml <?xml version"1.0" enco…

鸿蒙Harmony应用开发—ArkTS声明式开发(容器组件:FlowItem)

瀑布流组件的子组件&#xff0c;用来展示瀑布流具体item。 说明&#xff1a; 该组件从API Version 9开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。仅支持作为Waterflow组件的子组件使用。 子组件 支持单个子组件。 接口 FlowItem() 使…

[数据集][目标检测]零售柜零食检测数据集VOC+YOLO格式5422张113类

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;5422 标注数量(xml文件个数)&#xff1a;5422 标注数量(txt文件个数)&#xff1a;5422 标注…

html5cssjs代码 018颜色表

html5&css&js代码 018颜色表 一、代码二、效果三、解释 这段代码展示了一个基本的颜色表&#xff0c;方便参考使用&#xff0c;同时也应用了各种样式应用方式。 一、代码 <!DOCTYPE html> <html lang"zh-cn"> <head><title>编程笔记…

Redis开发规范与性能优化(二)

开发规范与性能优化 3.客户端使用 1.【推荐】避免多个应用使用一个Redis示例 正例:不相干的业务拆分&#xff0c;公共数据库做服务化 2.【推荐】使用带有连接池的数据库&#xff0c;可以有效控制链接&#xff0c;同时提高效率&#xff0c;标准使用方式如代码所示 public c…

AMD芯片使用Stable-Diffusion

AMD芯片使用Stable-Diffusion 由于A卡的Stable Diffusion工具的逐步完善&#xff0c;之前只能使用CPU跑&#xff0c;现在已支持AMD显卡进行AI绘图。 下载 官网链接&#xff1a;https://github.com/AUTOMATIC1111/stable-diffusion-webui/wiki/Install-and-Run-on-AMD-GPUs 按…

LAMP网站部署(Discuz论坛网站部署)

目录 mysql命令 语法 选项 参数 实例 安装php 安装Mariadb 关掉防火墙和selinux 启动HTTP服务 初始化数据库 查看数据库是否创建成功 修改HTTP的配置文件 浏览器打开 将以下所有目录都加上权限 最后首页效果 mysql命令 是MySQL数据库服务器的客户端工具&#xff0c;它工作在命…

【Linux下qt软件安装打包附带问题: dpkg: error processing package xxxx +解决方式+自我尝试+记录】

【Linux下qt软件安装打包附带问题&#xff1a; dpkg: error processing package xxxx 解决方式自我尝试记录】 1、前言2、实验环境3、问题说明4、我的努力与查到解决的方式&#xff08;1&#xff09;补充两个文件&#xff0c;让软件正常执行&#xff08;2&#xff09;尝试修复d…

springboot+vue学生选课系统 java+ssm+idea+_mysql

系统包含三种角色&#xff1a;管理员、老师、学生&#xff0c;系统分为前台和后台两大模块&#xff0c;主要功能如下。 ide工具&#xff1a;IDEA 或者eclipse 编程语言: java 学生网上选课系统可以实现教室管理&#xff0c;老师管理&#xff0c;课程管理&#xff0c;教学计划管…

为什么我接不到大单?

以前的领导创业多年&#xff0c;今天找我聊了一下想让我跟他一起做点事情&#xff0c;聊了一下我的现状&#xff0c;突然让我明白为何我一直都接不到大单了 说起来也不是完全没有好的机会&#xff0c;貌似有点像“公交车定律”&#xff0c;当我很忙碌的时候订单一个接一个&…

闯关升级游戏特点,闯关小程序游戏开发

闯关升级类游戏一直以来都备受玩家青睐&#xff0c;其独特的游戏性和吸引力让人们乐此不疲。这类游戏以挑战性关卡和角色成长为核心&#xff0c;让玩家在不断的冒险中获得成就感与乐趣。让我们一起深入探讨这类游戏的特点&#xff0c;以及为何它们如此受欢迎。 挑战性关卡设计…

C语言中内存函数的使用

memcpy函数的使用和模拟实现 memcpy的使用 函数使用说明&#xff1a; • 函数memcpy从source的位置开始向后复制num个字节的数据到destination指向的内存位置。 • 这个函数在遇到 \0 的时候并不会停下来。 • 如果source和destination有任何的重叠&#xff0c;复制的结…

提升数据分析效率,选择IBM SPSS Statistics专业统计分析软件

在当今信息爆炸的时代&#xff0c;数据已经成为决策的重要依据。对于研究人员、学者、企业管理者等群体来说&#xff0c;如何高效地进行数据分析并得出准确结论至关重要。而IBM SPSS Statistics作为一款专业统计分析软件&#xff0c;为用户提供了强大的工具和功能&#xff0c;助…

【SQL】1084. 销售分析III (多种解法;is null 和 =null 的区别图示 )

前述 知识点学习&#xff1a;MySQL 中 is null 和 null 的区别 题目描述 leetcode题目&#xff1a; 1084. 销售分析III 写法一 思路&#xff1a;“所有售出日期都在这个时间内”&#xff0c;也就是“在这个时间内售出的商品数量等于总商品数量” -- 解法1&#xff1a;ACCE…

【深度学习】diffusers 学习过程记录,StableDiffusion扩散原理

教程地址&#xff1a;https://huggingface.co/docs/diffusers/quicktour 文章目录 环境扩散模型噪声残差的作用原理&#xff0c;文字编码如何给入Unetschedulerguidance_scalescheduler.init_noise_sigma训练时候的反向传播 环境 python3.10安装环境&#xff1a; pip install…

Gitee配置SSH登录

一、背景 新入手的电脑&#xff0c;需要对Gitee上存放的项目进行更改上传&#xff0c;发现上传不了需要登录&#xff0c;便采用SSH密钥进行登录&#xff0c;防止远程管理工程中的信息泄露 二、前提 电脑已下载Git Bash工具&#xff0c;在项目下点击鼠标右键&#xff0c;进入…

halconOCR文字识别

1、OCR文字识别 FontFile : Universal_0-9_NoRej dev_update_window (off) read_image (bottle, bottle2) get_image_size (bottle, Width, Height) dev_open_window (0, 0, Width, Height, black, WindowHandle) set_display_font (WindowHandle, 16, mono, true, false) dev…

适用于系统版本:CentOS 6/7/8的基线安全检测脚本

#!/bin/bash #适用于系统版本&#xff1a;CentOS 6/7/8 echo "----------------检测是否符合密码复杂度要求----------------" #把minlen&#xff08;密码最小长度&#xff09;设置为8-32位&#xff0c;把minclass&#xff08;至少包含小写字母、大写字母、数字、特殊…

JVM及垃圾回收算法

一、JVM 1、jvm的内存组成 五大内存区域&#xff0c;分1.7和1.8 1.堆内存&#xff1a;引用类型的数据&#xff0c;内部组成&#xff1a;1.新生代&#xff08;伊甸区和幸存者区&#xff09;2.老年代。该区域经常发生垃圾回收的操作 堆是JVM中最大的一块内存区域&#xff0c;用…

mac安全干净卸载Anaconda3

使用which python显示当前使用的是/Users/username/anaconda3/bin/python 现在想卸载Anaconda&#xff0c;恢复使用mac系统自带的Python 删除隐藏文件目录 rm -rf ~/.anaconda修改~/.bash_profile文件&#xff0c;将anaconda相关删除 也有可能不是~/.bash_profile而是~/.zs…