博客

一、map介绍

• std::map是一种关联容器，即以
  
  key-value
  
  键值对的形式存储数据。
• map底层实现是
  
  红黑树
  
  ，而C++11新增容器unordered_map与map用法基本一致，但底层是：
  
  哈希表
  
  。
• 红黑树是一种平衡二叉树，而平衡二叉树在二叉排序树基础上的，所以红黑树也就有排序的特性（unordered_map没有排序）。可以做到在O(log n)时间内完成查找，插入和删除，在对单次时间敏感的场景下比较建议使用map做为容器。

二、map的属性和方法

iterators

capacity

Element access

Modifiers

Operations

三、map的具体用法

3.1 iterator（迭代器访问）

map<string, int> myMap;
myMap["张三"] = 20;
myMap["李四"] = 22;
myMap["孙钱"] = 18;
for (map<string, int>::iterator it = myMap.begin(); it != myMap.end(); it++)
{
    cout << it->first << " ：" << it->second << endl;
}
/* 输出
李四 ：22
孙钱 ：18
张三 ：20
*/

由以上代码可以看到，map会对元素进行排序，”李四”开头字母

L

、”孙钱”开头字母

S

、”张三”开头字母

Z

，

L < S < Z

，可见map默认以key值从小到大排序。

map<string, int> myMap;
myMap["张三"] = 20;
myMap["李四"] = 22;
myMap["孙钱"] = 18;
for (auto it = myMap.rbegin(); it != myMap.rend(); it++)
{
    cout << it->first << " ：" << it->second << endl;
}

rbegin()和rend()则可从尾到头遍历。

3.2 capacity（容量）

• 
size()

  返回map中键值对的个数
• 
max_size()

  map中能存储的最大值
• 
empty()

  判断map是否为空：为空返回true，不为空返回false

map<string, int> myMap;
myMap["张三"] = 20;
myMap["李四"] = 22;
myMap["孙钱"] = 18;
cout << myMap.size() << endl;//大小为3
cout << myMap.max_size() << endl;//最大容量：89478485
cout << myMap.empty() << endl;//非空即为0

3.3 Element access（下标访问）

• map重载了
  
[]

  运算符，可以通过map[]通过key值访问其value。
• at作用和[]用法一致，实现效果一致。
• 如果某个key值不存在，即没有该键值对，返回0。（可见各个位置初始值为0）。

map<string, int> myMap;
myMap["张三"] = 20;
myMap["李四"] = 22;
myMap["孙钱"] = 18;
cout << myMap["张三"] << endl;//20
cout << myMap.at("张三") << endl;//20
cout << myMap["王五"] << endl;//0

3.4 Modifiers（修改器）

这部分主要用于修改元素，如

增删改查

等操作。

3.4.1 insert

因为map中存储的元素时键值对类型（pair），所以insert可以有两种插入方式：

（1）使用pair、value_type、make_pair()函数，插入一个键值对

map<string, int> myMap;
myMap.insert(pair<string, int>("李四", 22));
myMap.insert(map<string, int>::value_type("张三", 20));
pair<map<string, int>::iterator, bool> ans;//定义返回值类型
ans = myMap.insert(make_pair("孙钱", 18));
cout << ans.first->first << ":" << ans.first->second << endl;
myMap.insert(myMap.begin(), make_pair("赵六", 28));

注意，插入后的返回值是一个pair类型，pair.first是map的迭代器，pair.second为是否插入成功的返回值。

（2）在指定位置插入元素

map<string, int> myMap;
myMap.insert(pair<string, int>("李四", 22));
myMap.insert(map<string, int>::value_type("张三", 20));
myMap.insert(make_pair("孙钱", 18));
myMap.insert(myMap.begin(), make_pair("赵六", 28));//在map头部后面插入
for (auto it = myMap.begin(); it != myMap.end(); it++)
{
	cout << it->first << ":" << it->second << endl;
}

但是通过显示的结果可知，即使指定在某个位置后插入，但是实际上map还是会根据

key值

将其排序。

注意，和前一种用法不一样的是，

返回值是迭代器

，而不是pair。

（3）在某个范围内插入元素，[first, last]

map<string, int> myMap;
myMap.insert(pair<string, int>("李四", 22));
myMap.insert(map<string, int>::value_type("张三", 20));
myMap.insert(make_pair("孙钱", 18));

map<string, int> newMap;
newMap.insert(myMap.begin(), myMap.end());
for (auto it : newMap)
cout << it.first << ":" << it.second << endl;

（4）一次性插入多个键值对

map<string, int> myMap;
myMap.insert({ {"李四", 22}, {"张三", 20} });//一次性插入两个键值对
myMap.insert(make_pair("孙钱", 18));

3.4.2 erase

删除元素，输入参数为迭代器，有以下两种遍历删除元素的方法：

（1）通过迭代器删除元素

• 因为erase的返回值是下一个迭代器的指针，所以可以用返回值做下一次删除的元素

  map<string, int> myMap;
  myMap.insert(map<string, int>::value_type("张三", 20));
  myMap.insert(map<string, int>::value_type("李四", 22));
  myMap.insert(map<string, int>::value_type("孙钱", 18));
  for (auto it = myMap.begin(); it != myMap.end(); )
  {
  it = myMap.erase(it);
  }
  cout << myMap.empty() << endl;
  

• 根据后
  
++

  的特点，先删除后it偏移。

  map<string, int> myMap;
  myMap.insert(map<string, int>::value_type("张三", 20));
  myMap.insert(map<string, int>::value_type("李四", 22));
  myMap.insert(map<string, int>::value_type("孙钱", 18));
  for (auto it = myMap.begin(); it != myMap.end(); )
  {
  	myMap.erase(it++);
  }
  cout << myMap.empty() << endl;
  

