当前位置:首页 » 《关于电脑》 » 正文

【C++】7000字介绍map容器和set容器的功能和使用

3 人参与  2024年12月07日 16:01  分类 : 《关于电脑》  评论

点击全文阅读


目录

一、关联式容器和序列式容器

二、键值对,>

三、树形结构的关联式容器

四、set容器(key模型)

1、文档官网

2、功能介绍:

3、注意事项:

4、基本使用,更多接口可查看官网:

(1)、插入一组数字并用迭代器遍历。

(2)、习惯用set进行排序和去重操作:

(3)、三种erase(删除)的区别:

五、multiset容器(允许插入重复值)

1、文档官网:

2、介绍:

3、基本使用:

3、因为可以插入重复值,所以有些接口也有所区别:

(1)、第二种删除方式的返回值:

(2)、count函数:

(3)、find函数

六、map容器(kvalue模型:),value>

1、文档官网

2、介绍:

3、pair模板类:

(1)、文档官网:

(2)、定义:

4、map的基本使用,更多接口可以查看官网进行学习:

七、multimap容器

八、map容器的[ ](重要)

计算水果出现的次数:

1、使用迭代器和find函数:

2、使用insert函数的返回值

3、使用map的[ ]


前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家

点击跳转到网站

一、关联式容器和序列式容器

1、序列式容器:vector、list、deque、forward_list(C++11)等,这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面存储的是元素本身。 2、关联式容器:也是用来存储数据的,与序列式容器不同的是,其里面存储的是<key, value>结构的键值对,在数据检索时比序列式容器效率更高

二、键值对<key, value>

通过key去找value 用来表示具有一 一 对应关系的一种结构,该结构中一般只包含两个成员变量key和value,key代表键值,value表示与key对应的信息。比如:现在要建立一个英汉互译的字典,那该字典中必然有英文单词与其对应的中文含义,而且,英文单词与其中文含义是一 一对应的关系,即通过该单词,在词典中就可以找到与其对应的中文含义。

三、树形结构的关联式容器

根据应用场景的不同,STL总共实现了两种不同结构的管理式容器:树型结构与哈希结构。树型结构的关联式容器主要有四种:map、set、multimap、multiset。这四种容器的共同点是:使用平衡搜索树(即红黑树)作为其底层结果,容器中的元素是一个有序的序列(中序遍历)。

四、set容器(key模型)

1、文档官网

set - C++ Reference

2、功能介绍:

(1)、set是按照一定次序存储元素的容器 (2)、在set中,元素的value也标识它(value就是key,类型为T),并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const),但是可以从容器中插入或删除它们。 (3)、在内部,set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。 (4)、 set容器通过key访问单个元素的速度通常比unordered_set容器慢,但它们允许根据顺序对子集进行直接迭代。 (5)、set在底层是用二叉搜索树(红黑树)实现的。

3、注意事项:

(1)、与map/multimap不同,map/multimap中存储的是真正的键值对<key, value>,set中只放 value,但在底层实际存放的是由<value, value>构成的键值对。 (2)、set中插入元素时,只需要插入value即可,不需要构造键值对。 (3)、set中的元素不可以重复(因此可以使用set进行去重)。 (4)、使用set的迭代器遍历set中的元素,可以得到有序序列(排序) (5)、set中的元素默认按照小于来比较(二叉搜索树的中序遍历) (6)、set中查找某个元素,时间复杂度为:【log_2  n】 (7)、set中的元素不允许修改,因为底层是二叉搜索树,如果对元素进行修改,就可能不满足二叉搜索树的结构。 (8)、set中的底层使用二叉搜索树(红黑树)来实现  (9)、头文件:<set>.

4、基本使用,更多接口可查看官网:

(1)、插入一组数字并用迭代器遍历。
#include<iostream>using namespace std;#include<set>int main(){set<int> s;//插入s.insert(5);s.insert(2);s.insert(10);s.insert(7);s.insert(6);s.insert(1);s.insert(4);s.insert(3);s.insert(8);s.insert(9);//迭代器set<int>::iterator it = s.begin();while (it!= s.end()){cout << *it << " ";it++;}cout << endl;//范围forfor (auto& e : s){cout << e << " ";}cout << endl;return 0;}

我们需要先查看文档学习相关接口和函数的介绍。迭代器对于各大容器都是一回事,所以使用方法是相同的。

(2)、习惯用set进行排序和去重操作:

根据上面的描述可知,set是根据搜索二叉树的中序遍历进行插入的,所以可以对一组数进行排序,并且不会插入相同的数,所以可以达到去重的功能。

(3)、三种erase(删除)的区别:

