首页 > 代码库 > multimap 多重映照容器[转]

multimap 多重映照容器[转]

multimap 多重映照容器

    multimap 与 map 一样,都是使用红黑树对记录型的元素数据,按元素键值的比较关系,进行快速的插入、删除和检索操作,所不同的是 multimap 允许将具有重复键值的元素插入容器。在 multimap 容器中,元素的键值与元素的映照数据的映照关系,是多对多的,因此,multimap 称为多重映照容器。multimap 与 map 之间的多重特性差异,类似于 multiset 与 set 的多重特性差异。
    multimap 多重映照容器实现了 Sorted Associative Container 、Pair Associative Container 和 Multimap Associative Container 概念的接口规范。
    multimap 与 map 容器有很多地方相似,这里不再重复介绍一些概念和函数,很多内容可以参考 map 里面的介绍。这里只讲一些常用用法。看代码。

    multimap 与 map 容器共用同一个 C++ 标准头文件 map 。在用到 multimap 的时候,需要用到宏语句 "#include <map>"

 

 

 

 1 /*    不同于 map 容器,multimap 容器只能采用迭代器的方式,而不能用数组方式,遍历容器的元素。迭代器方式的元素访问,一般要用 begin 和 end 函数找出遍历开始的首元素和结束元素,然后通过迭代器的 “++” 和 “*“ 操作取出元素。
 2     下面的示例程序,将水果价格元素表的记录打印出来。由于水果价格作为元素的键值,并采用默认的 less<float> 作比较函数对象,将按价格由小到大打印出来。
 3 */
 4 
 5 -------------------------------------------------------- 遍历 multimap 容器元素
 6 #pragma warning(disable:4786)
 7 #include <map>
 8 #include <iostream>
 9 using namespace std;
10 int main()
11 {
12     multimap<float, char*> mm;
13     mm.insert(pair<float, char*>(3.0f, "apple"));
14     mm.insert(pair<float, char*>(3.0f, "pear"));
15     mm.insert(pair<float, char*>(2.6f, "orange"));
16     mm.insert(pair<float, char*>(1.8f, "banana"));
17     mm.insert(pair<float, char*>(6.3f, "lichee"));
18     // 遍历打印
19     multimap<float, char*>::iterator  i, iend;
20     iend = mm.end();
21     for (i=mm.begin(); i!=iend; ++i)
22         cout << (*i).second <<      << (*i).first << "元/斤 \n";
23 
24     return 0;
25 }

 

 

 

 

 

/*    利用 multimap 容器定义的反向迭代器 reverse_iterator 和 const_reverse_iterator ,及获取反向首尾元素的 rbegin 和 rend 函数,可反向遍历 multimap 容器的元素。
    例如下面使用反向遍历,将水果价格表的记录按价格大小,由大到小打印出来。
    注意:键值相同的 pear 将先于 apple 打印出来。可见,在等键值的反向遍历情形下,后插入的元素先打印出来。
*/

-------------------------------------------------------- 反向遍历 multimap 容器的元素
#pragma warning(disable:4786)
#include <map>
#include <iostream>
using namespace std;
int main()
{
    multimap<float, char*> mm;
    mm.insert(pair<float, char*>(3.0f, "apple"));
    mm.insert(pair<float, char*>(3.0f, "pear"));
    mm.insert(pair<float, char*>(2.6f, "orange"));
    mm.insert(pair<float, char*>(1.8f, "banana"));
    mm.insert(pair<float, char*>(6.3f, "lichee"));
    // 反向遍历打印
    multimap<float, char*>::reverse_iterator  r_i, r_iend;
    r_iend = mm.rend();
    for (r_i=mm.rbegin(); r_i!=r_iend; ++r_i)
        cout << (*r_i).second <<      << (*r_i).first << "元/斤 \n";

    return 0;
}

 

 

 

 

 

 

 

 

 

 1 /*    由于键值允许重复插入,在 multimap 容器中具有同一个键值的元素有可能不只一个。因此,multimap 容器的 find 函数将返回第一个搜索到的元素位置,如果元素不存在,则返回 end 结束元素位置。equal_range 函数则返回一个可指示相等元素范围区间的 pair 对象。
 2 */
 3 
 4 -------------------------------------------------------- multimap 容器的元素的搜索1
 5 #pragma warning(disable:4786)
 6 #include <map>
 7 #include <iostream>
 8 using namespace std;
 9 
