非固有キーを使用したダイレクトアドレステーブル

ダイレクトアドレステーブルを設計する際に、別個でないキーを使用するなど、練習問題に取り組んでいます。 INSERT、DELETE、およびSEARCHはO（1）時間で実行する必要があるという制約があります。引数はオブジェクトを設定するポインタです。非固有キーを使用したダイレクトアドレステーブル

明らかな解決策の1つは、テーブルエントリがリンクされたリストの先頭を指しているチェーン化を使用することです（NULLにすることもできます）。このような連鎖では、INSERTとDELETEはO（1）時間で実行されますが、SEARCHは実行されません。提案があれば幸いです。

2012-05-04 Iceman

研究あなたは{ユニークな、非ユニーク}と{キー、キーの値を}保存するかどうかに応じて、STLの連想コンテナstd::unordered_set、std:unordered_map、std::unordered_multisetの設計、std::unorderd_multimap。 C++ 11コンパイラ（MSVC++> = 2010またはgcc> = 4.4など）がない場合は、Boost.Unorderedを使用できます。

UPDATE： あなたは、特にCライブラリを探している場合は：彼は非個別のキーを必要とするが、彼はマルチマップを使用することができhttp://attractivechaos.wordpress.com/2008/09/02/implementing-generic-hash-library-in-c/

2012-05-04 14:18:37 TemplateRex

を見てみましょう（C++ 11はオプションですとにかく場合） –

感謝。ええ、もしC++ 11がオプションであれば。私はCでソリューションを設計し、タグを編集しようとしています。 – Iceman

@Iceman私はC実装へのリンクを使って自分のアンカーを更新しました。 – TemplateRex

答えて