boost :: multi_index_container con random_access e ordered_unique
-
19-09-2019 - |
Domanda
Ho un problema trovare lavoro boost::multi_index_container
con accesso casuale e con orderd_unique allo stesso tempo. (Mi dispiace per la domanda lengthly, ma penso che dovrei usare un esempio ..)
Ecco un esempio: Supponiamo che io voglio produrre N oggetti in una fabbrica e per ciascun oggetto ho una domanda per soddisfare (questa domanda è noto al momento della creazione del multi-indice). Beh, nel mio algoritmo ottengo risultati intermedi, che ho Conservare nella seguente classe:
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
};
Il vettore parts
descibes, quali oggetti sono prodotti (la sua lunghezza è N ed è lexicographically più piccolo allora la mia domanda coresp-vector!) - per ogni tale vettore conosco l'used_time pure. Inoltre ho un valore per questo vettore di oggetti prodotti.
ho avuto un altro vincolo in modo che non riesco a produrre ogni oggetto - il mio algoritmo ha bisogno di memorizzare diversi intermediate_result
-oggetti in una struttura di dati. E qui boost::multi_index_container
viene utilizzato, perché la coppia di parts
e used_time
descrive una intermediate_result
unico (e dovrebbe essere unico nella mia struttura di dati), ma la max_value
è un altro indice che dovrò prendere in considerazione, perché il mio algoritmo ha sempre bisogno del intermediate_result
con il più alto max_value
.
Così ho cercato di usare boost::multi_index_container
con ordered_unique<>
per i miei "parti e used_time-coppia" e ordered_non_unique<>
per il mio max_value
(diversi intermediate_result
-oggetti possono avere lo stesso valore).
Il problema è: il predicato, che è necessario per decidere quali "parti e used_time-pair" è più piccolo, utilizza std::lexicographical_compare
sul mio parts
-vettore e quindi è molto lento per molti intermediate_result
-oggetti.
Ma ci sarebbe una soluzione:. La mia domanda per ogni oggetto non è così in alto, quindi ho potuto memorizzare su ogni possibile parti-vector i risultati intermedi unicamente dalla sua used_time
Ad esempio: se ho un ( 2 , 3 , 1)
domanda-vector poi ho bisogno di una struttura di dati che memorizza (2+1)*(3+1)*(1+1)=24
eventuali parti-vettori e su ciascuna di tali voci diverse used_times, che devono essere unico! (Memorizzare il tempo più piccolo non è sufficiente - ad esempio: se il mio ulteriore vincolo è: per soddisfare un determinato momento esattamente per la produzione)
Ma come faccio a combinare un random_access<>
-indice con un ordered_unique<>
-index?
( Example11 non ha aiutato me su questo ..)
Soluzione 2
(ho dovuto usare una risposta proprio a scrivere codice-blocchi - scusate!)
Il composite_key
con used_time
e parts
(come suggerito Kirill V. Lyadvinsky) è sostanzialmente quello che ho già implementato. Voglio eliminare il lessicografico confrontare della parts
-vettore.
Supponiamo che io ho memorizzato il needed_demand in qualche modo allora potrei scrivere una funzione semplice, che restituisce l'indice corretto all'interno di un accesso casuale di dati-struttura come quella:
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);
}
}
Ovviamente questo può essere realizzato in modo più efficiente e questo non è l'unico ordinamento dell'indice possibile per la richiesta necessaria. Ma supponiamo questa funzione esiste come membro-funzione della intermediate_result
! E 'possibile scrivere qualcosa di simile per evitare che 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>
>
>
>
Se questo è possibile e io inizializzato il multi-indice con tutti i possibili parts
-vettori (per esempio nel mio commento di cui sopra avrei spinto 24 mappe vuote nella mia struttura di dati), fa questo trovare la voce giusta per un determinato intermediate_result
in tempo costante (dopo aver calcolato l'indice corretto con get_index
)?
Mi chiedo questo, perché non ho ben capito, come l'indice random_access<>
è collegata con l'indice ordered_unique<>
..
Ma grazie per le vostre risposte finora !!
Altri suggerimenti
Per usare due indici si potrebbe scrivere il seguente:
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>
>
>
>
Si potrebbe utilizzare composite_key
per confrontare used_time
in un primo momento e vector
solo se necessario. Oltre a questo, tenere a mente che è possibile utilizzare la funzione di membro come indice.