使用sort()对unordered_map进行排序

Question

我正在尝试使用 sort() 函数对一个 unordered_map 进行排序，但是我一直得到编译器错误。有人能帮忙吗？

bool comp(pair<char,int> a, pair<char,int> b) {
    return a.second < b.second;
}

void rearrangeKDist(char str[], int d) {
    int n = strlen(str);
    unordered_map<char, int> table;
    for (int i=0; i<n; i++) {
        unordered_map<char, int>::iterator it = table.find(str[i]);   
        if (it == table.end()) {
            table.insert(make_pair(str[i], 1));
        } else {
            it->second = it->second+1;
        }
    }
    for (unordered_map<char, int>::iterator it=table.begin(); it!=table.end(); it++)
        cout<<it->first<<" "<<it->second<<endl;
    sort(table.begin(), table.end(), comp);
    for (unordered_map<char, int>::iterator it=table.begin(); it!=table.end(); it++)
        cout<<it->first<<" "<<it->second<<endl;

}

- pratiksaha

---

为什么要对未排序的map进行排序？如果需要有序数据，请使用常规的map。（提示：你无法原地对其进行排序，这会破坏该map的不变性。） - Borgleader

相对于 find/insert/increment...，你可以使用侧节点来执行操作，只需 ++table[str[i]] 即可。 - Barry

可能性[重复]（https://dev59.com/qoDba4cB1Zd3GeqPGqBX）/我在这里的解释（https://dev59.com/qoDba4cB1Zd3GeqPGqBX/30971939#30971939） - Tony Delroy

Answer 1

从编译和逻辑角度来看，这是不可能的。从类型角度来看，std::sort 需要：

-RandomIt 必须满足 ValueSwappable 和 RandomAccessIterator 的要求。
-解引用 RandomIt 的类型必须满足 MoveAssignable 和 MoveConstructible 的要求。

std::unordered_map 上的迭代器类型是 ForwardIterator，而不是 RandomAccessIterator，所以第一个要求未满足。迭代器的解引用类型是 pair<const Key, T>，它不是可移动赋值的（无法分配给const），所以第二个要求也未满足。

从逻辑上讲，对一个无序容器进行排序是没有意义的。它是无序的。并且复杂度保证了unordered_map能够实现需要的特定排序方式，你不应该去打乱它。

如果您想要对您的unordered_map进行“排序”，请将它们放入vector中：

std::vector<std::pair<char, int>> elems(table.begin(), table.end());
std::sort(elems.begin(), elems.end(), comp);

- Barry

---

为了使用std::sort，我们需要添加头文件 #include <algorithm>。 - Nejc Galof

嗨谢谢你的答复，我真的很喜欢第一个原因的解释方式。我正在从新手过渡到中级阶段，您能否提供一些建议，告诉我们应该查看哪种资源，以便我们可以像您在这里所做的那样更加扎实地解释问题？@Barry - Jason