首页 > 编程语言 >【C++进阶】C++关联式容器map和set用法详解

【C++进阶】C++关联式容器map和set用法详解

时间:2024-03-15 15:59:56浏览次数:24  
标签:map set 进阶 迭代 insert C++ 键值 pair

map和set用法详解

上一节我们讲解了二叉搜索树,在讲解之前我们先来讲一下set和map,因为set和map的底层是AVL树和红黑树,而AVL树和红黑树又是一种二叉搜索树,所以我们先熟悉一下map的set及其用法,也为后面的模拟实现做铺垫。

一,关联式容器

在前面的STL容器中,我们学习了string,vector,list等,这些都是这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面存储的是元素本身。
而map和set是关联式容器,关联式容器也是用来存储数据的,存储数据时可不是随便存放的,还要与其他数据进行关联,而且与序列式容器不同的是,其里面存储的是 <key, value>结构的键值对,在数据检索时比序列式容器效率更高。

二,键值对pair

在关联式容器中存储的不单单只是元素,而是一种键值对结构,该结构中一般只包含两个成员变量key和value,key代表键值,value表示与key对应的信息。

其代码是这样的:

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

先来看set,set是一个K模型的结构,不能有重复元素。
在这里插入图片描述

set是按照一定次序存储元素的容器,其中序遍历可以得到升序序列,这是因为其内部仿函数是less,上图可以看到默认的是less。set中的元素不能修改,set在底层是用二叉搜索树(红黑树)实现的。

所以set实际上是排序+去重

1. set的用法

下面来看set的用法


先来看构造:
在这里插入图片描述
set可以构造为空,也可以用迭代器区间构造

set<int> s1;
vector<int> v(10,1);
set<int> s2(v.begin(),v.end());
set<int> s3(s2);

然后来看下set的迭代器:

在这里插入图片描述
迭代器部分的使用和之前的其他容器没有什么区别

set<int> s;
set<int>::iterator it = s.begin();
while(it != s.end()){
	cout<<*it<<" ";
	++it;
}

当然也支持范围for,但是注意尽量加上引用,因为其内部存储的是键值对,加上引用可以减少拷贝

for(auto &e : s){
	cout<<e<<" ";
}

set不能对数据做修改,只能插入和删除
在这里插入图片描述
我们看一下插入
在这里插入图片描述
set可以值插入,也可以传入迭代器位置插入,也可以传入迭代器区间。

set<int> s;
s.insert(1);
set<int>::iterator it = s.begin();
s.insert(it,2);
int a[] = {1,2,3,4};
s.insert(a.begin(),a.end());

来看删除之前先看一下find
在这里插入图片描述

find会返回要查找值的迭代器位置,如果找不到,则返回最后一个位置

find一般会和erase搭配使用

现在来看set的删除
在这里插入图片描述
可以传入迭代器位置,也可以传入值来删除,也可以传入迭代器区间。
这里删除时传入值和迭代器位置的删除方式略有不同,

set<int> s;//set排序+去重
int a[] = { 1,3,5,2,4,8,5,6,7 };
for (auto &e : a) {
	s.insert(e);
}
auto pos = s.find(3);
if (pos != s.end()) {
	cout << "找到了" << endl;
	s.erase(pos);
}

s.erase(1);

如果删除的值不存在呢,当传入的是迭代器位置时,不存在会报错,而传入的是值时则不做处理。

auto poss = s.find(10);
s.erase(poss);	//

s.erase(10);

报错:
在这里插入图片描述


下面来看看count函数,这个接口的作用就是返回set中值的个数,没有则为0 。一般用来检查一个值在不在
在这里插入图片描述


再来看下这两个接口,这两个接口是用来确定一段区间,比如要删除set中2~5之间的数,要找到这个区间就传入这个区间的两端的值,会返回这两个位置的迭代器。
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

具体的使用场景看下面来理解:
可以看到 lower_boundupper_bound 返回的值

