第四章:树形结构的关联式容器(map+set)
系列文章目录
文章目录
- 系列文章目录
- 前言
- 1、关联式容器与序列式容器
- 1.1 键值对
- 2、set的介绍
- 3、multiset的介绍
- 3.1 接口count与容器multiset
- 4、map的介绍
- 4.1 接口insert
- 4.2 operator[]和at
- 5、multimap的介绍
前言
根据应用场景的不桶,STL总共实现了两种不同结构的管理式容器:树型结构与哈希结构。树型结构的关联式容器主要有四种:map、set、multimap、multiset。这四种容器的共同点是:使用平衡搜索树(即红黑树)作为其底层结果,容器中的元素是一个有序的序列。
1、关联式容器与序列式容器
vector、list、deque、forward_list(C++11)等,这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面存储的是元素本身。
而关联式容器也是用来存储数据的,与序列式容器不同的是,其里面存储的是<key, value>结构的键值对,在数据检索时比序列式容器效率更高。 (插入删除只需挪动指针指向,无需挪动数据,查找时间logN)
关联式容器有两种,一种是map、set、multimap、multiset采用树形结构,他们的底层都是红黑树,另一种是哈希结构。
1.1 键值对
用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量key和value,key代表键值,value表示与key对应的信息。比如:现在要建立一个英汉互译的字典,那该字典中必然有英文单词与其对应的中文含义,而且,英文单词与其中文含义是一一对应的关系,即通过该应该单词,在词典中就可以找到与其对应的中文含义。
SGI-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){}
};
2、set的介绍

-
set是关联式容器,它表面上只存放value,实际底层中存放的是由<value,value>组成的键值对。
-
set中的元素不可以重复(因此可以使用set进行去重)。
-
使用set的迭代器遍历set中的元素,可以得到有序序列(排序+去重)。
-
为了保证元素的唯一性,set中的元素均为const,所以并不能对元素进行修改,但可以进行插入删除。
-
set中的底层使用二叉搜索树(红黑树)来实现。
-
set调用find将采用中序遍历。
void test1()
{set<int> s1;s1.insert(3);s1.insert(1);s1.insert(2);s1.insert(4);s1.insert(3);s1.insert(5);for (auto e : s1){cout << e << " ";}cout << endl;
}
//结果
1 2 3 4 5
3、multiset的介绍

与set的区别为 :允许键值冗余。
使用multiset的迭代器遍历multiset中的元素,可以得到有序非去重序列(排序)。
void test1()
{multiset<int> s2;s2.insert(3);s2.insert(1);s2.insert(2);s2.insert(4);s2.insert(3);s2.insert(5);for (auto e : s2){cout << e << " ";}cout << endl;
}//结果
1 2 3 3 4 5
3.1 接口count与容器multiset
set的count和find的作用一样,都是用于查找set中是否存在某个元素。
其实count是为了容器multiset设计的,该容器允许插入重复的元素,此时count会返回红黑树中被搜索元素的个数。
void test1()
{multiset<int> s1;s2.insert(3);s2.insert(1);s2.insert(2);s2.insert(4);s2.insert(3);s2.insert(5);cout << s1.count(3) << endl;
}//结果
2
4、map的介绍

map是关联式容器,根据特定的存储顺序,用于存储由键值及其映射值组合的元素。
可以看到Alloc中有一个键值对pair,这个pair是一个key/value结构的struct模板类。这个类将一对键值耦合在一起,所以,map的存储方式是通过在搜索二叉树中存储键值对pair,而搜索二叉树的k/v模型是在节点中存储key和value,并不相同。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){}
};
4.1 接口insert

使用map的迭代器遍历map中的元素,可以得到有序序列(排序+去重)。
void test2()
{map<string, string> dict;dict.insert(pair<string, string>("left", "左边"));dict.insert(pair<string, string>("right", "右边"));dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("string", "字符串"));dict.insert(make_pair("count", "计数"));dict.insert(make_pair("count", "计数"));map<string, string>::iterator it = dict.begin();while (it != dict.end()){cout << it->first << ":" << it->second << endl;++it;}
}
//结果
count:计数
left:左边
right:右边
sort:排序
string:字符串
make_pair是一个函数模板:

