後押し:: multi_index_containerをrandom_accessとordered_uniqueで
-
19-09-2019 - |
質問
私は、ランダムアクセスと同時にorderd_uniqueで問題になっboost::multi_index_container
の仕事を持っています。 (私はlengthly質問には申し訳ないが、私は、私は例を使用すべきだと思う...)
ここでは例:私は工場でN個のオブジェクトを生成すると仮定し、各オブジェクトのために、私は(この要求は、マルチインデックスの作成時に知られている)達成する需要を持っています。 まあ、私のアルゴリズムの中に、私は次のクラスに格納中間結果を取得ます:
class intermediate_result
{
private:
std::vector<int> parts; // which parts are produced
int used_time; // how long did it take to produce
ValueType max_value; // how much is it worth
};
ベクトルparts
は(!その長さがNであり、それは私のcoresp需要ベクトルその後、辞書的に小さい)オブジェクトが生成され、descibes - 各ようなベクターのために私は同様used_timeを知っています。さらに私は、生成オブジェクトのこのベクトルの値を取得します。
私は別の制約を持って - 私のアルゴリズムは、データ構造内に複数のintermediate_result
-オブジェクトを格納する必要があります。そして、ここboost::multi_index_container
とparts
のペアがユニークused_time
を記述しているのでintermediate_result
は、使用されている(そしてそれは私のデータ構造内で一意でなければなりません)が、私のアルゴリズムは常に持つmax_value
を必要とするためintermediate_result
は、私が検討する必要があります別の指標であります最高max_value
ます。
だから私は(異なるboost::multi_index_container
-オブジェクトが同じ値を持つ場合があります)私のordered_unique<>
のために私の「パーツ&used_time・ペア」のためのordered_non_unique<>
とmax_value
でintermediate_result
を使用しようとしました。
問題がある:小さくなる「パーツ&used_time・ペア」を決めるために必要とされる述語は、私のstd::lexicographical_compare
ベクトルにparts
を使用していますので、多くのintermediate_result
-オブジェクトのための非常に遅いです。
しかし、解決策があるでしょう:各オブジェクトのための私の需要はそれほど高くないので、私はそのused_time
によって一意の可能の部分ベクトルに中間結果を格納することができます。
たとえば:私は、需要ベクトル( 2 , 3 , 1)
を持っているならば、私は(2+1)*(3+1)*(1+1)=24
可能部品ベクトルと、そのような各エントリ上で一意である必要はあり異なるused_timesを、格納するデータ構造を必要とします! (最小の時間を記憶するだけでは不十分である - 例えば:私の追加の制約がある場合:正確に製造するために与えられた時間を満たすために)
しかし、どのように私はrandom_access<>
インデックスとordered_unique<>
インデックスを組み合わせていますか?
( Example11 の助けにはなりませんでしたこの1の私...)
解決 2
(私は、コードブロックを記述するために自身の答えを使用していた - !申し訳ありません)。
(キリルV. Lyadvinskyが示唆されているように)composite_key
とused_time
とparts
は、私はすでに実装した内容は基本的です。私はparts
-ベクトルの比較辞書式を取り除きたい。
私は何とか、私はそのようなランダム・アクセス・データ構造内の正しいインデックスを返す単純な関数を書くことができneeded_demandを保存したとし
int get_index(intermediate_result &input_result) const
{
int ret_value = 0;
int index_part = 1;
for(int i=0;i<needed_demand.size();++i)
{
ret_value += input_result.get_part(i) * index_part;
index_part *= (needed_demand.get_part(i) + 1);
}
}
これは明らかに、より効率的に実装することができ、これは必要な需要のための唯一の可能なインデックスの順序ではありません。しかし、ここでは、この機能はintermediate_result
のメンバー関数として存在すると仮定してみましょう! lexicographical_compare
を防ぐために、このような何かを書くことが可能ですか?
indexed_by<
random_access< >,
ordered_unique<
composite_key<
intermediate_result,
member<intermediate_result, int, &intermediate_result::used_time>,
const_mem_fun<intermediate_result,int,&intermediate_result::get_index>
>
>
>
これは特定のための右のエントリを見つけない、これは可能であると私はすべての可能なparts
ベクトル(つまり、私は私のデータ構造で24空のマップをプッシュしただろう上記の私のコメントで)とマルチインデックスを初期化した場合(intermediate_result
で正しい指標を計算した後)、一定時間内にget_index
?
私は非常に表示されていないので、私は、これを聞いている、random_access<>
インデックスはordered_unique<>
インデックスとリンクされているか..
しかし、これまでのところ、あなたの答えをありがとうございました!!
他のヒント
あなたは以下のように書くことができる2つのインデックスを使用するには
indexed_by<
random_access< >,
ordered_unique<
composite_key<
intermediate_result,
member<intermediate_result, int, &intermediate_result::used_time>,
member<intermediate_result, std::vector<int>, &intermediate_result::parts>
>
>
>
あなたは必要な場合のみ最初とcomposite_key
でused_time
を比較するためvector
を使用することができます。それに加えて、あなたはインデックスとしてメンバ関数を使用することができることを覚えておいてください。