【C++进阶04】STL中map、set、multimap、multiset的介绍及使用

这篇具有很好参考价值的文章主要介绍了【C++进阶04】STL中map、set、multimap、multiset的介绍及使用。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【C++进阶04】STL中map、set、multimap、multiset的介绍及使用,C++,c++,开发语言,windows

一、关联式容器

vector/list/deque…
这些容器统称为序列式容器
因为其底层为线性序列的数据结构
里面存储的是元素本身

map/set…
这些容器统称为关联式容器
关联式容器也是用来存储数据的
与序列式容器不同的是
其里面存储的是<key, value>结构的键值对
在数据检索时比序列式容器效率更高

二、键值对

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

三、set

3.1 树形结构的关联式容器

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

3.2 set的介绍

  1. set是按照一定次序存储元素的容器
    与map/multimap不同的是
    map/multimap中存储的是真正的键值对<key, value>
    set中只放value,但在底层实际存放的是由<value, value>构成的键值对

  2. 在set中,元素是唯一的
    元素的value就是key,类型为T
    set元素可以插入或删除,但不能修改
    map不能修改key,但可以修改value值
    set中插入元素时,只需要插入value即可,不需要构造键值对

  3. set中的元素总是按内部比较对象(类型比较)
    默认按照小于来比较
    所指示的特定“严格弱排序”准则进行排序
    使用set的迭代器遍历set中的元素,可以得到有序序列

  4. set容器通过key访问单个元素的速度通常比
    unordered_set容器慢,但它们允许根据顺序对
    子集进行直接迭代

  5. set中查找某个元素,时间复杂度为: l o g 2 n log_2 n log2n

set中的元素之所以不允许修改是怕破坏搜索规则

3.3 set的定义及使用

set的定义

set<int> s1; // 构造int类型的空容器

set<int> s2(s1); // 拷贝构造

string str("abcd");
set<char> s3(str.begin(), str.end()); // 迭代器构造某段区间

set<int, greater<int>> s4; // 比较方式改为大于 

set的各个接口跟之前学的vector、list差不多
就不多介绍
set的使用

void test_set()
{
	set<int> s;
	// 插入元素并去重
	s.insert(1);
	s.insert(1);
	s.insert(2);
	s.insert(1);
	s.insert(2);
	s.insert(3);
	s.insert(4);
	s.insert(3);

	// 搜索树不允许修改key,可能会破坏搜索的规则
	// 1. 迭代器遍历容器
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	// 2. 范围for遍历容器
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	// 删除元素
	s.erase(1);
	
	// 查找删除
	set<int>::iterator pos = s.find(2);
	if (pos != s.end())
		s.erase(pos);

	// 计算容器中值为3的元素
	cout << s.count(3) << endl;

	// 清空容器
	s.clear();

	// 交换两个容器的数据
	set<int> tmp{ 5, 7, 9 };
	s.swap(tmp);
}

// 输入一个值,查找在不在
void test_set2()
{
	set<int> s;
	s.insert(1);
	s.insert(1);
	s.insert(2);
	s.insert(1);
	s.insert(2);
	s.insert(3);
	s.insert(3);
	s.insert(3);

	int x;
	while (cin >> x)
	{
		/*
		set<int>::iterator it = s.find(x);
		if (it != s.end())
		{
			cout << "在" << endl;
		}
		else
		{
			cout << "不在" << endl;
		}
	*/
		if (s.count(x))
		{
			cout << "在" << endl;
		}
		else
		{
			cout << "不在" << endl;
		}
	}
}

multiset 允许冗余,其他跟set还是一样的

void test_set3()
{
	multiset<int> s;
	s.insert(1);
	s.insert(1);
	s.insert(2);
	s.insert(1);
	s.insert(2);
	s.insert(3);
	s.insert(3);
	s.insert(3);

	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	
	// 有多个key,find找中序的第一个key
}

四、map

4.1 map的介绍

  1. map是关联容器,它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元
    素,使用迭代器遍历map中的元素,可以得到一个有序序列

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

  3. map容器中的键值key不能修改,但元素值value可以修改
    因为map底层是根据每个元素的键值key构建的

  4. 在内部,map中的元素总是按照键值key进行比较排序的
    不传内部比较对象时,map中元素键值key默认按小于比较

  5. map中通过键值访问单个元素的速度通常比unordered_map容器慢,但map允许根据顺序
    对元素进行直接迭代

  6. map支持下标访问符,即在[]中放入key,就可以找到与key对应的value

  7. map的底层是平衡二叉搜索树(红黑树)
    map查找某个元素时间复杂度为 l o g N log N logN

4.2 map的定义及使用

map的定义

// 构造一个key为string,value为char的容器
map<string, char> m1; 

// 构造一个跟m1一样的容器
map<string, char> m2(m1);

// 迭代器构造m2的某段区间的容器
map<string, char> m3(m2.begin(), m2.end());

// key的比较方式改成大于
map<string, char, greater<string>> m4; 

