boost :: multi_index_container avec random_access et ordered_unique

Question

J'ai un problème pour obtenir du travail de boost::multi_index_container avec accès aléatoire et orderd_unique en même temps. (Je suis désolé pour la question lengthly, mais je pense que je devrais utiliser un exemple ..)

Voici un exemple: Supposons que je veux produire des objets N dans une usine et pour chaque objet que j'ai une demande à remplir (cette demande est connue lors de la création du multi-index). Eh bien, dans mon algorithme j'obtenir des résultats intermédiaires, que je stocker dans la classe suivante:

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
};

Le parts vectoriel descibes, quels objets sont produits (sa longueur est N et il est lexicographique plus petite que ma demande coresp vecteur!) - pour chaque vecteur Je sais que le used_time aussi bien. De plus je reçois une valeur pour ce vecteur d'objets produits.

Je suis une autre contrainte pour que je ne peux pas produire chaque objet - mon algorithme a besoin de stocker plusieurs objets intermediate_result dans une structure de données. Et ici boost::multi_index_container est utilisé, parce que la paire de parts et used_time décrit un intermediate_result unique (et il doit être unique dans ma structure de données), mais le max_value est un autre indice que je vais devoir considérer, parce que mon algorithme a toujours besoin intermediate_result avec le plus max_value.

J'ai donc essayé d'utiliser boost::multi_index_container avec ordered_unique<> pour mes « pièces et used_time paire » et ordered_non_unique<> pour mon max_value (différents objets intermediate_result-peuvent avoir la même valeur).

Le problème est: le prédicat, qui est nécessaire pour décider « pièces et used_time paire » est plus petite, utilise std::lexicographical_compare sur mon parts vecteur et est donc très lent pour de nombreux objets intermediate_result. Mais il y aurait une solution. Ma demande pour chaque objet est pas élevé, donc je pouvais stocker sur chaque possible pièces vecteur les résultats intermédiaires de façon unique par son used_time

Par exemple: si j'ai une demande ( 2 , 3 , 1) vecteur alors je besoin d'une structure de données qui stocke (2+1)*(3+1)*(1+1)=24 pièces vecteurs possibles et chacune de ces entrées les différents used_times, qui doivent être uniques! (Stockage le plus petit temps est insuffisant - par exemple: si ma contrainte supplémentaire est: pour répondre à un moment donné exactement pour la production)

Mais comment puis-je combiner un random_access<>-index avec un indice ordered_unique<>?
( Example11 n'a pas aidé moi sur ce ..)

Answer 1

(je devais utiliser votre propre réponse à écrire du code blocs - désolé)

Le composite_key avec used_time et parts (comme Kirill V. Lyadvinsky suggéré) est fondamentalement ce que je l'ai déjà mis en œuvre. Je veux me débarrasser de la lexicographique comparer du parts vecteur.

Supposons que je l'ai mis en mémoire les needed_demand en quelque sorte alors je pourrais écrire une fonction simple, qui renvoie l'index correct dans un accès aléatoire des données structure telle que:

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);
    }
}

Il est évident que cela peut être mis en œuvre de manière plus efficace et ce n'est pas la seule commande d'index possible pour la demande nécessaire. Mais supposons que cette fonction existe en tant que membre fonction de intermediate_result! Est-il possible d'écrire quelque chose comme ceci pour éviter 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>
    >
  >
>

Si cela est possible et j'initialisé le multi-index avec tous les parts vecteurs possibles (par exemple dans mon commentaire ci-dessus, je l'aurais poussé 24 cartes vides dans ma structure de données), est-ce trouver la bonne entrée pour une donnée intermediate_result en temps constant (après calcul de l'indice correct avec get_index)?
Je dois demander cela, parce que je ne vois pas tout à fait, comment l'indice de random_access<> est lié à l'indice de ordered_unique<> ..

Mais je vous remercie pour vos réponses à ce jour !!

Answer 2

Pour utiliser deux indices, vous pouvez écrire:

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

Vous pouvez utiliser composite_key pour comparer used_time au premier et vector seulement si nécessaire. En outre, garder à l'esprit que vous pouvez utiliser la fonction de membre comme indice.