10 // 课程记录结构体
11 struct CourseRecord
12 {
13     // 课程信息结构体
14     struct CourseInfo
15     {
16         char* course;  // 课程名
17         int  period;   // 学时
18         char* required; // 必修或选修
19     };
20 
21     char* teacher;  // 任课教师
22     CourseInfo  cf;
23     CourseRecord(char* teacher_, char* course_, int period_, char* required_)
24     {
25         teacher = teacher_;
26         cf.course = course_;
27         cf.period = period_;
28         cf.required = required_;
29     }
30 };
31 
32 int main()
33 {
34     // 创建 multimap 容器对象 mm
35     typedef multimap<char*, CourseRecord::CourseInfo>  coursemmap;
36     coursemmap  mm;
37     // 插入第1条记录
38     CourseRecord  course1 = CourseRecord("张三","操作系统开发",60,"必修");
39     pair<char*, CourseRecord::CourseInfo>  pairCourse1(course1.teacher, course1.cf);
40     mm.insert(pairCourse1);
41 
42     // 插入第2条记录
43     CourseRecord  course2 = CourseRecord("李四","编译器开发",30,"必修");
44     pair<char*, CourseRecord::CourseInfo>  pairCourse2(course2.teacher, course2.cf);
45     mm.insert(pairCourse2);
46 
47 
48     // 插入第3条记录
49     CourseRecord  course3 = CourseRecord("李四","数据结构",20,"必修");
50     pair<char*, CourseRecord::CourseInfo>  pairCourse3(course3.teacher, course3.cf);
51     mm.insert(pairCourse3);
52 
53 
54     // 插入第4条记录
55     CourseRecord  course4 = CourseRecord("李四","Java 开发应用",38,"必修");
56     pair<char*, CourseRecord::CourseInfo>  pairCourse4(course4.teacher, course4.cf);
57     mm.insert(pairCourse4);
58 
59     // 插入第5条记录
60     CourseRecord  course5 = CourseRecord("王五","C++程序设计",58,"必修");
61     pair<char*, CourseRecord::CourseInfo>  pairCourse5(course5.teacher, course5.cf);
62     mm.insert(pairCourse5);
63 
64     // 记录搜索
65     cout << "搜索<李四老师>的任课记录:\n";
66     pair<coursemmap::iterator, coursemmap::iterator>  p = mm.equal_range("李四");
67     // 打印结果
68     coursemmap::iterator  i;
69     for (i=p.first; i!=p.second; ++i)
70         cout << (*i).first <<     
71              << (*i).second.course <<     
72              << (*i).second.period << "学时    "
73              << (*i).second.required <<     
74              << endl;
75     cout << endl << endl;
76 
77     return 0;
78 }

 

 

 

 

 

 

 

 1 -------------------------------------------------------- multimap 容器的元素的搜索2
 2 #pragma warning(disable:4786)
 3 #include <iostream>
 4 #include <string>
 5 #include <UTILITY>
 6 #include <map>
 7 using namespace std;
 8 
 9 struct userdevice
