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

Question

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

Answer 1

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

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

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

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

为了有效地做到这一点，您可能会使用类似堆的方法并在更新值时进行冒泡。由于字数只会增加，这将非常适合堆。但是，您将遇到维护问题。那就是：你如何引用一个值在堆中的位置，并跟踪从底部掉下来的值。