目录

前言 

一、set的介绍

介绍：

set的使用：

定义：

迭代器：

 set的函数

set的使用：

二、map的介绍 

介绍：

迭代器

修改操作

下面是两个使用实例

使用注意：

 multimap:

---

前言 

map和set是一种专门用来搜索的容器，底层为二叉搜素树

二叉搜索树：即比父节点小放在左边，比父节点大的放在右边
 

map能存储两个数据类型，我们称之为<key-value>模型

set只能存储一个数据类型，我们称之为<key>模型

一、set的介绍

介绍：

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

set的使用：

1、 set的使用

定义：

set<类型> s;

迭代器：

set的迭代器的遍历顺序为中序遍历

begin  ：返回set中起始位置元素的迭代器
end     ：返回set中最后一个元素后面的迭代器
rbegin ：返回容器逆序的第一个元素的迭代器
rend    ：返回容器逆序的最后一个元素的前一个位置的迭代器

 set的函数

1、pair<iterator,bool> insert (const value_type& x )    在set中插入元素x，实际插入的是<x, x>构成的键值对，如果插入成功，返回<该元素在set中的位置，true>,如果插入失败，说明x在set中已经存在返回<x在set中的位置，false>
2、void erase ( iterator position )    删除set中position位置上的元素
3、size_type erase ( const key_type& x )    删除set中值为x的元素，返回删除的元素的个数
4、void erase ( iterator first, iterator last )    删除set中[first, last)区间中的元素
5、void swap (set<Key,Compare,Allocator>& st )    交换set中的元素
6、iterator find ( const key_type& x ) const    返回set中值为x的元素的位置
7、size_type count ( const key_type& x ) const    返回set中值为x的元素的个数

set的使用：

#include <set>
#include<iostream>
using namespace std;
void TestSet()
{
	// 用数组array中的元素构造set
	int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4,
	6, 8, 0 };
	set<int> s(array, array + sizeof(array) / sizeof(array[0]));
	cout << s.size() << endl;
	
	// 正向打印set中的元素，从打印结果中可以看出：set可去重
	for (auto& e : s)
	cout << e << " ";
	cout << endl;
	
	// 使用迭代器逆向打印set中的元素
	for (auto it = s.rbegin(); it != s.rend(); ++it)
	cout << *it << " ";
	cout << endl;
	
	// set中值为3的元素出现了几次
	cout << s.count(3) << endl;
}

注意事项：

1. 与 map/multimap 不同， map/multimap 中存储的是真正的键值对 <key, value> ， set 中只放value ，但在底层实际存放的是由 <value, value> 构成的键值对。
2. set 中插入元素时，只需要插入 value 即可，不需要构造键值对。
3. set 中的元素不可以重复 ( 因此可以使用 set 进行去重 ) 。
4. 使用 set 的迭代器遍历 set 中的元素，可以得到有序序列
5. set 中的元素默认按照小于来比较
6. set 中查找某个元素，时间复杂度为： log2 n
7. set 中的元素不允许修改 ( 为什么 ? --- 麻烦 排序的维护，唯一性的维护，时间复杂度的维护)
8. set 中的底层使用二叉搜索树 ( 红黑树 ) 来实现。

二、map的介绍 

介绍：

1. map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元 素。

2. 在map中，键值key通常用于排序和唯一地标识元素，而值value中存储与此键值key关联 的内容。

键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类 型value_type绑定在一起，为其取别名称为pair

3. 在内部，map中的元素总是按照键值key进行比较排序的。

4. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序 对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。

5. map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。

6. map通常被实现为二叉搜索树(平衡二叉搜索树(红黑树))。  

迭代器

begin()和end()    begin:首元素的位置，end最后一个元素的下一个位置

rbegin()和rend()    反向迭代器，rbegin在end位置，rend在begin位置，其++和–操作与begin和end操作移动相反

修改操作

1、pair insert ( const value_type& x ) 在map中插入键值对x，注意x是一个键值 对，返回值也是键值对：iterator代表新插入 元素的位置，bool代表释放插入成功

2、void erase ( iterator position )删除position位置上的元素

3、size_type erase ( const key_type& x )删除键值为x的元素

4、void erase ( iterator first, iterator last )删除[first, last)区间中的元素

5、const_iterator find ( const key_type& x ) const 在map中插入key为x的元素，找到返回该元 素的位置的const迭代器，否则返回end

6、size_type count ( const key_type& x ) const 返回key为x的键值在map中的个数，注意 map中key是唯一的，因此该函数的返回值 要么为0，要么为1，因此也可以用该函数来判断一个key是否在map中  

下面是两个使用实例

可以用map来查找

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main() {
	map<string, string> dict;
	dict.insert(pair<string,string>("insert", "插入"));
	dict.insert(pair<string, string>("erase", "删除"));
	dict.insert(pair<string, string>("left", "左边"));
	dict.insert(pair<string, string>("string", "字符串"));

	string str;
	while (cin >> str)
	{
		auto ret = dict.find(str);
		if (ret!=dict.end())
		{
			cout <<ret->first <<":" << ret->second << endl;
		}
		else
		{
			cout << "单词拼写错误" << endl;
		}
	}
	return 0;
}

我们可以用map来统计出现的次数，如下：

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main() {
	string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };
	// 统计水果出现的次
	map<string, int> countTree;
	for (auto str : strs)
	{
		countTree[str]++;
	}
	for (auto m : countTree)
	{
		cout << m.first << ":" << m.second << endl;
	}
	return 0;
}

使用注意：

1. map中的的元素是键值对

2. map中的key是唯一的，并且不能修改

3. 默认按照小于的方式对key进行比较

4. map中的元素如果用迭代器去遍历，可以得到一个有序的序列

5. map的底层为平衡搜索树(红黑树)，查找效率比较高O(log_2 N)

6. 支持 [] 操作符，operator[] 中实际进行插入查找。

 multimap:

1、Multimaps是关联式容器，它按照特定的顺序，存储由key和value映射成的键值对<key,
value>，其中多个键值对之间的key是可以重复的。
2、在multimap中，通常按照key排序和惟一地标识元素，而映射的value存储与key关联的内
容。key和value的类型可能不同，通过multimap内部的成员类型value_type组合在一起，
value_type是组合key和value的键值对:typedef pair<const Key, T> value_type;
3、在内部，multimap中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对
key进行排序的。
4、multimap通过key访问单个元素的速度通常比unordered_multimap容器慢，但是使用迭代
器直接遍历multimap中的元素可以得到关于key有序的序列。
5、multimap在底层用二叉搜索树(红黑树)来实现 

使用： 

3.2.2 multimap的使用
multimap中的接口可以参考map，功能都是类似的。
注意：

multimap中的key是可以重复的。
multimap中的元素默认将key按照小于来比较
multimap中没有重载operator[]操作(思考下为什么?)。
使用时与map包含的头文件相同

--------------------------------------------------------------------------------------------------------------------------------

 本文的讲解到此结束，谢谢大家的观看，有问题欢迎给我留评论。