【STL】容器 - set和map的使用

news/2024/4/25 9:15:16/文章来源:https://blog.csdn.net/Hello_World_213/article/details/127671360

目录

前言

一.键值对

1.在SGI - STL中对键值对的定义: 

2.make_pair

二.set

1.set的概念与注意事项

2.set的使用(常用接口)

<1>.构造函数

<2>.迭代器与范围for

<3>.插入和查找

<4>.删除erase

<5>.计数count

三.map

1.map的概念与注意事项

2.map的使用(常用接口)

<1>.构造函数

<2>.迭代器与范围for

<3>.查找find

<4>插入insert

<5>.删除erase

<6>.计数count

<7>.operator[]与at(重点)

前言

序列式容器与关联式容器

序列式容器:

string, vector, list, deque是序列式容器, 其底层都为线性结构, 在结构上没有其余特点, 里面存储的值是元素本身

关联式容器:

set, map, multiset, multimap是关联式容器, 其底层的结构有一定的特性与规则, 存储的是<key, value>键值对, 对于数据检索而言效率更高

注: set虽然是只存储key的容器, set也可以看为是<key, value>模型, 其中value就是key, 即为<key, key>, 在实际存储中只需要存储一个key即可

set和map, multiset和multimap

set和map的底层都是用红黑树实现的, 都自带去重

set和map的区别: set存储key, map存储key/value

multiset, multimap和set, map的区别: multiset, multimap不会去重, 其余都相同

由于其他内容过于相似, 只是去不去重的问题, 本篇博客主要介绍set和map, 对于multiset和multimap的介绍更像是基于map和set的扩展

一.键值对

一对用来表示一对对应关系, 经典的<key, value>模型, key代表键值, value表示对应的信息

在stl中, 用pair类将键值对进行了封装, 一个pair类对象就是一个键值对

1.在SGI - STL中对键值对的定义: 

template<class T1, class T2>
struct pair
{typedef T1 first_type;typedef T2 second_type;//默认构造pair():first(T1()), second(T2()){}//有参构造pair(const T1& a, const T2& b):first(a), second(b){}//成员变量T1 first; // keyT2 second;// value
};

2.make_pair

make_pair是C++提供的一个函数模板, 用来构建pair对象

为了使用者在创建键值对对象时更加轻松, 不用再去写过长的模板参数, 而是可以通过函数模板自动类型推导(这一点在使用map时会深有体会)

//模拟实现
template<class T1, class T2>
pair<T1, T2>& make_pair(const T1& first, const T2& second)
{return pair<T1, T2>(first, second);
}

二.set

1.set的概念与注意事项

1.set中只可以存储值, 这个值既是key, 又是value, 不需要构建键值对

2.set支持增删查, 而并不支持修改操作, 因为key是不可以被修改的

3.set的底层使用红黑树实现

4.set的查找效率是OlogN

5.set中不可以存储相同数据, 故可以达到去重的效果

6.set可以自己控制仿函数, 可以按照自己的比较规则来实现, 默认情况下使用less仿函数, 中序遍历是一个升序序列, 相反如果使用greater仿函数, 中序遍历就是一个降序序列

2.set的使用(常用接口)

set中元素不是连续存储的, 每个元素也只是一个单一的值, 所以不支持operator[]

<1>.构造函数

//构造函数
void set_test1()
{//默认构造set<int> s1;//迭代器区间构造vector<int> v = { 7,2,4,3,5,1,9 };set<int> s2(v.begin(), v.end());//拷贝构造set<int> s3(s2);//or: set<int> s3 = s2;//C++11新增构造函数set<int> s = { 7,2,4,3,5,1,9 };
}

<2>.迭代器与范围for

