3

std :: multimapのように機能するが、ランダムなn番目の要素へのアクセス時間が一定であるSTLコンテナーを探しています。多くの理由でstd::multimapであるようなメモリ内の構造があるため、これが必要ですが、そこに格納されているアイテムは、リストボックスでユーザーに提示する必要があります。データ量が膨大なため、仮想アイテムを含むリストボックスを使用しています（つまり、リストコントロールはX行の値をポーリングします）。

回避策として、現在、追加のstd::vectorを使用して「インデックス」をstd::mapに格納しており、次のように入力します。

std::vector<MMap::data_type&> vec;
for (MMap::iterator it = mmap.begin(); it != mmap.end(); ++it)
    vec.push_back((*it).second);

しかし、これはあまり洗練された解決策ではありません。

そのような封じ込め器はありますか？

4

4 に答える 4

5

必要なものは次のとおりです。 ブーストマルチインデックス

于 2010-05-30T11:27:40.410 に答える
2

そのリストにはいくつのアイテムがあり、どのタイプのアイテムであり、その途中でどのくらいの頻度で挿入または削除する必要がありますか？これによっては、ソートされたものstd::vector<std::pair<key,value>>を使用std::binary_searchしたり、キーのみを比較する検索述語で使用したりしても問題ない場合があります。

于 2010-05-30T11:34:28.490 に答える
1

要件に加えて、あなたのコメントから、アイテムの挿入/削除も計画しているようです。私は2000万人がかなり多いように思われることを認めなければなりません。

今、私はポーリングのアイデアを理解していますが、あなたは次のようなことを考えましたunordered_multimapか？ある位置でポーリングする代わりに、O（1）のキーでポーリングできますが、キーのタイプによってはオーバーヘッドが少し大きくなります。

主な利点は、2つのコンテインの同期を維持する必要がないことです。もちろん、コンテンツをソートしたい場合は機能しません。

したがって、コンテンツを並べ替えて、ランダムな位置への高速（O（1）ではない）アクセスが必要な場合は、B+TreeまたはRadixTreeを検討できます。彼らのアイデアは、アイテムを一度に数百のメモリの連続したゾーンに保持することです。

それは私の頭のてっぺんです。焼き付けられたソリューションが必要な場合は、自動入力された回答を検討してください:)

于 2010-05-30T17:47:11.100 に答える
0

hash_multimapを試してください。ハッシュはほぼ一定の時間を提供します。Hash_multimapはVisualStudioの拡張機能であり、GCCも同様の拡張機能を提供していると確信しています。あなたが必死なら、ブーストには何かハッシュがあります。

于 2010-05-30T17:53:10.727 に答える