时间戳

首页 > 解决方案 > 这段代码使用 std::sort 按值对 CPP 中的地图进行排序有什么问题？

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

问题描述

我正在尝试使用 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,

标签： c++

解决方案

无法重新排序地图的元素。Astd::map是按键排序的，而 astd::unordered_map是无序的，顾名思义。

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

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

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

推荐阅读