C++中map按照从大到小的顺序存储元素

map按照从大到小存储元素

引言
map的大致介绍
- 概述
场景
- 误区
- 示例
- - 示例代码（方法一）
  - 运行结果
  - 示例代码二（方法二）
  - 运行结果

引言

在对map的使用中，由于对业务的需要，希望map中存储元素能够按照键的大小从大到小的顺序递减存储元素，但之前没有对这块进行了解，只是想当然的使用sort来对map中的元素进行排序，但是不能这样操作的。
本文记录如何对map中的元素按照键的大小从大到小进行递减的存储元素。

map的大致介绍

概述

map是C++标准容器中的一种，也是一种关联容器，用于存储键值对，内部使用红黑树实现，可以快速查找和插入。其存储的元素默认按照键的大小从小到大的递增。

场景

由于map中存储的元素默认是按照键的值从小到大的顺序进行存储的，但是业务却希望map能够按照键的值从大到小的顺序存储元素。

误区

我的第一反应是使用sort函数来对map进行排序，但是后来发现sort排序后编译器编译不通过，反复修改折腾，最后才知道sort函数要求传入的容器迭代器类型为随机访问迭代器。而只有vector,deque和array等序列容器可以通过sort排序。

示例

本例子是一个map我想把内部的元素按照键的值从大到小的顺序存储。

示例代码（方法一）

第一种方法是通过一个类，在类中实现一个仿函数，仿函数主要是实现比较键的大小，使mapd的键按照我们预期的顺序排序。下面是示例代码。
main.cpp

#include <iostream>
#include <string>
#include <map>
#include <algorithm>
using namespace std;

struct mapSort 
{
    bool operator() (const int& a,const int& b) const
    {
        return a > b;
    }
};

map<int, string, mapSort> hashPair = { {1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"},
                             {100, "C"},  {90, "XC"},  {50, "L"},  {40, "XL"},
                             {10, "X"},   {9, "IX"},   {5, "V"},   {4, "IV"},
                             {1, "I"} };

class Solution {
public:
    void printPairs() 
    {
        for (const auto& var:hashPair)
        {
            cout << "key:" << var.first << "value:" << var.second << endl;
        }
        cout << "==========================" << endl;
    }
    Solution() 
    {
        printPairs();
    }
    string intToRoman(int num) {
        string strValue;
        for (const auto& /*[value, symble]*/var : hashPair) {
            int value = var.first;
            string symble = var.second;
            while (num >= value) {
                num -= value;
                strValue += symble;
            }
            if (num == 0) {
                break;
            }
        }
        return strValue;
    }
};

int main()
{
    Solution obj;
    // 3 58 1994
    cout<<"input 3,and ouput :"<<obj.intToRoman(3)<<endl;
    cout << "input 58,and ouput :" << obj.intToRoman(58) << endl;
    cout << "input 1994,and ouput :" << obj.intToRoman(1994) << endl;
    std::cout << "Hello World!\n";
}

上述代码中，map<int,string>的键为int，若是按照键的值从大到小的顺序存储，需要定义个一个类或者结构体，在其中写一个仿函数bool operator() (const int& a,const int& b) const，通过这个仿函数来实现容器的键的比较，使其按照键的值从大到小的顺序的存储。定义map的时候，需要在键值类型的后面加上该类的名称，map<int, string, mapSort>其中mapSort就是仿函数实现键排序的类。这样map中的元素就可以按照键的值从大到小进行排序了。

运行结果

在这里插入图片描述

示例代码二（方法二）

第二种方法是定义一个函数，该函数与上述的仿函数功能一致，就是使map的键按照期望的顺序从大到小排序，然后将这个函数定义为一个函数指针，最终在定义map的时候，将函数指针座位参数传入。不过map的初始化就要放在后面单独进行了。

#include <iostream>
#include <string>
#include <map>
#include <algorithm>
using namespace std;

bool compare_map(const int& a, const int& b)
{
    return a < b;
}
bool(*fun)(const int&, const int&) = compare_map;
map<int, string, bool(*)(const int&, const int&)> hashPair(fun);

class Solution {
public:
    void printPairs() 
    {
        for (const auto& var:hashPair)
        {
            cout << "key:" << var.first << "value:" << var.second << endl;
        }
        cout << "==========================" << endl;
    }
    Solution() 
    {
        hashPair[1000] = "M";
        hashPair[900] = "CM";
        ...//这里省略部分插入操作，实则需要写上
        hashPair[1] = "I";
        printPairs();
    }
    string intToRoman(int num) {
        string strValue;
        for (const auto& /*[value, symble]*/var : hashPair) {
            int value = var.first;
            string symble = var.second;
            while (num >= value) {
                num -= value;
                strValue += symble;
            }
            if (num == 0) {
                break;
            }
        }
        return strValue;
    }
};

int main()
{
    Solution obj;
    // 3 58 1994
    cout<<"input 3,and ouput :"<<obj.intToRoman(3)<<endl;
    cout << "input 58,and ouput :" << obj.intToRoman(58) << endl;
    cout << "input 1994,and ouput :" << obj.intToRoman(1994) << endl;
    std::cout << "Hello World!\n";
}