C++进阶 | [4] map and set

摘要:set,multiset,map,multimap

前言

1. 容器 

  • 序列式容器:只存储数据,数据之间无关联关系。例如,vector、list、deque、……
  • 关联式容器:不仅存储数据,且数据之间有关联关系。例如,map、set、…

2. 键对值

用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量 key 和 valuekey 代表键值,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){}
};

本文将介绍 set、multiset、map、multimap 。 


1. set

set - C++ Reference (cplusplus.com)

set 是一个 key 模型的搜索二叉树。因此,set 对于数据具有排序(搜索二叉树的特点) + 去重(不允许重复值)的作用。
注意:set 内存储的数据不可被修改(BST都不支持修改key)


1)insert

//single element (1)    
pair<iterator,bool> insert (const value_type& val);

//with hint (2)    
iterator insert (iterator position, const value_type& val);

//range (3)    
template <class InputIterator>
void insert (InputIterator first, InputIterator last);

通过文档可以看到 insert 有 3 个重载。

当使用 pair<iterator,bool> insert (const value_type& val); 插入指定值的结点,函数返回的是一个 pair<iterator,bool> 的对象。该 pair 的 first 为迭代器,指向新插入的元素(插入成功 second 值为 true)或已有的等效元素(插入失败 second 值为 false)

使用示例:

#include<set>
#include<map>
#include<vector>
#include<iostream>void test_set()
{std::set<int> s1;std::vector<int> vt = { 4,2,6,1,8,9,5,3,2,4 };for (auto e : vt){auto tmp = s1.insert(e);std::cout << e << " " << tmp.second << std::endl;}
}int main()
{test_set();return 0;
}

2)erase & find & count

(1)
     void erase (iterator position);

ps. position 必须是存在的,否则会报错

(2)
     size_type erase (const value_type& val);

ps.val 是否 是 存在的值都可以

(3)
     void erase (iterator first, iterator last);

由于 iterator position 不存在而报错的举例:

void test_set()
{std::set<int> s1;std::vector<int> vt = { 4,2,6,1,8,9,5,3,2,4 };for (auto e : vt){auto tmp = s1.insert(e);std::cout << e << " " << tmp.second << std::endl;}std::set<int>::iterator it2 = s1.find(7);//没找都会返回s1.end()s1.erase(it2);//这样就会导致删除错误//因此,如果通过find函数找到结点再erase,那么使用erase之间要进行判断
}

  •  find count 的区别:
    iterator find (const value_type& val) const; 👉 find 返回类型是 iterator,判断是否 find 成功需要取到这个返回值,并判断是否与 std::set::end 相等。即 find 是都成功判断起来比较麻烦。
    
    size_type count (const value_type& val) const; 👉 (这里 size_type 参看文档可知是 size_t。)count 返回类型为 size_t,成功返回1,失败返回0,比较方便判断。

3)lower_bound & upper_bound

iterator lower_bound (const value_type& val) const;

Return value

An iterator to the the first element in the container which is not considered to go before* val, or set::end if all elements are considered to go before val.

Member types iterator and const_iterator are bidirectional iterator types pointing to elements.

*在这句话中,"go before" 表示在顺序上位于指定值 val 之前的意思。换句话说,如果元素被认为在指定值 val 之前,即比 val 小或者按照容器自身的排序规则排在 val 之前,那么这些元素就被视为"go before val"


iterator upper_bound (const value_type& val) const;

Return value

An iterator to the the first element in the container which is considered to go after* val, or set::end if no elements are considered to go after val.

Member types iterator and const_iterator are bidirectional iterator types pointing to elements.

*类比上面的 "go before",这句话中的 "go after" 就很好理解了。

void test_set2()
{std::set<int> myset;std::set<int>::iterator itlow, itup;for (int i = 1; i < 10; i++) myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90itlow = myset.lower_bound(30);                     //       ^// itloew将指向第一个不位于30之间的元素,即>=30,即30itup = myset.upper_bound(60);                      //                   ^// itup将指向第一个位于60之后的元素,即>60,即70myset.erase(itlow, itup);                     // 10 20 70 80 90std::cout << "Myset Contains:";for (std::set<int>::iterator it = myset.begin(); it != myset.end(); ++it)std::cout << ' ' << *it;
}

对于上述代码,itlow = myset.lower_bound(30); == itlow = myset.lower_bound(25);  即这两句话得到的itlow是相等的。>=30即30;>=25即30.
而对于 myset.erase(itlow, itup); 即删除 [ 30, 60 ] 这个闭区间的所有值。