map的插入和删除
【C++进阶04】STL中map、set、multimap、multiset的介绍及使用,C++,c++,开发语言,windows
value_type是pair的别名

typedef pair<const key, T> calue_type;

因此插入时需要构造一个pair的匿名对象

void test_map()
{
	map<string, string> dict;
	
	// 构造一个pair的匿名对象去插入
	dict.insert(pair<string, string>("int", "整型")); 
	
	// 用pair代码会很长,更常用的是make_pair
	// make_pair是一个函数模板,能通过传参自动推导类型
	dict.insert(make_pair("sort", "排序")); 
	dict.insert(make_pair("string", "字符串"));
	dict.insert(make_pair("count", "计数"));

	// 已经有的key,会插入失败
	dict.insert(make_pair("count", "(计数)")); 
	
	// map<string, string>::iterator dit = dict.begin();
	auto dit = dict.begin();
	while (dit != dict.end())
	{
		// 直接*dit无法通过编译.C++不支持返回两个值
		// dit解引用后是一个pair的结构体,里面有两个值,并不支持流插入
		// cout << (*dit).first << ":" << (*dit).second << endl;
		cout << dit->first << ":" << dit->second << endl; // 结构体里的指针一般用箭头
		dit++;
	}
	cout << endl;

	// 根据key值删除
	dict.erase(string);
	
	//迭代器删除
	map<string, string>::iterator pos = dict.find(sort);
	if (pos != dict.end())
		dict.erase(pos);
}

insert的返回值是pair
pair第一个成员是map的迭代器类型
第二个成员是bool类型

  • 若插入元素的键值key在map中不存在
    insert插入成功,并返回插入后元素的迭代器和true
  • 若插入元素的键值key在map中已存在
    则insert插入失败,并返回map中键值为key元素的迭代器和false

map的operator[ ]
【C++进阶04】STL中map、set、multimap、multiset的介绍及使用,C++,c++,开发语言,windows
operator[ ] 的返回值
【C++进阶04】STL中map、set、multimap、multiset的介绍及使用,C++,c++,开发语言,windows
[ ]operator实现的逻辑分为以下3个步骤:

  1. 调用insert函数插入键值对
  2. 拿出从insert函数获取到的迭代器
  3. 返回该迭代器位置元素的值value

代码分解

mapped_type& operator[] (const key_type& k)
{
	//1. 调用insert函数插入键值对
	pair<iterator, bool> ret = insert(make_pair(k, mapped_type()));
	//2. 拿出从insert函数获取到的迭代器
	iterator it = ret.first;
	//3. 返回该迭代器位置元素的值value
	return it->second;
}

[ ]的插入、修改、查找、插入+修改
以及统计水果出现的次数

void test_map2()
{
	string arr[] = { "苹果", "香蕉", "西瓜", "梨子", "香蕉", "西瓜", "西红柿", "香蕉", "西瓜", "苹果", "西红柿" };
	map<string, int> countMap;

	//for (auto e : arr) // 统计水果出现次数
	//{
	//	map<string, int>::iterator it = countMap.find(e);
	//	if (it == countMap.end())
	//	{
	//		countMap.insert(make_pair(e, 1));
	//	}
	//	else
	//	{
	//		it->second++;
	//	}
	//}

	for (auto& e : arr) // 方括号统计水果出现次数
	{
		countMap[e]++; // [] 的三个功能: 插入、修改、查找、插入+修改
	}

	for (auto& kv : countMap)
	{
		cout << kv.first << ":" << kv.second << endl; // 结构体里的指针一般用箭头
	}
	cout << endl;

}

// countMap[e]++; 这段代码底层实现
// V& operator[](const K& key)
// {
// 	pair<iterator, bool> ret = insert(make_pair(key, V()));
// 	return ret.first->second;
//}

void test_map3()
{
	map<string, string> dict;
	dict.insert(make_pair("sort", "排序"));
	dict.insert(make_pair("string", "字符串"));
	dict.insert(make_pair("count", "计数"));
	dict.insert(make_pair("count", "(计数)"));

	dict["left"]; // 插入
	dict["right"] = "右"; // 插入+修改
	dict["string"] = "(字符串)"; // 修改
	cout << dict["string"] << endl; // 查找
	cout << dict["endl"] << endl; // 查找

	auto dit = dict.begin();
	while (dit != dict.end())
	{
		cout << dit->first << ":" << dit->second << endl; 
		dit++;
	}
	cout << endl;
}

[ ]operator的返回值是key的value的引用
所以我们对该函数返回值的修改
实际就是对键值key的value的修改

multimap
multimap跟map基本一样
只是multimap允许键值冗余
find返回值是返回搜索树中序第一个键值
为key的元素的迭代器

由于冗余,调用operator[ ]时
返回键值应为哪个key的value引用
而存在歧义,因此multimap没有operator[ ]接口

如果支持迭代器就一定支持范围for
因为范围for的底层就是迭代器

