45

std::map値で並べ替え、次にキーで並べ替える必要があります。マップには、次のようなデータが含まれています。

  1  realistically
  8         really
  4         reason
  3     reasonable
  1     reasonably
  1     reassemble
  1    reassembled
  2      recognize
 92         record
 48        records
  7           recs

順番に値を取得する必要がありますが、キッカーは、値が順番になった後にキーをアルファベット順に並べる必要があることです。これどうやってするの？

4

5 に答える 5

68

std::mapその要素を でソートしますkeys。valuesいつソートするかは気にしません。

を使用std::vector<std::pair<K,V>>して並べ替えることができ、その後に次のものstd::sortが続きstd::stable_sortます。

std::vector<std::pair<K,V>> items;

//fill items

//sort by value using std::sort
std::sort(items.begin(), items.end(), value_comparer);

//sort by key using std::stable_sort
std::stable_sort(items.begin(), items.end(), key_comparer);

std::sortであるため、最初の並べ替えを使用し、最悪の場合はどちらをnlog(n)使用する必要があります。std::stable_sortn(log(n))^2

std::sortwhileはパフォーマンス上の理由から選択されていることに注意してくださいstd::stable_sort。値による順序を保持する必要があるため、正しい順序付けに必要です。

コメントに記載されている@gsfは、最初に比較する比較子を選択した場合にのみ 使用でき、それらが等しい場合は.std::sortvalueskeys

auto cmp = [](std::pair<K,V> const & a, std::pair<K,V> const & b) 
{ 
     return a.second != b.second?  a.second < b.second : a.first < b.first;
};
std::sort(items.begin(), items.end(), cmp);

それは効率的なはずです。

しかし、待ってください。より良いアプローチがあります: storestd::pair<V,K>の代わりにstd::pair<K,V>比較子はまったく必要ありません — 標準の比較子 forでstd::pair十分firstです。VsecondK

std::vector<std::pair<V,K>> items;
//...
std::sort(items.begin(), items.end());

それはうまくいくはずです。

于 2013-11-07T17:03:38.690 に答える
16

std::setの代わりに使用できますstd::map。

キーと値の両方を格納できstd::pair、コンテナのタイプは次のようになります。

std::set< std::pair<int, std::string> > items;

std::set元のキーと に保存された値の両方で値を並べ替えますstd::map。

于 2013-11-07T17:34:00.273 に答える
1

std::map定義した述語を使用して値をソートするか、述語を指定std::lessしない場合は、すでに値をソートしています。 std::setまた、define コンパレータの順にアイテムを格納します。ただし、セットもマップも、複数のキーを持つことはできません。std::map<int,std::set<string>データ構造のみを使用してこれを達成したい場合は、 a を定義することをお勧めします。std::lessまた、 for string はアルファベット順ではなく辞書順でソートされることにも注意してください。

于 2013-11-07T17:07:22.127 に答える
0

編集：他の2つの答えは良い点です。それらを他の構造に注文したり、印刷したりすることを想定しています。

「最高」にはさまざまな意味があります。「最も簡単」、「最速」、「最も効率的」、「最小コード」、「最も読みやすい」という意味ですか?

最も明白なアプローチは、2 回ループすることです。最初のパスで、値を並べ替えます。

if(current_value > examined_value)
{
    current_value = examined_value
    (and then swap them, however you like)
}

次に、2 番目のパスで単語をアルファベット順に並べ替えますが、値が一致する場合のみです。

if(current_value == examined_value)
{
    (alphabetize the two)
}

厳密に言えば、これは「バブル ソート」であり、スワップを行うたびに最初からやり直す必要があるため、処理が遅くなります。スワップを行わずにリスト全体を通過すると、1 つの「パス」が終了します。

他の並べ替えアルゴリズムもありますが、原則は同じです。値で並べ替え、次にアルファベット順に並べ替えます。

于 2013-11-07T17:09:24.740 に答える