C++之map和set

摘星

发布于 2023-04-28 09:02:16

6860

发布于 2023-04-28 09:02:16

文章被收录于专栏：C/C++学习C/C++学习

前言

本文介绍了C++STL中的关联式容器map和set的相关概念，主要介绍了它们的概念和使用。

一、关联式容器

我们之前了解的STL容器中的vector、list、deque等都被称为序列式容器，因为它们的底层为线性序列的数据结构，存储的是元素本身。那么什么是关联式容器呢？他与序列式容器又有什么区别呢？实际上，关联式容器也是用来存储数据的，但它与序列是不同它所存储的是<key, value>结构的键值对，这种存储方式在进行数据检索时比序列式容器的效率高。

二、键值对

键值对是用于表示具有一一对应关系的一种结构，这种结构中一般只包含两个成员变量key和value，其中key代表键值，value表示与key对应的信息。例如，英汉词典，单词与它的中文含义之间是一一对应的关系，即通过该词就能在词典中找到它的中文含义。那么单词就是key键值，中文含义就是value这个键值对应的信息。 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(T1(a))
		,second(T2(b))
	{}
};

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

1.概念

根据应用场景的不同，STL共实现了两种不同结构的关联式容器：树形结构和哈希结构。树形结构的关联式容器有四种：map、set、multimap、multiset。这四种容器的共同特点是：它们的底层都是一个平衡搜索树（红黑树），容器中的元素是一个有序的序列。哈希结构的关联式容器有两种：unordermap、unorderset。它们的底层实现是哈希表。

2.set

set的介绍

set是按照一定次序存储元素的容器，set中的元素总是按照内部比较对象（类型比较）所指示的特定排序准则进行排序，使用set的迭代器遍历set可以得到有序序列，注意：set中的元素默认按小于进行排序；

与map不同，map中存储的是键值对<key,value>，set中只放value，但是底层实际存放的是<value,value>构成的键值对；
在set中，元素的value也可以标识它（value就是key，类型为T），并且每一个value都必须是唯一的，即set中的元素是不能重复的，因此可以用set进行去重；
set中的元素不能在容器中进行修改，只能进行增、删、查等操作；
set查找某个元素的时间复杂度为：

log_2 n

，set容器通过key访问单个元素的效率比unordered_set效率低，但是它允许根据顺序对元素进行直接迭代；

set的底层是二叉搜索树（红黑树）。

set的使用

set的模板参数列表

Compare 参数是比较器类型，一般不需要显示传递，如果无法比较（自定义类型），需要用户自己显示传递比较规则（一般情况下按照函数指针或者仿函数来传递）。

set的构造

set的迭代器

set的容量

set的操作

set的应用举例

#include<set>
int main()
{
	int arr[] = { 1, 2, 5, 6, 4, 7, 32, 45, 6, 9, 10, 3};
	set<int> si(arr, arr+sizeof(arr)/sizeof(arr[0]));
	cout << si.size() << endl;
	//正向打印si中的元素
	for (auto e : si)
	{
		cout << e <<"  ";
	}
	cout << endl;
	//逆向打印si中的元素
	for (auto it = si.rbegin(); it != si.rend(); ++it)
	{
		cout << *it <<" ";
	}
	cout << endl;
	cout << si.count(3) << endl;
	return 0;
}

运行截图：

3.map

map的介绍

map是关联式容器，他按照特定的次序（按照key来比较）存储由键值key和值value组合而成的键值对元素；
在map中，键值key可以唯一的标识元素，值value中存储与键值key关联的内容。键值key和value的类型可能不一样。在map内部，key与value通过成员类型value_type绑定在一起，并取别名为pair；

typedef pair<const key, T> value_type;

在map中，元素总是按照键值key来进行比较排序；
map中通过键值访问单个元素的效率通常比unordered_map的效率低，但是map允许根据顺序对元素进行直接迭代（对map的元素进行迭代，可以得到一个有序的序列）；
map支持下标访问，即在[]中放入key，就可以直接找到与key对应的value；
map的底层实现是通过平衡二叉树（红黑树）。

map的使用

map的模板参数列表

Compare 参数是比较器类型，一般不需要显示传递（缺省为小于比较，即升序排序），如果无法比较（自定义类型），需要用户自己显示传递比较规则（一般情况下按照函数指针或者仿函数来传递）。

map的构造

map的迭代器

map的容量

map的元素访问

map的操作

大部分操作与set类似，参考set的使用即可。

map的应用举例

#include<map>
#include<string>
int main()
{
	map<string, string> m;
	m.insert(make_pair("peach", "桃子"));
	m.insert(pair<string, string>( "banana","香蕉"));
	m["apple"] = "苹果";
	cout << m.size() << endl;
	cout << m.count("apple") << endl;
	for (auto it : m)
	{
		cout << it.first << ":" << it.second << endl;
	}
	//插入桃子
	auto ret = m.insert(make_pair("peach", "桃子"));//如果插入成功ret.second是true；如果插入失败ret.second是false；
	if (ret.second)cout << "<peach, 桃子>不在m中，插入成功" << endl;
	else cout << "插入失败" << endl;
	//删除苹果
	m.erase("apple");
	if (m.count("apple")) cout << "苹果还在" << endl;
	else cout << "苹果已经被删除" << endl;
	return 0;
}

4.multiset

与set的区别是，multiset可以存储重复的元素，其他的性质操作都与set相同。用一个代码看一下它与set的区别：

#include <set>//set和multiset的头文件都是set
void TestSet()
{
	int array[] = { 2, 1, 3, 3, 9, 6, 0, 5, 8, 4, 7 };
	// 注意：multiset在底层实际存储的是<int, int>的键值对
	set<int> s(array, array + sizeof(array) / sizeof(array[0]));
	for (auto& e : s)
		cout << e << " ";
	cout << endl;
}
void TestmultiSet()
{
	int array[] = { 2, 1, 3, 3, 9, 6, 0, 5, 8, 4, 7 };
	// 注意：multiset在底层实际存储的是<int, int>的键值对
	multiset<int> s(array, array + sizeof(array) / sizeof(array[0]));
	for (auto& e : s)
		cout << e << " ";
	cout << endl;
}
int main()
{
	TestSet();
	TestmultiSet();
	return 0;
}