map和set的应用

1. 序列式和关联式容器

序列式容器：比如：vector、list、deque、forward_list等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。
关联式容器：关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的键值对，在数据检索时比序列式容器效率更高。底层是树形结构（红黑树）。

2.set和multiset

两者的区别在于set不允许数据冗余，即不能存储相同的数据。multiset可以存储相同的数据。

2.1 构造

set<string> s1; //空初始化

int arr[10] = { 4,0,9,3,5,8,7,1,2,11 };
set<int> s(arr, arr + 10); //迭代器区间初始化

set<int> s2(s);  //拷贝构造

multiset同理。

2.2 迭代器

迭代器和其他容器类似。

void testset()
{
	int arr[10] = { 4,0,9,3,5,8,7,1,2,11 };
	set<int> s(arr, arr + 10); 

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

	set<int>::reverse_iterator rit = s.rbegin();
	while (rit != s.rend())
	{
		cout << *rit << " ";
		rit++;
	}
}

int main()
{
	testset();
	return 0;
}

运行结构如下

由于底层是搜索树，因此遍历结果为升序，反向遍历则为降序。

2.3 修改

count返回set内值为val的元素的个数，这个函数对于set没有太大作用。要么存在为1，要么不存在为0。因为set不允许数据冗余。对于multiset比较实用，可以统计某个元素的次数。

lower_bound返回第一个大于等于val的元素的迭代器。
upper_bound返回第一个大于val的元素的迭代器。

3. map和multimap

3.1 map

1. map是关联式容器，它按照特定的次序(通过比较key的大小)存储由键值key和值value组合而成的元素。
2. 在map中，键值key通常用于排序和唯一的标识元素，而值value中存储与此键值key关联的
   内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型
   value_type绑定在一起，为其取别名称为pair:
   typedef pair value_type;
3. 在内部，map中的元素总是按照键值key进行比较排序的。
4. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序
   对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
5. map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
6. map通常被实现为红黑树。

map和multimap的接口和set类似。最不同的为map支持[ ]的访问。

void test_map()
{
	map<string, string> dict;
	dict.insert(make_pair("1", "one")); //调用接口
	dict.insert({ "2", "two" });        //隐式类型转换
	dict.insert(pair<string,string>("0", "zero")); //匿名对象

	map<string, string>::iterator it = dict.begin();
	cout << it->first << ":" << it->second<<endl;

	map<string, int> fruit;
	fruit["苹果"];            //插入
	fruit["苹果"] = 8;     //修改
	fruit["香蕉"] = 3;     //插入+修改

	map<string, int>::iterator it1 = fruit.begin();
	while(it1!=fruit.end())
	{
			cout << it1->first << ":" << it1->second << endl;
			++it1;
	}

}

由于存储的是pair，所以使用->更方便访问结构内的成员

operator[] 的原理大致如下

map fruit;
fruit[“苹果”]; //插入
fruit[“苹果”] = 8; //修改
fruit[“香蕉”] = 3; //插入+修改

operator[] 具有以上的功能。

总结

1. map中的的元素是键值对
2. map中的key是唯一的，并且不能修改
3. 默认按照小于的方式对key进行比较
4. map中的元素如果用迭代器去遍历，可以得到一个有序的序列
5. map的底层为平衡搜索树(红黑树)，查找效率比较高$O(lo{g}_{2}N)$
6. 支持[]操作符，operator[]中实际进行插入查找。

3.2. multimap

1. multimaps是关联式容器，它按照特定的顺序，存储由key和value组成的键值对 value>，其中多个键值对之间的key是可以重复的。
2. 在multimap中，通常按照key排序和唯一的标识元素，而value存储与key关联的内
   容。key和value的类型可能不同，通过multimap内部的成员类型value_type组合在一起，
   value_type是组合key和value的键值对:
   typedef pair value_type;
3. multimap通过key访问单个元素的速度通常比unordered_multimap容器慢，但是使用迭代
   器直接遍历multimap中的元素可以得到关于key有序的序列。
4. multimap在底层用红黑树来实现。
   注意：multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以
   重复的。

multimap的接口和map类似。但是没有重载operator[]，因为key可以有很多个。