問題タブ [intrusive-containers]

私の目標は、ストリングインターニングを行うことです。このために、次のことができるハッシュ化されたコンテナー クラスを探しています。

• ノードごとに 1 つのメモリ ブロックのみを割り当てる
• ノードごとに異なるユーザーデータ サイズ

値の型は次のようになります。

すべての String オブジェクトのサイズは異なります。これは、演算子 new + 配置 new で実現されます。したがって、基本的にはノードを自分で割り当てて、後でコンテナーにプッシュしたいと考えています。

以下の容器は適していません:

• std::unordored_set

• ブースト::マルチインデックス::*

  異なるサイズのノードを割り当てることはできません

• boost::intrusive::unordered_set

  最初はうまくいくようです。しかし、いくつかの欠点があります。まず、バケット配列を割り当て、負荷係数を自分で維持する必要があります。これは単に不必要であり、エラーが発生しやすいものです。

  しかし、もう 1 つの問題は解決が困難です。文字列型のオブジェクトしか検索できません。しかし、エントリを探すたびに文字列を割り当てるのは非効率的で、入力として std::string しかありません。

このタスクに使用できるハッシュ化されたコンテナーは他にありますか?

boost::intrusive のドキュメントでは、スマート ポインターを侵入型コンテナーで使用する方法について説明していますが、使用する可能性が最も高いスマート ポインターは使用できないと述べています。リソース管理スマート ポインター (boost::shared_ptr など) を使用できないことを意味します。"

どうしてこれなの？禁止すべき明確な理由が思いつきません。正確には何が壊れますか？とにかく、侵入型コンテナはその中のアイテムの割り当てを管理しません。私の場合、intrusive_ptr を使用したいのですが、shared_ptr が機能しない理由がわかりません。

編集：明確にするために、フックポインター（たとえば、侵入型の単一リンクリストの次のポインター）がスマートポインターであることを意味します。

たとえば、要素が複数のマップから参照されているとします。たとえば、名前から要素へのマップ、アドレスから要素へのマップ、および要素への年齢のマップなどです。たとえば名前で要素を検索し、3 つのマップすべてから要素を削除したいですか?

いくつかの解決策が思い浮かびます：

1) 最も単純明快。名前から要素へのマップで要素を検索し、他の両方のマップを検索してそれらの要素を見つけ、3 つすべての要素エントリを削除します。

2) 3 つのマップすべてにウィーク ポインターを格納します。共有ポインタをどこかに、せいぜい要素自体に保存します。1 つのマップで要素を見つけたら、その要素を削除します。他のマップから要素にアクセスしようとして、ウィーク ポインターを共有ポインターに変換できないことに気付いた場合は、エントリを削除します。

3) 侵入型マップを使用します。これには、要素を見つけるために残りのマップを検索する必要がないという利点があります。ただし、オブジェクトは複数のマップに格納されるため、要素自体を邪魔にならないようにすることはできません。むしろ、要素にはフックを実装するメンバーが必要になる場合があります。

4) その他？

これに対する非常にきれいな解決策はありますか？私はこの問題に何度かぶつかっています...

いくつかの考え。通常、ソリューション 1 は、プロジェクトが成長するにつれて自然に実装されるものです。要素自体が他のマップの重要な情報を持ち、他のコンテナーがマップである場合、これはおそらくまったく問題ありません。ただし、キーが欠落している場合、またはコンテナーがリストなどの場合、非常に遅くなる可能性があります。解決策 2 は、ウィーク ポインターの実装に依存しており、非常に遅くなる可能性もあります。解決策 3 が最善のようですが、やや複雑でしょうか?

私は現在、いくつかの Windows ルックアサイド リストに頭を悩ませようとしていますが、混乱しているメモリ アドレスがいくつか見られます。

私が投稿した別の質問から、 sergmat（元の質問）のおかげでいくつかのコードが生成されました：

基本的に、上記の WinDBG 出力からわかることは、アドレス 0x82d5ffc0 に単一リンク リストがあることです。この出力は、32 ビット Windows 7 システムで生成されました。

ただし、これは私が混乱する場所です.Windows 7 64ビットシステムで同じ操作を実行すると、これが出力されます(アドレスは明らかに異なります):

のNext値は0x0000000001bf0003有効な仮想アドレスではないようです。また、仮想から物理への変換を実行しようとしましたが、失敗しました。

この値はページへの何らかのオフセットのように見えますが、アドレスをどのように計算する必要があるかは完全にはわかりません。

リスト ヘッダー内には追加のデータがあります。これは_SLIST_HEADER構造であり、_SINGLE_LIST_ENTRY. 次のデータが含まれています。

最初のヘッダーの後に一連の 3 つのユニオンがあり、これは 64 ビット システムでHeader16あるため、これを含むユニオンを使用する必要があると思います。

要素にはHeader16.NextEntry有効な仮想アドレスが含まれているため、これが次のリスト要素の実際の値なのか、それとも別のものなのかはわかりません。

_SINGLE_LIST_ENTRY.Nextしたがって、 64ビットシステムで要素がどのように計算されるかを明確にするのを手伝ってくれる人がいれば、大いに感謝します。

ありがとう

侵入型のデータ構造をコーディングしていて、ベース フックとメンバー フックのどちらを使用するか迷っています。コードは何度も呼び出されるため、私の質問は、パフォーマンスと、コンパイラがそのようなコードをどの程度インライン化できるかに関するものです。

基本フックは継承に基づいていますが、メンバー フックはテンプレート パラメーターを介してメンバーへのポインターを使用します。私の設計上の選択はメンバーフックを使用することですが、私の経験では、ポインターは静的コードよりも最適化がはるかに難しいと言われています。一方、これらのポインターはすべてコンパイル時に認識されており、おそらくコンパイラーは何が起こっているかを分析する魔法を行うことができます。

誰もこれについて経験がありますか？データ、ヒント、参考文献は大歓迎です。

私はhash.h、侵入型ハッシュ構造とそのインターフェースをlist.h含むヘッダー、および侵入型リストとそのインターフェースを含むヘッダーを定義する C プロジェクトに取り組んでいます。

ハッシュはリストを使用して実装され、ハッシュの実装をサポートするために使用できる他のデータ構造がないため、このコンテキストでは抽象化はあまり価値がありません。

抽象化はさておき、侵入リストの代わりに侵入ハッシュを使用する利点はありますか?