C++STL详解（九）map和set的使用

一.关联式容器的介绍

C++STL包含了序列式容器和关联式容器：

1. 序列式容器里面存储的是元素本身，其底层是线性的数据结构，就譬如我们之前学习的vector，list，deque等等。
2. 关联式容器里面存储的是<key,value>的键值对，在数据检索时比序列式容器效率更高。就譬如我们现在要学习的map和set等。

这里需要给大家提醒的一点是：

我们之前学习的queue、stack、priority_queue属于容器适配器，他们会使用别的容器来适配。

下面，我们开始介绍下键值对这个东西。
键值对是用来表示一一对应关系的一种结果，这个结构中一般是包含两个成员变量key和value。

• key表示键值。
• value表示与key对应的信息。

二.键值对

在SGI-STL中,关于键值对的定义如下所示：

template<class K,class V>
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表示键值，second则表示实值，在给关联式容器插入数据时，会构建pair对象
就譬如以下代码，就可以构建出一个键值key为string，实值value为int的匿名键值的键值对pair对象。

pair<string,int>("haha",1);

这样的写法有些繁琐，因此库中设计了一个函数模板make_pair，可以根据传入的参数调用pair构建对象并返回，如下：

make_pair("hehe",123);

下面，我们给出make_pair的定义：

template<class T1,class T2>
pair<T1,T2> make_pair(T1 x,T2 y)
{
	return (pair<T1,T2>(x,y));
}

这个函数在实际应用时，会被编译器优化为内联函数，因此不会产生太大的消耗。
比如我们若是要创建一个字典，那么这个字典中的英文单词与中文含义应该是一一对应的，也就是说，我们应该能够通过单词找到它对应的中文含义。
这样的情况，我们就可以利用键值对来完成这个任务。

三.set的使用

3.1set的定义

在我们之前介绍二叉搜索树时，我们大家可以发现其的模板参数只用了一个T1，而我们的set的底层就是一种特殊的二叉树，我们可以将其理解为只有一个实值value的特殊模型。
下图为cpp库中set的定义：

其中：

• 参数1：T即是set的实值
• 参数2：compare是中序遍历结果的排列，默认是升序
• 参数3：空间配置器

下面，我们来学习以下set的定义方式：

根据CPP官方文档，我们可以总结出如下的定义方式：
方式1：构造一个空的容器

set<int> s1;

方式2：拷贝构造

set<int> s1(s2);

方式3：迭代器区间构造

vector<int> s2={1,2,3,4,5,6,7,8,9,10};
set<int> s1(s2.begin(),s2.end());

方式4：构造空容器，并指定比较方式

set<int,greater<int>> s4;

3.2迭代器

作为STL的容器，set也是支持迭代器操作的。
对于set的迭代器而言，我们需要掌握的是以下的内容：

• 二叉搜索树的中序遍历为有序，因此我们这里的迭代器++应该是到中序的下一个结点
• set的迭代器是一个双向迭代器， 是支持++和–的。

我们可以在官方文档中看到如下内容：

另外，由于我们使用的是平衡搜索二叉树，因此它是不支持修改的，因此set中的迭代器都是const的，都是不能修改的。
如下：

3.3set的使用

下面我们来看看set的相关操作：

下面，我们通过下面的这段代码来实践下：

