Associative Container

1. 自定义类型作为关键字
关联容器对其关键字类型有一些限制。对于有序容器map、multimap、set、multiset，关键字类型必须定义元素比较的方法。默认情况下，标准库使用关键字类型的<运算符来比较两个关键字。在集合类型中，关键字类型就是元素类型；在映射类型中，关键字类型是元素的第一部分的类型。
对于自定义的类MyClass我们无法直接定义一个MyClass类型的set、map，因为MyClass没有<等比较运算符。可以采用如下示例的方法解决。

#include <map>
#include <set>
#include <string>
#include <iostream>
#include <vector>

typedef struct _BOARD_
{
	std::string m_name;
	int m_version;
}Board;

bool compareVersion(const Board & b1, const Board &b2)
{
	return b1.m_version > b2.m_version;
}

int main(){
	/* set */
	Board b0{ "Seagate", 300 };
	Board b1{ "Ring", 100 };
	Board b2{ "Novatek", 200 };

	std::multiset<Board, decltype(compareVersion)*> aset{compareVersion};
	aset.insert(b0);
	aset.insert(b1);
	aset.insert(b2);
	for (auto it : aset)
	{
		std::cout << it.m_name << " : " << it.m_version << std::endl;
	}

	/* map */
	std::pair<Board, int>p0{ b0, 0 };
	std::pair<Board, int>p1{ b1, 1 };
	std::pair<Board, int>p2{ b2, 2 };
	std::multimap<Board, int,decltype(compareVersion)*> amap{ compareVersion };
	amap.insert(p0);
	amap.insert(p1);
	amap.insert(p2);
	for (auto it : amap)
	{
		std::cout << it.first.m_name << " : " << it.first.m_version <<" : "<< it.second << std::endl;
	}

	system("pause");
}

2. 检查insert的返回值
insert(或emplace)返回的值依赖于容器类型和参数。对于不包含重复关键字的容器，添加单一元素的insert和emplace版本返回一个pair，告诉我们插入操作是否成功。pair的first成员是一个迭代器，指向具有给定关键字的元素；second成员是一个bool值，指出元素是插入成功还是已经存在于容器中。如果关键字已存在容器中，则insert什么事情也不做，且返回值中的bool部分为false。如果关键字不存在，元素被插入容器中，且bool值为true。请看如下单词计数程序（统计每个单词在输入中出现的次数）：

#include <map>
#include <string>
#include <iostream>

int main(){
	std::map<std::string, int> word_count;
	std::string astr;
	while (std::cin>>astr)
	{
		/* ret的类型是std::pair<std::map<std::string, int>::iterator, int> */
		auto ret = word_count.emplace(std::make_pair(astr, 1));
		//std::pair<std::map<std::string, int>::iterator, int> ret = word_count.emplace(std::make_pair(astr, 1));
		if (!ret.second)
		{
			++(ret.first->second);
		}
	}
	for (auto it:word_count)
	{
		std::cout << it.first << " appears: " << it.second << " times." << std::endl;
	}

	system("pause");
}

顺便说下在while中正确终止std::cin的方法，Windows下按F6。
对于允许重复关键字的容器multiset、multimap，接受单个元素的insert（或emplace）操作返回一个指向新元素的迭代器，无需返回一个bool值，因为insert（或emplace）总是向这类容器中加入一个新元素。例如：

#include <map>
#include <string>
#include <iostream>

int main(){
	std::multimap<std::string, int> word_count;
	std::string astr;
	while (std::cin >> astr)
	{
		/* ret的类型是std::map<std::string, int>::iterator */
		auto ret = word_count.emplace(std::make_pair(astr, 1));
		//std::map<std::string, int>::iterator ret = word_count.emplace(std::make_pair(astr, 1));
	}
	for (auto it : word_count)
	{
		std::cout << it.first << " appears: " << it.second << " times." << std::endl;
	}

	system("pause");
}

3. 在multimap或multiset中查找元素
在一个不允许重复关键字的关联容器中查找一个元素是一件很简单的事情——元素要么在容器中，要么不在。但对于允许重复关键字的容器来说，过程就更为复杂：在容器中可能有很多元素具有给定的关键字。如果一个multimap或multiset中有多个元素具有给定关键字，则这些元素在容器中会相邻存储。</font color>
例如对于包含多个相同关键字的amp，提取出相同关键字的方法如下：

#include <map>
#include <set>
#include <string>
#include <iostream>

int main(){
	std::multimap<std::string, int> amap{ { "Hisi", 1 }, { "Qualcomm", 2 },
	                                      { "Arm", 5 } , { "Qualcomm", 3 }, { "Qualcomm", 9 }};
	std::multimap<std::string, int>::iterator it = amap.find("Qualcomm");
	std::multimap<std::string, int>::size_type num = amap.count("Qualcomm");
	for (int i = 0; i != num; ++i)
	{
		std::cout << (*it).first << " : " << (*it).second << std::endl;
		++it;
	}
}

也可用equal_range来实现相同的功能：

#include <map>
#include <string>
#include <iostream>

int main(){
	std::multimap<std::string, int> amap{ { "Hisi", 1 }, { "Qualcomm", 2 },
	{ "Arm", 5 }, { "Qualcomm", 3 }, { "Qualcomm", 9 } };

	auto iter = amap.equal_range("Qualcomm");

	for (auto it = iter.first; it != iter.second; ++it)
	{
		std::cout << (*it).first << " : " << (*it).second << std::endl;
	}
	system("pause");
}

运行以上两段程序会得到相同的输出：

Qualcomm : 2
Qualcomm : 3
Qualcomm : 9