C++:map和set的认识和简单使用/关联式容器

关联式容器

关联式容器即是用来存储数据的，并且存储的是<Key，Value>结构的键值对，在数据检索时效率比序列式容器高。

序列式容器也就是vector、list、queue等容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。

键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。比如，英汉翻译中，苹果对应着apple，香蕉对应着banana。

pair/make_pair

map和set底层实现原理都是二叉树，准确地来说，是红黑树。而map和set的区别就是，set没有键值对，只有一个value。而map则是拥有键值对，在底层的实现中，键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:

typedef pair<const key, T> value_type;

而pair是一个类，里面的成员分别是first和second，first表示的是第一个类型的变量，seconde表示第一个类型的变量。

通过pair来绑定键值对，比如pair<string,int>("str",1)。其中，pair<string,int>可以使用make_pair来替换，make_pair("str",1)。

其实make_pair就是对pair进行了封装。 

 make_pair返回的值，就是一个pair的对象。

树形结构的关联式容器

关联式容器有两种：一种是哈希结构的关联式容器，另一种是树形结构的关联式容器。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。

set容器

认识set

①set是按照一定次序存储元素的容器

②在set中，元素的key也标识它，并且每个key必须是唯一的。

③set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们

④set中的元素总是按照其内部比较对象(类型比较）所指示的特定严格弱排序准则（set中的元素默认按照小于来比较）进行排序，即升序。

⑤set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。

⑥set在底层是用二叉搜索树(红黑树)实现的

⑦set中查找某个元素，时间复杂度为：long_2 N

⑧set中的元素不可以重复(因此可以使用set进行去重)

⑨使用set的迭代器遍历set中的元素，可以得到有序序列

⑩set中的元素不允许修改

使用set

set的模板参数列表：

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

具体函数接口这里就不一一列出来了，要用的时候，一个优秀的程序员应该拥有查和阅读文档的能力。下方是文档链接：set的文档

下面是代码是使用例子：

#include<iostream>
#include<set>
using namespace std;


int main()
{
	//使用数组arr中的元素构造set
	int arr[] = { 2,3,5,6,1,8,7,4,9,2,0,3,0,1 };
	set<int> s(arr, arr + sizeof(arr) / sizeof(arr[0]));
	cout << s.size() << endl;

	//打印set中的元素
	for (auto& e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	//set中值为3的元素出现的次数
	cout << s.count(3) << endl;

	cout << endl;

	//使用迭代器
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
	}
	cout << endl;

	//查找元素
	auto pos1 = s.find(3);                 //O(logN)
	auto pos2 = find(s.begin(), s.end(), 3);//O(N)

	//删除pos元素
	if (pos1 != s.end())
	{
		s.erase(pos1);
	}
	cout << s.erase(1);
	cout << s.erase(3);

	//对[）左闭右开的区间的元素进行删除
	set<int> myset;
	set<int>::iterator itlow, itup;

	//10 20 30 40 50 60 70 80 90 
	for (int i = 1; i < 10; ++i) myset.insert(i * 10);
	itlow = myset.lower_bound(25);
	itup = myset.upper_bound(65);
	//对[25,65）范围的数据全部删除
	myset.erase(itlow, itup);

	return 0;
}

multiset容器

multiset与set的区别就是，set去重，而multiset不去重。其它与set几乎一样，但multiset底层实际存储的是<int,int>键值对。

int main()
{
	int array[] = { 2, 1, 3, 9, 6, 0, 5, 8, 4, 7 };
	// 注意：multiset在底层实际存储的是<int, int>的键值对
	multiset<int> s(array, array + sizeof(array) / sizeof(array[0]));
	for (auto& e : s)
		cout << e << " ";
	cout << endl;
	return 0;
}

map容器

认识map

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

②在map中，键值key通常用于排序和唯一地标识元素，而值value中存储与此键值key关联的内容，key与value使用pair绑定起来。

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

④map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。这个下标访问，是我们平常使用的随机访问有点不一样，下面将会对[]进行主要分析。

⑤map通常被实现为二叉搜索树（红黑树）

使用map

map的模板参数:

Key:键值对中key的类型。

T：键值对中的value的类型。

Compare：比较器的类型。map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)

Alloc：通过空间配置器来申请底层空间，不需要传递，除非不想使用标准库提供的空间配置器

需要说明的接口：

operator[]

通过查文档我们发现，map中的operator[]传入的是key值，返回来的是key值对应的value的引用。需要注意的是，在元素访问时，有一个与operator[]类似的操作at()(该函数不常用)函数，都是通过key找到与key对应的value然后返回其引用，不同的是：当key值不存在时，operator[]用默认value与key构造键值对然后插入，返回改默认的value，而at()则是直接抛异常。

使用例子：

	//pair/make_pair
	map<string, string> dict;
	dict.insert(pair<string, string>("排序", "sort"));
	dict.insert(pair<string, string>("右边", "right"));
	dict.insert(pair<string, string>("左边", "left"));
	dict.insert(make_pair("字符串", "string"));

	//operator[]
	dict["迭代器"] = "iterator";
	dict["插入"];
	//修改
	dict.insert(pair<string, string>("左边", "xxx"));
	dict["插入"] = "insert";
	//查找
	cout << dict["左边"] << endl;

总结一下：

① map中的的元素是键值对 ②map中的key是唯一的，并且不能修改 ③默认按照小于的方式对key进行比较 ④map中的元素如果用迭代器去遍历，可以得到一个有序的序列 ⑤map的底层为平衡搜索树(红黑树)，查找效率比较高O(log_2 N) ⑥支持[]操作符，operator[]中实际进行插入查找

multimap容器

multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重复的。

注意：

①multimap中的key是可以重复的。 ②multimap中的元素默认将key按照小于来比较 ③multimap中没有重载operator[]操作。因为一个key对应着多个value，不知道要找哪一个。 ④使用时与map包含的头文件相同