后台开发:核心技术与应用实践3.4.2 map的查增删

3.4.2 map的查增删


1.?map的插入


先讲下map的插入,map的插入有3种方式:用insert函数插入pair数据、用insert函数插入value_type数据和用数组方式插入数据。

【例3.18】 用insert函数插入pair数据。

#include <map>

#include <string>

#include <iostream>

using namespace std;

int main()

{

    map<int, string> mapStudent;

    mapStudent.insert(pair<int, string>(1, "student_one"));

    mapStudent.insert(pair<int, string>(2, "student_two"));

    mapStudent.insert(pair<int, string>(3, "student_three"));

    map<int, string>::iterator iter;

    for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++){

       cout<<iter->first<<" "<<iter->second<<endl;

    }

    return 0;

}

程序的执行结果是:

1 student_one

2 student_two

3 student_three

例3.18中,声明了一个key为int类型,value为string类型的map,用insert函数插入pair数据,且需要在insert的参数中将(1, "student_one")转换为pair数据再进行插入。

【例3.19】 用insert函数插入value_type数据。

#include <map>

#include <string>

#include <iostream>

using namespace std;

int main()

{

    map<int, string> mapStudent;

    mapStudent.insert(map<int, string>::value_type (1,"student_one"));

    mapStudent.insert(map<int, string>::value_type (2,"student_two"));

    mapStudent.insert(map<int, string>::value_type (3,"student_three"));

    map<int, string>::iterator  iter;

    for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++){

       cout<<iter->first<<" "<<iter->second<<endl;

    }

    return 0;

}

程序的执行结果是:

1 student_one

2 student_two

3 student_three

例3.19中,声明了一个key为int类型,value为string类型的map,用insert函数插入value_type数据,且需要在insert的参数中将(1, "student_one")转换为map<int, string>::value_type数据再进行插入。

【例3.20】 map中用数组方式插入数据。

    #include <map>

    #include <string>

#include <iostream>

using namespace std;

int main(){

    map<int, string> mapStudent;

    mapStudent[1] = "student_one";

    mapStudent[2] = "student_two";

    mapStudent[3] = "student_three";

    map<int, string>::iterator iter;

    for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++){

        cout<<iter->first<<" "<<iter->second<<endl;

    }

    return 0;

}

程序的执行结果是:

1  student_one

2  student_two

3  student_three

例3.20中展示了用数组方式在map中插入数据,和数组访问一样,有下标、直接赋值。以上3种用法,虽然都可以实现数据的插入,但是它们是有区别的,当然了第一种和第二种在效果上是完成一样的,用insert函数插入数据,在数据的插入上涉及集合的唯一性这个概念,即当map中有这个关键字时,insert操作是插入数据不了的,但是用数组方式就不同了,它可以覆盖以前该关键字对应的值。

mapStudent.insert(map<int, string>::value_type (1, "student_one"));

mapStudent.insert(map<int, string>::value_type (1, "student_two"));

上面这两条语句执行后,map中1这个关键字对应的值是student_one,第二条语句并没有生效,那么这就涉及如何知道insert语句是否插入成功的问题了,可以用pair来获得是否插入成功,程序如下:

pair<map<int, string>::iterator, bool> insert_pair;

insert_pair = mapStudent.insert(map<int, string>::value_type (1, "student_one"));

可以通过pair的第二个变量来知道是否插入成功,它的第一个变量返回的是一个map的迭代器,如果插入成功的话insert_Pair.second应该是true的,否则为false。

【例3.21】 用pair判断insert到map的数据是否插入成功。

#include <map>

#include <string>

#include <iostream>

using namespace std;

int main(){

    map<int, string> mapStudent;

    pair<map<int, string>::iterator, bool> insert_pair;

     insert_pair = mapStudent.insert(pair<int,string>(1,"student_one"));

    if(insert_pair.second == true){

        cout<<"Insert Successfully"<<endl;

    }

    else{

        cout<<"Insert Failure"<<endl;

    }

    insert_pair = mapStudent.insert(pair<int, string>(1, "student_two"));

    if(insert_pair.second == true){

          cout<<"Insert Successfully"<<endl;

     }else{

          cout<<"Insert Failure"<<endl;

    }

     map<int, string>::iterator iter;

     for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++){

          cout<<iter->first<<" "<<iter->second<<endl;

     }

     return 0;

}

程序的执行结果是:

Insert Successfully

Insert Failure

1 student_one

