底层以红黑树实现的map和set_map 红黑树

操作

set的使用举例

例

#include <set>
void TestSet()
{
    // 用数组array中的元素构造set
    int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 
6, 8, 0 };
 set<int> s(array, array+sizeof(array)/sizeof(array[0]));
 cout << s.size() << endl;
 // 正向打印set中的元素，从打印结果中可以看出：set可去重
 for (auto& e : s)
 cout << e << " ";
 cout << endl;
 // 使用迭代器逆向打印set中的元素
 for (auto it = s.rbegin(); it != s.rend(); ++it)
 cout << *it << " ";
 cout << endl;
 // set中值为3的元素出现了几次
 cout << s.count(3) << endl;
}

map

map介绍：

map是KV模型

1.map是关联容器，他按照特定的次序（按照key来比较）存储由键值key和值value组合而成的元素。

2.mao中的键值key常用于排序和唯一的标识元素，而值value中存储与此键值key关联的内容。键值key和value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair：

typedef pair<const key,T>value_type;

3.在内部，map中的元素总是按照键值key进行比较排序的。

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

5.map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。

6.map通常被实现为二叉搜索树

map的使用

map模板参数说明

key：键值对中key的类型 

T：键值对中value的类型

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

Alloc：空间配置器 默认内存池

构造

迭代器

容量和元素访问操作

需要注意的是：当key不在map中时，通过operator去获取对应的value时，operator[]会用默认的value与key构造键值然后插入，返回该默认value。

对于元素访问，还有一个at（）函数，当要访问的key不存在时，会直接抛异常。

map中元素的修改

map使用举例：

void Testmap()
{
	map<string, string> m;
	//向map中插入元素的方式： 
	//将键值对插入map中，用pair直接来构造键值对
	m.insert(pair<string, string>("peach", "桃子"));
 
	//将键值对插入map中，用make_pair函数来构造键值对
	m.insert(make_pair("monkey", "猴子"));
 
	//借用operator[]来向map中插入没有的元素
	m["apple"] = "苹果";
 
	//key不存在时抛异常 就用at 例如m.at("apple") ="苹果";
 
	cout << m.size() << endl;
 
	//用迭代器去遍历
	for (auto& e : m)
	{
		cout << e.first << "对应的中文是：" << e.second << endl;
	}
	cout << endl;
 
	//map中的键值对key一定是唯一的，如果key存在将插入失败
	auto ret = m.insert(make_pair("peach", "桃子"));
	if (ret.second)//ret的second是一个bool，插入成功就是true反之则是false
		cout << "<peach,桃子>不在map中，已经插入" << endl;
	else
		cout << "键值为peach的元素已经存在：" << ret.first->first << "-----" << ret.first->second << "插入失败" << endl;
 
	//删除key为"apple"的元素
	m.erase("apple");
	if (1 == m.count("apple"))
		cout << "apple还在" << endl;
	else
		cout << "apple被删了" << endl;
}

总结：

1.map是KV模型，其中的元素是键值对

2.map中的key是唯一的，并且是不能修改的

3.默认按照小于的方式对key进行比较

4.map中的元素如果用迭代器去遍历，可以得到一个有序的序列

5.map的底层为红黑树，查找效率非常高O(logN)

6.map支持[] 访问，operator[]中实际进行插入查找

multiset和multimap

multiset和mutimap允许冗余（key冗余）

底层结构

对于map和set，他们底层都是用二叉搜索树来实现的，但是二叉搜索树也有它自身的缺陷：

在数据有序或者接近有序的情况下插入效率非常低下。时间复杂度为O(N)

因此我们对map、set等关联式容器的底层结构的二叉树进行平衡处理，即采用平衡树来解决。