c++ - C++ Map で最大値を見つける方法

Question

私のデータ構造クラスの先生は、本を読んで単語数を数える課題を私たちに与えました。それがすべてではありません; 最も一般的な 100 の単語を表示する必要があります。私の腸は地図を並べ替えるように言っていますが、地図から 100 単語だけが必要です。グーグルで調べた後、キーではなく値でマップをソートするための「教科書の答え」はありますか?

Answer 1

「教科書の答え」があるとは思えませんが、答えはノーです。マップを値でソートすることはできません。

値を使用して、いつでも別のものを作成できmapます。ただし、これは最も効率的なソリューションではありません。私がより良いと思うのは、値を にチャックしてからpriority_queue、最初の 100 をポップすることです。

単語を 2 番目のデータ構造に格納する必要がないことに注意してください。単語へのポインターまたは参照、またはmap::iterator.

ここで、検討できる別のアプローチがあります。これは、最初のマップを作成するときに、上位 100 の候補の実行順序を維持するためです。そうすれば、2回目のパスを実行して余分な構造を構築する必要がなくなります。これは、あなたが指摘したように無駄です。

これを効率的に行うには、おそらくヒープのようなアプローチを使用し、値を更新するたびにバブルアップを行います。単語数は常に増加するだけなので、これはヒープに非常に適しています。ただし、メンテナンスの問題が発生する可能性があります。つまり、ヒープ内の値の位置を参照する方法と、底から落ちる値を追跡する方法です。