例3.21中,用pair判断insert到map的数据是否插入成功。pair变量insert_pair中的第一个元素的类型是map<int, string>::iterator,是和即将要判断的map中的key、value类型一致的一个map的迭代器。如果insert成功了,则insert_pair.second的结果为true,否则则为false。同一个key已经有数据之后,再insert就会失败。而数组插入的方式,则是直接覆盖。

【例3.22】 数据方式插入map覆盖原有的数据。

#include <map>

#include <string>

#include <iostream>

using namespace std;

int main()

{

    map<int,string> mapStudent;

    mapStudent[1] =  "student_one";

    mapStudent[1] =  "student_two";

    mapStudent[2] =  "student_three";

    map<int, string>::iterator iter;

    for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++){

        cout<<iter->first<<" "<<iter->second<<endl;

    }

    return 0;

}

程序的执行结果是:

1 student_two

2 student_three

例3.22中展示了mapStudent[1]上已经有数据"student_one"了,再用语句:

mapStudent[1] =  "student_two";

就可以直接覆盖成功。

2.?map的遍历

map数据的遍历,这里也提供3种方法,来对map进行遍历:应用前向迭代器方式、应用反向迭代器方式和数组方式。应用前向迭代器,上面举例程序中已经讲解过了,这里着重讲解应用反向迭代器的方式,下面举例说明。

【例3.23】 map反向迭代器的使用举例。

#include <map>

#include <string>

#include <iostream>

using namespace std;

int main(){

    map<int,string> mapStudent;

    mapStudent[1] =  "student_one";

    mapStudent[2] =  "student_two";

    mapStudent[3] =  "student_three";

     map<int, string>::reverse_iterator   iter;

     for(iter = mapStudent.rbegin(); iter != mapStudent.rend(); iter++){

          cout<<iter->first<<" "<<iter->second<<endl;

     }

     return 0;

}

程序的执行结果是:

3 student_three

2 student_two

1 student_one

例3.23中,iter就是一个反向迭代器reverse_iterator,它需要使用rbegin()和rend()方法指出反向遍历的起始位置和终止位置。注意,前向遍历的一般是从begin()到end()遍历,而反向遍历则是从rbegin()到rend()。

【例3.24】 用数组方式遍历map。

#include<map>

#include<string>

#include<iostream>

using namespace std;

int main(){

    map<int,string> mapStudent;

    mapStudent[1] =  "student_one";

    mapStudent[2] =  "student_two";

    mapStudent[3] =  "student_three";

    int iSize = mapStudent.size();

    for(int i = 1; i <= iSize; i++){

        cout<<i<<" "<<mapStudent[i]<<endl;

    }

     return 0;

}

例3.24中,用size()方法确定当前map中有多少元素。用数组访问vector时,下标是从0~(size-1),而用数组访问map,却是从1~size,这是有所不同的,请使用者多加注意。

3.?map的查找

在这里可以充分体会到map在数据插入时保证有序的好处。要判定一个数据(关键字)是否在map中出现的方法比较多,这里给出2种常用的数据查找方法。

第一种:用count函数来判定关键字是否出现,其缺点是无法定位数据出现位置,由于map的一对一的映射特性,就决定了count函数的返回值只有两个,要么是0,要么是1,当要判定的关键字出现时返回1。

第二种:用f?ind函数来定位数据出现位置,它返回的一个迭代器,当数据出现时,它返回数据所在位置的迭代器;如果map中没有要查找的数据,它返回的迭代器等于end函数返回的迭代器。

【例3.25】 用f?ind方法查找map中的数据。

#include<map>

#include<string>

#include<iostream>

using namespace std;

int main(){

    map<int,string> mapStudent;

    mapStudent[1] = "student_one";

    mapStudent[2] = "student_two";

    mapStudent[3] = "student_three";

     map<int, string>::iterator iter=mapStudent.find(1);

     if(iter != mapStudent.end()){

          cout<<"Found, the value is "<<iter->second<<endl;

     }else{

          cout<<"Do not found"<<endl;

    }

     return 0;

}

程序的执行结果是:

Find, the value is student_one

f?ind函数返回的是一个迭代器;找不到对应数据的时候,则会返回mapStudent.end()。

4.?map的删除

用erase方法可删除map中的元素。erase的函数原型是:

map.erase(k)

删除map中键为k的元素,并返回size_type类型的值以表示删除的元素个数,代码如下:

map.erase(p)