void set_test2()
{//正向遍历://默认使用less仿函数set<int> s = { 7,2,4,3,5,1,9 };//正向迭代器 - 底层是中序遍历set<int>::iterator it = s.begin();while (it != s.end()){cout << *it++ << ' ';}cout << endl;//范围forfor (auto& elem : s){cout << elem << ' ';}cout << endl;//反向遍历://方法一: 反向迭代器 reverse_iterator, rbegin(), rend()set<int>::reverse_iterator rit = s.rbegin();while (rit != s.rend()){cout << *rit++ << ' ';}cout << endl;//方法二://显式使用greater仿函数, 改变值的比较规则, 需要包头文件functionalset<int, greater<int>> s2 = { 7,2,4,3,5,1,9 };set<int>::iterator it2 = s2.begin();while (it2 != s2.end()){cout << *it2++ << ' ';}cout << endl;//范围forfor (auto& elem : s2){cout << elem << ' ';}cout << endl;
}

<3>.插入和查找

void set_test4()
{set<int> s = { 7,2,4 };s.insert(3);s.insert(5);s.insert(1);s.insert(9);for (auto& elem : s){cout << elem << ' ';}cout << endl;set<int>::iterator pos = s.find(5);if (pos != s.end()){cout << *pos << " is find" << endl;}
}

在multiset中查找会找到中序遍历中的第一个符合条件的值

multiset<int> ms = { 5,6,8,12,1,5,3,12,9,4,2,5 };
for (auto& elem : ms)
{cout << elem << ' ';
}
cout << endl;
multiset<int>::iterator pos = ms.find(5);
while (pos != ms.end())
{cout << *pos << ' ';pos++;
}
cout << endl;

multiset的插入会插入到所有相同值的最右侧, 也就是中序遍历的最后一个 

且set的insert与multiset的insert返回值类型不同

multiset<int> ms = { 5,6,8,12,1,5,3,12,9,4,2,5 };
for (auto& elem : ms)
{cout << elem << ' ';
}
cout << endl;
multiset<int>::iterator pos = ms.insert(5);;
while (pos != ms.end())
{cout << *pos << ' ';pos++;
}
cout << endl;
for (auto& elem : ms)
{cout << elem << ' ';
}

<4>.删除erase

void set_test3()
{set<int> s = { 7,2,4,3,5,1,9 };//set容器的erase接口既可以传值删除, 又可以传iterator删除//有什么区别?s.erase(3);for (auto& elem : s){cout << elem << ' ';}cout << endl;set<int>::iterator pos = s.find(4);if (pos != s.end()){s.erase(pos);}for (auto& elem : s){cout << elem << ' ';}cout << endl;
}

set容器的erase接口既可以传值删除, 又可以传iterator删除, 有什么区别? 

如果传入的是iterator, 则必须要走一步find操作, 在底层看来erase的传值删除实际是封装了先调用find查找, 再使用find返回的iterator删除这两步

上面是删除存在的数据, 如果此时删除一个不存在的数据且不用if(pos != s.end())进行判断, 传iterator删除是有问题的, 因为如果find找不到对应数据会返回end(), 所以erase传值删除的底层也是封装了find, 如果返回end(), erase底层会有检查, 所以如果是传iterator删除, 需要手动添加if(pos != s.end())这个条件, 否则如果数据不存在就会有问题

在multiset中会存在重复元素, erase会删除所有存在的元素

void multiset_test()
{multiset<int> ms = { 5 ,6,8,12,1,5,3,12,9,4,2,5 };for (auto& elem : ms){cout << elem << ' ';}cout << endl;ms.erase(5);for (auto& elem : ms){cout << elem << ' ';}cout << endl;
}

<5>.计数count

set为了与multiset保持一致也支持了这个接口, 因为set中不能存放重复数据所以count只有1或这是0

但在multiset中, count可以统计这个元素存在多少个

multiset<int> ms = { 5,6,8,12,1,5,3,5,9,4,2,5 };
for (auto& elem : ms)
{cout << elem << ' ';
}
cout << endl;
cout << "数字5有: " << ms.count(5) << "个" << endl;

三.map

1.map的概念与注意事项

1.map中存储的是键值对 --- pair<key, value>

