C++:关联式容器map的使用

1、map的简介

map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair: typedef pair<const key, T> value_type;
在内部，map中的元素总是按照键值key进行比较排序的。
map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
map支持下标访问符，即在[ ]中放入key，就可以找到与key对应的value。
map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。

key: 键值对中key的类型
T：键值对中value的类型
Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器

2、map的初始化

2.1、方法1

	map<int, int> m;  //构造一个空的

2.2、方法2

map<char, int> m;
	m['a'] = 10;
	m['b'] = 30;
	m['c'] = 50;
	m['d'] = 70;
	map<char, int> m1(m);  //拷贝构造

2.3、方法3

map<char, int> m;
	m['a'] = 10;
	m['b'] = 30;
	m['c'] = 50;
	m['d'] = 70;
	map<char, int> m2(m.begin(), m.end());   //迭代器构造

3、map的排序的比较（仿函数）

struct classcomp 
{
	bool operator() (const char& lhs, const char& rhs) const
	{
		return lhs > rhs;
	}
};
	map<char, int, classcomp> m3;                 // class as Compare

4、 map的常用内置函数使用

4.1迭代器

map<int,int> v;
	//Iterators(迭代器)
	v.begin();          //获取第一个数的位置
	v.end();            //获取最后一个数的位置
	v.rbegin();         //获取最后一个数的位置
	v.rend();           //获取第一个数的位置

4.2容量

map<int,int> v; 
    //Capacity(容量)
	v.size();           //获取v数据的个数
	v.max_size();       //返回字符串可以达到的最大长度
	v.empty();          //判断v是否为空

4.3元素访问

    map<char, int> m;
	m['a'] = 10;           //和数组下标类似，但是是以key找出value
	cout << m['a'] <<endl;
    /*operator[]的原理是：
    用<key, T()>构造一个键值对，然后调用insert()函数将该键值对插入到map中
    如果key已经存在，插入失败，insert函数返回该key所在位置的迭代器
    如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器
    operator[]函数最后将insert返回值键值对中的value返回*/

3.4修改器

map<char, int> m;
	map<char, int> m1;
	m['a'] = 10;
	m['b'] = 30;
	m['c'] = 50;
	m['d'] = 70;
	m.insert(make_pair('e', 88));      //插入元素

	map<char, int>::iterator it = m.find('b');
	m.erase(it);                     // erasing by iterator
	m.erase('c');                    // erasing by key
	it = m.find('d');
	m.erase(it, m.end());            // erasing by range

	m1.swap(m);                      //交换
	m1.clear();                      // 清空

3.5操作

map<char, int>::iterator it = m.find('b');
m.count('a');

5、map的遍历(迭代)

5.1迭代器

map<char, int>::iterator it = m.begin();
	while (it != m.end())
	{
		cout << (*it).first << " " << (*it).second << endl;
		it++;
	}

5.2范围for

    for (auto e : m)
	{
		cout << e.first << " " << e.second << endl;
	}

总结

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