从map中删除迭代器p所指向的元素。p必须指向map中确实存在的元素,而且不能等于map.end(),返回void类型,代码如下:

map.erase(b,e)

从map中删除一段范围内的元素,该范围由迭代器对b和e标记。b和e必须标记map中的一段有效范围:即b和e都必须指向map中的元素或最后一个元素的下一个位置。而且,b和e要么相等(此时删除的范围为空),要么b所指向的元素必须出现在e所指向的元素之前,返回void类型。常用的是第二种,并且是在遍历的过程中删除元素。

【例3.26】 用erase方法删除map中的元素。

#include <map>

#include <string>

#include <iostream>

using namespace std;

int main(){

    map<int, string> mapStudent;

    mapStudent[1]="student_one";

    mapStudent[2]="student_two";

    mapStudent[3]="student_three";

    mapStudent[4]="student_four";

    map<int, string>::iterator iter=mapStudent.begin();

    for(;iter!=mapStudent.end();){

        if((*iter).second=="student_one"){

            mapStudent.erase(iter++);

        }

        else{

            ++iter;

        }

    }

    for(iter=mapStudent.begin();iter!=mapStudent.end();iter++){

        cout<<iter->first<<" "<<iter->second<<endl;

    }

    return 0;

}

程序的执行结果是:

2 student_two

3 student_three

4 student_four

mapStudent.erase(iter++);中的iter++,不是erase(iter),然后iter++。因为iter指针被erase之后就失效了,不能再用iter++;也不是erase(++iter),这样就不是删iter原来指向的元素了。

5.?map的排序

map的排序默认按照key从小到大排序,但有以下几点需要注意:①按照key从大到小排序;②key(第一个元素)是一个结构体;③想按value(第二个元素)排序。

map是STL里面的一个模板类,现在来看下map的定义:

template < class Key, class T, class Compare = less<Key>,

           class Allocator = allocator<pair<const Key,T> > > class map;

它有4个参数,其中比较熟悉的有两个:Key和Value。第4个是Allocator,用来定义存储分配模型的,此处不作介绍。

现在重点看下第3个参数:

class Compare = less<Key>

这也是一个class类型的,而且提供了默认值less<Key>。less是STL里面的一个函数对象,那么什么是函数对象呢?

所谓的函数对象,即调用操作符的类,其对象常称为函数对象(function object),它们是行为类似函数的对象。表现出一个函数的特征,就是通过“对象名+(参数列表)”的方式使用一个类,其实质是对operator()操作符的重载。

现在来看一下less的实现:

template <class T> struct less : binary_function <T,T,bool> {

    bool operator() (const T& x, const T& y) const

        {return x<y;}

};

它是一个带模板的struct,里面仅仅对()运算符进行了重载,实现很简单,但用起来很方便,这就是函数对象的优点所在。STL中还为四则运算等常见运算定义了这样的函数对象,与less相对的还有greater:

template <class T> struct greater : binary_function <T,T,bool> {

    bool operator() (const T& x, const T& y) const

        {return x>y;}

};

因此,要想让map中的元素按照key从大到小排序,可以如例3.27所示。

【例3.27】 让map中的元素按照key从大到小排序。

#include <map>

#include <string>

#include <iostream>

using namespace std;

int main(){

    map<string, int, greater<string> > mapStudent;

        mapStudent["LiMin"]=90;

        mapStudent["ZiLinMi"]=72;

        mapStudent["BoB"]=79;

    map<string, int>::iterator iter=mapStudent.begin();

    for(iter=mapStudent.begin();iter!=mapStudent.end();iter++){

            cout<<iter->first<<" "<<iter->second<<endl;

        }

        return 0;

}

程序的执行结果是:

ZiLinMi 72

LiMin 90

BoB 79

如例3.27中所示,只需指定它的第3个参数Compare,把默认的less指定为greater,即可达到按照key从大到小排序。现在知道如何为map指定Compare类了,如果想自己写一个Compare的类,让map按照想要的顺序来存储,比如按照学生姓名的长短排序进行存储,那么只要自己写一个函数对象,实现想要的逻辑,并在定义map的时候把Compare指定为自己编写的这个就可以实现了,代码如下:

struct CmpByKeyLength {

    bool operator()(const string& k1, const string& k2) {

        return k1.length() < k2.length();

    }

};

这里不用把Compare定义为模板,直接指定它的参数为string类型就可以了。

【例3.28】 重定义map内部的Compare函数。

