目录

关联式容器

树形结构的关联式容器

set

set的删除erase

multiset

 multiset的删除:erase

 map

【pair键值对】

【map的插入insert】

 【遍历map】

map的operator[] && 统计次数

multimap

关于map的一个练习小程序

关联式容器

在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、dequeforward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？
关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的键值对，在数据检索时比序列式容器效率更高。
在二叉搜索树中包括key模型和key/value模型的二叉搜索树，set就是key模型的二叉搜索树，map是key/value的二叉搜索树。

树形结构的关联式容器

set

我们向set中插入几个值，并用迭代器遍历打印。

void test_set1()
{
	//排序+去重
	set s;
	s.insert(3);
	s.insert(1);
	s.insert(5);
	s.insert(2);
	s.insert(8);

	//set::iterator it = s.begin();
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

set的删除erase

如果想要删除set中的某一个值，我们看下图，它可以删除一个迭代器，也可以删除一个值，那么他们有什么区别呢？

当删除一个迭代器位置，必须保证迭代器位置有效；如果直接删除值，即便set里没有这个值也不做反馈。

删除值：

迭代器做检查：它不做处理

迭代器不做检查：编译出错

 

【erase的返回值】

set删除后，会返回删除元素的个数，那么为什么它返回的不是布尔值，而是删除的元素个数？这就跟multiset有关系。它其实是为了multiset而设置的。

multiset

multiset和set的区别不大，它们真正的区别是，set可以去重，但是multiset会对插入的数字排序，但是不去重，他允许key值冗余重复。

void test_multiset()
{
	multiset s;
	s.insert(3);
	s.insert(1);
	s.insert(5);
	s.insert(2);
	s.insert(8);
	s.insert(1);
	s.insert(8);

	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

 multiset的删除:erase

因为multiset中有冗余的数字，如1，8。当要删除1的时候，因为先要查找1，那么我们怎么知道要删除的是哪一个1呢？我们可以来打印pos这个迭代器位置，然后将pos迭代器后位置的数字，依次打印，来看一下到底是哪个1。

	set::iterator pos = s.find(1);
	while (pos != s.end())
	{
		cout << *pos << " ";
		++pos;
	}
	cout << endl;

通过这段代码可以发现，find找到的是multiset中序遍历的第一个1。所以当find的val有多个值时，返回中序第一个val值所在节点的迭代器。

 【把所有的1都删掉】：

方法1：

要删除所有的1，如果用while循环这种形式删除，那么while的循环条件还要加一个*pos==1，这样删除的数字必须是1，如果不是1就退出while循环。如果直接s.erase(pos)删除后++pos，这样会导致迭代器失效，删除当前的1后，迭代器pos的位置已经不是指向原来的位置，已经被下一个1替代，这样直接++pos，迭代器pos的位置就指向2位置。因为迭代器会失效，所以我们用一个变量tmp来记录下一个位置。然后删除后将记录的位置再赋给迭代器就可以了。

	pos = s.find(1);
	while (pos != s.end() && *pos == 1)
	{
		//auto tmp = pos;
		set::iterator tmp = pos;
		++tmp;
		s.erase(pos);
		pos=tmp;
	}

方法2：

在mutliset的删除中，还可以传值，当我们删除数字1，直接传1，它的返回值就是删除的1的个数。这就是刚才上面set的erase返回值为什么是元素个数的原因。而erase(1)的底层实现就是用，上面的代码实现的。

---

 值得注意的是，在增删查改中，set和multiset中没有修改，set的结构是一个搜索二叉树，也就是说它的key值的顺序已经是固定的，如果随便改变key值，那么搜索二叉树的结构顺序会打乱。

 map

map是key/value类型的二叉搜索树，它里面有两个类型模板，class Key和class T,T就是value值。在map中它将Key和value又封装到了这个pair键值对里 。

typedef pair value_type;

【pair键值对】

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。

pair键值对也是一个结构体，因为是C++也可以看作类，而struct关键字可以不用控制结构体里面的访问限定（如果要控制访问就用class）。pair结构体里面有两个成员，first是第一个模板参数key和second是第二个模板参数value（一般是这样的，有可能出现value在前，key在后的情况）。

---

除了键值对，map和set其它差不多。

【map的插入insert】

在insert接口中，传入的参数是val，但是map容器的插入需要传两个值key和value，为什么insert传入的参数只有一个val呢？

我们看到，val它的类型是value_type，value_type是什么类型呢？它的类型是一个键值对pair类型，也就是说C++将pair类型封装成value_type(将pair类型typedef成value_type)

 【插入的三种方法】：

	map dict;
//方法一：
	pair kv1("sort", "排序");
	dict.insert(kv1);

	//法二:匿名对象
	dict.insert(pair("string", "字符串"));

	//法三:make_pair
	dict.insert(make_pair("test", "测试"));

make_pair插入：make_pair的底层我们看到，就是返回个匿名对象，就是将我们写的第二种方式封装一下，但是用起来更方便。make_pair还有一个优势，它可以自动推导类型，因为传入了参数模板，所以make_pair可以自动推导类型，交给编译器去处理。

在一般情况下，我们最常使用方法三。

 【遍历map】

map的遍历还是用迭代器，当打印迭代器指针解引用的内容，发现报错。因为迭代器解引用后，返回的是一个pair类型，也就是说流插入“<<”运算符没有重载pair类型。所以打印map里的内容。

 要将pair中的成员都打印出来，因为pair结构体用struct封装，所以可以用到里面的成员变量,pair有两个成员变量first和second。但是下面这种情况还是报错，这是因为“.”的优先级非常高，高于“*”,所以要用括号将*it括起来。

这里在包括号之后，还会报错，是因为要包string的头文件，因为用到了string的流插入重载。

这里我们可以简便写一下it迭代器的类型，用auto代替，这时候auto的作用就体现出来了。

这里可以用指针的箭头，这样就不用解引用再取类中成员变量了，也不用考虑运算符优先级。

	//map::iterator it = dict.begin();
	auto it = dict.begin();
	while (it != dict.end())
	{
		//cout << *it << endl;
		cout << (*it).first << ":" << (*it).second << endl;
		cout << it->first << ":" << it->second << endl;
		++it;
	}
	cout << endl;

运行结果：

【范围for方法遍历map】:

这里的auto我们可以加上引用&，如果不加引用也可以，但是代价有点大，需要将map里的pair都赋给kv进行深拷贝，然后再取pair的成员变量。但是引用就是别名，不用深拷贝，直接取pair里面的成员变量即可。

map的operator[] && 统计次数

我们先不用operator[]，统计一下数组中每种水果的个数。

用范围for遍历数组，然后统计里面各个水果的个数：我们在map里面查找当前遍历的水果存不存在，如果不存在，在map中新插入这个水果；如果存在，找到了map中有这个水果，那么将对应的水果的pair中的second+1。

因为map中的查找find返回值是一个迭代器，所以迭代器指向map中的某一个元素，就是指针指向这个节点，pair存在这个节点中，直接箭头解引用就可以修改second的值。

map与set不一样的一点是，map可以修改值，但是map只能修改second的值，first用来组成搜索二叉树的结构，因为它的前后顺序不能改变，所以first值也不能改变。

	string arr[] = { "苹果", "苹果", "香蕉", "苹果", "香蕉", "樱桃" };
	map countMap;
	for (auto& str : arr)
	{
		//在map里找arr存不存在，如果不存在找到map的end位置，那么将这个元素插入map中；
		//如果存在那么说明在map中找到相同的元素，直接将找到的相同元素pair中的second+1。
		map::iterator ret = countMap.find(str);//find返回类型是一个迭代器
		if (ret == countMap.end())
		{
			countMap.insert(make_pair(str, 1));
		}
		else
		{
			ret->second++;
		}
	}
	for (auto& kv : countMap)
	{
		cout << kv.first << ":" << kv.second << endl;
	}
	cout << endl;

运行结果：

 

 【优化方案】：

上面这段代码，有一个冗余的地方，就是当我们find查找map中存不存在某个元素的时候，会将map都遍历一遍，然后插入。如果这个元素不存在，要遍历一遍，遍历到map的最后，当我们第一次插入这个元素的时候，又要遍历一遍整个map，也就是说新插入一个元素要遍历两边map。

而在map的insert接口中，insert的返回值是pair。在文档中有解释说明这个返回值的意思：大意是，pair的第一个元素first返回值是一个迭代器，无论是插入新元素还是老元素，都返回插入元素的迭代器，这个迭代器就是一个指针，指向的还是一个pair。Insert中pair返回值的第二个元素second的返回值是一个bool类型，当插入新元素，返回真，当插入老元素返回false。

 所以优化代码可以写成：

当我们在map中插入元素，insert的返回值：第一个first返回当前map指向的迭代器，当插入了新元素，insert的second返回为true。当范围for遍历到第二个苹果的时候，还是在map中插入该pair键值对，但是此时map中已经有了苹果（二叉搜索树会根据键值对的first进行比较），所以insert的返回值中，第一个还是返回map当前元素的迭代器，但是insert返回值第二个已经变成false。

所以用一个变量接收insert的返回值，当kv的second是false，将kv中的first（first是迭代器）中的second元素++（迭代器是指针，要用箭头解引用找到里面元素）。

insert的返回类型实在太长了，所以用auto代替。

	string arr[] = { "苹果", "苹果", "香蕉", "苹果", "香蕉", "樱桃" };
	map countMap;
	for (auto& str : arr)
	{
		//pair::iterator, bool> kv = countMap.insert(make_pair(str, 1));
		auto kv = countMap.insert(make_pair(str, 1));
		if (kv.second == false)
		{
			kv.first->second++;
		}
	}

---

前两种方法是可以的，但是还有一种最常用的方法，直接用operator[]统计水果出现的次数 。一句代码统计次数，operator[]的底层就是上面那种优化的方法，只不过把它封装起来。

	string arr[] = { "苹果", "苹果", "香蕉", "苹果", "香蕉", "樱桃" };
	map countMap;
	for (auto& str : arr)
	{
		countMap[str]++;
	}

那么operator[]内部怎么实现的呢？我们来看文档：

这里有一个mapped_type(),它是模板的匿名对象，这里统计水果次数，那么这个mapped_type是int类型，在C语言中我们没有无参构造的概念，但是在C++中，我们可以将所有类型都当作一个类，并且它有构造函数，所以这个mapped_type()是一个无参构造，它的默认值是0。

用苹果举例子，在最开始还没有苹果这个水果的时候，传入一个key是string类型的，传入pair中发现，map中还没有苹果，mapped_type()值是0，insert后的返回值是是一个pair,取pair的first是迭代器，迭代器指向map遍历的当前节点；将这个迭代器解引用，也就是将指针解引用，解引用得到pair键值对，也就是map遍历的当前节点的键值对，取它的second，second的类型是int，就是记录苹果次数的值。

那么最开始没有苹果的时候，mapped_type()因为无参构造给的值是0，为什么最后在countMap[str]++之后会变成1呢？这是因为operator[]的返回值是mapped_type&引用类型的，它返回的是次数的引用，那么这个++是作用在函数调用的返回值上面的。最开始没有苹果的时候，传入这个水果，它的次数是mapped_type()无参构造0次，这个被插入到map当中，所以返回值引用的也是当前指向的map节点的pair键值对的第二个成员变量second中，当前的返回值是0，++后变成了1，那么map遍历的当前节点，第一个苹果的键值对pair的second由0变1。所以这个++是作用在函数调用的返回值mapped_tyep&上，而不是mapped_type& operator[] (const key_type& k)。（return后面的语句）

在第二次遇到苹果后，insert中传入的k是苹果，而这个苹果出现过了，insert返回pair(iterator,false)，无参构造mapped_type()也失效了，直接忽略。找到这个返回值的迭代器，迭代器指向的是第二个苹果的节点，取到节点中pair的second，这时候second是1（上一次返回值引用修改的），返回值mapped_type&还是1，当执行countMap[str]++后，返回值从1变2，这时候第二个苹果节点的pair的second也随之变成了2（引用就是别名，用的还是一块空间）。之后每一次出现苹果，insert的返回值都会返回false，无参构造都被忽略，返回值依旧是原来的数，执行countMap[str]++后返回值才改变。

 所以operator[]内部实现代码可以写成这样：

mapped_type& operator[](const key_type& k)
{
    pair ret=insert(make_pair(k,mapped_type()));
    //return *(ret.first).second;
    return ret.first->second;
}

【总结】：operator[] 的功能：

                1.插入

                2.查找对应的key/value

                3.修改对应的key/value

如果水果第一次出现，插入+修改

水果不是第一次出现，查找+修改

我们再来举个例子看看，我们可以通过调试来看这段代码。（俺不调了，展示不出来）。

当insert在遇到相同key值的情况下，并不会修改value值，value还是第一个left出现的value。当operator[]遇到相同的key值left时，他会修改value值，充当的是修改；当给出一个新的key值，并没有给value的时候（如test），它充当的是插入；当存在key值，且value值也存在，那么operator[]充当的是查找，可以打印出它的返回值。所以operator[]不能从当查找，如果没有map中没有这个key值，它会插入，所以查找最好用find。

void test_map3()
{
	map dict;
	dict.insert(make_pair("sort", "排序"));
	dict.insert(make_pair("left", "左边"));
	dict.insert(make_pair("left","剩余")); //insert在有相同key的情况下，不会修改。

	dict["left"] = "剩余";          //修改--有这个key值，就修改value
	dict["test"];					//插入--没有这个值就插入
	cout << dict["sort"] << endl;	//查找--有这个值，就查找
}

multimap

multimap和multiset一样，允许key值冗余。

需要注意的是，multimap和mutliset的头文件分别是map,和set，他俩没有各自的头文件。

【count函数】

count对于multi版本的map很有用，它会记录出现的key值数量

关于map的一个练习小程序

本公司现在要给公司员工发波福利，在员工工作时间会提供大量的水果供员工补充营养。由于水果种类比较多，但是却又不知道哪种水果比较受欢迎，然后公司就让每个员工报告了自己最爱吃的k种水果，并且告知已经将所有员工喜欢吃的水果存储于一个数组中。然后让我们统计出所有水果出现的次数，并且求出大家最喜欢吃的前k种水果

先用map将水果统计出来，然后对value排序，排序有很多种方法：sort排序，multimap排序，优先级队列排序。

    //sort
    //sort要传入迭代器区间，sort底层是快排，
    //快排要三数取中，不然的话遇到快排遇到有序情况时间复杂度非常大
    //但是三数取中需要获取下标，map是二叉树结构无法获取下标
    //所以要将map中的键值对pair都导入vector中，vector有下标，这样就能用sort
    //但是pair可以比较大小吗，我们可以查看文档，发现pair的比较
    //用大于来举例，可以比较key值，如果key值小于等于，那么比较value值
    //但是我们不想比较，key值，指向比较value值，所以我们可以用一个仿函数来控制
    //传入的仿函数按map中second值比较。
    //因为找前k大的水果，所以让second降序排列

struct CountVal
{
	bool operator()(const pair& p1, const pair& p2)
	{
		return p1.second > p2.second;
	}
};

struct CountIterVal
{
	bool operator()(const map::iterator& l, const map::iterator& r)
	{
		return l->second > r->second;
	}
};

struct CountValPQ
{
	bool operator()(const pair& l, const pair& r)
	{
		return l.second < r.second;//小于才是大堆
	}
};

struct CountIterValPQ
{
	bool operator()(const map::iterator& l, const map::iterator& r)
	{
		return l->second < r->second;
	}
};

void GetFavoriteFruit(const vector& fruits, size_t k)
{
	map countMap;
	for (auto& str : fruits)
	{
		countMap[str]++;
	}

	//数据不大，排序
	//sort/multimap

	//vector> sortV;
	//for (auto& kv : countMap)
	//{
	//	sortV.push_back(kv);
	//}

//sort放pair
	//sort(sortV.begin(), sortV.end(),CountVal());//仿函数给对象

	//for (int i = 0; i < k; i++)
	//{
	//	cout << sortV[i].first << ":" << sortV[i].second << endl;
	//}

	//上面这种方法，将pair拷贝到vector里，如果string很大，那么vector开辟空间也很大；
	//并且pair是一个自定义对象，pair里的string也是一个自定义对象，都要进行深拷贝，代价很大
	//所以我们不放pair，在vector里放map的迭代器，这样只放一个指针，32位下只有4byte，节省空间
//sort放迭代器
	//vector::iterator> SortV;
	遍历map将迭代器放入vector中
	//map::iterator it = countMap.begin();
	//while(it != countMap.end())
	//{
	//	SortV.push_back(it);
	//	++it;
	//}
	//sort(SortV.begin(), SortV.end(), CountIterVal());
	//for (int i = 0; i < k; i++)
	//{
	//	cout << SortV[i]->first << ":" << SortV[i]->second << endl;
	//}

//mulitmap
	multimap> sortMap;
	for (auto& kv : countMap)
	{
		sortMap.insert(make_pair(kv.second, kv.first));
	}

//priority_queue
	//priority_queue, vector>, CountValPQ> pq;
	//for (auto& kv : countMap)
	//{
	//	pq.push(kv);
	//}

	//while (k--)
	//{
	//	cout << pq.top().first << ":" << pq.top().second << endl;
	//	pq.pop();
	//}

//priority_queue iterator
	priority_queue::iterator, vector::iterator>, CountIterValPQ> pqiter;
	map::iterator it = countMap.begin();
	while (it != countMap.end())
	{
		pqiter.push(it);
		++it;
	}

	while (k--)
	{
		cout << pqiter.top()->first << ":" << pqiter.top()->second << endl;
		pqiter.pop();
	}

}