10

unordered_mapそれで、私はSTLから新しく標準化されたもので遊んでいました。私が持っているコードはこのようなものです。 unordered_map を作成し、それを埋めて、出力するだけです:

    unordered_map<int,string> m1;

    m1[5]="lamb";
    m1[2]="had";
    m1[3]="a";
    m1[1]="mary";
    m1[4]="little";
    m1[7]="fleece";
    m1[6]="whose";
    m1[10]="fleecey";
    m1[8]="was";
    m1[9]="all";

for(unordered_map<int,string>::const_iterator i = m1.begin(); i != m1.end(); ++i)
cout<<i->first<<" "<<i->second<<endl;

ただし、取得する出力は次のように並べられています。

1 mary
2 had
3 a
4 little
5 lamb
6 whose
7 fleece
8 was
9 all
10 fleecey

しかし、地図を注文してもらうために代価を払いたくありません! それが unordered_map を使用している理由です...ここで何が起こっているのですか?

追記：私はgcc version 4.3.4 20090804 (release) 1 (GCC)このように使用してコンパイルしていますg++ -std=c++0X maptest.cpp

4

2 に答える 2

10

「順不同」とは、アイテムをランダムに格納したり、マップに配置した順序を維持したりすることを意味するものではありません。これは、特定の順序に依存できないことを意味します。まったく逆に、注文に代償を払う必要はありません。実装はアイテムを明示的に注文するのではなく、ハッシュマップであり、その要素を好きな方法で保存します。これは通常、かなりパフォーマンスの高い方法です。ちょうどこれらのキーと、マップ上の操作のこの数と順序を正確に使用すると、ハッシングアルゴリズムとマップの他の内部動作が、順序付けられているように見える順序でアイテムを格納することになります。たとえば、文字列は明らかにランダム化されたレイアウトにつながる可能性があります。

余談ですが、これはおそらく、(少なくともいくつかの) 整数をそれ自体にマップするハッシュを使用し、ハッシュの下位ビット (マップサイズの命令と同じ数) を使用して、基になるインデックスを決定するマップによって引き起こされます。配列 (たとえば、CPython はこれを行います - 衝突を比較的簡単かつ効率的に処理するためのいくつかの非常に賢い追加機能を備えています。同じ理由で、CPython 文字列とタプルのハッシュは非常に予測可能です)。

于 2011-07-29T23:49:14.193 に答える
2

ご参考までに、ここに libc++ からの出力を示します。これには、 の恒等関数もありますstd::hash<int>。

9 all
8 was
10 fleecey
6 whose
7 fleece
4 little
1 mary
3 a
2 had
5 lamb

ハッシュ コンテナーを実装するにはいくつかの方法があり、それぞれに独自のトレードオフがあります。

于 2011-07-30T02:13:20.427 に答える