set提供了三种删除

第一种是删除某个迭代器位置:如果存在就删除,如果不存则报错:

这里涉及一个find函数:find函数为查找某个数,并返回该位置,若没找到则返回end();

set<int> s;//插入s.insert(5);s.insert(2);s.insert(10);s.insert(7);s.insert(6);s.insert(1);s.insert(4);s.insert(3);s.insert(8);s.insert(9);//迭代器set<int>::iterator it = s.begin();it = s.find(1);//find函数为查找某个数,并返回该位置,若没找到则返回end();if (it != s.end()){s.erase(it);}

因为找不到会报错,所以需要用一个if语句进行判断,否则会如下:

第二种是删除某个val值,并返回删除的个数;

//第一二种删除,如果存在就删除,如果不存在就不做处理s.erase(10);s.erase(9);s.erase(1000);

第三种是删除一个迭代器区间,左闭右开;

这里涉及两个操作:

lower_bound:返回大于等于k的位置

upper_bound:返回大于k的位置

利用上述两个函数得到一个左闭右开区间在进行删除。

假设我们删除区间[3,6],因为erase的参数为左闭右开区间,所以我们需要得到区间

[3,7),所以lower_bound可以得到左闭,upper_bound可以得到右开:

//第三种删除//删除区间[3,6],则需要得到区间[3,7)auto start = s.lower_bound(3);cout << "start指向的位置的值:" << *start << endl;auto finish = s.upper_bound(6);cout << "finish指向的位置的值:" << *finish << endl;s.erase(start, finish);

五、multiset容器(允许插入重复值)

1、文档官网:

multiset - C++ Reference

2、介绍:

(1)、multiset是按照特定顺序存储元素的容器,其中元素是可以重复的。 (2)、 在multiset中,元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成的键值对,因此value本身就是key,key就是value,类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的),但可以从容器中插入或删除。 (3)、在内部,multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。 (4)、multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢,但当使用迭代器遍历时会得到一个有序序列。 (5)、 multiset底层结构为二叉搜索树(红黑树)。

3、基本使用:

multiset容器和set容器是类似的,最大的区别就是set不能存储重复的数据,而multiset容器可以存储重复的数据
int main(){multiset<int> mus;//插入mus.insert(5);mus.insert(2);mus.insert(10);mus.insert(7);mus.insert(6);mus.insert(1);mus.insert(4);mus.insert(3);mus.insert(8);mus.insert(9);mus.insert(9);mus.insert(9);multiset<int>::iterator it = mus.begin();while (it != mus.end()){cout << *it << " ";it++;}cout << endl;return 0;}

3、因为可以插入重复值,所以有些接口也有所区别:

(1)、第二种删除方式的返回值:
上面我们知道第二种删除时有返回值的,返回的就是删除元素的个数,在set容器中,返回值无非就是0和1,实际使用在这里才能体现出来:
(2)、count函数:
该函数的作用为:返回val值在容器中的个数,在set中返回值也无非就是0和1,在multiset容器中才能更好使用。
(3)、find函数
set中的find函数作用为:查找val值,存在则返回该位置,不存在则返回end(); 而mulitset容器可能存在多个重复值,所以功能会有所不同: mulitset容器中find函数为: 找中序遍历中出现的第一个val值,并返回位置。

六、map容器(kvalue模型:<key,value>)

1、文档官网

map - C++ Reference

2、介绍:

(1)、 map是关联容器,它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。 (2)、在map中,键值key通常用于排序和惟一的标识元素,而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同,并且在map的内部,key与value通过成员类型 pair 绑定在一起,为其取别名称为value_type : typedef pair<const key, T> value_type; (3)、在内部,map中的元素总是按照键值key进行比较排序的。 (4)、map中通过键值访问单个元素的速度通常比unordered_map容器慢,但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时,可以得到一个有序的序列)。 (5)、map支持下标访问符,即在[ ]中放入key,就可以找到与key对应的value。 (6)、map通常被实现为二叉搜索树(更准确的说:平衡二叉搜索树(红黑树))。 (7)、头文件:<map>

3、pair模板类:

因为map的成员是pair模版类对象,所以先学习pair模板类;

(1)、文档官网:

pair - C++ Reference

(2)、定义:

pair是一个模板类,定义在<utility>头文件中。它用于将两个不同类型的值组合成一个单一的对象(键值对)。这两个值可以是相同类型,也可以是不同类型。 (3)、make_pair函数: 该函数的作用就是构建一个pair对象:

pair<int, int> pa1(1,1);cout << pa1.first << " " << pa1.second << endl;pair<int, int> pa2 = make_pair(2, 2);cout << pa2.first << " " << pa2.second << endl;

