由2个值组合成key的STL map排序问题

时间:2022-10-01 19:15:28

在C++中,map是典型的关联容器或者叫映射容器(associative container),其中的每一个元素都是由key-value这样成对出现的内容组成的,比如学号和学生之类具有一一对应关系的情形,学号可以作为key,学生对象可以作为key所对应的value。很显然这种情况下的key只有一个值,但是,在实际工作中,我们可能会经常需要使用多个值组合起来作为key的情况,比如我们要按照学生的视力和身高进行排序,以决定学生的座位排在前面还是后面,而且还是假定要用map来解决这样的问题(当然,这样的问题有很多其它的解决办法),那应该怎么办呢?

 

(1)  单值作为key的情形

我们知道map在缺省状态下,其数据是按照key的升序进行排列的。假定我们有一个Student类,声明如下:

[cpp]  view plain copy
  1. class Student  
  2. {  
  3. private:  
  4.          int id;                  // 学号  
  5.          string name;             // 姓名  
  6.          float eyesight;          // 视力  
  7.          float height;            // 身高  
  8.          float chinese;           // 语文成绩  
  9.          float english;           // 英文成绩  
  10.          float math;              // 数学成绩  
  11. public:  
  12.          Student(int id, string name,floateyesight, float height,float chinese, float english,float math)  
  13.          {  
  14.                    this->id = id;  
  15.                    this->name = name;  
  16.                    this->eyesight = eyesight;  
  17.                    this->height = height;  
  18.                    this->chinese = chinese;  
  19.                    this->english = english;  
  20.                    this->math = math;  
  21.          }  
  22.    
  23.          int get_id()  
  24.          {  
  25.                    return id;  
  26.          }  
  27.    
  28.          string get_name()  
  29.          {  
  30.                    return name;  
  31.          }  
  32.    
  33.          float get_eyesight()  
  34.          {  
  35.                    return eyesight;  
  36.          }  
  37.    
  38.          float get_height()  
  39.          {  
  40.                    return height;  
  41.          }  
  42.    
  43.          float get_chinese()  
  44.          {  
  45.                    return chinese;  
  46.          }  
  47.    
  48.          float get_english()  
  49.          {  
  50.                    return english;  
  51.          }  
  52.    
  53.          float get_math()  
  54.          {  
  55.                    return math;  
  56.          }  
  57. };  
 

那么下面的程序:

[cpp]  view plain copy
  1. int main(int argc,char**argv)  
  2. {  
  3.        map<int, Student> stu_map;    // int作为key的类型,Student作为value的类型  
  4.        stu_map.insert(make_pair(4,Student(4, "Dudley",1.1f, 170.2f, 90.5f, 89.5f, 93.0)));  
  5.        stu_map.insert(make_pair(3,Student(3, "Chris", 1.1f, 163.4f, 93.5f,90.0f, 83.5f)));  
  6.        stu_map.insert(make_pair(2,Student(2, "Bob", 1.5f, 166.6f, 86.0f,98.5f, 85.0f)));  
  7.        stu_map.insert(make_pair(1,Student(1, "Andrew", 1.5f, 173.2f, 98.5f,100.0f, 100.f)));  
  8.    
  9.        map<int, Student>::iterator iter;  
  10.        for(iter = stu_map.begin(); iter != stu_map.end();++iter)  
  11.        {  
  12.               cout<< iter->first << "\t"<< iter->second.get_name() << endl;  
  13.        }  
  14.    
  15.        return 0;  
  16. }  
 

就会按照学号的升序给出输出:

1          Andrew

2          Bob

3          Chris

4          Dudley

这是缺省的情形,如果要将学生的姓名按照学号的降序输出,那么仅需将上面main函数中的

map<int,Student> stu_map;改为

map<int,Student, greater<int> > stu_map;

以及

map<int,Student>::iterator iter;改为

map<int,Student, greater<int> >::iteratoriter;

即可。

 

其实,map<int,Student> stu_map;这是一种缺省的情况,它和

map<int,Student, less<int> > stu_map;是一样的。

 

(2) 多值组合作为key的情形

现在,我们来看看多个值组合起来作为key的情况,为此,我们需要为key定义一个类,如下:

