第二章游戏中的数据结构与算法第六节stl非线性容器

STL中的非线性容器Map容器map的结构。map的操作。了解熟悉map的结构，并熟练掌握map的操作。2map将key/valuepair（键值/实值对组）当作元素，进行管理。它们可根据key的排序准则自动将元素排序使用map之前，必须先包含头文件<map>：#include<map>map被定义为命名空间std内的classtemplates：namespacestd{template<classKey,classT,classCompare=less<Key>,classAllocator=allocator<pair<constKey,T>>>classmap; }6STL中的非线性容器6.1：map容器3第一个template参数被当做元素的key，第二个template参数被当做元素的value。第三个template参数可有可无，用来定义排序准则。第四个template用来定义内存模型。map的元素类型Key和T，必须满足以下两个条件：1）key/value必须具备可赋值和可复制的性质。2）对排序准则而言，key必须是可比较的。Map根据元素的key自动对元素进行排序。根据已知的key搜寻某个元素时，就能够有很好的性能，而根据已知value搜寻元素时，性能比较差。6STL中的非线性容器6.1：map容器4map的操作构造、拷贝和析构mapc产生一个空的map，其中不含任何元素mapc(op)以op为排序准则，产生一个空的mapmapc1(c2)产生某个map的副本，所有元素均被复制mapc(beg,end)以区间[beg;end)内的元素产生一个mapmapc(beg,end,op)以op为排序准则，利用[beg;end)内的元素生成一个mapc.~map()销毁所有元素，释放内存6STL中的非线性容器6.1：map容器5有两种方式可以定义排序准则：1）以template参数定义。std::map<float,std::string,std::greater<float>>coll;2）以构造函数参数定义。在这种情况下，可以有一个“排序准则类型”并为它指定不同的排序准则。如果使用者没有提供特定排序准则，就采用预设准则——仿函数less<>。less<>是透过operator<对元素进行排序。6STL中的非线性容器6.1：map容器6map<string,float>mShoolReport; mShoolReport["Tom"]=80;mShoolReport["Jack"]=89;mShoolReport["John"]=60;mShoolReport["Rose"]=50;产生mShoolReport的副本，所有元素均被复制map<string,float>mShoolReport2(mShoolReport);以区间[beg;end)内的元素产生一个mapmap<string,float>mShoolReport3(mShoolReport2.begin(),mShoolReport2.end());6STL中的非线性容器6.1：map容器7非变动性操作c.size()返回容器的大小c.empty()判断容器大小是否为零。等同于size()==0c.max_size()返回可容纳的最大元素数量c1==c2判断是否c1等于c2c1!=c2判断是否c1不等于c2，等同于!(c1==c2)c1<c2判断是否c1小于c2c1>c2判断是否c1大于c2，等同于c2<c1c1<=c2判断是否c1小于等于c2，等同于!(c2<c1)c1>=c2判断是否c1大于等于c2，等同于!(c1<c2)6STL中的非线性容器6.1：map容器8元素间比较动作只能用于类型相同的容器。换言之，容器的key、value、排序准则都必须有相同的类型，否则编译期会产生类型方面的错误。std::map<float,std::string>c1;std::map<float,std::string,std::greater<float>>c2;...if(c1==c2){//ERROR:differenttypes...}6STL中的非线性容器6.1：map容器9特殊的搜寻动作成员函数find()用来搜寻拥有某个key的第一个元素，并返回一个迭代器，指向该位置。不能以find()搜寻拥有某特定value的元素，必须改用通用算法如find_if()，或直接写一个循环。std::multimap<std::string,float>coll;std::multimap<std::string,float>::iteratorpos;for(pos=coll.begin();pos!=coll.end();++pos){ if(pos->second==value) {

