c++ - 如何在 C++ Map 中找到最大值

Question

我在数据结构课上的老师给我们布置了一项作业，让我们阅读一本书并数一数有多少字。那不是全部;我们需要显示 100 个最常用的单词。我的直觉说要对 map 进行排序，但我只需要 map 中的 100 个单词。谷歌搜索后，是否有“教科书答案”来按值而不是键对 map 进行排序？

Answer 1

我怀疑是否存在“教科书答案”，答案是否定的:您不能按值对 map 进行排序。

您始终可以使用这些值创建另一个 map。但是，这不是最有效的解决方案。我认为更好的做法是将值放入 priority_queue，然后弹出前 100 个值。

请注意，您不需要将单词存储在第二个数据结构中。您可以存储指向单词的指针或引用，甚至是 map::iterator。

现在，您可以考虑另一种方法。那就是在您构建第一张 map 时保持前 100 名候选者的运行顺序。这样就不需要进行第二遍并构建一个额外的结构，正如您所指出的那样，这是一种浪费。

要有效地执行此操作，您可能会使用类似堆的方法，并在更新值时进行冒泡。由于字数只会增加，这非常适合堆。但是，您手上会有维护问题。即:如何引用堆中值的位置，并跟踪从底部掉落的值。