2.map支持增删查改, 这个改指的是value可以修改, key不可以修改

3.map的底层使用红黑树实现

4.map的查找效率是OlogN

5.map中不可以存储相同数据, 故可以达到去重的效果

6.map可以自己控制仿函数, 可以按照自己的比较规则来实现, 默认情况下使用less仿函数, 中序遍历是一个升序序列, 相反如果使用greater仿函数, 中序遍历就是一个降序序列

7.map中存储的是键值对pair<key, value>, 比较只能用key比

2.map的使用(常用接口)

<1>.构造函数

void map_test1()
{//默认构造map<string, string> m1;//迭代器区间构造pair<string, string> kv1("home", "家");pair<string, string> kv2("happy", "高兴");pair<string, string> kv3("sort", "排序");vector<pair<string, string>> v = { kv1,kv2,kv3 };map<string, string> m2(v.begin(), v.end());//拷贝构造map<string, string> m3(m2);
}

<2>.迭代器与范围for

void map_test2()
{pair<string, string> kv1("home", "家");pair<string, string> kv2("happy", "高兴");pair<string, string> kv3("sort", "排序");vector<pair<string, string>> v = { kv1,kv2,kv3 };map<string, string> m(v.begin(), v.end());//迭代器遍历map<string, string>::iterator it = m.begin();while (it != m.end()){cout << it->first << "-" << it->second << ' ';it++;}cout << endl;//范围for遍历for (auto& elem : m){cout << elem.first << "-" << elem.second << ' ';}cout << endl;
}

<3>.查找find

void map_test3()
{pair<string, string> kv1("home", "家");pair<string, string> kv2("happy", "高兴");pair<string, string> kv3("sort", "排序");vector<pair<string, string>> v = { kv1,kv2,kv3 };map<string, string> m(v.begin(), v.end());//根据键值查找map<string, string>::iterator pos = m.find("happy");//如果没找到, m.find()返回m.end()if (pos != m.end()){cout << pos->first << '-' << pos->second << endl;}
}

<4>插入insert

这里insert的返回值是pair<iterator, bool>这是一个伏笔, 在后面operator[]的实现会体现他的作用 

void map_test4()
{map<string, string> m;//第一种插入方式, 先构造对象, 再插入pair<string, string> kv("good", "好");m.insert(kv);//第二种插入方式, 匿名对象m.insert(pair<string, string>("bad", "坏"));//第三种插入方式, 使用make_pair函数模板m.insert(make_pair("beautiful", "漂亮"));for (auto& elem : m){cout << elem.first << "-" << elem.second << ' ';}cout << endl;
}

<5>.删除erase

void map_test5()
{pair<string, string> kv1("home", "家");pair<string, string> kv2("happy", "高兴");pair<string, string> kv3("sort", "排序");vector<pair<string, string>> v = { kv1,kv2,kv3 };map<string, string> m(v.begin(), v.end());for (auto& elem : m){cout << elem.first << "-" << elem.second << ' ';}cout << endl;//传迭代器删除map<string, string>::iterator pos = m.find("happy");if (pos != m.end()){m.erase(pos);}for (auto& elem : m){cout << elem.first << "-" << elem.second << ' ';}cout << endl;//传key值删除cout << m.erase("home") << endl;for (auto& elem : m){cout << elem.first << "-" << elem.second << ' ';}cout << endl;
}

<6>.计数count

与set一样, count函数也是为multimap准备的, map中的count只是为了与multimap保持一致

<7>.operator[]与at(重点)

set是没有重载operator[]的, 在map中重载的operator[]是根据key返回对应的value的引用

map中的operator[]存在两种情况

1.传入的key值存在在map中, 则operator[]执行: 查找+修改value 

2.传入的key值不存在于map中, 则operator[]执行: 插入+修改value

如果这里insert没有返回这个pair<iterator, bool>, 那么在第2种情况, operator[]就要遍历两次, 第一次遍历, 查找且没有找到; 则需第二次遍历, 执行插入