（2）通过key值删除元素

map<string, int> myMap;
myMap.insert({ {"李四", 22}, {"张三", 20} });
myMap.emplace_hint(myMap.begin(), make_pair("孙钱", 18));
myMap.erase("李四");//删除key值为李四的元素

3.4.3 swap

swap交换两个map的内容，两个map的所有内容均交换。

map<string, int> myMap;
myMap.insert(map<string, int>::value_type("张三", 20));
myMap.insert(map<string, int>::value_type("李四", 22));
myMap.insert(map<string, int>::value_type("孙钱", 18));
map<string, int> myMap2;
myMap2["王五"] = 30;
myMap2["赵六"] = 50;
myMap.swap(myMap2);
for (auto it = myMap.begin(); it != myMap.end(); it++)
{
cout << it->first << ":" << it->second << endl;
}

3.4.4 clear

clear清空map的键值对，size = 0。

map<string, int> myMap;
myMap.insert(map<string, int>::value_type("张三", 20));
myMap.insert(map<string, int>::value_type("李四", 22));
myMap.insert(map<string, int>::value_type("孙钱", 18));
myMap.clear();
cout << myMap.empty() << endl;

3.4.5 emplace

用法和insert一样，只是内部实现机制不同，emplace更快，但是只能插入一个键值对。

emplace的插入可以，将创建新键值对所需的数据作为参数直接传入即可，此方法可以自行利用这些数据构建出指定的键值对。

map<string, int> myMap;
myMap.emplace(map<string, int>::value_type("张三", 20));//法1
myMap.emplace(pair<string, int>("李四", 22));//法2
myMap.emplace("赵六", 30);

3.4.6 emplace_hint

emplace_hint有点类似于insert的第二种用法，在指定位置插入。

但是，emplace_hint和emplace一样，可以将数据参数直接输入。

第一个参数是要插入的位置，接下来第二、三个参数分别是key 和 value。

map<string, int> myMap;
myMap.insert({ {"李四", 22}, {"张三", 20} });
myMap.emplace_hint(myMap.begin(), "孙钱", 18);

当然，和insert一样，指定位置插入，但是map仍然会根据key值大小进行排序。

3.5 Operations（操作）

这部分操作用于查找元素，计算元素大小。

3.5.1 find

map有find方法，需和algorithm库的find区别。map的find方法寻找键值对中的键值，返回一个迭代器。如果迭代器不是

map.end()

，那么说明找到元素，返回该元素的迭代器。

map<string, int> myMap;
myMap.insert({ {"李四", 22}, {"张三", 20} });
myMap.emplace_hint(myMap.begin(), make_pair("孙钱", 18));
auto it = myMap.find("李四");//寻找是否有名为"赵四"的人
if (it != myMap.end())
{
cout << it->first << ":" << it->second << endl;
}

3.5.2 count

map和set两种容器的底层结构都是

红黑树

，所以容器中不会出现相同的元素，因此count()的结果只能为0和1。

所以可以用

count

判断map是否有某键值对。

map<string, int> myMap;
myMap.insert({ {"李四", 22}, {"张三", 20} });
myMap.emplace_hint(myMap.begin(), make_pair("孙钱", 18));
cout << myMap.count("张三") << endl;//输出1

3.5.3 lower_bound

在STL里有lower_bound函数，用于在有序容器中找到第一个大于val值的迭代器。

同样的，在map中有该方法，返回

大于或等于

某个键值

key

的迭代器。

map<int, int> myMap;
myMap[1] = 2;
myMap[2] = 4;
myMap[3] = 7;
myMap[5] = 8;
myMap[6] = 9;
auto it = myMap.lower_bound(3);
if (it != myMap.end())
{
    cout << it->first << ":" << it->second << endl;//3:7
}

3.5.4 upper_bound

和lower_bound类似，不过upper_bound返回的是

大于

某个键值

key

的迭代器。

map<int, int> myMap;
myMap[1] = 2;
myMap[2] = 4;
myMap[3] = 7;
myMap[5] = 8;
myMap[6] = 9;
auto it = myMap.upper_bound(3);
if (it != myMap.end())
{
    cout << it->first << ":" << it->second << endl;//5:8
}

3.5.5 equal_range

pair<const_iterator,const_iterator> equal_range (const key_type& k) const;
pair<iterator,iterator>             equal_range (const key_type& k);

如上是map中equal_range的原形，返回值是一个pair类型，pair类型里是两个迭代器，pair::first返回的值等于lower_bound的返回值，即大于等于某个值的第一个值的迭代器；pair::second返回的值等于upper_bound返回的值，即大于某个值的第一个值的迭代器。

所以，equal_range用于计算某个值的所有插入的元素。因为我们可能插入（insert）了很多元素，但是实际上只有一个值有效，也就是第一个插入的值。equal_range就可以为

multimap

计算所有插入的元素。

而

map


不论传入多少个都只有一个值

，equal_range得到也只有一个值。

以下是multimap的

equal_range

：

multimap<int, int> myMap;
myMap.insert(make_pair(1, 5));
myMap.insert(make_pair(2, 4));
myMap.insert(make_pair(3, 6));
myMap.insert(make_pair(3, 5));
myMap.insert(make_pair(3, 4));


auto ret = myMap.equal_range(3);
for (auto it = ret.first; it != ret.second; it++)
{
	cout << it->first << ":" << it->second << endl;
}
//输出：
/*
3:6
3:5
3:4
*/

参考

• 
  http://www.cplusplus.com/
  
• 
  http://c.biancheng.net/view/7173.html