研究プロジェクトに役立つデータ構造のアイデアがあり、それに相当する名前または STL が既にあるかどうかを確認したい場合:
サイズのスパース配列をポインターnの配列として作成します。sqrt(n)
に項目を挿入するiには、 のポインターに移動しi/sqrt(n)ます。そのポインタが の場合null、サイズ の新しい配列に割り当てますsqrt(n)。アイテムを新しい配列の位置に挿入しますi mod sqrt(n)。
O(sqrt(n))利点は単純です。最初はスペースしか必要としない大きな配列を作成できます。一定時間内に任意の要素にアクセスでき、すべてのn位置にスペースを割り当てる必要なく、配列の一部を埋めることができます。
これはすでにハッシュテーブルのバケット化に使用されている可能性があり、別のアプリケーション (非常に大きな DNA シーケンスのコンティグのメモ化) を念頭に置いています。私の質問は: これに名前はありますか? 私が使用できる一般的な実装はありますか?