void test_set2()
{
	// 排序+去重
	set<int> s;
	s.insert(5);
	s.insert(1);
	s.insert(6);
	s.insert(3);
	s.insert(4);

	// [60, 70]
	// [)
	auto start = s.lower_bound(3);  // >=val
	cout << *start << endl;

	auto finish = s.upper_bound(5);  // >val
	cout << *finish << endl;
	//s.erase(start, finish);

	while (start != finish)
	{
		cout << *start << " ";
		++start;
	}
	cout << endl;

	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

在这里插入图片描述
所以可以得知,lower_bound 返回的是>=所要查找的值,upper_bound 返回的是 >呀查找的值,其实为的是返回的是一个左闭右开的区间

2. multiset的用法

现在来看multiset,multiset在底层中存储的是<value, value>的键值对
multisetset的区别是这个可以存放重复的值。
在这里插入图片描述

其他的接口和set相差不大:
在这里插入图片描述

multiset也是默认升序的,这里也体现出count接口的作用,统计某个值出现了几次。

void test_set3()
{
	// 排序
	multiset<int> s;
	s.insert(5);
	s.insert(1);
	s.insert(6);
	s.insert(3);
	s.insert(4);
	s.insert(5);
	s.insert(1);
	s.insert(1);
	s.insert(5);
	s.insert(1);
	s.insert(1);
	s.insert(2);
	s.insert(7);
	s.insert(10);


	multiset<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	cout << s.count(5) << endl;
	cout << s.count(1) << endl;
}

但是对于find接口,当一个值出现多次的时候,要返回哪一个呢,我们可以来验证一下

	it = s.find(5);
	while (it != s.end() && *it == 5)
	{
		// *it += 100;

		cout << *it << " ";
		++it;
	}
	cout << endl;

其实find找到后会返回中序的第一个值

四,map

map是关联容器,它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素

在这里插入图片描述
从上图可以看到,map的默认比较器Compare也是less,当其中序遍历时,是按照Key的值来升序排列的。

也就是说map中存储的是一种键值对结构,和set不同的是map里面有两个值,也就是KV模型结构,map也不能存储Key相同的节点。

在map中,键值key通常用于排序和惟一地标识元素,而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同,并且在map的内部,key与value通过成员类型value_type绑定在一起,为其取别名称为pair:

typedef pair<const key, T> value_type;

1. 键值对pair的介绍

在讲map的用法之前先说一下键值对pair,什么是键值对呢?

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

其中pair中的first就对应的是map中的Key,second对应的是map的Value。

2. map用法

来看一下map的构造
在这里插入图片描述
这里和set的差别不大


map的迭代器用法也和set一样,也支持范围for,同样也要注意加上&

在这里插入图片描述


我们直接来看insert

在这里插入图片描述
map的插入时和set不同,这里的value_type是一个pair。
在这里插入图片描述
返回值也是一个pair

插入时可以用匿名对象:

map<string, string> m;

m.insert(pair<string, string>("sort", "排序"));
m.insert(pair<string, string>("apple", "苹果"));
m.insert(pair<string, string>("BMW", "宝马"));

当然最推荐的方式是 make_pair

m.insert(make_pair("jeep", "吉普"));

也可以支持隐式类型转换,这里是因为C++11 支持多参数构造函数的隐式类型转换

m.insert({ "apple", "苹果" });

插入后我们也可以验证map存储的是pair,查看pair里面的值:

for (auto& kv : m)
{
	cout << kv.first << ":" << kv.second << endl;
}
cout << endl;

map也可以在迭代器位置插入和迭代器区间插入


map是支持[]的,这里的[]和平时我们用的可不一样,

在讲[]之前我们先来想想如何用map来统计每种水果出现的次数:
一般的方法我们是这样:

string s[] = {"apple","binina","jim","tom","apple","jerry","jim","apple"};
map<string, int> m;

//统计水果个数
for (auto &e : s) {
	map<string, int>::iterator it = m.find(e);//map的find如果找到会返回其迭代器位置,找不到会返回end()
	if (it != m.end()) {
		it->second++;
	}else{
		m.insert(make_pair(e, 1));
	}
}
for (auto& e : m) {
	cout << e.first << ":" << e.second << endl;
}

cout << endl;

但是我们要是用[],那么就方便很多:

//用[]统计
for (auto& e : s) {
	m[e];
}
for (auto& e : m) {
	cout << e.first << ":" << e.second << endl;
}

可以看到两种方法的结果是一样的!
在这里插入图片描述

这是为什么呢?因为当我们定义map为<string, int>时,[]既可以在没有这种水果的时候进行插入,又可以在水果存在的时候统计其出现的次数,并且分别存储在map的Key和Value中。

从下图可以看到这里传入的是map中的Key,返回的是Value。
在这里插入图片描述
在其内部其实是调用了insert的,
在这里插入图片描述


而为什么要调用insert呢?
这就要先来看看insert的返回值了
在这里插入图片描述
这里插入的时候,返回的是也一个pair结构,但是里面存储的一个是iterator迭代器位置,一个是bool值,这里注意:返回的pair和map存储的pair不是同一个

  1. 当检测到要插入的值不存在时,这个返回的pair中iterator是插入后的位置,bool为true,
  2. 当检测到要插入的值存在时,这个返回的pair中iterator是要插入的原位置,bool为false,

知道了insert的返回值我们来看[]如何调用insert的

在这里插入图片描述


map的erase和set也一样
在这里插入图片描述
知道了[]的原理后,[]不仅可以统计次数,还可以插入元素,修改Value值,

map<string, string> dict;
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("string", "字符串"));
dict.insert(make_pair("sort", "xxx"));