template <class T1,class T2>
pair<T1,T2> make_pair (T1 x, T2 y)
{return ( pair<T1,T2>(x,y) );
}
为了保证元素的唯一性,map中的元素均为const,所以并不能对元素进行修改,但可以进行插入删除。
4.2 operator[]和at
使用map统计每个字符出现个数
void test3()
{string arr[] = { "西瓜", "西瓜", "苹果", "苹果", "香蕉", "梨" };map<string, int> countMap;for (auto& e : arr){auto ret = countMap.find(e);if (ret == countMap.end()){countMap.insert(make_pair(e, 1));}else{ret->second++;}}for (auto e : countMap){cout << e.first << ":" << e.second << endl;}
}


调用insert函数,函数的第二个参数为value类型的缺省值,调用默认构造。
返回值是pair<iterator,bool>,pair.first 表示迭代器 ,解引用就为pair数据 ,pair数据取second就为value。
void test4()
{string arr[] = { "西瓜", "西瓜", "苹果", "苹果", "香蕉", "梨" };map<string, int> countMap;for (auto& e : arr){countMap[e]++;}for (auto e : countMap){cout << e.first << ":" << e.second << endl;}
}
V& operator[](const K& key)
{pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;
}

【operator[]的作用】:
-
插入:插入 left,第二个给缺省值,而string缺省值为空串。
-
修改:由于插入的left已经存在,所以插入失败,并寻找之前已经存在的left对应的迭代器,把left迭代器的返回值 value修改为左边。
-
插入+修改:插入right,第二个缺省值为空串,并把返回值 value修改为右边。
-
查找:直接返回对应的value值即可。
5、multimap的介绍

