c++ - 使用 std::sort 按值对 CPP 中的 map 进行排序的代码有什么问题？

Question

我正在尝试使用 std::sort 和自定义比较函数按值对 Map 进行排序。但是我得到一个编译错误。

Ps:我不想使用 Lambda 函数。

我已经尝试过在 dcompare 函数中使用迭代器变量作为参数。

class Solution {
public:
    int foo(int n) {
        unordered_map<int,int> M ;
        // Inputs = {2,4,5,2,4,2,1}
        M[4] = 2;
        M[5] = 1;
        M[2] = 3;
        M[1] = 1;

        for(auto it : M){
            cout<<it.first<<" : "<<it.second<<endl;
        }

        sort(M.begin(), M.end(), dcompare);

        for(auto it : M){
            cout<<it.first<<" : "<<it.second<<endl;
        }

        return 0;
    }

private:
    static bool dcompare(const std::pair<int,int> itL, const std::pair<int,int> itR) {
        return (itL.second < itR.second);
    }
};

当我将变量更改为迭代器时出现同样的错误

static bool dcompare(const map<int,int>::iterator itL, const map<int,int>::iterator itR) 
{ 
    return (itL->second < itR->second); 
}

这是我得到的编译器错误:

stl_algo.h: In instantiation of 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::_Rb_tree_iterator<std::pair<const int, int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::pair<int, int>, std::pair<int, int>)>]':
stl_algo.h:4866:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = std::_Rb_tree_iterator<std::pair<const int, int> >; _Compare = bool (*)(std::pair<int, int>, std::pair<int, int>)]'
Line 15: Char 42:   required from here
stl_algo.h:1969:22: error: no match for 'operator-' (operand types are 'std::_Rb_tree_iterator<std::pair<const int, int> >' and 'std::_Rb_tree_iterator<std::pair<const int, int> >')
     std::__lg(__last - __first) * 2,

Answer 1

无法对 map 元素重新排序。顾名思义，std::map 按键排序，而 std::unordered_map 是无序的。

错误本身告诉您 std::sort 尝试对迭代器使用减法运算符，但没有这样的运算符用于映射迭代器。这反过来又告诉您映射迭代器不是随机访问迭代器。 std::sort 要求输入迭代器是随机访问迭代器。

一个解决方案是创建一个指向 map 元素的指针数组，并对数组进行排序。或者，如果您不再需要 map ，您可以将元素本身移动到数组中。或者您可以复制这些元素。

另一种解决方案是使用多索引容器而不是 map 。然而，标准库不提供这样的容器。多索引容器可以实现为一组具有共享节点的树。一个多节点将拥有每个索引树的子节点。因此，一个索引可以是 map 的键查找，而另一个索引可以按值排序。