9

std::map<int, ...>挿入時に整数キーの昇順で反復が行われるようにするにはどうすればよいですか？

4

3 に答える 3

22

何もする必要はありません。マップは、キーの値に従って昇順になります。

内部的には、マップはキー間の比較を実行して要素を並べ替えます。デフォルトでは、を使用します。これは整数の場合std::less<KEY>と同じです。bool operator<(int, int)ユーザー定義タイプの場合、次のオプションが必要です。

  1. bool operator<(const MyType&, const MyType&)ユーザー定義型間の厳密な弱順序比較の実装を実装します。タイプに自然な順序がある場合は、これを使用します

  2. 厳密な弱順序を実装するバイナリファンクターを提供します。これは、3番目のテンプレートパラメーターとしてマップに渡すことができます。タイプに自然な順序がない場合、またはfromポイント1で使用std::less<Key>される順序とは異なる順序でマップを作成する場合は、これを使用します。bool operator<(...)

通常、舞台裏で行われるのは、マップが自己平衡二分木として実装され、厳密な弱順序がマップに新しい要素を配置し、2つの要素が等しいかどうかを判断するために使用されることです。余談ですが、同じロジックがに適用されますstd::set。ここで、キーと値は同じです。

于 2013-01-22T16:55:17.277 に答える
15

std::mapそれ自体を行います。何もする必要はありません。

デフォルトでは、キーは昇順で並べ替えられます。降順で並べ替えを実行する場合は、 3番目のテンプレート引数std::greater<T>としてに渡します。std::map

std::map<int, X>  m1;                    //sorts key in increasing order
std::map<int, X, std::greater<int>>  m2; //sorts key in decreasing order
std::map<int, X, std::less<int>> m3;     //sorts key in increasing order

3番目のテンプレートパラメータのデフォルトの引数はですので、上記と同じタイプです！std::less<T>m1m3

デモ：

#include <iostream>
#include <map>
#include <string>

int main()
{
    std::cout << "\nkeys are in increasing order: \n";
    std::map<int, std::string> m1;
    m1[5] = "first insertion but higher key";
    m1[1] = "second insertion but lower key";
    for(auto const & item : m1) 
       std::cout << "{" << item.first  <<"," << item.second << "}\n";

    std::cout << "\nkeys are in decreasing order: \n";   
    std::map<int, std::string, std::greater<int> > m2;
    m2[1] = "first insertion but lower key";
    m2[2] = "second insertion but higher key";
    for(auto const & item : m2) 
       std::cout << "{" << item.first  <<"," << item.second << "}\n";
}

出力：

keys are in increasing order: 
{1,second insertion but lower key}
{5,first insertion but higher key}

keys are in decreasing order: 
{2,second insertion but higher key}
{1,first insertion but lower key}

どちらの場合も、アイテムはの3番目のテンプレート引数で指定されたとおりに順序付けられていることに注意してくださいstd::map。出力は挿入の順序ではなく、キーの順序に依存します。

ライブデモ

std::unordered_map要素をソートしないものもあります。

于 2013-01-22T16:56:27.540 に答える
1

map通常は二分探索木として実装されるため、イテレータはすでにソートされたキーを提供します。

注文を気にしない場合はunordered_map（c ++ 11またはboostから）使用できます。これにより、注文の取引がある程度スピードアップします。

于 2013-01-22T16:58:29.413 に答える