10 {
11     string m_devicename;
12     long m_deviced;
13     int m_devicePopedom;
14 };
15 
16 typedef multimap<string, userdevice> USERTABLE;        
17 typedef USERTABLE::const_iterator CIT;
18 typedef pair<CIT, CIT> Range;
19 
20 int main()
21 {    
22     // 定义一个迭代器
23     CIT it;
24     // 定义4个设备
25     userdevice d1, d2, d3, d4;
26     d1.m_deviced = 12341234;
27     d1.m_devicename = "d1";
28     d1.m_devicePopedom = 123;
29     
30     d2.m_deviced = 23622344;
31     d2.m_devicename = "d2";
32     d2.m_devicePopedom = 234;
33     
34     d3.m_deviced = 3451234;
35     d3.m_devicename = "d3";
36     d3.m_devicePopedom = 345;
37     
38     d4.m_deviced = 43622344;
39     d4.m_devicename = "d4";
40     d4.m_devicePopedom = 456;
41     
42     USERTABLE m_user;
43     m_user.insert(pair<string, userdevice>("zhangsanfeng",d1));
44     m_user.insert(pair<string, userdevice>("zhangsanfeng",d2));
45 
46     m_user.insert(pair<string, userdevice>("zhangsanfeng2",d3));
47     m_user.insert(pair<string, userdevice>("zhangsanfeng2",d4));
48     
49     // 查找方法一(查找key值是"zhangsanfeng")
50     Range range = m_user.equal_range("zhangsanfeng");
51     for (CIT i = range.first; i!=range.second; ++i)
52     {
53         cout<< i->second.m_deviced <<,
54             << i->second.m_devicename.c_str()<<,
55             << i->second.m_devicePopedom
56             << endl;
57     }
58     cout<< endl;
59     
60 
61 
62     // 查找方法二(查找"zhangsanfeng2")
63     CIT it2 = m_user.find("zhangsanfeng2");
64     while(it2!=m_user.end())
65     {        
66         cout<< it2->second.m_deviced <<,
67             << it2->second.m_devicename.c_str()<<,
68             << it2->second.m_devicePopedom
69             << endl;
70         ++it2;
71     }
72     cout<< endl;
73     
74 
75     // 遍历
76     CIT it3 = m_user.begin();
77     while (it3!=m_user.end())
78     {
79         cout<< i->second.m_deviced <<,
80             << it3->second.m_devicename.c_str()<<,
81             << it3->second.m_devicePopedom
82             << endl;
83         
84         ++it3;
85     }
86     cout<< endl;
87 
88     return 0;
89 }

 

 

 

 

 

 

 

 1 /*    下面的示例程序调用 multimap 容器的 size 和 count 函数,对元素个数和去某键值的元素个数进行统计
 2 */
 3 
 4 -------------------------------------------------------- multimap 容器元素的设计
 5 #pragma warning(disable:4786)
 6 #include <map>
 7 #include <iostream>
 8 using namespace std;
 9 
10 
11 int main()
12 {
13     multimap<int, char> mm;
14     // 打印元素个数:0
15     cout << mm.size() << endl;  
16     mm.insert(pair<int, char>(3, a));
17     mm.insert(pair<int, char>(3, c));
18     mm.insert(pair<int, char>(4, d));
19     mm.insert(pair<int, char>(5, e));
20     // 打印键值为 3 的元素个数
21     cout << mm.count(3) << endl;
22     // 打印元素个数
23     cout << mm.size() << endl;
24 
25     return 0;
26 }

 

 

 

 

 

 

 

 

 

 

 

 

 

 
---------------------- multimap 小结
    multimap 多重映照容器也是一种依元素键值进行插入、删除和检索的有序关联容器,元素的检索具有对数阶的算法时间复杂度。与 map 容器的区别是,multimap 允许元素键值出现重复,这导致 multimap 多重映照容器不能像 map 容器那样,可简便地利用数组方式访问或添加容器元素。
    
    multimap 缺点:和 map 的缺点差不多。multimap 是比较复杂的用法,如果能用 vector 、list 这些容器完成的事情,就不需要用到 multimap .
    multimap 优点:相比 map ,multimap 能允许重复键值的元素插入。