五、map和set的区别

  1. map元素是key-value(关键字-值)对
    set元素是关键字
    map和set都不允许插入重复关键字

  2. set迭代器是const
    所以不允许修改元素值
    map可以修改value,但不能修改key
    map和set底层红黑树依靠关键字保持有序性
    所以不允许修改关键字

  3. map支持下标操作,set则不支持
    注意:map下标通过insert实现
    也就是尝试插入一个查询键值对
    如果存在则返回该键值对

✨✨✨✨✨✨✨✨
本篇博客完,感谢阅读🌹
如有错误之处可评论指出
博主会耐心听取每条意见
✨✨✨✨✨✨✨✨文章来源地址https://www.toymoban.com/news/detail-777672.html

到了这里,关于【C++进阶04】STL中map、set、multimap、multiset的介绍及使用的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【高阶数据结构】map和set的介绍和使用 {关联式容器;键值对;map和set;multimap和multiset;OJ练习}

    关联式容器和序列式容器是C++ STL中的两种不同类型的容器。 关联式容器是基于键值对的容器 ,其中每个元素都有一个唯一的键值,可以通过键值来访问元素。关联式容器包括set、multiset、map和multimap。 序列式容器是基于元素序列的容器 ,其中元素按照一定的顺序排列,可以

    2024年02月11日
    浏览(40)
  • 详解map、set、multimap、multiset的使用

    ✍ 作者 : 阿润菜菜 📖 专栏 : C++ map、set、multimap、multiset是C++ STL中的四种关联容器,它们内部都使用了红黑树这种高效的平衡检索二叉树来存储数据 。它们的区别和用法如下: map是一种 键值对 容器,它可以根据键来快速查找、插入和删除值,它的键是唯一的,不能重复

    2024年02月03日
    浏览(32)
  • 【C++】map/multimap/set/multiset的经典oj例题 [ 盘点&全面解析 ] (28)

    前言 大家好吖,欢迎来到 YY 滴C++系列 ,热烈欢迎! 本章主要内容面向接触过C++的老铁 主要内容含: 欢迎订阅 YY 滴C++专栏!更多干货持续更新!以下是传送门! YY的《C++》专栏 YY的《C++11》专栏 YY的《Linux》专栏 YY的《数据结构》专栏 YY的《C语言基础》专栏 YY的《初学者易

    2024年02月04日
    浏览(45)
  • map、multimap、set、multiset讲解

    2023年07月10日
    浏览(44)
  • C++进阶--unordered_set、unordered_map的介绍和使用

      在C++98中,STL提供了底层为红黑树结构的一系列关联式容器,在查询时效率可达到 l o g 2 N log_2N l o g 2 ​ N ,即最差情况下需要比较红黑树的高度次,当树中的节点非常多时,查询效率也不理想。最好的查询是,进行很少的比较次数就能够将元素找到,因此在C++11中,STL又

    2024年01月16日
    浏览(50)
  • 【C++入门到精通】C++入门 —— set & multiset (STL)

    前面我们讲了C语言的基础知识,也了解了一些初阶数据结构,并且讲了有关C++的命名空间的一些知识点以及关于C++的缺省参数、函数重载,引用 和 内联函数也认识了什么是类和对象以及怎么去new一个 ‘对象’ ,也了解了C++中的模版,以及学习了几个STL的结构也相信大家都

    2024年02月08日
    浏览(41)
  • 详解 C++中STL的map/multimap

    ap容器中所有元素都是pair,pair中第一个元素为key(键值),起到索引作用,第二个元素为value(实值)。 同时,所有元素都会根据元素的键值自动排序。 map/multimap属于关联式容器,底层数据结构是用二叉树实现的。它的优点就是可以根据key值快速找到value值。 这里需要了解map与

    2024年02月16日
    浏览(48)
  • 【C++入门到精通】C++入门 —— map & multimap (STL)

    各位小伙伴们,在这个美好的中秋节来临之际,我衷心祝福你和你的家人度过一个幸福、团圆的时刻。愿明月的皎洁照耀你的每一天,团圆的月饼传递着我对你的思念和祝福。祝福你在中秋佳节里收获幸福与快乐,家庭和睦,心想事成。中秋快乐! 前面我们讲了C语言的基础

    2024年02月08日
    浏览(40)
  • Google 开源库Guava详解(集合工具类)—Maps、Multisets、Multimaps

    Maps有许多很酷的实用程序,值得单独解释。 Maps.uniqueIndex(Iterable,Function)解决了一个常见的情况,即有一堆对象,每个对象都有一些唯一的属性,并希望能够根据该属性查找这些对象。 假设我们有一堆字符串,我们知道它们有唯一的长度,我们希望能够查找具有特定长度

    2024年02月03日
    浏览(44)
  • 【C++】 使用红黑树模拟实现STL中的map与set

    前面的文章我们学习了红黑树,也提到了C++STL中的map和set的底层其实就是用的红黑树来实现的(而map和set的使用我们前面也学过了)。 既然红黑树我们也学习过了,那这篇文章我们就用红黑树来简单实现一下STL中的map和set,重点是学习它的框架。 上一篇文章我们实现了红黑

    2024年02月12日
    浏览(31)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包