……; }}6STL中的非线性容器6.1：map容器10map的特殊搜寻操作函数count(key)返回“键值等于key”的元素个数find(key)返回“键值等于key”的第一个元素，找不到就返回end()lower_bound(key)返回“键值为key”的元素的第一个可插入的位置，也就是“键值>=key”的第一个元素位置upper_bound(key)返回“键值为key”的元素的最后一个可插入的位置，也就是“键值>key”的第一个元素位置equal_range(key)返回“键值为key”的元素的第一个可插入位置和最后一个可插入位置，也就是“键值==key”的元素区间6STL中的非线性容器6.1：map容器11map<string,float>mShoolReport; mShoolReport["Tom"]=80;mShoolReport["Jack"]=89;mShoolReport["John"]=60;mShoolReport["Rose"]=50;map<string,float>::iteratorpos=mShoolReport.find("Jack");if(pos!=mShoolReport.end()){ cout<<"Key="<<pos->first<<'\t'<<"Value:" <<pos->second<<endl;}else cout<<"为此键值的元素不存在！"<<endl;6STL中的非线性容器6.1：map容器12赋值操作Map只支持所有容器都提供的基本指派操作操作功能c1=c2将c2中所有元素赋值给c1c1.swap(c2)将c1和c2的元素互换swap(c1,c2)同上。此为全局函数这些操作函数中，赋值动作的两端容器中的元素必须具有相同类型。6STL中的非线性容器6.1：map容器13迭代器函数和元素存取map不支持元素直接存取，因此元素的存取通常是经由迭代器进行。不过有个例外：map提供下标操作符，可直接存取元素函数功能c.begin()返回一个双向迭代器（key被视为常数），指向第一个元素c.end()返回一个双向迭代器（key被视为常数），指向最后元素的下一个位置c.rbegin()返回一个逆向迭代器，指向逆向遍历时的第一个元素c.rend()返回一个逆向迭代器，指向逆向遍历时的最后元素的下一个位置6STL中的非线性容器6.1：map容器14std::map<std::string,float>coll;...std::map<std::string,float>::iteratorpos;for(pos=coll.begin();pos!=coll.end();++pos){std::cout<<"key:"<<pos->first<<"\t"<<"value:"<<pos->second<<std::endl;}获得元素的key:pos->first获得元素的value：pos->second尝试改变元素的key，会引发错误,改变value没有问题：pos->first=“hello”; //错误pos->second=13.5;6STL中的非线性容器6.1：map容器15元素的插入和删除c.insert(elem)插入一份elem副本c.insert(pos,elem)插入一份elem副本c.insert(beg,end)将区间[beg;end)内所有元素的副本安插到c（无返回值）c.erase(elem)移除“key与elem相等”的所有元素，返回被移除的元素个数c.erase(pos)移除迭代器pos所指位置上的元素，无返回值c.erase(beg,end)移除区间[beg;end)内的所有元素，无返回值c.clear()移除全部元素，将整个容器清空6STL中的非线性容器6.1：map容器16有3个不同的方法可以将value传入map：1）运用value_type。std::map<std::string,float>coll;...coll.insert(std::map<std::string,float>::value_type("otto",22.3));2）运用pair<>。std::map<std::string,float>coll;...coll.insert(std::pair<std::string,float>("otto",22.3));coll.insert(std::pair<conststd::string,float>("otto",22.3));6STL中的非线性容器6.1：map容器17std::map<std::string,float>coll;...coll.insert(std::make_pair("otto",22.3));3）运用make_pair()。如果要删除“拥有某个value”的元素，调用erase()即可：std::map<std::string,float>coll;...coll.erase(key);m[key]返回一个引用，指向键值为key的元素。如果该元素尚未存在，就插入该元素map的直接元素存取：6STL中的非线性容器6.1：map容器18以数组的方式使用map对象的优点是：可以透过更方便的接口对着map插入元素。std::map<std::string,float>coll;coll["otto"]=7.7;1）处理coll["otto"]：如果存在键值为"otto"的元素，以上式子返回该元素的引用。如果没有任何元素的键值是"otto"，以上式子便为map自动插入一个新元素，键值key为"otto"，数据值value则以默认构造函数进行构造2）将数据7.7赋值给value：将数据7.7赋值给上述刚刚诞生的新元素。以数组的方式使用map对象，其缺点是：可能会不小心误插入新元素。6STL中的非线性容器6.1：map容器19本节介绍了map的结构与操作。map的元素都是“实值/键值”所形成的一个对组（key/valuepairs）。每个元素有一个键，是排序准则的基础。每一个键只能出现一次，不允许重复。选择题（单选题）以下哪一个容器不可以用来表示线性表？（

）A．