#include <iostream>
#include <map>
#include <vector>
#include <set>
using namespace std;
int main()
{
	vector<int> arr1 = { 7,8,9,6,5,4,1,2,3 };
	set<int> s1(arr1.begin(), arr1.end());
	//迭代器遍历
	cout << "迭代器遍历结果：" << endl;
	set<int>::iterator it = s1.begin();
	while (it != s1.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	
	cout << "---------------------------" << endl;
	cout << "empty:" << s1.empty() << endl;
	cout << "size:" << s1.size() << endl;
	cout << "max_size:" << s1.max_size() << endl;
	//数据插入
	cout << "---------------------------" << endl;
	cout << "insert(5):";
	s1.insert(5);
	for (auto e : s1)
	{
		cout << e << ' ';
	}
	cout << endl;
	//数据删除
	cout << "---------------------------" << endl;
	cout << "erase(5):";
	s1.erase(5);
	for (auto e : s1)
	{
		cout << e << ' ';
	}
	cout << endl;
	//数据交换、查找、清理
	cout << "---------------------------" << endl;
	set<int> s2 = { 100,200,300 };
	s1.swap(s2);
	for (auto e : s1)
		cout << e << ' ';
	cout << endl;
	for (auto e : s2)
		cout << e << ' ';
	cout << endl;
	cout << "s2.find(8):";//
	cout << (s2.find(8) != s2.end()) << endl;//1
	cout << "s2.clear():" << endl;
	s2.clear();
	for (auto e : s2)
		cout << e << ' ';
	cout << endl;
	return 0;
}

打印结果如下：

最后，我们再谈一谈count，虽然count可以用来查找元素键值的数量的，但，对于set来说，由于不允许冗余的存在，因此count在这里实现的是查找元素是否存在。
实践代码如下：

#include <iostream>
#include <map>
#include <vector>
#include <set>
using namespace std;
int main()
{
	vector<int> arr1 = { 7,8,9,6,5,4,1,2,3 };
	set<int> s1(arr1.begin(), arr1.end());
	for (int i = 0; i < 10; i++)
	{
		if (s1.count(i))
			cout << i << "在set中" << endl;
		else
			cout << i << "不在set中" << endl;
	}
	return 0;
}

打印结果如下：

除了上述的使用方法之外，我们还可以通过更改比较方式来更改set中数值的排序方式。
如下：

int main()
{
		vector<int> arr1 = { 7,8,9,6,5,4,1,2,3 };
	set<int,greater<int>> s1(arr1.begin(), arr1.end());
	for (auto e : s1)
		cout << e << ' ';
	cout << endl;
	return 0;
}

结果如下：
这样，我们就完成了降序排列元素。

四.set的特点

set具有以下特点：

• 只有键值，键值就是实值，所以传递参数时只需要传递一个值。
• 自带去重机制，不允许数据冗余
• 使用迭代器遍历时，默认为升序
• 普通迭代器也不允许修改。

五.multset

5.1multset的使用

multset是set的另一个版本，对于multset来说，不同点有二：

• multset允许数据冗余。
• count可以在这里得到真正的使用。

我们先把CPP官网的图贴到下面：

这里，我们不再赘述multset的操作，先演示下数据冗余的效果。

int main()
{
  vector<int> arr1 = { 7,7,8,9,6,5,4,1,2,3 };
  multiset<int> s1(arr1.begin(), arr1.end());
  for (auto e : s1)
	  cout << e << ' ';
  cout << endl;
  return 0;
}

结果如下：

然后，我们现在再来使用以下count函数

 cout << s1.count(7) << endl;

结果：2

因此，在multset中，count函数可以计算出相同元素的数量。

5.2multset的查找以及结构

由于multset是允许冗余的，因此就出现了一个问题：如果我们要使用查找函数
那么，返回的是哪个元素呢？
我们来实验下：

int main()
{
  vector<int> arr1 = { 7,7,8,9,6,5,4,1,2,3 };
  multiset<int> s1(arr1.begin(), arr1.end());
  auto it = s1.begin();
  while (it != s1.end())
  {
	  cout << *it << ":" << &*it << endl;
	  it++;
  }
  cout << "s1.find(7):" << &*s1.find(7) << endl;
  return 0;
}

我们发现，我们查找到的是中序遍历中第一次出现的元素。
下面，我们看下multset的结构：

六.map

6.1map的介绍

map是二叉搜索树改造的key/value模型，是一个真正意义上的键值对模型。
应用场景很多，如下：

• 中英文词典
• 电话号码查询快递信息
• 电话号码+验证码

首先，我们先来看以下map的文档介绍：

其中

• 参数1：键值
• 参数2：实值
• 参数3：比较方式
• 参数4：空间配置器

在map中，会用到之前说过的pair结构，也就是说，first表示键值，second表示实值。

6.2map的定义方式

下面，我们来学习一下map的定义方式

通过上图，我们可以得知，可以有如下定义：
方式一: 指定key和value的类型构造一个空容器

map<int,string> ml;//键值为int，实值为string

方式二: 拷贝构造某类型容器

map<int,string> m2(m1);

方式三: 迭代器区间构造

map<int,string> m3(m2.begin(),m2.end());

方式四: 指定比较方式

map<int,string,greater<int>> m4;

我们下面实际的应用一下

int main()
{
	vector<pair<string, int>> arr = { make_pair("1",11),make_pair("2",22),make_pair("3",33) };
	map<string, int> m1;
	map<string, int> m2(arr.begin(),arr.end());
	cout << "m1:" << ' ';
	for (auto e : m1)
		cout << e.first << ':' << e.second << "  ";
	cout << endl;
	cout << "m2:" << ' ';
	for(auto e:m2)
		cout << e.first << ':' << e.second << "  ";
	cout << endl;
	return 0;
}

打印结果：

m1:
m2: 1:11 2:22 3:33

6.3map的使用

对于map而言，除了新增了一个operator[]和部分函数的返回值不一样之外，与set没啥区别。
下面，我们实践一下。

#include <iostream>
#include <map>
#include <vector>
#include <set>
using namespace std;
int main()
{
	vector<pair<string, int>> arr={ make_pair("kuku",1),make_pair("kiki",2) };
	map<string, int> m1(arr.begin(), arr.end());
	cout << "迭代器遍历结果：";
	map<string, int>::iterator it1 = m1.begin();
	while (it1 != m1.end())
	{
		cout << "<" << it1->first << ";" << it1->second << ">";//注意，这里用的是->操作符
		++it1;
	}
	cout << endl;
	//判空，解引用，size和maxsize
	cout << "empty:" << m1.empty() << endl;
	cout << "[]:" << m1["kuku"] << endl;//这里要通过键值访问
	cout << "size:" << m1.size() << endl;
	cout << "maxsize:" << m1.max_size() << endl;
	//插入
	m1.insert(make_pair("lili",3));
	cout << "insert:" <<(--m1.end())->first<< (--m1.end())->second<<endl;
	//删除
	m1.erase("lili");
	cout << "erase:";
	for (auto e : m1)
	{
		cout << "<" << e.first << ',' << e.second << ">,";
	}
	cout << endl;
	//交换，查找，清理
	map<string, int> m2 = {make_pair("trousers",44),make_pair("trou",66) ,make_pair("trouser",55)};
	m1.swap(m2);
	for (auto e : m1)
		cout << e.first << ' ' << e.second << ' ';
	cout << endl;
	for (auto e : m2)
		cout << e.first << ' ' << e.second << ' ';
	cout << endl;
	cout << (m1.find("kuku")!=m1.end()) << endl;//find返回的是一个迭代器
	cout << "m2.clear" << endl;
	m2.clear();
	cout<<m2.empty();
}

打印结果如下：

下面，我们详细的介绍几个函数

6.4 insert函数

由于insert函数要返回两个值：

• 是否插入成功
• 插入成功的迭代器位置

由于要返回两个值，因此insert的函数返回值应该是一个pair类型的。

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

6.5 find和count函数

在map中，find和count都可以用来判断元素是否存在，但他们有以下的区别：

• find返回的是迭代器
• count返回的是键值数

6.6 map中的修改

map是可以修改pair中的第二个值的，也就是value。
我们可以通过迭代器进行修改，如下：

map<string,int>::iterator it1=m1.begin()++;
it1->second=77;

下面，我们可以用map来实现水果统计的代码：

vector<string> word={"苹果","梨子","桃子","苹果","梨子","桃子","苹果","梨子"};
map<string,int> table;
for(auto& e:word)
{
	if(!table.count(e))
		table.insert(make_pair(e,i));
	else
		table.find(e)->second++;
}
for(auto e:table)
{
	cout << "<" << e.first << ',' << e.second << ">,";
}

6.7 map中的operator[]

operator[]是返回实值，方括号内为键值。如果键值不存在的话，那么会插入信的键值对。
因此，operator是一个功能非常强大的东西。
我们可以结束operator[],把上面的统计水果改为下述代码：

int main()
{
	vector<string> word={"苹果","梨子","桃子","苹果","梨子","桃子","苹果","梨子"};
	map<string,int> table;
	for(auto& e:word)
	{
	table[e]++;
	}
	for(auto e:table)
	{
	cout << "<" << e.first << ',' << e.second << ">,";
	}
}

下面，我们介绍以下operator[]的实现：

1. 调用insert，插入一个make_pair对象
2. 获取到first，即获取到iterator
3. 通过迭代器，获取到second

通过这样的一套形式，我们就可以实现一个operator
也就是说，是长这个样子的

(this->insert(make_pair(k,mapped_type()))).first)->second

因此，我们的operator[]是非常强大的，它有以下功能：插入+修改+查找。

七.map的特点

• 包含键值和实值，插入时需要插入pair对象
• 自带去重机制，不允许数据冗余（键值）
• 使用迭代器遍历时，默认为升序（依靠键值排序）
• 普通迭代器允许修改实值，const迭代器什么都不允许修改。

八.multimap

对于multimap而言，我们只需要注意两个点

• 允许键值冗余
• 没有重载operator[]