4)equal_range

pair<iterator,iterator> equal_range (const value_type& val) const;

Return value

The function returns a pair, whose member pair::first is the lower bound of the range (the same as lower_bound), and pair::second is the upper bound (the same as upper_bound).

如上,即 pair::first 为 按顺序第一个 >= val 的结点的 iterator,pair::second 为 按顺序第一个 > val 的结点的 iterator.
(ps.这个函数对 set 容器来说用处不大)


2. multiset

multiset - C++ Reference (cplusplus.com)

相比与 setmultiset 允许重复值。因此,multiset 对于数据仅具有排序的作用。multiset 与 set 很相似,以下简化表达,且只讲解一些存在差异的地方。

①对于重复值,插入到右树还是左树都可以。因为插入之后导致搜索二叉树不平衡会旋转,图例如下;

②如果有重复值,find(val) 会返回中序遍历序列的第一个值为 val 的 iterator;

equal_range(val) → 返回值 pair::first >= valpair::second > val →  [ first, second ) 在这个区间内,则找到了所有重复的 val 值结点;

count(val) 会统计值为 val 的结点个数;

erase(val) 删除所有值为 val 的结点,并返回删除结点的个数(return size_t)


3. map

map - C++ Reference (cplusplus.com)

map 是一个 KV 模型的搜索二叉树。KV 即 key and valuevaluekey 的映射值。key 不可被修改,value 可被修改。根据下表,KV的 K 即key_type,V即 mapped_type。KV 整体即 value_type。
(前面自己实现的 KV 模型的BST的 key 与 value 是分开的,而 map 的处理是将两者融合进 pair对象中。)

member typedefinition
key_typeThe first template parameter (Key)
mapped_typeThe second template parameter (T)
value_typepair<const key_type,mapped_type>

1)insert

single element (1)
pair<iterator,bool> insert (const value_type& val);
with hint (2)
iterator insert (iterator position, const value_type& val);
range (3)
template <class InputIterator>void insert (InputIterator first, InputIterator last);

value_type → pair<const key_type,mapped_type> → pair<const Key,T>

如下代码,Key → string,T → string. 

void test_map()
{std::map<std::string, std::string> dict;dict.insert(std::pair<std::string, std::string>("sort", "排序"));//方式一:匿名对象std::pair<std::string, std::string> pr("test", "测试");//方式二dict.insert(pr);pr = { "cruel","残忍的" };dict.insert(pr);auto it = dict.begin();while (it != dict.end()){std::cout << it->first << ":" << it->second << " ";++it;}std::cout << std::endl;
}
  • std::make_pair

对于 map 的 insert ,以下介绍一种更常用的写法。

std::make_pair:(function)<utility>

template <class T1, class T2>pair<T1,T2> make_pair (T1 x, T2 y);
//插入更常用的写法↓  方式三:make_pair()
dict.insert(std::make_pair("autumn","秋天"));

2)用 map 统计次(个)数

思路:对于一组给定的数据,实例化出相应的 map 对象,在 map<Type, int> 中依次查找给定的数据,该数据未在其(map实例化的对象)中则插入数据,若有则对其数量(int)++.

示例代码如下:

void test_Count()
{std::vector<std::string> vstr = { "apple","banana","grap","apple","cherry","cherry","grap","cherry","lemon","grap" };std::map<std::string, int> Count;for (auto str : vstr){if (Count.find(str) == Count.end())//没找到Count.insert(std::make_pair(str, 1));else//找到了++Count.find(str)->second;}auto it = Count.begin();while (it != Count.end()){std::cout << it->first << ":" << it->second << std::endl;++it;}
}
  • ⭐ std::map::operator[]

mapped_type& operator[] (const key_type& k);

Access element

If k matches the key of an element in the container, the function returns a reference to its mapped value.

If k does not match the key of any element in the container, the function inserts a new element with that key and returns a reference to its mapped value. Notice that this always increases the container size by one, even if no mapped value is assigned to the element (the element is constructed using its default constructor).

A similar member function, map::at, has the same behavior when an element with the key exists, but throws an exception when it does not.

A call to this function is equivalent to:
(*((this->insert(make_pair(k,mapped_type()))).first)).second

注意该函数的返回值:

Member type mapped_type is the type of the mapped values in the container, defined in map as an alias of its second template parameter (T) 

分析:

  1. 如上,通过阅读文档可知,[key] → 该操作有两种情况:①key已经存在,则返回key的映射值(mapped value)的引用;②key不存在,则插入key,并返回这个key的映射值的引用。
  2. A call to this function is equivalent to: (*((this->insert(make_pair( k,mapped_type() ))).first)).second
    逐步拆解这句代码👇

 

通过使用这个函数,下面进一步优化上面统计次(个)数的代码:

void test_Count2()
{std::vector<std::string> vstr = { "apple","banana","grap","apple","cherry","cherry","grap","cherry","lemon","grap" };std::map<std::string, int> Count;for (auto str : vstr){++Count[str];//⭐}auto it = Count.begin();while (it != Count.end()){std::cout << it->first << ":" << it->second << std::endl;++it;}
}

4. multimap

multimap - C++ Reference (cplusplus.com)

  • 相比于 mapmultimap 允许重复值。
  • 不支持 operator[]

END

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

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

相关文章

AI智能体|扣子Coze文生图功能接入微信公众号

大家好&#xff0c;我是无界生长。 AI智能体&#xff5c;扣子Coze文生图功能接入微信公众号本文分享了如何将Coze平台的文生图功能接入微信公众号的详细操作流程&#xff0c;包括创建图像流、创建并配置Bot、设置提示词和开场白、调试、发布等步骤。如果看完还没学会的话&…

stream-并行流

定义 常规的流都是串行的流并行流就是并发的处理数据&#xff0c;一般要求被处理的数据互相不影响优点&#xff1a;数据多的时候速度更快&#xff0c;缺点&#xff1a;浪费系统资源&#xff0c;数据少的时候开启线程更耗费时间 模版 Stream<Integer> stream1 Stream.of…

ELK 日志监控平台(一)- 快速搭建

文章目录 ELK 日志监控平台&#xff08;一&#xff09;- 快速搭建1.ELK 简介2.Elasticsearch安装部署3.Logstash安装部署4.Kibana安装部署5.日志收集DEMO5.1.创建SpringBoot应用依赖导入日志配置文件 logback.xml启动类目录结构启动项目 5.2.创建Logstash配置文件5.3.重新启动L…

wordpress教程视频 wordpress教程网盘 wordpress教程推荐wordpress教程网

WordPress&#xff0c;作为一款强大且灵活的开源内容管理系统&#xff0c;已成为许多网站开发者与运营者的首选。其强大的功能、丰富的插件以及易于上手的特点&#xff0c;使得无论是初学者还是专业开发者都能轻松构建出个性化的网站。然而&#xff0c;对于初学者来说&#xff…

亚马逊高效广告打法及数据优化,亚马逊高阶广告打法课

课程下载&#xff1a;https://download.csdn.net/download/m0_66047725/89342733 更多资源下载&#xff1a;关注我。 课程内容&#xff1a; 001.1-亚马逊的广告漏斗和A9算法的升级变化.mp4 002.2-流量入口解析和广告的曝光机制.mp4 003.3-标签理论 .mp4 004.4-不同广告类…

在未来你将何去何从?

在数字化的浪潮中&#xff0c;信息技术行业无疑是推动全球经济和社会发展的重要动力。随着科技的不断迭代与进步&#xff0c;云计算、大数据、人工智能&#xff08;AI&#xff09;、物联网&#xff08;IoT&#xff09;、5G通信和区块链等技术已经深入到我们生活的每一个角落&am…

计算机专业必考之计算机指令设计格式

计算机指令设计格式 例题&#xff1a; 1.设相对寻址的转移指令占3个字节&#xff0c;第一字节为操作码&#xff0c;第二&#xff0c;第三字节为相对偏移量&#xff0c; 数据在存储器以低地址为字地址的存放方式。 每当CPU从存储器取出一个字节时候&#xff0c;自动完成&…

Java实现图书系统

首先实现一个图书管理系统,我们要知道有哪些元素? 1.用户分成为管理员和普通用户 2.书:书架 书 3.操作的是: 书架 目录 第一步:建包 第二步:搭建框架 首先:完成book中的方法 其次:完成BookList 然后:完成管理员界面和普通用户界面 最后:Main 第三步:细分方法 1.退…

【数学建模】碎纸片的拼接复原

2013高教社杯全国大学生数学建模竞赛B题 问题一模型一模型二条件设立思路 问题求解 问题一 已知 d i d_i di​为第 i i i张图片图片的像素矩阵 已知 d i d_i di​都是 n ∗ m n*m n∗m二维矩阵 假设有 N N N张图片 模型一 我们认为对应位置像素匹配为 d i [ j ] [ 1 ] d k…

访问构造方法(反射)

文章目录 前言一、反射是什么&#xff1f;二、访问构造方法 1.Constructor对象的获取方法2.Constructor方法的使用总结 前言 Java的反射机制可以实现访问、检测和修改Java对象本身信息的功能&#xff0c;在java.lang.reflect包下提供此功能。可以使程序员更加深入地控制程序的运…

openflow协议抓包分析

1、准备实验拓扑&#xff1a; 在Mininet环境中创建一个简单的SDN拓扑&#xff0c;包括控制器、交换机、主机等。 确保拓扑能够正常运行&#xff0c;SDN交换机与控制器建立连接。 采用主机Ubuntu22.04主机&#xff0c;IP地址是192.168.87.130&#xff0c;安装opendaylight控制…

【HarmonyOS4学习笔记】《HarmonyOS4+NEXT星河版入门到企业级实战教程》课程学习笔记(十二)

课程地址&#xff1a; 黑马程序员HarmonyOS4NEXT星河版入门到企业级实战教程&#xff0c;一套精通鸿蒙应用开发 &#xff08;本篇笔记对应课程第 19节&#xff09; P19《18.ArkUI组件-页面路由》 以访问京东页面为例&#xff0c;访问过的页面并没有消失&#xff0c;而是进入了…

三维大场景管理-3Dtiles规范

简介 &#xff1a; 这篇文章都是三年前写的了&#xff0c;一直在笔记库存中&#xff0c;今天把他放出来。主要是讲Cesium 的3Dtiles 格式&#xff0c;当然3Dtiles主要是解决场景管理大场景的LOD实现的问题&#xff0c;不管是剔除渲染性能优化之Culling 剔除或者 LOD 、3Dtiles…

吉林大学计科21级《软件工程》期末考试真题

文章目录 21级期末考试题一、单选题&#xff08;2分一个&#xff0c;十个题&#xff0c;一共20分&#xff09;二、问答题&#xff08;5分一个&#xff0c;六个题&#xff0c;一共30分&#xff09;三、分析题&#xff08;一个10分&#xff0c;一共2个&#xff0c;共20分&#xf…

基于tcp实现自定义应用层协议

认识协议 协议&#xff08;Protocol&#xff09; 是一种通信规则或标准&#xff0c;用于定义通信双方或多方之间如何交互和传输数据。在计算机网络和通信系统中&#xff0c;协议规定了通信实体之间信息交换的格式、顺序、定时以及有关同步等事宜的约定。简易来说协议就是通信…

Linux shell编程学习笔记50:who命令

0 前言 2024年的网络安全检查又开始了&#xff0c;对于使用基于Linux的国产电脑&#xff0c;我们可以编写一个脚本来收集系统的有关信息。比如&#xff0c;我们可以使用who命令来收集当前已登陆系统的用户信息&#xff0c;当前运行级别等信息。 1. who命令 的功能、格式和选项…

初级爬虫的总结一

初级爬虫的总结一之百度网页爬虫 一、寻找正确的sugrec二、url拼接出问题&#xff0c;解决办法 我遇到的问题&#xff1a; 1、没有找对网页sugrec&#xff0c;导致connect-type没有找对&#xff0c;以及一些小问题 2、url拼接时候出现乱码 一、寻找正确的sugrec 1、打开百度网…

【讲解下Web前端三大主流的框架】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…

node.js学习P3-P10

P3 npm package.json&#xff08;package解读npm工具换镜像源&#xff09; 一个package.json文件可以的作用 作为一个描述文件&#xff0c;描述了你的项目依赖哪些包 &#xff0c;用来干什么的允许我们使用“语义版本规则”&#xff0c;指明你项目依赖的版本让你的构建更好的…

Web安全:SQL注入之时间盲注原理+步骤+实战操作

「作者简介」&#xff1a;2022年北京冬奥会网络安全中国代表队&#xff0c;CSDN Top100&#xff0c;就职奇安信多年&#xff0c;以实战工作为基础对安全知识体系进行总结与归纳&#xff0c;著作适用于快速入门的 《网络安全自学教程》&#xff0c;内容涵盖系统安全、信息收集等…