解释insert的返回值pair<iterator, bool>:

由于map不会插入重复的键值, 插入时如果该键值已经存在, 则直接返回存在的这个键值对的迭代器, 如果插入的键值不存在, 则先插入, 后返回插入的这个键值对的迭代器, 但是需要插入的是<key,value>, 这时value就通过一个value的匿名对象去调用他的默认构造, 来构造出一个键值对

注: 对于内置类型, 例如int而言, int()这难道也要去调用int的默认构造吗? C++为了兼容自定义类型, 规定如int()这样的值就默认为0, float()就是0.0

这样operator[]的实现就可以复用一个insert就可以了

void map_test6()
{string str_array[] = { "老师", "学生", "校长","学生" ,"学生" ,"学生" ,"学生" ,"学生" ,"学生","老师","老师" };//统计老师,学生,校长各自的人数map<string, int> m;for (int i = 0; i < sizeof(str_array) / sizeof(str_array[0]); ++i){m[str_array[i]]++;}for (auto& elem : m){cout << elem.first << "-" << elem.second << ' ';}cout << endl;
}

对operator[]实现的解读

(this->insert(make_pair(key, value))) --- 拿到insert返回值 --- pair<iterator, bool>对象

( (this->insert(make_pair(key, value))) ).first --- 根据拿到的返回值对象, 去访问第一个成员iterator, 这个iterator是新插入或者查找到的key的键值对

(* ( (this->insert(make_pair(key, value))) ).first ).second --- 对拿到的iterator解引用, 在去访问iterator的第二个成员value, 以引用的形式返回

对于at而言, 只有查找+修改value的功能, 如果找不到就会抛出异常

void map_test7()
{string str_array[] = { "老师", "学生", "校长","学生" ,"学生" ,"学生" ,"学生" ,"学生" ,"学生","老师","老师" };//统计老师,学生,校长各自的人数map<string, int> m;for (int i = 0; i < sizeof(str_array) / sizeof(str_array[0]); ++i){m[str_array[i]]++;}for (auto& elem : m){cout << elem.first << "-" << elem.second << ' ';}cout << endl;m.at("校长") += 100;for (auto& elem : m){cout << elem.first << "-" << elem.second << ' ';}cout << endl;m.at("主任");
}

 

 

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

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

相关文章

SpringCloudAlibaba-Nacos配置中心

SpringCloudAlibaba-Nacos配置中心

开发环境 开发工具&#xff1a;IDEA 2021.3.2 JDK版本&#xff1a;JDK1.8 Maven版本&#xff1a;Maven3.8 SpringCloud版本&#xff1a;Hoxton.SR12 SpringCloudAlibaba版本&#xff1a;2.2.7.RELEASE SpringBoot版本&#xff1a;2.3.12.RELEASE Nacos版本&#xff1a;2.0.3 准…
阅读更多...
Allegro基本规则设置指导书之Same Net Spacing规则设置

Allegro基本规则设置指导书之Same Net Spacing规则设置

Allegro基本规则设置指导书之Same Net Spacing规则设置 下面介绍基本规则设置指导书之Same Net Spacing规则设置 设置Line到其它的间距规则 从左往右 线到线，通孔pin，表贴pin，测试pin，通孔Via，盲埋孔，测试孔，微孔，铜皮，Bond finger，hole之间的间距 设置pin到其它的…
阅读更多...
【1. MySQL锁机制】

【1. MySQL锁机制】

文章目录共享锁&#xff08;读锁也叫S锁&#xff09;/排他锁&#xff08;写锁也叫X锁&#xff09;行锁表锁意向锁间隙锁乐观锁悲观锁共享锁&#xff08;读锁也叫S锁&#xff09;/排他锁&#xff08;写锁也叫X锁&#xff09; 共享锁&#xff08;S锁&#xff09;&#xff1a;当一…
阅读更多...
【数据结构】搜索二叉树(C++实现)

【数据结构】搜索二叉树(C++实现)

