[数据结构与算法]【C++】map和set

本文将衔接二叉搜索树，介绍C++中的两个容器set和map。
在进入本文之前，建议先回顾之前关于二叉搜索树的介绍：
二叉搜索树详解

set介绍

概念

·set就是Key模型的二叉搜索树，对于set而言，其key值是每个结点的唯一标识，也就是说set中的元素不允许重复。
·虽然set只存放key，但在底层来说，set和map一样，存放的也是<key, value>的键值对。只不过对于set来说，其value就是key，类型为T。
·set的元素不可被修改，这是因为set本身是有序的，而为了保证其有序性，因此其元素不可被修改；若要修改，则应删除该结点，在插入改后的结点。
·set的底层是用红黑树实现的。

set的使用

set的接口使用与其他容器基本一直，这里不作详细介绍，仅将常用接口列出，参考其他容器接口即可，具体可以查表。

set的构造

set的迭代器

set的迭代器与其他容器的迭代器类似，这里仅介绍常见的几个迭代器接口，其余迭代器查表即可：

set的容量

set的修改

set的使用举例

void test_set()
{
	vector<string> arr = { "apple", "sort", "banana", "left", "right", "level", "elegant", "apple", "banana", "apple" };
	set<string> s(arr.begin(), arr.end());
	//s的大小
	cout << s.size() << endl;
	//使用迭代器遍历s
	set<string>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	//使用反向迭代器遍历s
	set<string>::reverse_iterator rit = s.rbegin();
	while (rit != s.rend())
	{
		cout << *rit << " ";
		rit++;
	}
	cout << endl;
	//计算s中apple出现的个数
	cout << s.count("apple") << endl;//1不可重复
}

multiset简单介绍

我们知道set是不允许数据冗余的，而是否有支持数据冗余的容器呢？对此C++提供了multiset容器，该容器运行多个相同的key值结点存在。
multiset与set基本相同，唯一不同的点为insert接口返回值不再是pair对象，而是插入新节点的迭代器，因为multiset不存在插入失败的情况。

void test_multiset()
{
	vector<string> arr = { "apple", "sort", "banana", "left", "right", "level", "elegant", "apple", "banana", "apple" };
	multiset<string> s(arr.begin(), arr.end());
	//s的大小
	cout << s.size() << endl;
	//使用迭代器遍历s
	multiset<string>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	//使用反向迭代器遍历s
	multiset<string>::reverse_iterator rit = s.rbegin();
	while (rit != s.rend())
	{
		cout << *rit << " ";
		rit++;
	}
	cout << endl;
	//计算s中apple出现的个数
	cout << s.count("apple") << endl;//可以重复，因此为apple出现的个数
}

map介绍

概念

·与set对应的是，map为二叉搜索树中的key-value模型。其中key值为用于排序和唯一标识的元素，而value存储的为与key值相关联的内容。
·与我们之前实现的二叉搜索树有所不同，map的底层是将key和value通过value_tape绑定在一起，并为其取别名为：pair，即：

template <class T1, class T2> struct pair;
typedef pair value_type;

·map支持用[]下标访问符,即[]内放入key值，即可找到key值对应的value。
·与set一样，map的底层也是用红黑树实现的。

map的使用

map的迭代器

map的容量与元素访问–重点介绍[]的重载

下标访问符[]的详细介绍

在介绍[]之前，我们要先来认识map中insert接口函数：

pair<iterator,bool> insert (const value_type& val);

·通过文档我们可以认识到insert函数接口的返回值为一个pair对象，其中pair对象中第一个参数为iterator迭代器，另一个参数为bool类型的值。
·其含义为当map中没有key值对应的结点时，将会插入key值的新节点，并返回新节点的迭代器，同时bool值设置为true，标识插入成功；
·而map中已经有key值的结点时，由于map容器不允许冗余，因此会插入失败，此时返回的pair对象中第一个参数为已经存在的结点的迭代器，同时bool值设置为false，表示插入失败。
由此，我们再来认识map中对于[]的重载：

mapped_type& operator[] (const key_type& k);//mapped_type为value值

可以看到文档中介绍该函数等价于下述语句。

·对上述语句逐一分析，将this指针省略，可以很容易的看出该语句的作用为：将一个<key, value>的pair对象插入到map中，返回插入结点的value值。
·再结合上面对于insert的介绍，我们可以很清楚的认识到：对于map中不存在的key值，[]将会执行插入操作，并返回新插入结点的value值的引用；对于map中存在的key值，[]将会返回已经存在结点的value值的引用。

map中的元素修改

map的使用举例

//统计一个数组中每个单词出现的次数
void test_map1()//1.先查找，再插入
{
	vector<string> arr = { "apple", "sort", "banana", "left", "right", "level", "elegant", "apple", "banana", "apple" };
	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));//插入新节点，次数更新为1
		}
		else//找到了
		{
			it->second++;//将该节点的value值++
		}
	}
	for (auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}
}
void test_map2()//2.直接利用insert接口的返回值更新次数
{
	vector<string> arr = { "apple", "sort", "banana", "left", "right", "level", "elegant", "apple", "banana", "apple" };
	map<string, int> countMap;
	for (auto& e : arr)
	{
		pair<map<string, int>::iterator, bool> ret = countMap.insert(make_pair(e, 1));
		if (!ret.second)//为假，插入失败，返回已经存在的结点迭代器
		{
			ret.first->second++;
		}
	}
	for (auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}
}
void test_map3()//3.利用[]更新次数
{
	vector<string> arr = { "apple", "sort", "banana", "left", "right", "level", "elegant", "apple", "banana", "apple" };
	map<string, int> countMap;
	for (auto& e : arr)
	{
		countMap[e]++;
	}
	for (auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}
}

multimap介绍

multimap与multiset类似，同样可以存放冗余的结点。只不过，multimap与map相比，multimap不支持[]下标访问符的重载，这是因为multimap的key值可以冗余，不能通过key值去寻找唯一的结点。

multimap的应用

//将字符串数组按出现次数从小到大排列，同时次数相同的字符串按字典序依次排列
void test_multimap()
{
	vector<string> arr = { "apple", "sort", "banana", "left", "right", "level", "elegant", "apple", "banana", "apple" };
	map<string, int> countMap;
	for (auto& e : arr)
	{
		countMap[e]++;
	}
	multimap<int, string> sortMap;
	for (auto& e : countMap)
	{
		sortMap.insert(make_pair(e.second, e.first));
	}
	for (auto& e : sortMap)
	{
		cout << e.second << ":" << e.first << endl;
	}
}

关联式容器

我们之前所接触的vector、list、deque、forward_list(C++11)等容器，，这
些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。
而这次介绍的map和set两个容器是关联式容器，关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。

键值对

即我们上面所介绍的pair结构体，是用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。
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)
 {}
};

树形结构的关联式容器

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