boost :: multi_index_container con random_access e ordered_unique

Question

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 ..)

Answer 1

(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 !!

Answer 2

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.