目录 一、二叉搜索树的概念 二、二叉搜索树的实现 2.1 节点的定义及构造 2.2 树的结构及功能展示 2.3 树的 Insert 2.4 树的中序遍历 2.4 树的 Find 2.5 树的 Erase 2.6 拷贝构造、赋值运算符重载、析构函数 三、递归实现树的增删查 3.1 递归实现 FindR 3.2 递归实…
阅读更多...
Linux开发工具

Linux开发工具

目录 一、yum工具 1.yum 背景知识 &#xff08;1&#xff09;商业生态 &#xff08;2&#xff09;开源生态 &#xff08;3&#xff09;软件生态本土化 2.yum 的基本使用 &#xff08;1&#xff09;查看软件包 &#xff08;2&#xff09;软件包名称构成 &#xff08;3&a…
阅读更多...
高级架构师_Redis_第2章_数据类型与底层数据结构

高级架构师_Redis_第2章_数据类型与底层数据结构

高级架构师_Redis_第2章_数据类型与底层数据结构 文章目录高级架构师_Redis_第2章_数据类型与底层数据结构第二章&#xff1a;数据类型与底层数据结构本章学习目标&#xff1a;第一节&#xff1a;Redis 数据类型选择和应用场景1.1 Redis 的 Key 的设计1.2 String 字符串类型1.3…
阅读更多...
SpringSecurity Oauth2实战 - 04 自定义AuthProvider实现登录认证

SpringSecurity Oauth2实战 - 04 自定义AuthProvider实现登录认证

文章目录1. 搭建资源服务器1. Token存储配置类 TokenStoreAutoConfiguration2. 资源服务器配置类 ResourceServerAutoConfiguration3. 在META-INF/spring.factories文件下添加配置类2. 搭建授权服务器1. 密码加密配置类 PasswordEncodeConfig2. RestTemplateConfig3. 授权服务器…
阅读更多...
SQL学习笔记（未完待续）

SQL学习笔记（未完待续）

鉴于自己最近在做后端开发的工作时&#xff0c;发现自己的SQL能力实在太差&#xff0c;开始学习SQL语句基础&#xff0c;学习过程中在本博客进行笔记记录&#xff0c;课程参考&#xff1a;https://www.bilibili.com/video/BV1UE41147KC?p2 基本概念 DBMS: 数据库管理系统&am…
阅读更多...
基于Python实现的文章整合搜索引擎网站（Scrapy+Django+MySQL）

基于Python实现的文章整合搜索引擎网站（Scrapy+Django+MySQL）

目 录 摘 要… 1 1 概述… 6 2 技术选型… 6 2.1 Scrapy-Redis 分布式爬虫 … 6 2.1.1 Redis… 6 2.1.2 Scrapy… 7 2.2 MySQL 数据存储 … 8 2.3 Django 搭建搜索网站 … 8 2.4 ElasticSearch 搜索引擎 … 9 2.4.1 Elasticsearch-RTF… 9 2.4.2 Elasticsearch-head… 10 2.4.3…
阅读更多...
Kotlin编程实战——集合(07)

Kotlin编程实战——集合(07)

一 概述 集合概述构造集合迭代器(Iterable<T>)区间与数列序列(Sequence<T>)集合操作概述集合转换集合过滤加减操作符分组(groupBy())取集合的一部分取单个元素集合排序集合聚合操作集合写操作List 相关操作Set 相关操作Map 相关操作 二 集合概述 set、list 、map…
阅读更多...
【python】Numpy统计函数总结

【python】Numpy统计函数总结

文章目录函数列表相关系数直方图函数列表 最值amin, amax, nanmin, nanmax, 极差ptp分位数percentile∗^*∗ quantile∗^*∗,统计量中位数median∗^*∗&#xff1b;平均数mean∗^*∗&#xff1b;变化幅度var&#xff1b;加权平均average标准差std&#xff1b;协方差cov&#x…
阅读更多...
运算放大器正反馈负反馈判别法