[cpp]  view plain copy
  1. class key  
  2. {  
  3. public:  
  4.        float eyesight;  
  5.        float height;  
  6.    
  7.        key(float x, floaty):eyesight(x), height(y)  
  8.        {  
  9.        }  
  10.    
  11.        friend bool operator < (constkey&,const key&);  
  12. };  
  13.    
  14. bool operator < (constkey& key1,const key& key2)  
  15. {  
  16.        // 按eyesight升序 + height升序排列  
  17.        if(key1.eyesight != key2.eyesight)        
  18.               return (key1.eyesight < key2.eyesight);  
  19.        else  
  20.               return (key1.height < key2.height);  
  21.         
  22.        // 按eyesight降序 + height降序排列  
  23.        //if(key1.eyesight != key2.eyesight)      
  24.        //     return(key1.eyesight > key2.eyesight);  
  25.        //else                                   
  26.        //     return(key1.height > key2.height);  
  27.    
  28.        // 按eyesight升序 + height降序排列  
  29.        //if(key1.eyesight != key2.eyesight)      
  30.        //     return(key1.eyesight < key2.eyesight);  
  31.        //else                                   
  32.        //     return(key1.height > key2.height);  
  33.    
  34.        // 按eyesight降序 + height升序排列  
  35.        //if(key1.eyesight != key2.eyesight)      
  36.        //     return(key1.eyesight > key2.eyesight);  
  37.        //else                                   
  38.        //     return(key1.height < key2.height);  
  39. }  
 

再修改main函数如下:

[cpp]  view plain copy
  1. int main(int argc,char**argv)  
  2. {  
  3.        map<key,Student> stu_map;  
  4.    
  5.        Studentstu4(4, "Dudley",1.1f, 170.2f, 90.5f, 89.5f, 93.0);  
  6.        Studentstu3(3, "Chris", 1.1f, 163.4f, 93.5f,90.0f, 83.5f);  
  7.        Studentstu2(2, "Bob", 1.5f, 166.6f, 86.0f,98.5f, 85.0f);  
  8.        Studentstu1(1, "Andrew", 1.5f, 173.2f, 98.5f,100.0f, 100.f);  
  9.    
  10.        stu_map.insert(make_pair(key(stu4.get_eyesight(),stu4.get_height()), stu4));  
  11.        stu_map.insert(make_pair(key(stu3.get_eyesight(),stu3.get_height()), stu3));  
  12.        stu_map.insert(make_pair(key(stu2.get_eyesight(),stu2.get_height()), stu2));  
  13.        stu_map.insert(make_pair(key(stu1.get_eyesight(),stu1.get_height()), stu1));  
  14.    
  15.        map<key,Student>::iterator iter;  
  16.        for(iter = stu_map.begin(); iter != stu_map.end();++iter)  
  17.        {  
  18.              cout<< iter->first.eyesight << "\t"<< iter->first.height  << "\t" << iter->second.get_id()<<"\t" <<iter->second.get_name() << endl;  
  19.        }  
  20.    
  21.        return 0;  
  22. }  

那么输出结果为:

1.1    163.4        3       Chris

1.1    170.2        4       Dudley

1.5    166.6        2       Bob

1.5    173.2        1       Andrew

从上面的输出,我们可以很明显地看到,是按照视力升序和升高升序输出的,另外三种可能的排序情况,也在类key的操作符“<”的重载函数中,用注释的形式给出了。

 

(3)结论

1.通常我们不用STL algorithm中的sort函数,来对一个map进行排序,而对vector的元素进行排序则可以很方面地使用sort函数;

2.多值组合作为key的情况,需要我们自己定义一个key类,并在该类中重载操作符“<”。


附两个值作为key的情况之完整的实验代码如下:

[cpp]  view plain copy
  1. #include <iostream>  
  2. #include <map>  
  3. #include <string>  
  4. using namespace std;   
  5.    
  6. class key  
  7. {  
  8. public:  
  9.        float eyesight;  
  10.        float height;  
  11.    
  12.        key(float x, floaty):eyesight(x), height(y)  
  13.        {  
  14.        }  
  15.    
  16.        friend bool operator < (constkey&,const key&);  
  17. };  
  18.    
  19. bool operator < (constkey& key1,const key& key2)  
  20. {  
  21.        // 按eyesight升序 + height升序排列  
  22.        if(key1.eyesight != key2.eyesight)        
  23.               return (key1.eyesight < key2.eyesight);  
  24.        else  
  25.               return (key1.height < key2.height);  
  26.         
  27.        // 按eyesight降序 + height降序排列  
  28.        //if(key1.eyesight != key2.eyesight)      
  29.        //     return(key1.eyesight > key2.eyesight);  
  30.        //else                                   
  31.        //     return(key1.height > key2.height);  
  32.    
  33.        // 按eyesight升序 + height降序排列  
  34.        //if(key1.eyesight != key2.eyesight)      
  35.        //     return(key1.eyesight < key2.eyesight);  
  36.        //else                                   
  37.        //     return(key1.height > key2.height);  
  38.    
  39.        // 按eyesight降序 + height升序排列  
  40.        //if(key1.eyesight != key2.eyesight)      
  41.        //     return(key1.eyesight > key2.eyesight);  
  42.        //else                                   
  43.        //     return(key1.height < key2.height);  
  44. }  
  45.    
  46. class Student  
  47. {  
  48. private:  
  49.          int id;                   //学号  
  50.          string name;              // 姓名  
  51.          float eyesight;           //视力  
  52.          float height;             //身高  
  53.          float chinese;            //语文成绩  
  54.          float english;            //英文成绩  
  55.          float math;               //数学成绩  
  56. public:  
  57.        Student(int id, string name,floateyesight,float height,float chinese,float english,float math)  
  58.        {  
  59.               this->id = id;  
  60.               this->name = name;  
  61.               this->eyesight = eyesight;  
  62.               this->height = height;  
  63.               this->chinese = chinese;  
  64.               this->english = english;  
  65.               this->math = math;  
  66.        }  
  67.    
  68.        int get_id()  
  69.        {  
  70.               return id;  
  71.        }  
  72.    
  73.        string get_name()  
  74.        {  
  75.               return name;  
  76.        }  
  77.    
  78.        float get_eyesight()  
  79.        {  
  80.               return eyesight;  
  81.        }  
  82.    
  83.        float get_height()  
  84.        {  
  85.               return height;  
  86.        }  
  87.    
  88.        float get_chinese()  
  89.        {  
  90.               return chinese;  
  91.        }  
  92.    
  93.        float get_english()  
  94.        {  
  95.               return english;  
  96.        }  
  97.    
  98.        float get_math()  
  99.        {  
  100.               return math;  
  101.        }  
  102. };  
  103.    
  104. int main(int argc,char**argv)  
  105. {  
  106.        map<key,Student> stu_map;  
  107.    
  108.        Studentstu4(4, "Dudley",1.1f, 170.2f, 90.5f, 89.5f, 93.0);  
  109.        Studentstu3(3, "Chris", 1.1f, 163.4f, 93.5f,90.0f, 83.5f);  
  110.        Studentstu2(2, "Bob", 1.5f, 166.6f, 86.0f,98.5f, 85.0f);  
  111.        Studentstu1(1, "Andrew", 1.5f, 173.2f, 98.5f,100.0f, 100.f);  
  112.    
  113.        stu_map.insert(make_pair(key(stu4.get_eyesight(),stu4.get_height()), stu4));  
  114.        stu_map.insert(make_pair(key(stu3.get_eyesight(),stu3.get_height()), stu3));  
  115.        stu_map.insert(make_pair(key(stu2.get_eyesight(),stu2.get_height()), stu2));  
  116.        stu_map.insert(make_pair(key(stu1.get_eyesight(),stu1.get_height()), stu1));  
  117.    
  118.        map<key,Student>::iterator iter;  
  119.        for(iter = stu_map.begin(); iter != stu_map.end();++iter)  
  120.        {  
  121.              cout<< iter->first.eyesight << "\t"<< iter->first.height  << "\t" << iter->second.get_id()<<"\t" <<iter->second.get_name() << endl;  
  122.        }  
  123.    
  124.        return 0;  
  125. }