正文
C++容器（四）：map类型
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
map 类型
map是键-值对的集合。map类型通常可以理解为关联数组：可以使用键作为下标来获取一个值，正如内置数组类型一样。而关联的本质在于元素的值与某个特定的键相关联，而非通过元素在数组内的位置来获取。
要使用map对象，必须包含map头文件：
#include <map>
在定义map对象时，必须指明键和值的类型：
map<string, int> wordCount; // empty map from string to int
1 map对象的构造函数
| 操作 | 含义 |
|---|---|
map<k, v> m | 创建一个名为m的map对象，其键和值的类型分别为k和v |
map<k, v> m(m2) | 创建m2的副本m，m与m2必须具有相同的键类型和值类型 |
map<k, v> m(b, e) | 创建map类型的对象m，存储迭代器b和e标记范围内的所有元素副本。元素的类型必须能够转换为pair<const k, v> |
对于键类型，唯一的约束就是必须支持
<操作，至于是否支持其他关系或相等运算，则不做要求。
2 map定义的类型
包括：键类型，值类型以及键-值（pair）类型。
| 类型 | 含义 |
|---|---|
map<k, v>::key_type | 在map容器中，用作索引的键的类型 |
map<k, v>::mapped_type | 在map类型中，键所关联的值的类型 |
map<k, v>::value_type | 一个pair类型，它的first元素具有const map<k, v>::key_type类型，而second则为map<k, v>::mapped_type类型 |
map迭代器进行解引用将产生pair类型的对象
对迭代器进行解引用时，将获得一个引用，指向容器的一个value_type类型值。
map<string, int>::iterator map_it = wordCount.begin();
// *map_it is a reference to a pair<const string, int> object
cout << map_it->first << " " << map_it->second << endl; // print the key and value of the elementmap_it->first = "new key"; // error: key is const type
++ map_it->second; // ok: we can change value through the iterator
3 给map添加元素
给map中添加键-值元素对时，有两种方式：一种是先用下标操作符获取元素，然后给获取的元素赋值，一种是使用insert成员函数实现。
3.1 使用下标访问map对象
如编写下段程序时：
map<string, int> wordCount; // empty map
// insert default initialized element with key "Anna"; then assign 1 to its value
wordCount["Anna"] = 1;
将发生以下事情：
- 在wordCount中查找键为
Anna的元素，没有找到；- 将一个新的键-值对插入到
wordCount中。它的键是const string类型的对象，保存Anna。而它的值则采用值初始化，这就意味着在本例中值为0；- 将这个新的键-值对插入到
wordCount中；- 读取插入的新元素，并将它的值赋为1。
- 下标操作符返回值的使用
通常来说，下标操作符返回左值。它返回的左值是特定键所关联的值。
cout << wordCount["Anna"] <<endl; // fetch element indexed by Anna; ptint 1
++ wordCount["Anna"]; // fetch the element and add one to it
cout << wordCount["Anna"] << endl; // fetch element and print it; print 2
有别于
vector或string类型，map下标操作符返回的类型与对map迭代器进行解引用获得的类型不相同。
- 下标行为的编程意义
对于map容器，如果下标表示的键在容器中不存在，则添加新元素，这一特性可使程序惊人的简练：
// count the number of times each word occurs in the input
map<string, int> wordCount; // empty map from string to int
string word;
while ( cin >> word )
++ wordCount[word];
这段程序创建一个map对象，用来记录每个单词出现的次数，while循环每次从标准输入读取一个单词，如果这是一个新的单词，则在wordCount中添加以该单词为索引的新元素，如果读入单词已经在map对象中，则将它所对应的值加1。
3.2 insert 成员函数
map容器的insert成员与顺序容器的类似，但有一点要注意：必须考虑键的作用。
| 操作 | 含义 |
|---|---|
m.insert(e) | e是一个用在m上的value_type类型的值。如果键(e.first)不在m中，则插入一个值为e.second的新元素；如果键在m中已经存在，则保持m不变。该函数返回一个pair类型对象，包含指向键为e.first的元素的map迭代器，以及一个bool的对象，表示是否插入了该元素 |
m.insert(begin, end) | begin和end是标记元素范围的迭代器，其中的元素必须为m.value_type类型的键-值对。对于该范围内的所有元素，如果其键在m中不存在，则将该键及其关联的值插入m。返回void类型 |
m.insert(iter, e) | e是一个用在m上的value_type类型的值。如果键(e.first)不在m中，则创建新元素，并以迭代器iter为起点搜索新元素存储的位置。返回一个迭代器，指向m中具有给定键的元素 |
- 以
insert代替下标运算
使用下标给map容器添加新元素时，元素的值部分将采用值初始化。通常，我们会立即为其赋值，其实就是对同一个对象进行初始化并赋值。而insert其语法更加紧凑：
// if Anna not already in wordCount, inserts new element with value 1
wordCount.insert( map<string, int>::value_type("Anna", 1) );
这个insert函数版本的实参：
map<string, int>::value_type("Anna", 1)
是一个新创建的pair对象，将直接插入到map容器中。但是传递给insert的实参相当笨拙，有两种方法可以简化：
// first
wordCount.insert( make_pair("Anna", 1) );// second
typedef map<string, int>::value_type valueType;
wordCount.insert( valueType("Anna", 1) );
前面我们已经学会了，使用下标操作符统计输入的单词，insert成员函数同样可以实现：
// count number of times each word occurs in the input
map<string, int> wordCount; // empty map from string to int
string word;
while ( cin >> word )
{
// insert element with key equal to word and value 1
// if word already in wordCount, insert does nothing
pair<map<string, int>::iterator, bool> ret =
wordCount.insert(make_pair(word, 1));
if ( !ret->second ) // word already in wordCount
++ ret.first->second; // increment counter
}
本处使用了带有一个键-值pair形参的insert版本将返回：包含一个迭代器和一个bool值的pair对象，其中迭代器指向map中具有相应键的元素，而bool值则表示是否插入了该元素。如果该键已在容器中，则其关联的值保持不变，返回的bool值为false；如果该键不在容器中，则插入新元素，且bool值为true。对于每个单词，都尝试insert它，并将它的值赋为1。if语句检测insert函数返回值，如果值为false则表示没有做插入操作；按照word索引的元素已在wordCount中存在，此时将该元素所关联的值加1。
4 查找并读取map元素
下标操作符给出了读取一个值的最简单方法：
map<string, int> wordCount; // empty map from string to int
int occurs = wordCount["Anna"];
但是，该方法存在一个副作用：如果该键不存在map容器中，则下标操作会插入一个具有该键的新的元素。大多数情况下，我们其实只是想知道某元素是否存在，当该元素不存在时，我们并不打算进行插入运算。为此，map容器提供的两个操作可以解决这一问题。
| 操作 | 含义 |
|---|---|
m.count(k) | 返回m中k的出现次数 |
m.find(k) | 如果m容器中存在按k索引的元素，则返回指向该元素的迭代器。如果不存在，则返回指向超出末端迭代器 |
// count()
int occurs(0);
if ( wordCount.count("Anna") )
occurs = wordCount["Anna"];// find()
int occurs(0);
map<string, int>::iterator iter = wordCount.find("Anna");
if ( iter != wordCount.end() )
occurs = iter->second;
5 从map对象中删除元素
| 操作 | 含义 |
|---|---|
m.erase(k) | 删除m中键为k的元素。返回size_type类型的值，表示删除的元素的个数 |
m.erase(p) | 从m中删除迭代器p所指向的元素。p必须指向m中确实存在的元素，而且不能等于m.end()。返回void类型 |
m.erase(b, e) | 从m中删除一段范围内的元素，该范围由迭代器对b和e标记。b和e必须标记m中的一段有效范围：即b和e都要指向m中的元素或最后一个元素的下一个位置。并且，b和e要么相等（此时删除范围为空），要么b所指向的元素必须出现在e所指向的元素之前。返回void类型 |
// erase of a key returns number of elements removed
if ( wordCount.erase( removalWord ) )
cout << "ok: " << removalWord << " removed!" << endl;
else
cout << "oops: " << removalWord << " not found!" << endl;
6 对map对象的迭代遍历
// get iterator positioned on the first element
map<string, int>::const_iterator iter = wordCount.begin();// for each element in the map
while ( iter != wordCount.end() )
{
// print the element key, value pairs
cout << iter->first << " occurs " << iter->second << " times." << endl;
++ iter; // increment iterator to denote the next element
}
参考文献：
- 《C++ Primer中文版（第四版）》，Stanley B.Lippman et al. 著， 人民邮电出版社，2013。