与map的区别:允许键值冗余。
使用multimap的迭代器遍历multiset中的元素,可以得到有序非去重序列(排序)。
void test5()
{multimap<string, string> dict;dict.insert(pair<string, string>("left", "左边"));dict.insert(pair<string, string>("right", "右边"));dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("string", "字符串"));dict.insert(make_pair("count", "计数"));dict.insert(make_pair("count", "数字"));multimap<string, string>::iterator it = dict.begin();while (it != dict.end()){cout << it->first << ":" << it->second << endl;++it;}
}
//结果
count:计数
count:数字
left:左边
right:右边
sort:排序
string:字符串
但是multimap并没有operator[],因为在map中,key和value是一对一的关系,在multimap中,key和value是一对多的关系,所以没办法判断当前key值对应哪一个value。
相关文章:
第四章:树形结构的关联式容器(map+set)
系列文章目录 文章目录 系列文章目录前言1、关联式容器与序列式容器1.1 键值对 2、set的介绍3、multiset的介绍3.1 接口count与容器multiset 4、map的介绍4.1 接口insert4.2 operator[]和at 5、multimap的介绍 前言 根据应用场景的不桶,STL总共实现了两种不同结构的…...
SpringBoot +Vue3 简单的前后端交互
前端:Vue3 创建项目: npm create vuelatest > cd <your-project-name> > npm install > npm run dev 项目结构图如下: 1、查看入口文件内容:main.js 代码如下: import ./assets/main.css impor…...
【Android】Mobile-Security-Framework-MobSF Manifest 静态扫描规则
前言 移动安全框架(MobSF)是一个自动化的一体化移动应用程序(Android/iOS/Windows)测试、恶意软件分析和安全评估框架,能够执行静态和动态分析。MobSF支持移动应用程序二进制文件(APK、XAPK、IPA和APPX&am…...
【C++】初谈迭代器
文章目录 前言一、什么是迭代器二、迭代器的分类三、迭代器的用法总结 前言 迭代器是一种可以访问和遍历容器中元素的对象,它类似于指针,但是具有更多的功能和灵活性。本文将介绍C迭代器的基本概念、分类、用法和注意事项。 一、什么是迭代器 迭代器&a…...
PL端案例开发手册
目 录 前 言 1 工程编译、程序加载方法 1.1 工程编译 1.2 程序加载 2 led-flash 2.1 案例说明 2.2 操作说明 2.3 关键代码 更多帮助 前 言 本文主要介绍PL端案例的使用说明,适用开发环境:Windows 7/10 64bit、Xilinx Unified 20…...
华为OD-整数对最小和
题目描述 给定两个整数数组array1、array2,数组元素按升序排列。假设从array1、array2中分别取出一个元素可构成一对元素,现在需要取出k对元素,并对取出的所有元素求和,计算和的最小值 代码实现 # coding:utf-8 class Solution:…...
Ubuntu 22LTS 配置静态IP
可行方法,需界面配置 转载自:哔哩哔哩链接地址 命令行配置:待补充...
【Python】Python爬虫:网络数据的提取利器
随着互联网的快速发展,网络数据已经成为了一项重要的资源。如何从海量的网络数据中提取出我们需要的信息,就成为了各个行业都需要解决的问题。而Python爬虫,就是解决这个问题的利器。 首先,让我们了解一下什么是Python爬虫。Pyth…...
20.图的遍历
目录 一. 深度优先遍历 二. 广度优先遍历 图的遍历算法和二叉树不同的是,图中可能存在回路,且图的任一顶点都可能与其它顶点相通,在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问,我们的解决思…...
ARM DIY(一)电源、SD卡座、SOC 调试
文章目录 前言加热台焊接热风枪吹焊电烙铁补焊电源调试SD 卡座调试DRAM 电路调试串口电路调试SOC 调试成品 前言 之前打样的几块 ARM 板,一直放着没去焊接。今天再次看到,决定把它焊起来。 加热台焊接 为了提高焊接效率,先使用加热台焊接…...
数学建模知识之小白入门篇
数学建模知识--小白入门篇 一、数学模型的定义二、建立数学模型的方法和步骤1. 模型准备2. 模型假设3. 模型构成4. 模型求解5. 模型分析 三、数模竞赛出题的指导思想四、竞赛中的常见题型1. 实际问题背景2.若干假设条件3.要求回答的问题 五、提交一篇论文…...
【日常积累】Linux下ftp服务安装
概述 FTP是一种在互联网中进行文件传输的协议,基于客户端/服务器模式,默认使用20、21号端口,其中端口20用于进行数据传输,端口21用于接受客户端发出的相关FTP命令与参数。FTP服务器普遍部署于内网中,具有容易搭建、方…...
确定了,TikTok将于9月12日正式关闭美国半闭环
外媒报道称,TikTok已对其官网的常见问题页面进行了更新。消息显示,其在美国和英国市场运营的半封闭模式将于9月12日正式结束,并将全力推进TikTok闭环小店业务。尽管我们早在本月初就获悉了这一消息,但实际得知后仍不免有些感慨。曾…...
ATFX汇评:英国7月零售销售年率大降,GBPUSD仍未升破1.3000
ATFX汇评:7月季调后零售销售年率,最新值-3.2%,前值-1.6%,降幅扩大;7月季调后核心零售销售年率,最新值-3.4%,前值-1.6%,降幅扩大。零售销售综合衡量除服务业外包括所有主要从事零售业…...
CTFhub-sqli注入-Referer注入
在最后添加 Referer: (注意 R 大写, Referer后面是 :,Content-Length: 与 Referer: 之间没有空行) 1 2 3 1 union select 1,database() -1 union select 1,database() -1 union select 1,group_concat(table_name)from information_sche…...
【案例】登录注册
<template><div class"loginhome"><Header :butShow"butShow"></Header><div class"formdiv"><div style"text-align:center;padding:10px;"><h3>你好登录账号{{ stauts 3? 注册:登录 }}…...
Unity 物体的运动之跟随鼠标
你想让鼠标点击哪里,你的运动的对象就运动到哪里吗? Please follow me ! 首先,你要先添加一个Plane ,以及你的围墙,你的移动的物体 想要实现跟随鼠标移动,我们先创建一个脚本 using System.Collections; using Syst…...
C++基础Ⅱ变量
目录儿 4 变量4.1 原始数据类型字符 char整型 short整型 int整型 long整型 long long单精度浮点型 float双精度浮点型 double布尔型 bool 4.2 sizeof 关键字 5 指针和引用 4 变量 4.1 原始数据类型 原始数据类型是构建C程序的最基础数据类型 所有数据都是基于这些原始数据类型…...
Linux管理SpringBoot应用shell脚本实现
Liunx系统如何部署和管理SpringBoot项目应用呢?最简单的方法就是写个shell脚本。 Spring Boot是Java的一个流行框架,用于开发企业级应用程序。下面我们将学习如何在Linux服务器上部署Spring Boot应用,并通过一个脚本实现启动、停止、重启等操…...
一篇搞懂浏览器的工作原理(万字详解)
摘要 本文是学习极客时间上的课程,进而整理出的浏览器工作原理。 第一部分:浏览器的进程和线程 (1)进程和线程的区别? 在浏览器中,各个进程负责处理自己的事情,而不同的进程中,也…...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...
Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
