抛开具体的编程语言场景，map 是一类非常基本的数据组织形式，其作用是将一个可 Hash 的值，映射到另一个值，而且一般来讲是一对一的（存在一对多的情况）。map 内部使用了红黑树，这棵树具有对数据自动排序的功能，使得对 map 的检索意义达到非常高的效率。基于键值的查找的复杂度是 Log(N)。

这里讲讲 C++标准库里面 map 的用法。

1 使用 map

头文件：

1
#include <map>

声明时需要指明键与值的类型：

1
std::map<int, string> persons;

2 数据插入

数据插入有三种方法：

  1. 使用insert函数插入pair数据，例如：
1
2
3
std::map<int, string> students;

students.insert (std::pair<int, string> (1, "Student A"));
  1. 用 insert 函数插入value_type的数据，例如：
1
2
3
std::map<int, string> students;

students.insert (std::map<int, string>::value_type (1, "Student A"));
  1. 用 Subscript 方式插入数据，例如：
1
2
3
std::map<int, string> students;

students[1] = "Student A"

上面三种插入方式的区别在于，第三种默认会覆盖已经存在的映射，而前两个不会。前两个插入方式等价，在插入的键已经存在于映射中时，当前的插入语句会被忽略。那么如何知道插入是否成功呢？可以通过insert函数的返回值来判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
std::map<int, string> students;

// res为pair<map<int, string>::iterator, bool>乐行
auto res = students.insert (pair<int, string> (1, "Student A"));
if (res.second == true)
  {
    std::cout << "Insert successfully" << std::endl;
  }
else
  {
    std::cout << "Insert fail" << std::endl;
  }

3 数据的遍历

使用迭代器：

1
2
3
4
5
for (auto iter = students.begin (); iter != students.end (); iter ++ )
  {
    // first为key，second为value
    cout<<iter->first<<' '<<iter->second<<endl;  
  }

4 查找并获取 map 中的元素

查找是 map 的核心功能。我们可以使用find函数来进行查找。当找到目标时，返回一个迭代器，否则返回end。

1
2
3
4
5
6
7
8
9
10
11
12
std::map<int, string> students;
// ...

auto iter = students.find (1);
if (iter == students.end ())
  {
    std::cout << "not found " << std::endl;
  }
else
  {
    string studentName = iter.second;
  }

5 删除元素

1
2
3
4
5
6
7
8
9
std::map<int, string> students;
// ...
auto iter = students.find (1);
student.erase (iter);

student.erase (1);

// 这会清空整个map
student.erase (students.begin (), students.end ());

6 Further Reading