《Map和Multimaps》word版.doc

maps 和 multimap1 简介map 和 multimap 将key（键值，或理解为排序关键字）/value（值）作为元素，成对存储，它们可根据key的排序准则自动将元素排序。multimap允许重复键值，maps不允许。如下图：使用map和multimap需要使用头文件，在使用这个头文件时，要用标准名称空间(using namespace std;)。map和multimap的元素是 key/value 对，map可以作为映射式数组使用，比如存储学生信息时，学生的学号和姓名就是一一对应的映射关系，或者在存储电话号码时，人名和电话号码也是映射关系，等等。map和multimap根据元素的key自动对元素进行排序。根据已知的key搜寻某个元素时，能够有很好的性能，根据已知的value搜寻元素时性能则很糟糕。“自动排序”这一性质使得map和multimap有 很重要的限制：不能直接改变元素的key，因为这会破坏正确顺序。要修改元素的key，必须先移除拥有该key的元素，然后插入拥有新的key值的元素。2 map和multimaps的构造函数表1 map和multimap的构造函数操作效果map c产生一个空的map/multimap，其中不含任何元素map c (op)以op为排序准则，产生一个空的map/multimapmap c1(c2)产生某个map/multimap的副本，所有元素均被复制map c (beg, end)以区间beg ; end内的元素产生一个map/multimapmap c (beg, end, op)以op为排序准则，利用beg ; end内的元素生成一个map/multimap在表1中的map可以是以下形式：表2 表1中map的可选形式map效果map一个map，以less（实际上就是小于号“”）为排序准则map一个map，以op为排序准则multimap一个multimap，以less为排序准则multimap一个multimap，以op为排序准则表2中，key为键值类型，elem为value值的类型。op可以是less或者是greater，在排序准则中要指定key的类型。第二个参数指定了value的类型：string声明一个map容器变量方法如下：第一个参数指定了key的类型：float#include #include #include 注意：此处两个“”中间有一个空格using namespace std;int main()mapfloat, string, greater mymap;return 0;mapfloat, string, greater mymap;语句中，mapfloat, string, greater 是类型，mymap是该map容器的变量，二者之间的关系就如同int a;语句中，变量类型int和变量a之间的关系。实际上，map是一种容器，这种容器可以存储任何类型的变量，但是具体你需要什么类型的map，还需要告诉编译器，比如在本例的map容器，以float类型为key，以string类型为value。这些是属于泛型编程的内容，具体细节以后接触C+的时候就会明白。要注意红色高亮部分的两个“”中间要有一个空格，因为连续的两个“”会被编译器解释为移位操作符，导致语法错误。以上程序片段在VC中编译会有一大票C4786警告，不必理会，在其他编译器中无此问题。3 数据的插入和删除3.1 插入数据1、使用pair和insert语句：#include #include #include using namespace std;int main()mapfloat, string, greater mymap;mymap.insert(pair(22.3,hello);mymap.insert(pair(78.5,ok);return 0;其中pair的功能是把pair后面尖括号里指定的两种类型合并为一个pair类型。因为map容器存储数据都是相关联的数据成对存储的，所以要先把两个值合成一个“pair类型”。比如上面例子中，pair(22.3, “hello”)实现的功能就是把一个float和一个string合并成一个pair类型变量（实际上这就是面向对象中所谓的“对象”，对象与类的关系类似于c语言中内置类型如int与该类型变量的关系。实际上pair是一个类）。这个pair类型变量的一对值分别是浮点值22.3和字符串”hello”。（注意string也是一个类，和c语言中的c风格字符串不一样，要使用string的话需要包含头文件）注意以上代码中黄色高亮部分：”hello”和”ok”实际上都是const string，而第一条insert语句中的pair指定的是string类型，这时pair会做一个自动的隐式类型转换，把const string类型（也就是”hello”）变成string类型。2、使用make_pair函数和insert，这是最方便的方法。#include #include #include using namespace std;int main()mapfloat, string, greater mymap;mymap.insert(pair(22.3,hello);mymap.insert(pair(78.5,ok);mymap.insert(make_pair(50.0,happy);return 0;make_pair也会执行必要的隐式类型转换。但是在VC6.0中编译时mymap.insert(make_pair(50.0,happy);这一句通不过，”happy”被认为是char6类型，没有被自动转换成string。在dev c+中编译顺利通过。看来VC6.0这个开发环境存在的主要目的是为基于MFC的win32编程服务的，用到c+核心内容时，会深刻感受到VC6.0的不标准。3、使用value_type和insert#include #include #include using namespace std;int main()mapfloat, string, greater mymap;mymap.insert(pair(22.3,hello);mymap.insert(pair(78.5,ok);mymap.insert(make_pair(50.0,happy);mymap.insert(map:value_type(53.7,lucky);return 0;4 将map视为关联式数组，以数组下标方式（即）非常量(Non-const)的map提供下标操作符以支持元素的直接存取。如表3操作效果mkey返回一个引用（C+中的一种新类型，是一个变量的别名，可以按照指针来理解，但是使用起来比指针简单，而且效率比指针高），该引用指向键值为key的元素。如果该元素尚未存在，则插入该元素。注意mkey中的索引值”key”不一定是整型，因为他是map容器每个元素的key，可以是任意类型，这样可以方便地实现关联式数组。#include #include #include using namespace std;int main()mapstring,float,less anothermap;anothermap.insert(make_pair(zhangsan,1.75);anothermap.insert(make_pair(lisi,1.72);anothermap.insert(make_pair(zhaoliu,1.69);anothermaplisi=1.77;anothermapwangwu=1.66;return 0;以上代码黄色高亮部分中，第一句anothermaplisi=1.77;在anothermap中已经存在了key值为”lisi”的元素，那么这一句将会用1.77覆盖掉原来lisi所对应的值(1.72)；黄色高亮部分中，第二句anothermapwangwu=1.66;another中不存在key值为”wangwu”的元素，那么会向anothermap中自动插入一个新元素，key值为”wangwu”，并把这个新插入的元素的value设置为某个默认值（比如当value的类型为int时，会默认设置为0），然后再把1.66赋给这个新插入元素的value。前面说过，map中不能存在key值相同的元素。因此，在使用insert添加map新元素时，如果新插入元素的key值与容器中原有元素的key值有重复，则insert会失败。但使用下标方式插入则不会出现插入失败，因为如果在原有元素中存在与新插入元素key值相同的元素，则会用新插入元素的value去覆盖掉原有元素的value。这是下标方式的优点，也是其缺点，比如这会导致我们错误地覆盖掉容器中的原有元素，或是不小心错误插入新元素。比如：coutanothermap“zhangsa”;在输入”zhangsan”时，少敲了一个”n”，这将会导致向anothermap中插入一个新值，其key为”zhangsa”，value为0。另外，以下标方式向map中添加元素的速度要比insert方式慢许多。4 迭代器(iterator)在STL中，迭代器的角色类似于C/C+中的指针。其声明方式如下：map:iterator pos;其中map表明这个迭代器的类型，map:iterator pos表示声明一个迭代器pos，其类型为map。迭代器用法：#include #include #include using namespace std;int main()mapstring,float,less anothermap;anothermap.insert(make_pair(zhangsan,1.75);anothermap.insert(make_pair(lisi,1.72);anothermap.insert(make_pair(zhaoliu,1.69);anothermaplisi=1.77;anothermapwangwu=1.66;map:iterator pos;for(pos = anothermap.begin();pos!=anothermap.end();pos+) return 0;黄色高亮部分第一句声明了迭代器pos。第二句在for循环中，首先用到了map容器的begin()成员函数，该函数返回调用该函数的对象(也就是anothermap)的第一个元素的迭代器（可以理解为指针）；end()函数返回的迭代器指向了调用该函数的对象的最后一个元素后面的位置。如下图：图中容器中共有7个元素a, b, c, d, e, f ，begin()所返回的迭代器指向a，end()所返回的迭代器指向最后元素g的后面的位置。另外需要注意的是for循环中的循环终止条件不是posfirst获得该元素的key以下表达式pos-second获得该元素的valueint main()mapstring,float,less anothermap;anothermap.insert(make_pair(zhangsan,1.75);anothermap.insert(make_pair(lisi,1.72);anothermap.insert(make_pair(zhaoliu,1.69);anothermaplisi=1.77;anothermapwangwu=1.66;map:iterator pos;for(pos = anothermap.begin();pos!=anothermap.end();pos+) coutfirst secondfirst这种方式改变元素的key：pos-first=”xuqi”; /编译时出错记住最前面提到的：不能直接改变元素的key，因为这会破坏正确顺序。要修改元素的key，必须先移除拥有该key的元素，然后插入拥有新的key值的元素。如果元素本身value的值非const，可以通过pos-second来改变value的值，如下面的语句：pos-second=1.73;/OK6 容器元素的删除6.1 通过erase()函数删除具有某个key值的单个元素如：要删除容器中拥有某个key值的元素，可以通过以下方式：anothermap.erase(lisi);完整代码如下：#include #include #include using namespace std;int main()mapstring,float,less anothermap;anothermap.insert(make_pair(zhangsan,1.75);anothermap.insert(make_pair(lisi,1.72);anothermap.insert(make_pair(zhaoliu,1.69);anothermaplisi=1.77;anothermapwangwu=1.66;map:iterator pos;for(pos = anothermap.begin();pos!=anothermap.end();pos+) coutfirst secondendl;coutendl;anothermap.erase(lisi);for(pos = anothermap.begin();pos!=anothermap.end();pos+) coutfirst secondendl;return 0;运行结果如下：可以看到，key为”lisi”的元素已经从anothermap对象中被删除。6.2 通过erase()函数删除某个位置上的元素#include #include #include using namespace std;int main()mapstring,float,less anothermap;anothermap.insert(make_pair(zhangsan,1.75);anothermap.insert(make_pair(lisi,1.72);anothermap.insert(make_pair(zhaoliu,1.69);anothermaplisi=1.77;anothermapwangwu=1.66;map:iterator pos;for(pos = anothermap.begin();pos!=anothermap.end();pos+) coutfirst secondendl; coutendl;pos = anothermap.find(lisi);if(pos!=anothermap.end() anothermap.erase(pos);for(pos = anothermap.begin();pos!=anothermap.end();pos+) coutfirst secondendl;return 0;运行结果：高亮部分的find()函数用来搜寻拥有某个key的第一个元素，并返回一个指向该元素的迭代器。如果没有找到这样的元素，就返回该容器的end()。注意，不能用find()搜索拥有某特定value的元素。如果我们需要删除map中具有某个value值的元素，可以通过如下方式：#include #include #include using namespace std;int main()mapstring,float,less anothermap;anothermap.insert(make_pair(zhangsan,1.75);anothermap.insert(make_pair(lisi,1.72);anothermap.insert(make_pair(zhaoliu,1.69);anothermaplisi=1.77;anothermapwangwu=1.66;map:iterator pos;for(pos = anothermap.begin();pos!=anothermap.end();pos+) coutfirst secondendl; coutendl; map:iterator temp;for(pos = anothermap.begin(); pos!= anothermap.end();pos+) if(pos-second=1.75) temp=pos; anothermap.erase(temp); break; for(pos = anothermap.begin();pos!=anothermap.end();pos+) coutfirst secondsecond=1.75)anothermap.erase(pos);因为对pos所指元素实施erase()之后，会使pos不再成为一个有效的anothermap迭代器，从而pos成为一种未定义的状态。因此，要删除具有某个value的元素，需要按照上面高亮部分代码所做的：声明另一个该类型的迭代器temp，用pos去遍历整个容器的所有元素，当发现第一个具有value值的元素时，把pos值赋给temp，然后用temp去删除。6.3 使用erase()移除某个区间内所有元素#include #include #include using namespace std;int main()mapstring,float,less anothermap;anothermap.insert(make_pair(zhangsan,1.75);anothermap.insert(make_pair(lisi,1.72);anothermap.insert(make_pair(zhaoliu,1.69);anothermaplisi=1.77;anothermapwangwu=1.66;map:iterator pos;for(pos = anothermap.begin();pos!=anothermap.end();pos+) coutfirst secondendl; coutendl; map:iterator ibeg; map:iterator iend; for(ibeg=anothermap.begin();ibeg!=anothermap.find(lisi);ibeg+); for(iend=anothermap.begin();iend!=anothermap.find(zhangsan);iend+); anothermap.erase(ibeg,iend);for(pos = anothermap.begin();pos!=anothermap.end();pos+) coutfirst secondendl;return 0;运行结果如下：可以看到，在容器中key为”lisi”和key为”zhangsan”之间的元素被删除。注意，删除区间包括”lisi”但不包括”zhangsan”。6.4 使用clear移除全部元素，将整个容器清空#include #include #include using namespace std;int main()mapstring,float,less anothermap;anothermap.insert(make_pair(zhangsan,1.75);anothermap.insert(make_pair(lisi,1.72);anothermap.insert(make_pair(zhaoliu,1.69);anothermaplisi=1.77;anothermapwangwu=1.66;map:iterator pos;for(pos = anothermap.begin();pos!=anothermap.end();pos+) coutfirst secondendl; coutendl; anothermap.clear();for(pos = anothermap.begin();pos!=anothermap.end();pos+) coutfirst secondendl;return 0;运行结果如下：7 当key值为用户自定义类型时，map的用法因为map容器会自动对存入容器的元素进行排序，排序规则由multimap中的op指定，op可以是less也可以是greater，其实就是小于号“”，如果不指定op，则op取默认值less。当op指定为less时，容器中所有元素按升序排列，op为greater时，容器中元素按降序排列。问题在于，当key值为内置类型，如int，float等类型时，编译器知道如何比较这些类型的值的大小，比如声明两个整型变量int a,b;当有表达式astu2，编译器是否知道如何比较这两个结构体变量？因为编译器不知道如何比较用户自定义类型，因此当key值为用户自定义类型时，map将无法实现在存储时自动排序。比如有如下代码：#include #include using namespace std;struct stu int num; float height;int main() stu stu1,stu2; stu1.num=1; stu1.height=1.75; stu2.num=2; stu2.height=1.65; map stumap; stumap.insert(make_pair(stu1,22); stumap.insert(make_pair(stu2,23); return 0;编译时，会提示如下错误：意思是，没有适合用来比较比较x和y的“小于号操作符(operator)”这里的x和y实际就是上面代码中的stu1和stu2。实际上，编译器不知道怎样比较stu这种类型。解决这个问题要用到一种叫做“操作符重载”的技术。实际上，小于号()和等于号(= =)都是函数，它们的返回值类型都是bool类型。它们的函数原型分别是：operator(参数)和operator=(参数)。举例来说：int a,b;a=4;b=5;当我们使用ab这个表达式时，实际上是调用了operator()这个函数，ab可以写成这样：a.operator(b);变量a加一个点符号是什么意思？想想结构体变量如何引用它们的成