上一篇笔记记录了二叉搜索树的实现，这一篇笔记介绍的 set 和 map，底层就是由二叉搜索树实现的，我们来学习他们两个的常用接口。

目录

set的使用

set的模板参数

insert

erase

count

lower_bound

upper_bound

multiset

count

erase

 find

键值对

map

 find

insert

make_pair

insert的返回值

operator []

重载 [] 的实现

---

set的使用

set的模板参数

T: set中存放元素的类型。
Compare：set中元素默认按照小于来比较
Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

insert

insert是向set里面插入值，因为底层为二叉搜索树，中序遍历一定为有序，并且没有数据冗余，可实现去重的功能：

erase

删除某个结点，和find配合使用，

find返回的是一个迭代器，传迭代器类型进行删除：

也可以直接传参数进项删除：

count

count有计数的意思，在 multi 版本下会返回数据出现的次数，在普通版本下，存在就返回 1 ，不存在返回 0 ，相较于 find ，更加方便查找：

lower_bound

返回大于等于参数的位置：

可以和erase的区间删除配合使用，

删除大于等于参数的所有值：

upper_bound

无论参数是否存在，返回的都是大于参数的位置：

可以和 lower_bound配合erase使用，删除一个闭区间的数据

我们传的是一个闭区间，而erase删除的是左闭右开区间，使用upper_bound刚刚好：

multiset

允许数据重复的set版本，接口用法几乎完全相同，常用的与set区别开的接口如下：

count

计数接口，set版本返回的是0和1，此版本下返回的是数据的个数：

erase

删除接口，set版本返回的是0和1，而此版本下删除返回的是删除数据的个数：

 find

若找的是重复的数据，返回的是中序遍历到的第一个数据的位置：

键值对

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)
   {}
};

是这样一个数据结构，我们可以将它作为二叉搜索树的结点来使用

一般只包含两个成员变量key和value，key代表键值，
value表示与key对应的信息

map

 find

会返回找到元素的迭代器，pari 数据结构中，key_type元素不允许修改，查找时找的也是key_type元素，而pair 中的第二个元素 value_type 允许修改。

因为这种性质，我们可以通过查找 key 而找到对应的 value ，并且对 value 进行修改。

void test9()
{
	//将以下数据插入map中，并且计数
	string arr[] = { "马克杯", "玻璃杯", "塑料杯", "玻璃杯", "玻璃杯", "玻璃杯", "马克杯", "马克杯", "塑料杯", "玻璃杯" };
	map<string, int> m;
	for (auto& str : arr)
	{
		map<string, int>::iterator it = m.find(str);
		//找到返回的是key_type（即pair的第一个数据）的迭代器
		if (it != m.end())
		{
			it->second++;    //找到pair的second( value_type ) 自增 1 
		}
		else     //没找到说明没有，则插入
		{
			m.insert(make_pair(str, 1));
		}
	}
}

insert

插入的一般是一个键值对，目前需要掌握的插入时的键值对构造有三种：

	map<int,string> m;
 
	//1. 声明类型，匿名对象
	m.insert(pair<int, string>(1, "a"));
 
	//2. 创建对象，插入对象
	pair<int, string> kv(2, "b");
	m.insert(kv);
 
	//3. 调用函数模板make_pair,不用声明pair类型
	m.insert(make_pair(3, "c"));

make_pair

insert的返回值

在上面find中，我们可以通过find对 key 进行查找，并且计数，但是这会有两次重复的查找过程，find先查找一次，insert 时要查找一次对此进行优化：

不用find ，直接通过 insert 也是可以实现的：

insert 插入成功后返回的一个pair的类型；

此pair中的first是插入元素的迭代器，second是bool值；

插入成功将pair中的second 元素设置为 true，

如果已存在要插入的key，则将为 pair的second 设置为false。

相当于返回的是pair,而这里的迭代器是指向的是插入的pair。

//insert 插入计数
void test10()
{
	//将以下数据插入map中，并且计数
	string arr[] = { "马克杯", "玻璃杯", "塑料杯", "玻璃杯", "玻璃杯", "玻璃杯", "马克杯", "马克杯", "塑料杯", "玻璃杯" };
	mapint> m;
	for (auto& str : arr)
	{
		auto ret = m.insert(make_pair(str, 1));
		if (ret.second == false)
		{
			ret.first->second++;
		}
	}
	//遍历
	auto it = m.begin();
	while (it != m.end())
	{
		cout << it->first << ":" << it->second << endl;
		it++;
	}
}

operator []

在map中，上述 find 和 insert 实现插入和计数都不算最简便的写法，最牛的写法是重载的 [] ：

重载 [] 的实现

那么重载的 [] 是怎么样实现的呢：

为了提高可读性，我们将其展开分析，如下图：

将上面那一长串展开，我们能清楚的看到，传进来的参数 k ，即 [] 中的 key_type 参数，在进入重载[]，后，和用 insert 插入计数的步骤大致相同：

用 k 和 value 的匿名对象构造pair类型插入到map对象中；

通过insert的返回值，拿到插入的pair的迭代器，再通过迭代器访问并返回second的引用，最后进行修改。