4、map的基本使用,更多接口可以查看官网进行学习:

(1)、map模版参数的说明:

(1)、key: 键值对中key的类型 (2)、T: 键值对中value的类型 (3)、Compare: (仿函数)比较器的类型,map中的元素是按照key来比较的,缺省情况下按照小于来比较,一般情况下(内置类型元素)该参数不需要传递,如果无法比较时(自定义类型),需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递) (4)、Alloc:通过空间配置器来申请底层空间,不需要用户传递,除非用户不想使用标准库提供的空间配置器 (5)、注意:在使用map时,需要包含头文件<map> (2)、插入函数insert: 我们常用第一种方式,即参数是一个value_type类型的引用,而value_type是pair<T1,T2>的别名,所以实际参数是一个pair对象。返回值下面再介绍。
int main(){map<string, string> ma;//一、使用匿名pair对象ma.insert(pair<string, string>("good", "好的"));//二、有名pair对象pair<string, string> pa("apple", "苹果");ma.insert(pa);//三、C++11中多参数隐式类型转换(构造函数)ma.insert({ "sort","排序" });//四、C++98常用make_pair函数链式调用:ma.insert(make_pair("age", "年龄"));map<string, string>::iterator it = ma.begin();while (it != ma.end()){cout << it->first << " " << it->second << endl;it++;}cout << endl;return 0;}
打印时的注意事项: 这里不能直接解引用访问,因为map的成员变量为pair对象,是自定义类型,没有重载"<<"运算符,所以只能用结构体的两种访问方式:点(.)和' -> '。  介意范围for加上引用,因为拷贝的代价有点大: 5、map是根据键值去重的: 与set类似,map也有排序和去重的功能,并且是根据键值k进行操作的: 如果是字符串,排序则依次根据首字母的ascll码值进行排序。

七、multimap容器

与set和mulitset类似,map也有一个与之对应的容器mulitmap容器

其他接口与上述类似,区别就是mulitmap容器可以插入重复值。插入是根据键值k来判断的,所以重复值即重复的键值k。

八、map容器的[ ](重要)

为了方便理解,我们以一个场景下进行讲解:

计算水果出现的次数:

string arr[] = { "苹果","菠萝","草莓","苹果","菠萝","草莓" ,"苹果","菠萝","草莓" "苹果","菠萝","草莓" };

1、使用迭代器和find函数:

for (auto& e : arr){map<string, int>::iterator flag = mapCount.find(e);if ( flag == mapCount.end())//说明没找到,则插入,并计数为1{mapCount.insert(make_pair(e, 1));}else//找到了,计数++{flag->second++;}}

2、使用insert函数的返回值

查看官网我们发现,使用map的[  ]时,会转化为如下:

我们可以看到是复用了insert函数,并运用了insert函数的返回值。所以首先我们需要理解insert的返回值是什么?

查看官网可以发现insert的返回值是一个pair<iterator,bool>的类模板类型:

因为不想新构造类模板,所以这里复用了pair类模板,pair类模板是一个单独的类模版,不是map独有的,所以每个地方都可以使用。

返回值模版参数的介绍:

(1)、bool:插入成功则为true,插入失败则为false(有重复键值K,则插入失败);

(2)、iterator:插入成功,则指向新插入元素所在的结点;插入失败,则指向map中与之键值k重复的那个结点。

知道了返回值的含义,我们就可以使用insert完成上述功能:

//使用insertfor (auto& e : arr){//构建insert返回值的pair对象pair<map<string, int>::iterator, bool> ret;ret = mapCount.insert(make_pair(e, 1));if (ret.second == false){//插入失败,说明已经存在,则计数++ret.first->second++;}}

3、使用map的[ ]

上述说明使用map的[ ]时,会转化为如下:

这样不方便观察,所以简化如下:

也就是说其实是复用了insert的返回值,来找到对应map结点位置的second。

其中,V()是默认构造的缺省值,(如int()),V为int,则默认值为0,V为指针,则默认值为nullptr。

所以可以使用[ ]完成水果计数:

//使用map的[ ]for (auto& e : arr){mapCount[e]++;}

参数e用键值key的引用进行接收,然后调用insert函数,若插入成功,则返回值pair对象的模版参数iterator就指向新插入这个结点,若插入失败,则指向map中重复键值K那个结点,最后返回该结点的second,所以我们在外面对mapCount[e]进行++,其实就是对键值K为e的那个结点的second进行++,以此达到计数的功能。

因为[ ]复用了insert函数,所以[ ]还能完成下述功能:


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/197660.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1