【C++】map和set的介绍+使用

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

注意：

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中的元素不允许修改

（2）set的使用

set的插入：

和很多容器一样，set设置了插入的接口，但是set的插入是有额外的功能性的！

我们试用下面的代码：

void test_set1()
{
	set<int> s1;
	s1.insert(2);
	s1.insert(6);
	s1.insert(2);
	s1.insert(3);
	s1.insert(3);
	s1.insert(5);
	s1.insert(8);
	s1.insert(8);
	s1.insert(6);
	s1.insert(7);

//两种迭代打印的方法：：
	set<int>::iterator it = s1.begin();
	while (it != s1.end())
	{
		// 搜索树不允许修改key，可能会破坏搜索的规则
		//*it1 += 1;
		cout << *it << " ";
		++it;
	}
	cout << endl;


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

}

输出结果：

set实现了去重和排序：

有重复的不插入
默认按照升序排列

同样的迭代器的使用方式也一样，只是这里的const迭代器和普通迭代器都是一样的，都不支持修改，原因是如果对二叉搜索树进行修改的话，很有可能会导致整棵树的结构被打乱，所以不支持修改。

set的查找：

应用代码：

void test_set2()
{
	// 排序 + 去重
	set<int> s1;
	s1.insert(2);
	s1.insert(6);
	s1.insert(2);
	s1.insert(3);
	s1.insert(3);
	s1.insert(5);
	s1.insert(8);
	s1.insert(8);
	s1.insert(6);
	s1.insert(7);
	int x;
	while (cin >> x)
	{
		/*auto ret = s1.find(x);
		if (ret != s1.end())
			cout << "在" << endl;
		else
			cout << "不在" << endl;*/

		if (s1.count(x))
			cout << "在" << endl;
		else
			cout << "不在" << endl;
	}
}

这里find的用法和算法库里的一样，但是为什么要再在set中创立一个呢？

set自带的查找和算法库中的查找有什么区别

set自带的查找是利用了搜索树的特点，查找时间复杂度为〇（logN）
如果用算法库中的查找则是通过暴力查找的方式进行的，时间复杂度为〇（N）

set的删除：



		set<int> s;
		s.insert(4);
		s.insert(5);
		s.insert(2);
		s.insert(1);
		s.insert(1);
		s.insert(3);
		s.insert(2);
		s.insert(1);

		s.erase(3);//直接给值删除

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

		int x;
		while (cin >> x)
		{
			set<int>::iterator pos = s.find(x);
			if (pos != s.end())
			{
				s.erase(pos);//迭代器删除
				cout << "删除" << x << "成功" << endl;
			}
			else
			{
				cout << x << "不在set中" << endl;
			}

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

删除接口也没什么可以过多介绍的了，还有size、empty、clear等接口和我们之前学的容器接口用法一样，大家可以自己实践一下！

（3）multiset的介绍+使用

set会自动实现去重的操作，那我们只想拥有排序等相关的操作，而不想去重，这里STL也为我们提供了multiset容器。

介绍：

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

用法：


void test_set3()
{
	multiset<int> s1;
	s1.insert(1);
	s1.insert(1);
	s1.insert(2);
	s1.insert(3);
	s1.insert(3);
	s1.insert(4);
	s1.insert(4);
	s1.insert(4);
	s1.insert(5);

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

	cout << endl;

	auto ret = s1.find(1);
	cout << *ret << endl;
	while (ret != s1.end() && *ret == 1)
	{
		cout << *ret << " ";
		++ret;
	}
	cout << endl;
	cout << s1.count(1) << " ";
	cout << s1.count(5) << " ";

}

输出结果：

这里我们看到，可以打印出重复的数据了，此时count的作用可以计数了，不需要局限于和find同等的用处。

（三）map

（1）map的介绍

使用 map 容器，必须引入该头文件#include < map >

map的使用文档

key: 键值对中key的类型

T：键值对中value的类型

Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比

较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户

自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)

Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的

空间配置器

介绍：

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

（2）map的使用

map的插入：

其实map的操作也和其他容器的操作是一样的，但由于map中存放的是键值对，所以我们以插入为例来介绍如何使用：

void test_map1()
{
	map<string, string> dict;
	//匿名对象的好处
	dict.insert(pair<string, string>("sort", "排序"));

	//不用匿名对象
	pair<string, string> kv("insert", "插入");
	dict.insert(kv);

	//make_pair是函数模板
	dict.insert(make_pair("left", "左边"));

	//可以这么写但是别这么用（隐式类型的转换） -- C++11再讲
	dict.insert({ "right", "右边" });

	//map的遍历
	map<string, string>::iterator it = dict.begin();
	while (it != dict.end())
	{
		//cout << *it << endl;//it->operator*() -- C++不支持返回两个值
		//cout << (*it).first << ":" << (*it).second << endl;

		cout << it->first << ":" << it->second << endl;

		it++;
	}
	cout << endl;

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

我们这里使用匿名对象配合insert使用非常方便，库中也给了make_pair函数模板来表示键值对的创建。

因为C++不支持返回两个值，所以我们这里用到了pair，通过pair的first和second，即可访问到两个值。

同时，map迭代器的使用方法和其他容器迭代器的使用方法一样，这是STL设计时为了方便使用，所采用的高维度泛型设计。

Key_value模型中，修改不能修改key，但是可以修改value。

**std::map::operator[]的使用（*重点）：**

引入：

我们利用map来统计各个水果出现的次数：

通过查找来挨个遍历查找统计个数

void test_map2()
{
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果",
					 "西瓜", "苹果", "香蕉", "苹果", "香蕉" };

	map<string, int> countMap;
	for (auto& str : arr)
	{
		map<string, int>::iterator it = countMap.find(str);
		if (it != countMap.end())
		{
			it->second++;
		}
		else
		{
			countMap.insert(make_pair(str, 1));
		}
	}
}

注意：

只要是一对一对的值都可以用pair
first和second是不允许被修改的

insert的返回值是一个pair，pair的first是一个迭代器（如果插入成功了指向新插入的位置，如果插入失败了，则返回已经存在的结点的位置），pair的second的一个bool值，插入成功是返回true，失败是返回false。

所以我们还可以通过返回值来统计个数

但是map库中给出 operator[ ] ，其实他的应用会让上述郭晨改变的更简单易懂！

在之前学习的容器中，operator[]都有随机访问的意思，这里的方括号已经没有了随机访问的意思
这里operator[]的参数是key，返回值是value的引用

其中可以对文档中的最后一句对此函数的调用等效于：

我么能深入探讨一下，理解如下：

所以operator[ ]的参数是key，返回值是value的引用！！！

我们可以用operator[ ]来统计次数：

因为返回的是value的引用所以，可以修改，这样一来，operator[]兼顾了两个功能：插入 + 修改

同样当map需要插入的时候，也就有了如下的写法：


void test_map2()
{
	map<string, string> dict;
	//dict.insert(pair<string, string>("sort", "排序"));
	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["count"] = "（计数）";//修改
	cout << dict["count"] << endl; // 查找

	//map<string, string>::iterator dit = dict.begin();
	auto dit = dict.begin();
	while (dit != dict.end())
	{
		//cout << (*dit).first << ":" << (*dit).second << endl;
		cout << dit->first << ":" << dit->second << endl;

		++dit;
	}
	cout << endl;
}

operator[ ]的使用不仅可以简化计数等，还可以兼顾插入、修改、查找等作用！大家重点理解！

感谢您的阅读！

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

c

开发语言