Boost.Intrusiveおよびunordered_map

Question

侵入的なunordered_mapの使用を検討しています。何らかの理由で、ライブラリにはunordered_setしかありません。侵入型ハッシュテーブルもありますが、同じ機能を備えているかどうかはわかりません。また、同じインターフェースもありません。
私は間違っていて、unordered_mapリンクを逃しましたか？
私がいない場合、それを実装するのに役立つチュートリアルがありますか？

Answer 1

これは興味深い質問です。 Boost.Intrusiveは、順序付きまたは順序なしのマップインターフェイスを提供していないようです。順序付けられたマップ（赤黒木、AVLツリー、スプレイツリー）と順序付けられていない（ハッシュテーブル）の両方のマップとして適切に機能する実装タイプが多数あります。しかし、マップはありません。その理由を説明できませんでした。

表示されるとおり、2つの選択肢があります：

1. ただhashtableを使用する：順序付けられていないコンテナはハッシュテーブルとして実装されます（そして、それらが呼び出されない hash_mapの唯一の理由は、既にその名前を使用している既存のライブラリとの名前の衝突を避けるためです）。仕事を終わらせたい場合に有効です。
2. 独自に実装する場合は、Boost.Intrusiveの unordered_set 。私は実装を見ていませんが、ほぼ確実に1つ以上のツリー型のラッパーです。 std::setとstd::mapは通常、赤黒ツリーのラッパーとして実装されます（私が調べたすべての標準ライブラリ実装で、GCC、MSVC、およびApacheのstdcxx）。また、libstdc ++がツリー実装を<map>および<set>でどのようにラップするかについても説明します。それは定型的なもので、多くは退屈ですが、どちらのタイプもほとんどすべての作業をツリーに委ねます。 Boost.Intrusiveのunordered_setでは、ほぼ同様のことが起こります。マップインターフェイスと設定インターフェイスの違いを確認し、それをunordered_mapをmapに変更するための基礎として使用する必要があります。

後者を行いました。ちょっと面倒ですし、ユニットテストを書くことを強くお勧めします（またはlibstdc ++またはBoost.Intrusiveに付属しているものを盗む）。しかし、それは実行可能です。また、SGI（ set 、 map ）または libstdc ++

更新：なぜマップを実行しないのかがわかりました。侵入型コンテナでは、格納する値型にデータ構造のノード情報を埋め込む必要があります。マップの場合、値とキーの両方に対してこれを行う必要があります。これが不可能というわけではありませんが、setの標準実装では、value_type sと同様に same 内部型を使用します。ただし、これらの内部タイプには one <=>変数のみがあります。キーと値を保存するために、キーと値をその変数にコピーし、ノードに保存します。侵入型（つまりコピーなし）でそれを行うには、その実装型をセットと互換性がないように変更する必要があります。キーと値への参照を別々に格納する必要があります。そのためには、使用する実装を変更する必要があります（おそらく<=>）。再び不可能ではありませんが、ライブラリの設計者は深刻なコードの重複を避けようとしている可能性が高いため、これを実装する簡単な方法がないため、マップを除外することにした可能性があります。

それは理にかなっていますか

Answer 2

この質問が聞かれてから長い時間が経ちましたが、ここに来る人々はunordered_setをマップとして使用する方法に興味を持つべきだと思います。解決策は、高度な挿入メソッドを使用することです。同じvalue_type内のキーとその値、および insert_check および insert_commit 。