C++的STL---＞map和set容器的使用

关联式容器和序列式的容器

首先，我们今天介绍的set和map容器是属于STL里面的关联式容器。不同于我们先前所学的string，vector还有list这样的线性逻辑结构。
set和map容器是属于关联式的，也就是set和map的元素的关系不在是先前那样简单的线性逻辑。set和map容器的底层是一个搜索二叉树！
更确切地说，是一棵兼具平衡性的红黑树！ 不过我们今天的任务只是简单认识一下如何使用这两个容器就可以了！

set容器介绍及其的使用

和学习其他的容器一样，我们也是通过文档来学习set的使用

set的使用文档

接下来我们通过代码来看一看set的使用

#include
//set定义在这个头文件中
#include
using namespace std;
void test_set1()
{
	set<int>s;
	//由于set不是线性结构，所以插入元素的方式只有insert
	s.insert(4);
	s.insert(3);
	s.insert(2);
	s.insert(1);
	//遍历set的方式可以使用迭代器
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

}
int main()
{   
	test_set1();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

那么假设我往set里面插入重复的值会发生什么呢?

#include
#include
#include
using namespace std;
//插入多次的1
void test_set2()
{
	set<int>s;
	s.insert(1);
	s.insert(1);
	s.insert(1);
	s.insert(1);
	s.insert(1);
	s.insert(4);
	s.insert(3);
	s.insert(5);
	s.insert(2);
	//直接使用范围for遍历了
	for (int e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}
int main()
{   
	//test_set1();
	test_set2();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

从结果不难看出：set容器对于插入的元素不仅会进行排序，还会去掉重复插入的元素！所以set容器的作用就是去重+排序！
set的删除对应的就是erase方法，提供了如下三种的重载删除的版本：

那么对应我们来使用erase方法：

#include
#include
using namespace std;
void test_set3()
{
	set<int>s;
	//由于set不是线性结构，所以插入元素的方式只有insert
	s.insert(4);
	s.insert(3);
	s.insert(2);
	s.insert(1);
	//遍历set的方式可以使用迭代器
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	//erase方法使用：版本一：提供迭代器版本
	//使用find查找需要删除的元素
	set<int>::iterator pos = s.find(3);
	if (pos != s.end())
	{
		cout << "找到待删除的节点" << endl;
		s.erase(pos);
	}
	for (int e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}
int main()
{   
	//test_set1();
	//test_set2();
	test_set3();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

然而提供迭代器的删除方法不仅要先查找，而且还要检查返回的迭代器的合法性！因此这种方法不是特别好用！而相对更常用的就是直接按值进行删除的版本

void test_set4()
{
	set<int>s;
	//由于set不是线性结构，所以插入元素的方式只有insert
	s.insert(4);
	s.insert(3);
	s.insert(2);
	s.insert(1);
	//遍历set的方式可以使用迭代器
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	//erase版本2：删除指定值的元素
	s.erase(3);
	for (int e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

使用这个重载版本的erase不仅很好地查找到了节点，同时也把这个节点删除了，而且不需要我们检查是否合法，函数内部会自行处理！
接下来再来介绍两个set里面比较特殊的方法。
首先第一个是lower_bound
一样我们可以通过查阅对应的文档了解使用：

lower_bound的使用

那么对于lower_bound的解释是这样的：接受一个参数x，返回一个指向的元素>=x的迭代器，具体我们可以通过下面这段代码来体会一下。

#include
#include
#include
using namespace std;
void test_set5()
{
	set<int>s;
	//由于set不是线性结构，所以插入元素的方式只有insert
	s.insert(4);
	s.insert(3);
	s.insert(2);
	s.insert(1);
	s.insert(6);
	//这里的3在set里面
	set<int>::iterator it1 = s.lower_bound(3);
	cout << *it1 << endl;
	//5不在set中
	auto it2 = s.lower_bound(5);
	cout << *it2;
}
int main()
{  test_set5();
   return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

从运行结果也不难看出，有3就返回指向3的迭代器，没有5就返回大于5的元素6的迭代器。 我们再来看看对应的upper_bound方法

upper_bound的说明文档

upper_bound的解释：接受一个参数x,返回指向>x的set中元素的迭代器
我们同样可以通过一段代码来验证是否是这样：

#include
#include
#include
using namespace std;
//upper_bound
void test_set6()
{
	set<int>s;
	//由于set不是线性结构，所以插入元素的方式只有insert
	s.insert(4);
	s.insert(3);
	s.insert(2);
	s.insert(1);
	s.insert(6);
	//这里的3在set里面
	set<int>::iterator it1 = s.upper_bound(3);
	cout << *it1 << endl;
	//5不在set中
	auto it2 = s.upper_bound(5);
	cout << *it2;
}
int main()
{
   test_set6();
   return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

可以看到即使这里的set里面有3这个元素，upper_bound也不会返回3，而是返回了4元素的迭代器！
对比lower_bound和upper_bound我们不难可以看出: lower_bound和upper_bound的设计也是为了实现左闭右开！
所以我们就可以利用这两个方法来做区间删除的操作！

include<iostream>
#include
#include
using namespace std;
void test_set7()
{
	set<int>s;
	//由于set不是线性结构，所以插入元素的方式只有insert
	s.insert(4);
	s.insert(3);
	s.insert(2);
	s.insert(1);
	s.insert(6);
	//删除区间[3,5]的所有整数
	auto start = s.lower_bound(3);
	auto finish = s.upper_bound(5);
	for (int e : s)
		cout << e << " ";
	cout << endl;
	//erase有删除迭代器区间的版本
	s.erase(start, finish);
	for (int e : s)
		cout << e << " ";
}
int main()
{  
   test_set7();
   return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

注意：set里面的元素是不能够被修改的！所以即使是使用普通的迭代器，我们也不能对set里面的元素进行写入操作！

---

map容器介绍及其使用

说完了set容器，那么接下来我们就要来看看map容器。同样我们可以通过文档进行学习。

map容器的说明文档

map的所有的元素都是一个pair,而为什么是pair的原因就是：c++不支持一个函数返回多个值！但是map又是模型的搜索树，所以才有了pair这个类型。
下面我们来看一看map的简单使用：

#include
#include
using namespace std;
void test_map1()
{
	map<int, int>m;
	int a[] = { 5,6,4,3,7,5,4,6,11,10,2,1 };
	//map的元素都是一个pair
	for (int e : a)
	//make_pair构造pair
		m.insert(make_pair(e, e));
	for (auto& kv : m)
		cout << kv.first << ":" << kv.second << endl;
}
int main()
{
   test_map1();
   return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

对于map来说，它是模型的二叉搜索树。map中元素的key参数是不能修改的，但是对应的val是可以进行修改的！
而map的erase和set几乎是一模一样的，这里就不在演示了。接下来我们看一看map的使用案例：

#include
#include
#include
#include
using namespace std;
//使用map的案例--->查找对应的编程语言出现的次数
void test_map2()
{
	map<string, int>m;
	string arr[] = { "C","C++" ,"java","python","php","C++","java","php"};
	for (const auto& str : arr)
	{
		map<string, int>::iterator it = m.find(str);
		//it!=m.end()说明先前已经存在了,那么就++
		if (it != m.end())
		{
			it->second++;
		}
		else
		{
			m.insert(make_pair(str, 1));
		}
	}
	//没找到说明就是第一次出现，插入
	for (const auto& kv : m)
	{
		cout << kv.first << " : " << kv.second << endl;
	}
}
int main()
{
    test_map2();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

这是一种解决的方式：但是这样显得很麻烦，上面的问题还可以用下面的方式解决：

#include
#include
#include
#include
using namespace std;
void test_map3()
{
	map<string, int> m;
	string arr[] = { "C","C++" ,"java","python","php","C++","java","php" };
	for (const auto& str : arr)
	{
		m[str]++;
	}
	for (const auto& kv : m)
	{
		cout << kv.first << ": " << kv.second << endl;
	}
}
int main()
{  
  test_map3();
  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

可以看到，这种方式的统计结果也是正确的。 而map[str]肯定就是调用了对应的operator[]函数，下面我们就来分析这个operator[]函数。

---

operator[]

接下来，我们就重点介绍这个operator[]函数
我们先来看文档里面对于operator[]的介绍

map的operator[]

那么在介绍operator[]之前，我们有必要了解一下insert函数的返回值

//标准库里map的insert函数的返回值
pair<iterator,bool> insert (const value_type& val);
1
2

insert方法的返回值是一个pair，这个pair的第一个成员是iterator,第二个则是标注是否成功插入

/* 也就说，对应函数的如果插入成功返回对应的新插入节点的
迭代器，如果插入失败，就返回关键字相同的节点的迭代器
*/
#include<>
void test_map4()
{
	map<string, int> m;
	string arr[] = { "C","C++" ,"java","python","php","C++","java","php" };
	for (const auto& str : arr)
	{   
		//完整的类型
		//pair < map::iterator, bool> ret = m.insert(make_pair(str,1));
		//等价写法
		auto ret = m.insert(make_pair(str, 1));
		//表明节点已经存在了
		if (!ret.second)
			ret.first->second++;
	}
}
int main()
{ 
  test_map4();
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

那么operator[]函数的实现方式类似下面这段代码：

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

看起来非常复杂，但是我们可以将其简化

//上面的代码等价于如下
//这里auto推导的类型是pair< map::iterator,bool>
//mapper等价于里面的V
auto ret=insert( make_pair(k,mapper()));
//这时候取到迭代器,然后使用箭头访问
return  ret.first->second;
1
2
3
4
5
6

而当时可能因为编译器对箭头运算符的支持度不够好，所以用了(*ret).second
那么当我们调用operator[]的时候，实际的过程会是这样的：

//实际的过程
map<string, int> m;
	string arr[] = { "C","C++" ,"java","python","php","C++","java","php" };
	for (const auto& str : arr)
	{  //调用operator[]->第一次str不在，插入
	  //后面搜索到同样已经在map中建立的str是，返回映射的v的引用
	  //起到可以写入的作用！
		m[str]++;
	}
1
2
3
4
5
6
7
8
9

总结：operator[]的作用：1.key不在map中，构建pair插入
2.key在map中是，返回pair中second成员的引用！

---

multiset和multimap

前面我们提到的set和map容器的元素的key都是不允许重复的。但是有的情况下又出现需要键值冗余的情况。所以官方库提供了multiset和multimap这两个允许键值冗余的容器。

multiset的使用文档
multimap的使用文档

#include
#include
void test_multiset1()
{  //multiset也是定义在头文件中
	multiset<int> ms;
	ms.insert(1);
	ms.insert(1);
	ms.insert(1);
	ms.insert(2);
	ms.insert(2);
	ms.insert(3);
	ms.insert(4);
	ms.insert(5);
	for (int e : ms)
		cout << e << " ";
	cout << endl;
}
int main()
{
   test_multiset();
   return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

可以看到这里确实是插入了多个相同的值。对于multimap也是如此。
这两个容器的操作和set，map类似。但是multimap不支持operator[],因为它有多个key，所以无法确定是哪一个key。
对于multiset和multimap我们就介绍到这里。

---

以上就是本文对于map和set容器的简单介绍。如果有不足或错误之处还望指出。希望大家一起共同进步。