2

簡単な質問ですが、答えは私にはわかりません。パフォーマンス上の理由から、パフォーマンスの観点から、次のシナリオでどのマップタイプ（または非マップタイプ？）のコンテナーを使用するのが最適ですか。

  • キーは符号なし整数であり、
  • 挿入は頻繁です、
  • 読み取りアクセスはさらに頻繁でランダムアクセスですが、
  • アイテムは昇順のキー値で挿入されます（最初に挿入されたアイテムにはキー0、次の1つのキー1など）。
  • アイテムはランダムに削除されます（対応するアイテムが削除されたため、遅かれ早かれキーのリストに「穴」ができます）。取り外しは挿入とほぼ同じ頻度です。

std::mapキーの昇順と頻繁な削除は、検索ツリーの継続的なリバランスを意味しているように思われるため、使用することを躊躇します。これは、パフォーマンスの無駄に思えます。

言い換えれば、アイテムのキーが何であるか、そしてキーが挿入のために表示される順序さえも事前に知っているという事実からパフォーマンスを得ることができますか？（アイテムの総数はわかりませんが。）

4

2 に答える 2

4

stl::mapハッシュと比較するためのプロファイリングだけでも--を使用する場合は、「アイテムはキー値の昇順で挿入される」という知識を使用stl::mapして、挿入にヒントを与えることで挿入操作の効率を大幅に向上させることができます。電話：

iterator insert ( iterator position_hint, const value_type& x );

...ここで、position_hintたとえば、挿入された前のアイテムへのイテレータになります。

于 2012-10-27T08:28:30.500 に答える
3

メモリに問題がない場合は、std::vectorカスタムタイプのを使用してみませんか？すべての要素が順番に並んでいるため、アクセス時間を最速にすることができ、要素が削除された場合はフラグを保存するだけです。このプロキシクラスについて考えてみましょう。

template<typename RealType>
class MyProxy {
public:
    RealType instance;
    bool isused;


    MyProxy(RealType) { /* TODO */ }
};

その後、あなたの中で使用されますstd::vector：

std::vector<MyProxy<MyRealType> > vec;

ルックアップの場合は、インデックスがの範囲内にあるかどうか、std::vectorおよびisusedフラグがであるかどうかを確認する必要がありtrueます。削除するには、インデックスの要素を取得しi、フラグをに設定しfalseます。挿入するには、の代わりにpush_backの新しいインスタンスを作成する必要があります。MyProxy<MyType>MyType

このアプローチの欠点は、もちろん、std::vectorが絶えず増加していることです。そのため、メモリ消費を監視し、最終的には解放する必要がありますvectorが、これはおそらくルックアップ、挿入、および削除の最速の方法です。

于 2012-10-27T08:23:38.500 に答える