一貫したパフォーマンスのための高速コンテナ

Question

頻繁な追加/削除をサポートするためのコンテナを探しています。私はコンテナがどれだけ大きくなるかわからないが、巨大な再割り当てのために屋台を望んでいない。私は、パフォーマンスと一貫した振る舞いの間に良いバランスが必要です。

最初は、std :: tr1 :: unordered_mapを考慮しましたが、データセットの上限がわからないため、衝突によって実際にunordered_mapのパフォーマンスが低下する可能性があります。それは良いハッシュ関数の問題ではないので、マップの占有率がバケット数の半分以上であれば、衝突が問題になる可能性があるためです。

私はstd :: mapを検討していますが、衝突の問題はありませんが、ログ（n）のパフォーマンスしかないためです。

unordered_mapのターゲットサイズがわからないときに、インテリジェントに衝突を処理する方法はありますか？私が想像するこの状況を処理するための他のアイデアは珍しくありませんか？

ありがとう

Answer 1

これは実行時のコンテナです。

最後に追加していますか（push_backなど）か、正面か中央ですか？ ランダムな場所で削除していますか、それとも何ですか？

どのように情報を参照していますか？ ランダムに、または正面または背面から、または何ですか？

ランダムアクセスが必要な場合は、配列またはハッシュに基づくものが優先されます。

再割り当てが大きな問題である場合は、ツリーやリストのようなものが必要です。

あなたは常にnew -ing（およびdelete -ing）あなたはコンテナに入れているオブジェクト、ある場合はそうであっても、一人でいることが、その場合には、あなたが見つけるかもしれない、 時間の大部分を消費する可能性があります使用済みのオブジェクトを迷惑メールリストに保存してリサイクルすることは理にかなっています。

私の提案は、コンテナの選択に悩まされるのではなく、1つだけを選んでプログラムを書いてからtune it, as in this exampleと書いてください。 あなたが選んだものとは無関係に、恐らくそれを変更したいかもしれません。 私がこの例で見つけたのは、既存のコンテナクラスがプログラミングの容易さによって、その存在を正当化することであり、できるだけ高速ではありませんでした。

あなたのプログラム内のいくつかの他のアクティビティが支配的なコストとなり、それを縮小できない限り、 はわかりませんが、最終的なスピードのスピードはデータ構造を手動でコーディングする必要があります。

Answer 2

どのようなアクセスが必要ですか？シーケンシャル、ランダムアクセス、キーによる検索？さらに、順序付けされていないマップを手動で再ハッシュしたり（rehashメソッド）、負荷率を設定することができます。いずれにしても、チェーンが長すぎるとき（すなわち、負荷率を超えたとき）にハッシュが再構築される。さらに、ハッシュテーブルのスローダウンポイントは、50％ではなく、80％に満たないときです。

実際には、hereなどのドキュメントをお読みください。