map/multimap

std::map的键值key不可重复，而std::multimap可以，也正是由于这种区别，std::map支持[ ]运算符，std::multimap不支持[ ]运算符。std::map内部自建一颗红黑树，这颗树具有对数据自动排序的功能，所以在std::map内部所有的数据都是有序的。

创建map

通过调用 map 容器类的默认构造函数，可以创建出一个空的 map 容器，比如：

std::map<std::string, int> myMap;

通过此方式创建出的 myMap 容器，初始状态下是空的，即没有存储任何键值对。鉴于空 map 容器可以根据需要随时添加新的键值对，因此创建空 map 容器是比较常用的。
当然在创建 map 容器的同时，也可以进行初始化，比如：

std::map<std::string, int> myMap{ {"C语言教程",10},{"STL教程",20} };

map 容器中存储的键值对，其本质都是 pair 类模板创建的 pair 对象。因此，下面程序也可以创建出一模一样的 myMap 容器：

std::map<std::string, int>myMap{std::make_pair("C语言教程",10),std::make_pair("STL教程",20)};

除此之外，在某些场景中，可以利用先前已创建好的 map 容器，再创建一个新的 map 容器。例如：

std::map<std::string, int>newMap(myMap);

map 类模板还支持取已建 map 容器中指定区域内的键值对，创建并初始化新的 map 容器。例如：

std::map<std::string, int>myMap{ {"C语言教程",10},{"STL教程",20} };
std::map<std::string, int>newMap(++myMap.begin(), myMap.end());

下面程序手动修改了 myMap 容器的排序规则，令其作降序排序：

std::map<std::string, int, std::greater<std::string> >myMap{ {"C语言教程",10},{"STL教程",20} };

成员函数

• find(key): 在 map 容器中查找键为 key 的键值对，如果成功找到，则返回指向该键值对的双向迭代器；反之，则返回和 end() 方法一样的迭代器。另外，如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
• lower_bound(key):返回一个指向当前 map 容器中第一个大于或等于 key 的键值对的双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
• upper_bound(key):返回一个指向当前 map 容器中第一个大于 key 的键值对的迭代器。
• equal_range(key):该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价。也就是说，该方法将返回一个范围，该范围中包含的键为 key 的键值对（map 容器键值对唯一，因此该范围最多包含一个键值对）。
• empty(): 若容器为空，则返回 true；否则 false。
• size(): 返回当前 map 容器中存有键值对的个数。
• max_size(): 返回 map 容器所能容纳键值对的最大个数，不同的操作系统，其返回值亦不相同。
• operator[]: map容器重载了 [] 运算符，只要知道 map 容器中某个键值对的键的值，就可以向获取数组中元素那样，通过键直接获取对应的值。
• at(key): 找到 map 容器中 key 键对应的值，如果找不到，该函数会引发 out_of_range 异常。
• insert(): 向 map 容器中插入键值对。
• erase(): 删除 map 容器指定位置、指定键（key）值或者指定区域内的键值对。
• swap(): 交换 2 个 map 容器中存储的键值对，这意味着，操作的 2 个键值对的类型必须相同。
• clear(): 清空 map 容器中所有的键值对，即使 map 容器的 size() 为 0。
• emplace(): 在当前 map 容器中的指定位置处构造新键值对。其效果和插入键值对一样，但效率更高。
• emplace_hint(): 在本质上和 emplace() 在 map 容器中构造新键值对的方式是一样的，不同之处在于，使用者必须为该方法提供一个指示键值对生成位置的迭代器，并作为该方法的第一个参数。
• count(key): 在当前 map 容器中，查找键为 key 的键值对的个数并返回。注意，由于 map 容器中各键值对的键的值是唯一的，因此该函数的返回值最大为 1。

访问与遍历

定义一个std::map方便后续操作：

std::map<std::string, std::string>myMap{ {"STL教程","http://logan_xu/example/stl"},
                                             {"C语言教程","http://logan_xu/example/c"},
                                             {"Java教程","http://logan_xu/example/java"} };

map 类模板中对[ ]运算符进行了重载，这意味着，类似于借助数组下标可以直接访问数组中元素，通过指定的键，我们可以轻松获取 map 容器中该键对应的值。

string cValue = myMap["C语言教程"];

注意，只有当 map 容器中确实存有包含该指定键的键值对，借助重载的 [ ] 运算符才能成功获取该键对应的值；反之，若当前 map 容器中没有包含该指定键的键值对，则此时使用 [ ] 运算符将不再是访问容器中的元素，而变成了向该 map 容器中增添一个键值对。其中，该键值对的键用 [ ] 运算符中指定的键，其对应的值取决于 map 容器规定键值对中值的数据类型，如果是基本数据类型，则值为 0；如果是 string 类型，其值为 ""，即空字符串（即使用该类型的默认值作为键值对的值）。
举例：

std::map<std::string, int>myMap;
int cValue = myMap["C语言教程"];
for (auto i = myMap.begin(); i != myMap.end(); ++i) {
    std::cout << i->first << " "<< i->second << std::endl;
}

程序执行结果为：

C语言教程 0

显然，对于空的 myMap 容器来说，其内部没有以 "C语言教程" 为键的键值对，这种情况下如果使用 [ ] 运算符获取该键对应的值，其功能就转变成了向该 myMap 容器中添加一个<"C语言教程",0>键值对（由于 myMap 容器规定各个键值对的值的类型为 int，该类型的默认值为 0）。

除了借助 [ ] 运算符获取 map 容器中指定键对应的值，还可以使用 at() 成员方法。和前一种方法相比，at() 成员方法也需要根据指定的键，才能从容器中找到该键对应的值；不同之处在于，如果在当前容器中查找失败，该方法不会向容器中添加新的键值对，而是直接抛出 out_of_range 异常。

除了可以直接获取指定键对应的值之外，还可以借助 find() 成员方法间接实现此目的。和以上 2 种方式不同的是，该方法返回的是一个迭代器，即如果查找成功，该迭代器指向查找到的键值对；反之，则指向 map 容器最后一个键值对之后的位置（和 end() 成功方法返回的迭代器一样）。

map< std::string, std::string >::iterator myIter = myMap.find("C语言教程");
// 通过myIter->first 访问key, myIter->second 访问value
cout << myIter->first << " " << myIter->second << endl;

插入数据

std::map<string, string> mymap;
//创建一个真实存在的键值对变量
std::pair<string, string> STL = { "STL","http://logan_xu/example/stl" };

//创建一个接收 insert() 方法返回值的 pair 对象
std::pair<std::map<string, string>::iterator, bool> ret;

//插入 STL，由于 STL 并不是临时变量，因此会以引用方式传参
ret = mymap.insert(STL);
std::cout << "ret.iter = <{" << ret.first->first << ", " << ret.first->second << "}, " << ret.second << ">" << std::endl;

//以右值引用的方式传递临时的键值对变量
ret = mymap.insert({ "C语言教程","http://c.biancheng.net/c/" });