3

基本的に、1 つの要素に複数のキーでアクセスできるコンテナーが必要です。これは、マップのキー タイプとして使用されるマルチキー クラスを定義することによって実行できますが、そのようなソリューションでは、既に挿入されている要素のキーを変更できないため、新しいエイリアスを作成することはできません。既存のエントリ。

std::mapwithキーは順序付けのために一定である必要があることは理解していますが、なぜこの制限が に存在する必要があるのstd::unordered_mapでしょうか?

必要に応じて、ポインターのマップを使用することもできると思いますが、より優れた、よりエレガントなソリューションはありますか?

編集: Andrei、Xeo を解決してくれてありがとう。Nicol、どのコンテナを使用すべきかについて何か提案はありますか?

4

3 に答える 3

8

キーを変更できない理由std::unordered_mapは、他の連想コンテナがキーを変更できない理由とほぼ同じです。そのデータ構造の内部編成が台無しになります。

ではunordered_map、キーはハッシュを取得するために使用され、そのハッシュは、要素を配置するバケット (およびもちろん、要素を取得するバケット) をコンテナに通知します。キーを変更すると、ハッシュも変更されます。つまり、要素を別のバケットに移動する必要があります。それは、基本的に、それを削除して再度挿入するようなものです。

一方、連想コンテナの全体的な考え方は、すべての要素が固定された 1 つの値で表されるため、コンテナ内の要素の位置をその値の関数としてすばやく計算できるということです。複数のキーが許可されている場合、要素が格納されている場所または格納される予定の場所をすばやく判断するには、どのキーを使用しますか?

あなたが望むのは、おそらく、標準ライブラリのものとは異なる複雑さの保証を持つアドホックなデータ構造です。

ただし、個人的には、 1 つのオブジェクトの複数のビューを共有するつもりであるため、参照セマンティクスを探しているだけのように思えます。特に世界の「エイリアス」を聞いたとき、それは自然に（スマート）ポインターの使用につながります。値として s を持つマップを使用することをお勧めしshared_ptrます。

于 2013-02-14T20:38:48.617 に答える
2

連想コンテナ (mapなどunordered_map) では、 の値によってkeyデータ構造内の要素の位置が決まります。非マルチ連想コンテナでは、キーが一意である必要もあります。

の変更keyが許可された場合、前述の設計不変条件が危険にさらされることになります。

  • でmapの、二分探索木での要素の配置

  • でunordered_map、要素をハッシュ バケットにリンクする

OP の要件を理解していればinsert()、次の C++ 風の疑似コードのように、コンテナの にラッパーを記述することで実現できる可能性があります。

Iterator insert_wrapper( Container & cont, Element const & elem ) {

    if elem in cont {
       cont.erase( elem );
    }

    return cont.insert( elem );
}
于 2013-02-14T20:46:20.023 に答える
1

ポインターのマップよりも参照のマップの方が味わい深いと思いますか?

int value = 6;

std::unordered_map<int, int&> m;

for(int i=0; i<5; ++i)
    m.emplace(i, value);

value = 4;

for(auto const& i: m)
    std::cout<<i.second<<' ';

もちろん、例で示したように、実際の値を別の場所に保存する必要があります。

于 2013-02-14T20:45:24.497 に答える