C++的map的自定义排序

川长思鸟来 2024-03-31 13:48 61阅读 0赞

#### 一、map的语法 ####

//所在头文件：<map>, std::map 类模板, std::map 通常由二叉搜索树实现。
    
    template < class Key,                                     // map::key_type
               class T,                                       // map::mapped_type
               class Compare = less<Key>,                     // map::key_compare
               class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
               > class map;

#### 二、map按键值Key排序 ####

默认按照less<key>升序排列，可以使用用greater< key>实现按Key值递减插入数据

#include<iostream>
    #include<map>
    using namespace std;
    
    int main()
    {
        srand((unsigned)time(NULL));
        multimap<int,int>mp;
    // multimap第三个参数默认为less<Key>,即 less<int>
        int n;
        cin>>n;
        int a,b;
        for(int i=0; i<n; i++)
        {
            a=rand()%4;
            b=rand()%4;
            //插入
            mp.insert(pair<int,int>(a,b));
        }
        map<int,int>::iterator iter;
        //遍历输出
        for(iter=mp.begin(); iter!=mp.end(); iter++)
            cout<<iter->first<<" "<<iter->second<<endl;
        return 0;
    }

输入8，Key升序，Value随机，打印结果如下

![4e87867043e94f499783c2bb0b3be226.png][]

#### 三、当Key值为自定义的类时 ####

方法1，写一个函数对象（仿函数）

#include<iostream>
    #include<map>
    using namespace std;
    
    typedef struct tagIntPlus
    {
        int num;
        int i;
    }IntPlus;
    
    //仿函数，自定义比较规则
    struct Cmp
    {
        bool operator () (IntPlus const &a, IntPlus const &b)const
        {
            if (a.num != b.num) {
                return a.num < b.num;
            }
    
            else {
                return a.i < b.i;
            }
        }
    };
    int main()
    {
        srand((unsigned)time(NULL));
        // 注意此处一定要有Cmp，否则无法排序会报错
        multimap<IntPlus, int, Cmp>mp;
        int n;
        cin >> n;
        int a, b;
        IntPlus intplus;
        for (int i = 0; i < n; i++)
        {
            a = rand() % 4;
            b = rand() % 4;
            intplus.num = a;
            intplus.i = b;
            mp.insert(pair<IntPlus, int>(intplus, i));
        }
        map<IntPlus, int>::iterator iter;
        for (iter = mp.begin(); iter != mp.end(); iter++)
            cout << iter->first.num << " " << iter->first.i << " " << iter->second << endl;
    
        system("pause");
        return 0;
    }

![3bc635c7b2e540b9b157ec3e0652d003.png][]

方法2，在类里重载小于号<，注意只重载小于号,不要去重载大于号，如果想改变为 升 / 降序列,只需改变判断条件即可

typedef struct tagIntPlus
    {
        int num;
        int i;
        bool operator < (tagIntPlus const& intplus)const
        {
            //当num不等时
            //前一个对象的num>后一个时返回true,降序排列。
            //反之升序排列
            if (num != intplus.num) {
                return num > intplus.num;
            }
            //前一个对象的i<后一个时返回true,升序排列
            else {
                return i < intplus.i;
            }
        }
    }IntPlus;

#### 四、用char\*类型作为map的主键 ####

find或count时，默认使用== 进行判断，char\*只是指针，如果两个字符串值相同，但是地址不同，是无法匹配的。所以最好使用std::string。如果非要用char\*，需要使用find\_if函数并且用bind2sd函数指定比较函数。（请使用C++11）

#include <map>
    #include <algorithm>
    #include <iostream>
    
    using namespace std;
    
    bool search(pair<char*, int> a, const char* b)
    {
        return strcmp(a.first, b) == 0 ? true : false;
    }
    
    int main()
    {
        map<char*, int> test;
        test.insert(pair<char*, int>("abc", 1));
    
        map<char*, int>::const_iterator iter = find_if(test.begin(), test.end(), bind2nd(ptr_fun(search), "abc"));
    
        if (iter != test.end())
        {
            cout << "find : " << iter->first << endl;
        }
    
        return 0;
    }

![394389f6883946339297391f75cde6d0.png][]

参考：

[C++中std::map自定义排序与std::unordered\_map自定义哈希函数 - 傍风无意 - 博客园][C_std_map_std_unordered_map_ - _ -]

[4e87867043e94f499783c2bb0b3be226.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/bb52d63d3d1d46c18d2309d538caa002.png
[3bc635c7b2e540b9b157ec3e0652d003.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/cad1341c61534ef5867714703a1aa05a.png
[394389f6883946339297391f75cde6d0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/79810d9fc295456aa074455a176dcb14.png
[C_std_map_std_unordered_map_ - _ -]: https://www.cnblogs.com/depend-wind/articles/12683863.html