标准模板库-map

1. map简介

• map是STL中的关联式容器，提供一对一的数据结构，其中第一个称为关键字Key，每个关键字只能在map中出现一次，第二个称为该关键字的值Value。map内部通过红黑树（一种平衡二叉树，能够对数据自动排序）实现，所以map内部的数据都是有序的。
• 增加和删除节点对迭代器的影响很小，对迭代器来说，可以修改值Value，而不能修改Key。

2. map的插入方法

• （1）使用insert方法插入pair数据，例如：

map<int, string> m;
m.insert(pair<int, string>(1, "zhang san"));
// 要判断insert是否插入成功，方法如下：
pair<map<int, string>::iterator, bool> insert_pair;
insert_pair = m.insert(pair<int, string>(1, "li si");
// insert_pair.first返回map的迭代器，insert_pair.second返回是否插入成功。

• （2）使用insert方法插入value_type数据，判断是否插入成功方式同上，例如：

map<int, string> m;
m.insert(map<int, string>::value_type(1, "li si"));

• （3）用数组方式插入数据，例如：

map<int, string> m;
m[1] = "zhang san";
m[2] = "li si";

• 区别：当map中已有此关键字时，insert方法插入不了数据，而数组方式则会覆盖该关键字以前的值。

3. map的遍历

• （1）使用前向迭代器。例如：map<int, string>::iterator iter;
• （2）使用反向迭代器。例如：map<int, string>::reverse_iterator iter;
• （3）使用数组的形式。并不常用

4. map的查找

• （1）用count()来判断关键字是否出现，由于map是一对一映射，因此count()方法只能返回0，或1。
• （2）用find()，传入要查找的Key，它返回一个迭代器，当找到数据时，返回该数据所在位置的迭代器，如果没有该数据，则返回等于end()方法返回的迭代器。该返回的迭代器为std::pair对象，iterator->first和iterator->second分别代表关键字和值。
• （3）
  lower_bound()：返回要查找关键字的下界迭代器。
  upper_bound()：返回要查找关键字的上界迭代器。
  equal_range()：返回一个pair，pair里的第一个变量是lower_bound返回的迭代器，pair里的第二个变量是upper_bound返回的迭代器。如果这两个迭代器相等的话，说明map中不出现这个关键字。

5. map删除元素

• iterator erase(iterator it); // 通过一个迭代器删除元素。
• iterator erase(iterator first, iterator last); // 删除一个范围，删除区间左闭右开。
• size_type erase(const Key& key); // 通过关键字删除。
• clear(); // 清空元素。

6. map其余常用方法

• map1.swap(map2)：交换map1与map2两个容器中的元素。
• map.count()：返回指定元素出现的次数。
• low_bound()：返回键值>=给定元素的第一个位置
• upper_bound()：返回键值>给定元素的第一个位置。