STL学习笔记 map
STL学习笔记-- map
map映照容器
map映照容器所处理的元素数据，与数据库表的具有键值的记录非常相似，由一个键值和其他若干数据（映照数组）组成，键值和映照数据之间，可建立一个数学上的映照关系，由此而得映照容器的名称。容器的数据结构同样是采用红黑树进行管理，插入的元素键值不允许重复，所使用的节点元素的比较函数，只对元素的键值进行比较，元素的各项数据可通过键值检索出来。
map 映照容器是一种关联容器，实现了 Sorted Associative Container 、Sorted Associative Container 、 Unique Associative Container 概念的接口规范
map 容易的 C++ 标准头文件为 map ，先要用宏语句 "#include <map>" ，将红黑树和 map 的头文件包含进来，才可对使用 map 的程序进行编译
创建 map 对象
为了操作 map 的数据，先要用 map 的构造函数，创建一个 map 对象。
1. map()
利用默认的 less<T> 函数对象和内存分配器，创建一个没有任何数元素的 map 对象。
例如，下面的代码创建了一个空的 map 对象 m ，元素的键值类型为 char ，元素的映照数据类型为 int ，键值的比较函数对象为 greater<char>
map<char, int, greater<char> > m; // 两个 ">" 、">" 符号不要写在一起了，记得要空格
2. map(const key_compare& comp)
指定一个比较函数对象 comp 来创建 map 对象，内存分配器为默认值。
map<T1,T2,less<T1> > mapA; //该容器是按键的升序方式排列元素。未指定函数对象，默认采用less<T1>函数对象。
map<T1,T2,greater<T1>> mapB; //该容器是按键的降序方式排列元素。
less<T1>与greater<T1> 可以替换成其它的函数对象functor。
可编写自定义函数对象以进行自定义类型的比较，使用方法与set构造时所用的函数对象一样。
例如，下面的代码使用自定义的函数对象 strLess ，创建一个 map 容器对象 m 。该容器的键值类型为 const char* ，映照容器数据类型为 int 。
// 定义字符串比较函数对象 strLess
struct strLess
{
bool operator() (const char* s1, const char* s2) const
{
return strcmp(s1, s2) < 0 ;
}
};
// 创建 map 容器对象 m
map<const char*, int > m(strLess());
3. map(const map&)
拷贝构造函数，用一个 map 容器的元素和比较函数，拷贝生成一个新的 map 容器对象。
例如，下面代码利用 map 容器对象 m1 ，创建另一个容器对象 m2 .
// map <int , char*> m1;
map<int, char*> m2(m1); // 使用默认的键值比较函数 less<int>
4. map(InputIterator first, InputIterator last)
用迭代器区间 [first, last) 所指的数据，作为 map 容器的元素（包括键值和映照数据），创建一个 map 容器对象。
例如，下面代码使用数组 pairArray 的 5 个 pair 对象，创建 map 容器对象 m 。
pair<const int, char> p1(1, 'a');
pair<const int, char> p1(2, 'b');
pair<const int, char> p1(3, 'c');
pair<const int, char> p1(4, 'd');
pair<const int, char> p1(5, 'e');
pair<const int, char> pairArray[] = {p1, p2, p3, p4, p5};
// 创建 map 容器对象 m
map<const int, char> m(pairArray, pairArray + 5);
5. map(InputIterator first, InputIterator last, const key_compare& comp)
用迭代器区间 [first, last)所指的数据和 comp 函数对象，创建一个 map 对象。
例如，下面代码使用 greater<int> 函数对象，取代默认的 less<int> ，创建一个 map 对象 m 。
map<const int, char, greater<const int> > m(pairArray, pairArray+5, greater<const int>());
元素的插入
map 容器对象创建出来后，下一步就是元素数据（包括键值和映照数据）的二叉树装入。
除可使用如下的 insert 函数，将整个元素数据进行性插入外，常用 map 容器的数组操作 "[]" ，显示地为不同键值赋予内容（映照数据），不过这个数组方法，不能检测是否插入 成功。
假设 map<int, string> mapStu;
1. 通过pair的方式插入对象 //往容器插入元素，返回pair<iterator,bool>
pair<iteraotr, bool> insert(const value_type& v)
将元素 v（包括键值和映照数据）插入 map 容器，重复的 V 值不被插入。返回一个 pair 配对对象。提供所插入元素的迭代器位置和 true/false 插入成功标志
例如，下面代码是 pair 方式的插入
mapStu.insert( pair<int,string>(3,"小张") );
2. 通过value_type的方式插入对象
mapStu.insert( map<int,string>::value_type(1,"小李") );
3. 通过数组的方式插入值
mapStu[3] = “小刘";
mapStu[5] = “小王"；
......
第三种方法非常直观，但存在一个性能的问题。插入3时，先在mapStu中查找主键为3的项，若没发现，则将一个键为3，值为初始化值的对组插入到mapStu中，然后再将值修改成“小刘”。若发现已存在3这个键，则修改这个键对应的value。
string strName = mapStu[2]; //取操作或插入操作
只有当mapStu存在2这个键时才是正确的取操作，【否则会自动插入一个实例，键为2，值为初始化值】。
前两种方法，采用的是insert()方法，该方法返回值为pair<iterator,bool>
pair< map<int,string>::iterator, bool> pairResult = mapStu.insert( pair<int,string>(3,"小张") );
如果插入成功，(pairResult.first)->first==3, (pairResult.first)->second=="小张" pairResult.second==true。
map 容器的元素插入
1 #pragma warning(disable:4786)
2 #include <map>
3 #include <iostream>
4 using namespace std;
5 int main()
6 {
7 // 创建 map 容器对象 m
8 map< const char *, float > m;
9 // 插入元素（水果名，单价），水果名位键值，单价为映照数据
10 m[ " apple " ] = 3.6f ;
11 m[ " orange " ] = 3.2f ;
12 m[ " banana " ] = 1.8f ;
13 m[ " pear " ] = 2.3f ;
14 m[ " lichee " ] = 6.3f ;
15 m.insert(pair< const char *, float >( " 何亮 " , 100.001f ) );
16 // 打印元素
17 cout << " 苹果价格： " << m[ " apple " ] << " 元/斤 \n " ;
18 cout << " 桔子价格： " << m[ " orange " ] << " 元/斤 \n " ;
19 cout << " 香蕉价格： " << m[ " banana " ] << " 元/斤 \n " ;
20 cout << " 雪梨价格： " << m[ " pear " ] << " 元/斤 \n " ;
21 cout << " 荔枝价格： " << m[ " lichee " ] << " 元/斤 \n " ;
22 cout << " pair插入 " << m[ " 何亮 " ] << " 元/斤\n " ;
23
24 return 0 ;
25 }
1 #pragma warning(disable:4786)
2 #include <map>
3 #include <iostream>
4 using namespace std;
5 int main()
6 {
7 // 创建 map 容器对象 m
8 map< const char *, float > m;
9 // 插入元素（水果名，单价），水果名位键值，单价为映照数据
10 m[ " apple " ] = 3.6f ;
11 m[ " orange " ] = 3.2f ;
12 m[ " banana " ] = 1.8f ;
13 m[ " pear " ] = 2.3f ;
14 m[ " lichee " ] = 6.3f ;
15 m.insert(pair< const char *, float >( " 何亮 " , 100.001f ) );
16 // 打印元素
17 cout << " 苹果价格： " << m[ " apple " ] << " 元/斤 \n " ;
18 cout << " 桔子价格： " << m[ " orange " ] << " 元/斤 \n " ;
19 cout << " 香蕉价格： " << m[ " banana " ] << " 元/斤 \n " ;
20 cout << " 雪梨价格： " << m[ " pear " ] << " 元/斤 \n " ;
21 cout << " 荔枝价格： " << m[ " lichee " ] << " 元/斤 \n " ;
22 cout << " pair插入 " << m[ " 何亮 " ] << " 元/斤\n " ;
23
24 return 0 ;
25 }
元素的删除
与 set 集合容器一样，map 映照容器的删除函数，可删除某个迭代器位置上的元素、等于某键值的元素、一个迭代器区间上的元素和容器中的所有元素。
1 . void erase(iterator position) 删除 position 所指的元素
2 . size_type erase( const key_type& k) 删除键值为 K 的元素。对 map 容器来说，此函数总是返回值 1 ，因为 map 容器不会出现键值重复的元素值。
3 . void erase(iterator first, iterator last) 删除 map 迭代器区间 [first, last) 上的所有元素
4 . void clear() 删除 map 容器的所有元素
例如，下面的代码将上一例子 map 对象 m 中， " lichee, 6.3 " 的元素数据删除
m.erase( " lichee " );
遍历 map 容器元素
1
2 /* 除了利用键值的数组方式来访问元素外，更一般可使用 map 容器的迭代器进行访问，通常需要用 begin 和 end 函数找出遍历开始的首元素和结束元素，然后通过迭代器的“++” 和“*” 操作，读取容器元素。
3
4 下面的示例程序，将一批学生记录（学号为键值）插入到 map 容器对象 m 中，然后，利用前向迭代器打印出来。由于 map 容器的元素是通过转换为 pair 对象插入到容器的，因此，学生记录结构体中各个变量域，需要通过 pair 对象的 first 和 second 变量 指出来。（关于 pair ，可参考之前的讨论 set 容器的文章）
5 */
6
7 -------------------------------------------------------- 遍历 map 容器元素
8 #pragma warning(disable:4786)
9 #include <map>
10 #include <iostream>
11 using namespace std;
12
13 // 学生信息结构体
14 struct StudentInfo
15 {
16 char * name;
17 int year;
18 char * addr;
19 };
20
21 // 学生记录结构体
22 struct StudentRecord
23 {
24 int id; // 学号，作键值
25 StudentInfo sf; // 学生信息，作映照数据
26 };
27
28 int main()
29 {
30 // 3个学生的记录
31 StudentRecord srArray[] = {
32 { 1 , " 何亮 " , 21 , " 武汉 " },
33 { 2 , " 何小亮 " , 20 , " 上海 " },
34 { 3 , " 何大亮 " , 22 , " 北京 " }
35 };
36 // 创建 map 容器对象 m ，管理学生记录
37 map< int , StudentInfo> m;
38 // 装入 3 笔学生记录
39 for ( int j= 0 ; j< 3 ; j++ )
40 m[srArray[j].id] = srArray[j].sf;
41 // 迭代器遍历元素
42 map< int , StudentInfo> ::iterator i, iend;
43 iend = m.end();
44 cout << " 学号 " << " 姓名 " << " 年龄 " << " 地址 " << endl;
45 for (i=m.begin(); i!=iend; ++ i)
46 cout << (*i).first << ' ' << (*i).second.name << ' ' << (*i).second.year << ' ' << (*i).second.addr << endl;
47 cout << endl;
48
49 return 0 ;
50 }
1
2 /* 除了利用键值的数组方式来访问元素外，更一般可使用 map 容器的迭代器进行访问，通常需要用 begin 和 end 函数找出遍历开始的首元素和结束元素，然后通过迭代器的“++” 和“*” 操作，读取容器元素。
3
4 下面的示例程序，将一批学生记录（学号为键值）插入到 map 容器对象 m 中，然后，利用前向迭代器打印出来。由于 map 容器的元素是通过转换为 pair 对象插入到容器的，因此，学生记录结构体中各个变量域，需要通过 pair 对象的 first 和 second 变量 指出来。（关于 pair ，可参考之前的讨论 set 容器的文章）
5 */
6
7 -------------------------------------------------------- 遍历 map 容器元素
8 #pragma warning(disable:4786)
9 #include <map>
10 #include <iostream>
11 using namespace std;
12
13 // 学生信息结构体
14 struct StudentInfo
15 {
16 char * name;
17 int year;
18 char * addr;
19 };
20
21 // 学生记录结构体
22 struct StudentRecord
23 {
24 int id; // 学号，作键值
25 StudentInfo sf; // 学生信息，作映照数据
26 };
27
28 int main()
29 {
30 // 3个学生的记录
31 StudentRecord srArray[] = {
32 { 1 , " 何亮 " , 21 , " 武汉 " },
33 { 2 , " 何小亮 " , 20 , " 上海 " },
34 { 3 , " 何大亮 " , 22 , " 北京 " }
35 };
36 // 创建 map 容器对象 m ，管理学生记录
37 map< int , StudentInfo> m;
38 // 装入 3 笔学生记录
39 for ( int j= 0 ; j< 3 ; j++ )
40 m[srArray[j].id] = srArray[j].sf;
41 // 迭代器遍历元素
42 map< int , StudentInfo> ::iterator i, iend;
43 iend = m.end();
44 cout << " 学号 " << " 姓名 " << " 年龄 " << " 地址 " << endl;
45 for (i=m.begin(); i!=iend; ++ i)
46 cout << (*i).first << ' ' << (*i).second.name << ' ' << (*i).second.year << ' ' << (*i).second.addr << endl;
47 cout << endl;
48
49 return 0 ;
50 }
map 容器元素的搜索
1 /* 利用 map 容器提供的 find 函数，可搜索出具有某一键值的元素。map 容器的元素键值是唯一的。find 函数返回的迭代器值为搜索到的元素位置，如果该元素不存在，则返回一个 end 结束元素位置。
2
3 下面的示例程序重写了 StudentRecord 结构体，以适于使用返回 pair 对象的 insert 函数将学生记录插入到 map 容器。 返回的 pair 对象的第二变量 second 中，判断是否插入成功（键值重复插入将失败）。然后，调用 find 函数，对学号为 2 的键值进行搜索，并将该学生的记录打印出来。
4 */
5 -------------------------------------------------------- map 容器元素的搜索
6 #pragma warning(disable:4786)
7 #include <map>
8 #include <iostream>
9 using namespace std;
10 // 学生记录结构体
11 struct StudentRecord
12 {
13 struct StudentInfo
14 {
15 char * name;
16 int year;
17 char * addr;
18 };
19 StudentRecord( int id_, char * name_, int year_, char * addr_)
20 {
21 id = id_;
22 sf.name = name_;
23 sf.year = year_;
24 sf.addr = addr_;
25 }
26 int id; // 学号，作键值
27 StudentInfo sf; // 其他信息
28 };
29
30 int main()
31 {
32 // 创建 map 容器对象 m
33 typedef map< int , StudentRecord::StudentInfo> studentmap;
34 studentmap m;
35 pair<studentmap::iterator, bool > p;
36
37 // 插入第一条学生记录
38 StudentRecord student1 = StudentRecord( 1 , " 何亮1号 " , 21 , " 武汉 " );
39 pair< int , StudentRecord::StudentInfo> pairStudent1(student1.id, student1.sf);
40 p = m.insert(pairStudent1);
41 if (! p.second)
42 cout << " 插入学生记录失败:\n "
43 << student1.id << ' '
44 << student1.sf.name << ' '
45 << student1.sf.year << ' '
46 << student1.sf.addr << ' '
47 << endl << endl;
48
49 // 插入第二条学生记录
50 StudentRecord student2 = StudentRecord( 2 , " 何亮2号 " , 22 , " 北京 " );
51 pair< int , StudentRecord::StudentInfo> pairStudent2(student2.id, student2.sf);
52 p = m.insert(pairStudent2);
53 if (! p.second)
54 cout << " 插入学生记录失败:\n "
55 << student2.id << ' '
56 << student2.sf.name << ' '
57 << student2.sf.year << ' '
58 << student2.sf.addr << ' '
59 << endl << endl;
60
61 // 插入第三条学生记录
62 StudentRecord student3 = StudentRecord( 3 , " 何亮3号 " , 23 , " 上海 " );
63 pair< int , StudentRecord::StudentInfo> pairStudent3(student3.id, student3.sf);
64 p = m.insert(pairStudent3);
65 if (! p.second)
66 cout << " 插入学生记录失败:\n "
67 << student3.id << ' '
68 << student3.sf.name << ' '
69 << student3.sf.year << ' '
70 << student3.sf.addr << ' '
71 << endl << endl;
72
73 // 插入键值重复的学生记录， 插入失败
74 StudentRecord student4 = StudentRecord( 3 , " 何亮4号 " , 24 , " 广州 " );
75 pair< int , StudentRecord::StudentInfo> pairStudent4(student4.id, student4.sf);
76 p = m.insert(pairStudent4);
77 if (! p.second)
78 cout << " 插入学生记录失败:\n "
79 << student4.id << ' '
80 << student4.sf.name << ' '
81 << student4.sf.year << ' '
82 << student4.sf.addr << ' '
83 << endl << endl;
84
85 // 记录搜索
86 studentmap::iterator i = m.find( 2 );
87 cout << " 搜索出学号为2的记录：\n "
88 << (*i).first << ' '
89 << (*i).second.name << ' '
90 << (*i).second.year << ' '
91 << (*i).second.addr << ' '
92 << endl << endl;
93
94 // 统计 map 容器 m 所有学生的个数
95 if (m.empty())
96 cout << " map 容器为空 " << endl;
97 else
98 cout << " map 容器元素个数为： " << m.size() << endl << endl;
99
100 return 0 ;
101 }
1 /* 利用 map 容器提供的 find 函数，可搜索出具有某一键值的元素。map 容器的元素键值是唯一的。find 函数返回的迭代器值为搜索到的元素位置，如果该元素不存在，则返回一个 end 结束元素位置。
2
3 下面的示例程序重写了 StudentRecord 结构体，以适于使用返回 pair 对象的 insert 函数将学生记录插入到 map 容器。 返回的 pair 对象的第二变量 second 中，判断是否插入成功（键值重复插入将失败）。然后，调用 find 函数，对学号为 2 的键值进行搜索，并将该学生的记录打印出来。
4 */
5 -------------------------------------------------------- map 容器元素的搜索
6 #pragma warning(disable:4786)
7 #include <map>
8 #include <iostream>
9 using namespace std;
10 // 学生记录结构体
11 struct StudentRecord
12 {
13 struct StudentInfo
14 {
15 char * name;
16 int year;
17 char * addr;
18 };
19 StudentRecord( int id_, char * name_, int year_, char * addr_)
20 {
21 id = id_;
22 sf.name = name_;
23 sf.year = year_;
24 sf.addr = addr_;
25 }
26 int id; // 学号，作键值
27 StudentInfo sf; // 其他信息
28 };
29
30 int main()
31 {
32 // 创建 map 容器对象 m
33 typedef map< int , StudentRecord::StudentInfo> studentmap;
34 studentmap m;
35 pair<studentmap::iterator, bool > p;
36
37 // 插入第一条学生记录
38 StudentRecord student1 = StudentRecord( 1 , " 何亮1号 " , 21 , " 武汉 " );
39 pair< int , StudentRecord::StudentInfo> pairStudent1(student1.id, student1.sf);
40 p = m.insert(pairStudent1);
41 if (! p.second)
42 cout << " 插入学生记录失败:\n "
43 << student1.id << ' '
44 << student1.sf.name << ' '
45 << student1.sf.year << ' '
46 << student1.sf.addr << ' '
47 << endl << endl;
48
49 // 插入第二条学生记录
50 StudentRecord student2 = StudentRecord( 2 , " 何亮2号 " , 22 , " 北京 " );
51 pair< int , StudentRecord::StudentInfo> pairStudent2(student2.id, student2.sf);
52 p = m.insert(pairStudent2);
53 if (! p.second)
54 cout << " 插入学生记录失败:\n "
55 << student2.id << ' '
56 << student2.sf.name << ' '
57 << student2.sf.year << ' '
58 << student2.sf.addr << ' '
59 << endl << endl;
60
61 // 插入第三条学生记录
62 StudentRecord student3 = StudentRecord( 3 , " 何亮3号 " , 23 , " 上海 " );
63 pair< int , StudentRecord::StudentInfo> pairStudent3(student3.id, student3.sf);
64 p = m.insert(pairStudent3);
65 if (! p.second)
66 cout << " 插入学生记录失败:\n "
67 << student3.id << ' '
68 << student3.sf.name << ' '
69 << student3.sf.year << ' '
70 << student3.sf.addr << ' '
71 << endl << endl;
72
73 // 插入键值重复的学生记录， 插入失败
74 StudentRecord student4 = StudentRecord( 3 , " 何亮4号 " , 24 , " 广州 " );
75 pair< int , StudentRecord::StudentInfo> pairStudent4(student4.id, student4.sf);
76 p = m.insert(pairStudent4);
77 if (! p.second)
78 cout << " 插入学生记录失败:\n "
79 << student4.id << ' '
80 << student4.sf.name << ' '
81 << student4.sf.year << ' '
82 << student4.sf.addr << ' '
83 << endl << endl;
84
85 // 记录搜索
86 studentmap::iterator i = m.find( 2 );
87 cout << " 搜索出学号为2的记录：\n "
88 << (*i).first << ' '
89 << (*i).second.name << ' '
90 << (*i).second.year << ' '
91 << (*i).second.addr << ' '
92 << endl << endl;
93
94 // 统计 map 容器 m 所有学生的个数
95 if (m.empty())
96 cout << " map 容器为空 " << endl;
97 else
98 cout << " map 容器元素个数为： " << m.size() << endl << endl;
99
100 return 0 ;
101 }
------------------------------- map 小结
直观来说，map 容器区别于 set 容器的一个主要特性在于，map 是处理带有键值的记录型元素数据的快速插入、删除 和检索，而 set 则可看成是对单一数据的处理。map 将一个元素划分出键值部分，并按这个局部的键值指定整个元素的函数比较规则，来建立容器的数据分布。map 的元素键值是唯一的，不允许重复的元素键值插入。 set 和 map 都是泛型库对二叉树的一个泛化。
map 缺点：map是比较高级的用法了，适合用 list , vector 就能完成的操作，就不需要用到 map 。
map 优点：相比 set ，map 可处理带有键值的记录型数据的快速插入、删除和检索。检索的速度也是非常快的。
------------- 讨论到 map 这里的时候，应该说，有些地方理解起来，就有些难度了。可以网上搜一些相关的代码看看，理顺逻辑，弄清结构，孰能生巧。
【好好学习，天天向上】 ||||||| 【 亮仔 到此一游 】
分类: STL学习笔记
标签: STL , C++ , 容器 , map
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息