map 平衡二叉树关系（联）式容器（已序）
字典 map<拼音，汉字>
map是一个容器，里面每一个元素分为两个逻辑块 其中一个逻辑区块叫做key(药匙) 另一个逻辑区块叫做value（值）
map是一个已序容器 元素进入容器会有一个排序的操作，通过key的大小进行排序，默认升序
map的元素中的key及value两者都必须是可以赋值和拷贝
key是必须可以被比较的 如果key是一个自定义类型，重载运算符（根据key值查找元素赫努埃，根据value查找运算符很慢）
最快的查找方式 ：二分查找（折半查找）
使用计算机解决实际问你 分析问题涉及的数据 合理组织数据 规划解决问题的算法的过程
算法：解决问题的流程
时间复杂度：运行时间
空间复杂度：指令空间、数据空间、环境栈空间
set理解为key和value是同一个数值的map
multimap允许出现多个重复的key值
map中key是唯一的 如果出现了多个key 后面的value覆盖前面的value
m.erase(5) 删除key为5的元素 这个key和对应的value都会被删除
三种插入方式：
m.insert(pair<int,string>(4,"1234"));//通过pair进行插入
m.insert(map<int,string>::value_type(5,"1234")); //通过map内部定义的一个结构进行插入
m.insert(make_pair(3,"1234"));//通过std里面的一个函数进行插入
1 // map.cpp : 定义控制台应用程序的入口点。 2 // 3 4 #include "stdafx.h" 5 #include<vector> 6 #include <string> 7 #include <map> 8 #include <set> 9 #include <xfunctional> 10 using namespace std; 11 12 class Cstu{ 13 char*name; 14 char age; 15 float height; 16 }; 17 18 int _tmain(int argc, _TCHAR* argv[]) 19 { 20 //set<int> s1;//set的key和value是同一数值的map 21 //s1.insert(1); 22 //s1.insert(2); 23 //multimap<int,double> m; 24 ////m[1] = 1.1;不可以这样添加 25 ////multimap的插入元素的方式 26 //m.insert(std::make_pair(1, 1.10)); 27 //m.insert(std::make_pair(1, 1.11)); 28 //m.insert(std::make_pair(1, 1.12)); 29 //m.insert(std::make_pair(2, 1.10)); 30 ////添加迭代器 31 //multimap<int,double>::iterator mit; 32 //mit = m.find(1); 33 //mit++; 34 //mit = m.lower_bound(1);//返回key为1的第一个可插入位置 35 //mit = m.lower_bound(1);//返回key为1的最后一个可插入位置 36 //printf("key=%d,value=%f\n", mit->first, mit->second); 37 //for (mit = m.begin(); mit != m.end(); ++mit) 38 //{ 39 // printf("key = %d,value = %f\n", mit->first, mit->second); 40 //} 41 //map<double, string, std::greater<double>> m1;//降序 42 //m1[1.1] = "zhang san"; 43 //m1[0.44] = "li si"; 44 //m1[3.21] = "wang wu"; 45 //m1[1.1] = "abc"; 46 47 //map<double, string, std::greater<double>>::iterator mit1; 48 49 //for (mit1 = m1.begin(); mit1 != m1.end(); ++mit1) 50 //{ 51 // printf("key = %f,value = %s\n", mit1->first, mit1->second.c_str());//c_str保证输出类型为字符串 52 //} 53 //vector<int> v; 54 //v[1]; 55 //Cstu s; 56 map<string, Cstu> m4; 57 map<int, Cstu> m3; 58 map<int, string> m2; 59 m2[17] = "zhang san"; 60 m2[2] = "li si"; 61 m2[5] = "wang wu"; 62 m2[2] = "abc"; 63 m2.erase(5); 64 m2.insert(pair<int, string>(4, "1234"));//通过pair进行插入 65 66 m2.insert(map<int, string>::value_type(5, "1234")); //通过map内部定义的一个结构进行插入 67 68 m2.insert(make_pair(3, "1234"));//通过std里面的一个函数进行插入 69 map<int, string>::iterator mit2; 70 mit2 = m2.find(17); 71 printf("key = %d,value = %s\n", mit2->first, mit2->second.c_str()); 72 printf("//================\n"); 73 74 for (mit2 = m2.begin(); mit2 != m2.end(); ++mit2) 75 { 76 printf("key = %d,value = %s\n", mit2->first, mit2->second.c_str()); 77 } 78 79 map<int, double> m; 80 m[1] = 3.14;//m表示一个容器，在这个容器里面有一个元素，这个元素的key为1，值映射为3.14 81 m[5] = 1.11; 82 m[2] = 4.54; 83 m[10] = 5.43; 84 map<int, double>::iterator mit; 85 for (mit = m.begin(); mit != m.end(); ++mit) 86 { 87 printf("key = %d,value = %f\n", mit->first,(*mit).second); 88 } 89 return 0; 90 }
原文：https://www.cnblogs.com/liugangjiayou/p/11438359.html