运算放大器正反馈负反馈判别法

---------------------------------------------------------------------------------------------------------------- 反馈可分为负反馈和正反馈。前者使输出起到与输入相反的作用&#xff0c;使系统输出与系统目标的误差减小&#xff0c;系统趋于稳定&#xff1b;后者使输出…
阅读更多...
浅谈java中的String

浅谈java中的String

Java中的String类型不属于八大基本数据类型&#xff0c;而是一个引用数据类型&#xff0c;所以在定义一个String对象的时候如果不直接赋值给这个对象&#xff0c;它的默认值就是null。我们要怎么理解String类型的不可变&#xff0c;在JDK源码中String这个类的value方法被final关…
阅读更多...
【C++】如何修改set的值

【C++】如何修改set的值

问题&#xff1a;尝试通过begin方法得到的迭代器去修改值&#xff0c;发现会报错。 set<string> st{"hello", "world", "good"}; set<string>::iterator it st.begin(); *it "test"; 原因&#xff1a;我们可以在源码里…
阅读更多...
怎么搭建搜题接口api

怎么搭建搜题接口api

怎么搭建搜题接口api 本平台优点&#xff1a; 多题库查题、独立后台、响应速度快、全网平台可查、功能最全&#xff01; 1.想要给自己的公众号获得查题接口&#xff0c;只需要两步&#xff01; 2.题库&#xff1a; 查题校园题库&#xff1a;查题校园题库后台&#xff08;点击…
阅读更多...
RTSP协议学习Ubuntu环境准备

RTSP协议学习Ubuntu环境准备

文章目录RTSP协议学习Ubuntu环境准备RTSP协议概述Ubuntu环境准备一、Ubuntu安装FFmpeg二、安装ZLMediaKit1、获取代码2、强烈推荐3、编译器3.1、编译器版本要求3.2、安装编译器4、cmake5、依赖库5.1、依赖库列表5.2、安装依赖库6、构建和编译项目7、运行8、测试三、测试推流测试…
阅读更多...
【Tomcat】解决Tomcat服务器乱码问题

【Tomcat】解决Tomcat服务器乱码问题

俩地方开展出现乱码的原因1、以startup.bat文件打开的服务器出现乱码2、在IDEA中运行Tomcat服务器出现乱码问题3、有关社区版IDEA如何开发JavaWeb项目出现乱码的原因 使用了错误的字符编码去解码字节流&#xff0c;所以出现乱码咱思维要清晰&#xff0c;就去找字符编码是否与其…
阅读更多...
【TS04——接口的多态——泛型接口】

【TS04——接口的多态——泛型接口】

接口的多态&#xff0c;同一个方法&#xff0c;传入不同的参数&#xff0c;他所对应的操作不同成为多态【参数不同】或者可以理解为同一个方法&#xff0c;返回不同的结果&#xff0c;称之多态。 interface IfnPerson {run():voidrun(id:number):voidrun(id:number,name:strin…
阅读更多...
【生日快乐】Node.js 实战 第1章 欢迎进入Node.js 的世界 1.3 安装Node

【生日快乐】Node.js 实战 第1章 欢迎进入Node.js 的世界 1.3 安装Node

Node.js 实战 文章目录Node.js 实战第1章 欢迎进入Node.js 的世界1.3 安装Node第1章 欢迎进入Node.js 的世界 1.3 安装Node 安装Node的最简单的方法是使用其官网上的安装程序。可以用对应Mac或 Windows的安装程序安装最新的当前版。 官网安装包下载地址&#xff1a;https://…
阅读更多...
Jenkins部署详细教程

Jenkins部署详细教程

Jenkins简介 Jenkins 是一个可扩展的持续集成引擎。是一个自成一体的开源自动化服务器, 可用于自动化与构建、测试、交付或部署软件相关的各种任务; Jenkins是一个高度可扩展的产品, 其功能可以通过安装插件来扩展。 在gitlab里可以完成源代码的管理&#xff0c;但是对于研发…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站