0

次を満たすデータ構造が必要です。

  • 任意の数の要素を格納します。各要素は 10 個の数値メトリックによって記述されます
  • log nメトリックのいずれかによる要素の高速 () 検索を可能にします
  • log n新しい要素の高速 () 挿入が可能
  • 素早い ( log n) 要素の削除が可能

そして、要素の構築に費用がかかると仮定しましょう。

次のプランを思いついた

  • すべての要素を DATA というベクトルに格納します。
  • std::sets10 のメトリックごとに 1 つずつ、 10 を使用します。それぞれstd:set軽量で、 vector へのインデックスである整数のみが含まれますDATA。比較演算子は、DATA 内の適切な要素を「検索」し、適切なメトリックを選択します。
template< int C >
struct Cmp
{
    bool operator() (int const a, int const b)
    {
        return ( DATA[a].coords[C] != DATA[b].coords[C] ) 
           ? ( DATA[a].coords[C] < DATA[b].coords[C] )
           : ( a < b );
    }
};

要素が変更されたり、ベクターから削除されたりすることはありません。新しい要素が DATA にプッシュ バックされ、そのインデックス ( DATA.size()-1) がセット ( ) に挿入されますset<int, Cmp<..> >。要素を削除するには、削除されたことを示すフラグを要素に設定し (実際にはDATAベクトルから削除せずに)、10 個すべての std::set から要素インデックスを削除します。

DATAこれは、グローバル変数である限り正常に機能します。(また、テンプレート化された構造体 Cmp をグローバル変数に依存させることで、型システムを悪用しています。)

ただし、DATAベクトルと std::set の ( ) をクラス内に囲み、それらでset<int, Cmp<...> >「インデックス」することはできませんでした。まず、外部クラス内で定義された比較演算子 Cmp は、外部クラスのフィールドにアクセスできません (したがって、DATA を評価できません)。Cmp は std::set によって構築されており、std::set は引数を持たないコンストラクターとの比較演算子を想定しているため、ベクトルを Cmp コンストラクターに渡すこともできません。DATAstd::sets

私は C++ 型システムに反対し、型システムが意図的に私を妨げている何かを達成しようとしているような気がします。(実行時にのみ構築される変数に std::set を依存させようとしています。)そして、型システムが私のやり方を好まない理由は理解していますが、これは正当な使用例だと思います。

std::set/red-black ツリーの再実装を提供せずに、上記のデータ構造/クラスを実装する方法はありますか? 私がまだ考えていないトリックがあるといいのですが。(そうです、boost には何かがあることは知っていますが、標準ライブラリに固執したいと思います。)

4

1 に答える 1

0

foo「値で調べる」のようなものを読んだときbar、私の最初の反応は amap<>または類似のものを使用することです。ただし、これにはいくつかの意味があります。

  1. 内のキーstd::map(または 内の値std::set) は一意であるため、2 つの要素が同じキーを共有することはできず、したがって 2 つのデータ オブジェクトが同じメトリックを持つことはできません。複数のデータ オブジェクトが同じメトリックを持つことができる場合 (これは質問からは明らかではありません)、std::multimap(またはstd::multiset) を使用しても機能します。
  2. キーが定数で、要素自体に格納されている場合、 a を使用するのset<data*,cmp>が一般的な方法です。コンパレータは、オブジェクトから対応するフィールドを取得して比較します。ルックアップでは、一時オブジェクトを作成し、それで find() を使用する必要があります。一部の実装には、別のタイプでの検索を可能にする拡張機能もあります。これにより、これははるかに簡単になりますが、移植には実際の作業が必要になります。 ただし、キーとして使用されるフィールドが一定のままであることが重要です。それらを変更すると、暗黙的にset<>. set<>これが、 aの要素が事実上一定である理由です。iterator値型として定数があります。ただし、ポインターを格納すると、定数ポインターは定数へのポインターとは異なるため、簡単に回避できます。それで足を撃たないでください！
  3. メトリクスがオブジェクト自体のプロパティではない場合 (またはメトリクスを冗長に格納してもかまわない場合) は、 を使用するのstd::mapが自然な選択です。メトリックに応じて、同じオブジェクトを複数のキーの下に格納することは、別々のコンテナ ( map<int,data*> c[10];) で行うことができます。pair<metric,value>ただし、たとえば aをキー ( ) として使用して、単一のマップでそれを行うことができますmap<pair<int,int>,data*> c;。
  4. a を使用しvector<>て実際の要素を格納し、それらをマップ内のポインターまたはインデックスとしてのみ参照することは確実に機能します。ただし、これにより、セットまたはマップを使用した上記のアプローチが機能するようになるため、ポインターを使用します。それがなければ、コンパレータはコンテナへの参照を保存する必要があり、現時点ではグローバル DATA コンテナを使用するだけです。ただし、これをベクターで機能させるのは難しいです。これは、正しく指摘したように、成長時に要素を再割り当てするためです。std::listまたはのような別のコンテナタイプを検討しstd::dequeます。前者でも要素を消去できますが、要素ごとのオーバーヘッドが高くなります。後者の要素あたりのオーバーヘッドは比較的低く、わずかに上回っていますstd::vector. その後、ポインターの代わりにイテレーターを格納することもできます。これは、そのために「チェック済み STL」を使用すると、デバッグに役立ちます。それでも、まだどこかで参照されているオブジェクトと参照されていないオブジェクトを手作業で記録する必要があります。
  5. 別のコンテナーを使用する代わりに、要素を動的に割り当てることもできますが、それ自体にはいくらかのオーバーヘッドがあります。要素ごとのオーバーヘッドが問題にならない場合は、参照カウント スマート ポインターを使用できます。アプリケーションがワンショット プロセスの場合は、生のポインターを使用して、OS が終了時にメモリを再利用できるようにすることもできます。

データ オブジェクトの複数のコピーを保存することはオプションではないと想定していることに注意してください。その場合は、map<int,data> m[10];各マップがデータ オブジェクトの独自のコピーを格納する を使用することもできます。その後、簿記の問題はすべて解決されますが、10 倍のオーバーヘッドが発生します。

于 2014-06-25T19:44:37.447 に答える