dict["left"]; // 插入
cout << dict["sort"] << endl; // 查找
dict["sort"] = "xxx"; // 修改
dict["right"] = "右边"; // 插入+修改

for (auto& kv : dict)
{
	cout << kv.first << ":" << kv.second << endl;
}
cout << endl;

3. multimap用法

在这里插入图片描述
multimap和multiset一样,和map和set的区别就是可以存储重复的值,但是这里的multimap不支持[]
在这里插入图片描述

五,总结

知道了set和map后,我们还是要多做练习才可以更深入的理解。下节我会讲解AVL树,终于要上难度了,希望大家可以在我的讲解下能轻松掌握!!

标签:map,set,进阶,迭代,insert,C++,键值,pair
From: https://blog.csdn.net/weixin_64906519/article/details/136475264

相关文章

  • C#--进阶
    CSharp进阶知识点学习知识点汇总简单数据结构类:Lesson1:ArrayList练习:usingSystem;usingSystem.Collections;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;usingSystem.Threading.Tasks;namespaceLesson1_练习{#region......
  • Write failed: Broken pipe > Couldn‘t read packet: Connection reset by peer SFTP
    如果你链接服务器的时候出现下面的提示:Writefailed:BrokenpipeCouldn’treadpacket:Connectionresetbypeer这个问题的原因是ChrootDirectory的权限问题,你设定的目录必须是root用户所有,否则就会出现问题。所以请确保sftp用户根目录的所有人是root,权限是750或者755。......
  • set容器详解
    set 是关联容器,含有键值类型对象的已排序集,搜索、移除和插入拥有对数复杂度。set 内部通常采用 红黑树 实现。平衡二叉树 的特性使得 set 非常适合处理需要同时兼顾查找、插入与删除的情况。和数学中的集合相似,set 中不会出现值相同的元素。如果需要有相同元素的集合,......
  • Git进阶命令-revert
    有关Git,之前有写过两篇文章:Git五个常见问题及解决方法Git进阶命令-reset一、revert命令使用场景有一天项目经理跟你说,你开发上线的代码有问题,需要马上撤回。撤回?你第一反应那不就是reset一下嘛。正当你满心欢喜,想找到需要reset的commitId时,你惊喜的发现,master分支......
  • 知识点总结,c,c++的各种知识点
    、1、C/C++1.1关键字(参考”嵌入式及Linux那些事“以及众多帖子汇总而成)volatile​ 当声明指向设备寄存器的指针时一定要用volatile,它会告诉编译器不要对存储在这个地址的数据进行假设。​ 中断服务程序中修改的供其他程序检测的变量。中断中直接从变量地址中读取数......
  • pta帅到没朋友(c/c++版)
     c语言中的小小白-CSDN博客c语言中的小小白关注算法,c++,c语言,贪心算法,链表,mysql,动态规划,后端,线性回归,数据结构,排序算法领域.https://blog.csdn.net/bhbcdxb123?spm=1001.2014.3001.5343给大家分享一句我很喜欢我话:知不足而奋进,望远山而前行!!!铁铁们,成功的路上必......
  • c/c++数据对齐问题
    c/c++如何在栈上保证数据对齐:#include<iostream>struct__attribute__((aligned(16)))X{}; intmain(){Xx{};std::cout<<((longlong)&x)%16;}汇编代码X86-64(仅开头部分):main:pushrbpmovrbp,rspsubrsp,16可以看到并没有做什么特别操作,仅仅准备......
  • setup factory添加注册表
       result=SessionVar.Get("%AppFolder%");proversion=SessionVar.Get("%ProductVer%");Registry.CreateKey(HKEY_LOCAL_MACHINE,"SOFTWARE\\*******\\***")Registry.SetValue(HKEY_LOCAL_MACHINE,"SOFTWARE\\*******\\......
  • vue3中setup使用及其语法糖的用法
    使用setup语法糖后,不用写setup函数;组件只需要引入不需要注册;属性和方法也不需要再返回,可以直接在template模板中使用。.setup语法糖中新增的apidefineProps:子组件接收父组件中传来的propsdefineEmits:子组件调用父组件中的方法defineExpose:子组件暴露属性,可以在父组件中......
  • Android NDK入门:在应用中加入C和C++的力量
    目录​编辑引NDK的设计目的与Java/Kotlin的结合使用场景开发流程设置项目以支持NDK编写本地代码使用JNI连接本地代码和Java/Kotlin代码编译和运行你的应用附 引自诩方向是android方向的移动端开发工程师,却从来没有真正仔细了解过NDK,这里就详细的整理了解一下n......