以下を達成するための適切な方法を決定しようとしています。
範囲が必要です->特定の範囲内でルックアップを設定します（[0x0 - 0xffffffff]など）。値は範囲の範囲に挿入されます (したがって、T = 一意の文字列を使用している場合)、insert("beef3490", [0x1234, 0xFFFF]); また、1 つの ID に複数の挿入が含まれる場合があり、それらは重複する場合と重複しない場合があります。さらに、重複する他の値が挿入される可能性があり、それらが重複する場所では、結果として一意の文字列のセットを受け取る必要があります。最後に、値を範囲から削除することもできます (必ずしも一致する必要はありませんが、通常は最初の挿入範囲内に含まれます)。
簡単な使用例を次に示します。
insert("beef3490", [0x1234, 0xFFFF])
insert("beef3490", [0x11111, 0x22222])
insert("flam1456", [0x8000, 0xA0000])
remove("beef3490", [0x21000, 0x22000])
lookup(0x0) -> set<>
lookup(0x2000) -> set<beef3490>
lookup(0x9456) -> set<beef3490, flam1456>
lookup(0x21212) -> set<flam1456>
lookup(0x99789) -> set<flam1456>
これは私にとって多くの質問につながります：
この種の問題の一般化された名前、または洞察を見つけることができる同様のタイプの問題はありますか?
次の制約を考えると、理想的な実装は何ですか:
- 高速/非常に高速なルックアップ時間
- メモリ使用量が膨れ上がることはありません (つまり、次の操作は同等のフットプリントを持ちます)。
- [10,20] を挿入、[20,30] を挿入、[14,24] を削除
- [10,15] を挿入、[25,30] を挿入
- 最後と同様に、データ構造は長時間稼働するシステムで安定している必要があります
- 挿入/削除時間は絶対にひどいわけではありません (ルックアップほど速くする必要はありません)。
理想的な実装が与えられた場合、それを C++ で使用するためのアドバイスはありますか
すべての応答とヘルプに感謝します。