27

たとえば、C++ ベクトルは、各要素が連続したメモリ空間を使用する動的配列を使用して実装されます。

C++ マルチマップが 1 対多の関係であることは知っていますが、内部構造は何ですか?

4

4 に答える 4

31

C++ 標準では、標準コンテナーの実装方法は定義されていません。ベクトルに対して言うような特定の制約のみが与えられます。

マルチマップには、特定の実行時の複雑さ (興味深い操作の場合は O(lg n)) とその他の保証があり、赤黒木として実装できます。これは、GNU 標準 C++ ライブラリに実装されている方法です。

于 2011-06-06T21:49:47.947 に答える
8

非常に多くの場合、赤黒の木です。たとえば、ドブ博士の STL の Red-Black Treesを参照してください。

于 2011-06-06T21:48:12.723 に答える
3

SOは私にコメントさせないので、「好ましい」答えへの追加：

値が B、C、D のキーが与えられた場合、各要素に独自のノードがあると、イテレータの動作を実装するのがはるかに簡単になります。Find() は、シリーズの最初の結果を返すように定義されており、その後の反復で残りの要素に移動します。マップとマルチマップの事実上の違いは、マルチマップは value_type 全体で < を使用してソートされるのに対し、マップでは key_type のみで < を使用することです。

訂正: C++11 標準では、同じキーを持つ既存の値の最後に新しい (キー、マッピング) ペアが挿入されることが明示されています。これは、私が考えていなかった疑問を提起します: マルチマップは、キーとマップされたターゲットの両方が同じである 2 つのノードを含むことができますか? 標準はこれについて明確な立場をとっていないようですが、マップされた型に比較演算子が必要ないことは注目に値します。テスト プログラムを作成すると、マルチマップが X を 1、2、1 にマップできることがわかります。つまり、「1」がターゲットとして複数回出現する可能性があり、2 つのインスタンスはマージされません。一部のアルゴリズムでは、これは欠陥です。

Dr. Dobbs によるこの記事では、一般的に使用される基本的な rb-tree 実装について説明しています。注意すべき主なポイントは、リバランス操作は実際にはキーをまったく気にしないということです。これが、重複したキーを許可する rb-tree を構築できる理由です。

于 2014-09-26T15:51:54.727 に答える
0

multimap は、単純なバージョン、つまり std::map と同じように、ほとんどが赤黒の木を使用して構築されます。C++ 標準自体は実装を指定していません。しかし、ほとんどの場合 (個人的に SGI STL を確認しました)、赤黒木が使用されます。Red Black ツリーは高さのバランスが取れたツリーであるため、フェッチ/読み取り操作は常に O(log(n)) 時間であることが保証されます。しかし、キーの値がどのように格納されているか疑問に思っている場合。それぞれkey->pairが赤黒ツリーの個別のノードとして保存されます (ただし、'b'以下のキーの場合のように、同じキーが複数回表示される場合があります)。キーは、rb-tree のルックアップ/検索に使用されます。キーが見つかると、ノードに格納されている値が返されます。

  std::multimap<char,int> mmp;

  mmp.insert(std::pair<char,int>('a',10));
  mmp.insert(std::pair<char,int>('b',20));
  mmp.insert(std::pair<char,int>('b',10));
  mmp.insert(std::pair<char,int>('b',15));
  mmp.insert(std::pair<char,int>('b',20));
  mmp.insert(std::pair<char,int>('c',25));
  mmp.insert(std::pair<char,int>('a',15));
  mmp.insert(std::pair<char,int>('a',7));


for (std::multimap<char,int>::iterator it=mmp.begin(); it!=mmp.end(); ++it){

    std::cout << (*it).first << " => "  << (*it).second << " . Address of (*it).second = " << &((*it).second) << '\n';
}

出力:

a => 10 . Address of (*it).second = 0x96cca24
a => 15 . Address of (*it).second = 0x96ccae4
a => 7 . Address of (*it).second = 0x96ccb04
b => 20 . Address of (*it).second = 0x96cca44
b => 10 . Address of (*it).second = 0x96cca64
b => 15 . Address of (*it).second = 0x96cca84
b => 20 . Address of (*it).second = 0x96ccaa4
c => 25 . Address of (*it).second = 0x96ccac4

最初は、 「b」のような単一のキーの値がstd::vector に格納される可能性があると考えていました。

template <class K, class V>
struct Node {
  K key;
  std::vector<V> values; 
  struct Node* left;
  struct Node* right;
}

しかし、後で、O(log(n)) の保証されたフェッチ時間に違反することに気付きました。さらに、値のアドレスを出力すると、共通キーを持つ値が連続していないことが確認されます。

これらのキーは operator< を使用して挿入されるため、同じキーを持つ値は挿入された順序で格納されます。

したがって、最初に (key = 'b', value = 20) を挿入し、次に (key = 'b', value = 10) を挿入すると、挿入は operator< を使用して行われます。 「b」、「二分木の右枝」に挿入されます。

私が使用したコンパイラは gcc-5.1 ( C++14) です。

于 2015-11-17T13:49:32.477 に答える