map说明

Map是STL的一个关联容器，它提供一对一的数据处理能力，map内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的.搜索效率是O(lgN). C++中的map类似python中的dict, 只不过python中的dict使用散列表实现的, 用时(N).
它的特点是增加和删除节点对迭代器的影响很小，除了那个操作节点，对其他的节点都没有什么影响。对于迭代器来说，可以修改实值，而不能修改key。
C++ STL中的标准规定：

  • map 有序, 用红黑树实现
  • unordered_map，无序，用散列表实现

关于has_map

hash_map 其实就是使用 hash 表来实现的 map。
注意，二叉树，哈希表仅仅是 dictionary 的实现方式，不能说 hash 就等于 dictionary，实现方式可以有多种多样。

map的功能

  • 自动建立Key － value的对应。key 和 value可以是任意你需要的类型
  • 根据key值快速查找记录，查找的复杂度基本是Log(N)，如果有1000个记录，最多查找10次，1,000,000个记录，最多查找20次
  • 快速插入Key - Value 记录
  • 快速删除记录
  • 根据Key 修改value记录
  • 遍历所有记录

map使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <map> 
#include <string> 
#include <iostream> 
using namespace std;
int main()
{
     //定义map对象，当前没有任何元素
     map<string,float> m;
     
     //插入元素，按键值的由小到大放入黑白树中
     m["Jack"] = 98.5 ;
     m["Bomi"] = 96.0 ;
     m["Kate"] = 97.5 ;
     
     //删除键值为"Jack"的元素
     m.erase("Jack") ;
     //先前遍历元素
     map<string,float> :: iterator it ;
     for(it = m.begin(); it != m.end(); it ++)
     {
          cout << (*it).first << " : " << (*it).second << endl ;
     }
     //反向遍历元素
     map<int, char> :: reverse_iterator rit ;
     for( rit = m.rbegin() ; rit != m.rend() ; rit ++)
     {
         //输入键值与映照数据
         cout << (*rit).first << " : " << (*rit).second << endl ;
     }
     // 元素搜索
     map<int, char> :: iterator it ;
     it = m.find("Bomi") ;
     if(it != m.end())  //搜索到该键值
         cout << (*it).first << " : " << ( *it ).second << endl ;
     else
         cout << "not found it" << endl ;
     return 0 ;
}

参考