#include <map>

#include <string>

#include <iostream>

using namespace std;

struct CmpByKeyLength {

    bool operator()(const string& k1, const string& k2) {

        return k1.length() < k2.length();

    }

};

int main(){

    map<string, int, CmpByKeyLength > mapStudent;

    mapStudent["LiMin"]=90;

    mapStudent["ZiLinMi"]=72;

    mapStudent["BoB"]=79;

    map<string, int>::iterator iter=mapStudent.begin();

    for(iter=mapStudent.begin();iter!=mapStudent.end();iter++){

        cout<<iter->first<<" "<<iter->second<<endl;

    }

    return 0;

}

程序的执行结果是:

BoB 79

LiMin 90

ZiLinMi 72

因此,想改变map的key排序方法,可以通过修改Compare函数实现。

key是结构体的,如果没有重载小于号(<)操作,就会导致insert函数在编译时就无法编译成功。其实,为了实现快速查找,map内部本身就是按序存储的(比如红黑树)。在插入<key, value>键值对时,就会按照key的大小顺序进行存储。这也是作为key的类型必须能够进行<运算比较的原因。

【例3.29】 key是结构体的map排序。

#include <map>

#include <string>

#include <iostream>

using namespace std;

typedef struct tagStudentInfo

{

    int iID;

    string  strName;

    bool operator < (tagStudentInfo const& r) const {

        // 这个函数指定排序策略,按iID排序,如果iID相等的话,按strName排序

        if(iID < r.iID)  return true;

        if(iID == r.iID) return strName.compare(r.strName) < 0;

        return false;

    }

}StudentInfo;// 学生信息

int main(){

    /*用学生信息映射分数*/

    map<StudentInfo, int>mapStudent;

    StudentInfo studentInfo;

    studentInfo.iID = 1;

    studentInfo.strName = "student_one";

    mapStudent[studentInfo]=90;

    studentInfo.iID = 2;

    studentInfo.strName = "student_two";

    mapStudent[studentInfo]=80;

    map<StudentInfo, int>::iterator iter=mapStudent.begin();

    for(;iter!=mapStudent.end();iter++){

        cout<<iter->first.iID<<" "<<iter->first.strName<<" "<<iter->second<<endl;

    }

    return 0;

}

程序的执行结果是:

1 student_one 90

2 student_two 80

例3.29中,mapStudent的key是StudentInfo类型的,要重载StudentInfo类型的<号,这样才能正常地插入到mapStudent中。

如果想按照map的value(第二个元素)排序,第一反应是利用stl中提供的sort算法实现,这个想法是好的,不幸的是,sort算法有个限制,利用sort算法只能对序列容器进行排序,只能是线性的(如vector、list、deque)。map也是一个集合容器,它里面存储的元素是pair,但是它不是线性存储的(如红黑树),所以利用sort不能直接和map结合进行排序。虽然不能直接用sort对map进行排序,那么可以间接进行,把map中的元素放到序列容器(如vector)中,然后再对这些元素进行排序呢?这个想法看似是可行的。要对序列容器中的元素进行排序,也有个必要条件:就是容器中的元素必须是可比较的,也就是实现了<操作的。那么现在就来看下map中的元素是否满足这个条件。

已知map中的元素类型为pair,具体定义如下:

template <class T1, class T2> struct pair

{

    typedef T1 first_type;

    typedef T2 second_type;

 

    T1 first;

    T2 second;

    pair() : first(T1()), second(T2()) {}

    pair(const T1& x, const T2& y) : first(x), second(y) {}

    template <class U, class V>

        pair (const pair<U,V> &p) : first(p.first), second(p.second) { }

}

pair也是一个模板类,这样就实现了良好的通用性。它仅有两个数据成员f?irst和second,即key和value,而且在<utility>头文件中,还为pair重载了< 运算符,具体实现如下所示:

template<class _T1, class _T2>

    inline bool

    operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)

    { return __x.first < __y.first

             || (!(__y.first < __x.first) && __x.second < __y.second); }

重点看下其实现,如下所示:

__x.first < __y.first || (!(__y.first < __x.first) && __x.second < __y.second)

这个less在两种情况下返回true。第一种情况:__x.f?irst < __y.f?irst,这种情况较好理解,就是比较key与__x、__y的大小,如果__x的key小于__y的key则返回true。

第二种情况有点费解,代码如下所示:

!(__y.first < __x.first) && __x.second < __y.second

当然由于||运算具有短路作用,即当前面的条件不满足时,才进行第二种情况的判断。第一种情况__x.f?irst < __y.f?irst不成立,即__x.f?irst >= __y.f?irst成立,在这个条件下,再来分析下!(__y.f?irst < __x.f?irst)  && __x.second < __y.second。

!(__y.f?irst < __x.f?irst)表示y的key不小于x的key,结合前提条件,__x.f?irst < __y.f?irst不成立,即x的key不小于y的key。

即:!(__y.f?irst < __x.f?irst) &&!(__x.f?irst < __y.f?irst )等价于__x.f?irst == __y.f?irst ,也就是说,第二种情况是在key相等的情况下,比较两者的value(second)。

这里比较令人费解的地方就是,为什么不直接写__x.f?irst == __y.f?irst呢?这么写看似费解,但其实也不无道理:前面讲过,作为map的key必须实现<操作符的重载,但是并不保证==操作符也被重载了,如果key没有提供==,那么__x.f?irst == __y.f?irst的写法就不对。由此可见,STL中的代码是相当严谨的,值得好好研读。

现在知道了pair类重载了<符,但是它并不是按照value进行比较的,而是先对key进行比较,key相等时候才对value进行比较。显然不能满足按value进行排序的要求。

而且,既然pair已经重载了<符,但不能修改其实现,也不能在外部重复实现重载

<符。

如果pair类本身没有重载<符,那么按照下面的代码重载<符,是可以实现对pair类按value比较的。但现在这样做不行了,甚至会出错(编译器不同,严格的就报错)。

typedef pair<string, int> PAIR;

bool operator< (const PAIR& lhs, const PAIR& rhs) {

    return lhs.second < rhs.second;

}

那么要如何实现对pair按value进行比较呢?第一种是最原始的方法,写一个比较函数;第二种刚才用到了,写一个函数对象,如下所示。这两种方式实现起来都比较简单。

typedef pair<string, int> PAIR;

bool cmp_by_value(const PAIR& lhs, const PAIR& rhs) {

    return lhs.second < rhs.second;

}

struct CmpByValue {

    bool operator()(const PAIR& lhs, const PAIR& rhs) {

        return lhs.second < rhs.second;

    }

};

接下来使用sort算法,来检验其是不是像map一样,也可以对指定的元素进行比较,代码如下所示:

template <class RandomAccessIterator>

void sort ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>

void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );

结果表明,sort算法和map一样,也可以对指定元素进行比较,即指定Compare。需要注意的是,map是在定义时指定的,所以传参的时候直接传入函数对象的类名,就像指定key和value时指定的类型名一样;sort算法是在调用时指定的,需要传入一个对象,当然这个也简单,类名()就会调用构造函数生成对象。

这里也可以传入一个函数指针,就是把上面说的第一种方法的函数名传过来。

【例3.30】 将map按value排序。

#include <map>

#include <vector>

#include <string>

#include <iostream>

using namespace std;

typedef pair<string, int> PAIR;

bool cmp_by_value(const PAIR& lhs, const PAIR& rhs) {

    return lhs.second < rhs.second;

}

struct CmpByValue {

    bool operator()(const PAIR& lhs, const PAIR& rhs) {

        return lhs.second < rhs.second;

    }

};

int main(){

    map<string, int> name_score_map;

    name_score_map["LiMin"] = 90;

    name_score_map["ZiLinMi"] = 79;

    name_score_map["BoB"] = 92;

    name_score_map.insert(make_pair("Bing",99));

    name_score_map.insert(make_pair("Albert",86));

    /*把map中元素转存到vector中*/

    vector<PAIR> name_score_vec(name_score_map.begin(), name_score_map.end());

    sort(name_score_vec.begin(), name_score_vec.end(), CmpByValue());

    /*sort(name_score_vec.begin(), name_score_vec.end(), cmp_by_value);也是可以的*/

    for (int i = 0; i != name_score_vec.size(); ++i) {

        cout<<name_score_vec[i].first<<" "<<name_score_vec[i].second<<endl;

    }

    return 0;

}

例3.30中要对map中的value进行排序,先把map的元素按pair形式插入到vector中,再对vector进行排序(用一个新写的比较函数),这样就可以实现按map的value排序了。

上一篇:【Docker】Rancher容器管理平台搭建


下一篇:MapGuide应用开发系列(四)---- 如何运行第一个.net实例代码