boost :: multi_index_container mit random_access und ordered_unique

Question

Ich habe ein Problem bekommen boost::multi_index_container Arbeit mit Random-Access und mit orderd_unique zugleich. (Es tut mir leid für die lengthly Frage, aber ich denke, ich sollte ein Beispiel verwenden ..)

Hier ein Beispiel: Angenommen, ich N Objekte in einer Fabrik produzieren will und für jedes Objekt, das ich eine Forderung zu erfüllen habe (diese Forderung bei der Erstellung des Multi-Index bekannt ist). Nun, in meinem Algorithmus ich Zwischenergebnisse, die ich in der folgenden Klasse speichern:

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

Der Vektor parts descibes, welche Objekte erzeugt werden (seine Länge N, und es ist lexikographisch kleiner als meine coresp nachfrage Vektor!) - für jeden solchen Vektor ich die used_time wie gut kennen. Zusätzlich ich für diesen Vektor produzierter Objekte einen Wert erhalten.

habe ich eine andere Einschränkung, so dass ich nicht jedes Objekt erzeugen kann - mein Algorithmus mehr intermediate_result-Objekte in einer Datenstruktur speichern muss. Und hier boost::multi_index_container verwendet wird, da das Paar von parts und used_time eine einzigartige intermediate_result beschreibt (und es soll in meinen Daten-Struktur eindeutig sein), aber der max_value ist ein weiterer Index Ich werde prüfen habe, weil mein Algorithmus immer die intermediate_result muss mit der höchste max_value.

Also habe ich versucht boost::multi_index_container mit ordered_unique<> für meine "Teile & used_time-pair" und ordered_non_unique<> für meine max_value (verschiedene intermediate_result-Objekte den gleichen Wert haben kann) verwendet werden.

Das Problem ist: das Prädikat, das die „Teile & used_time-Paar“ ist kleiner, verwendet std::lexicographical_compare auf meinem parts-Vektor und ist daher sehr langsam für viele intermediate_result-Objekte zu entscheiden, benötigt wird. Aber es wäre eine Lösung. Meine Nachfrage für jedes Objekt ist nicht so hoch, deshalb konnte ich speichere auf jedem möglich Teile-Vektor die Zwischenergebnisse eindeutig durch seine used_time

Zum Beispiel: Wenn ich eine bedarf Vektor ( 2 , 3 , 1) habe, dann brauche ich eine Datenstruktur, die speichert (2+1)*(3+1)*(1+1)=24 möglich, Teile-Vektoren und auf jeden solchen Eintrag, um die verschiedenen used_times, das eindeutig sein müssen! (Die kleinste Zeit Speicherung reicht nicht aus - zum Beispiel: wenn meine zusätzliche Einschränkung ist: eine vorgegebene Zeit für die Produktion genau zu treffen)

Aber wie kombiniere ich einen random_access<>-Index mit einem ordered_unique<>-Index?
( Example11 nicht helfen mich auf diesem ..)

Answer 1

(Ich hatte eine eigene Antwort zu verwenden, um Code-Blöcke zu schreiben - sorry)

Die composite_key mit used_time und parts (wie Kirill V. Lyadvinsky vorgeschlagen) ist im Grunde, was ich bereits implementiert haben. Ich möchte von der lexikographischen des parts-Vektor zu vergleichen, um loszuwerden.

Angenommen ich die needed_demand gespeichert habe irgendwie dann könnte ich eine einfache Funktion schreiben, die den korrekten Index innerhalb einer Schreib-Lese-Daten-Struktur wie die zurückgibt:

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

Natürlich kann diese effizient umgesetzt mehr werden, und dies ist nicht die einzige mögliche Index Bestellung für den benötigten Bedarf. Aber nehmen wir an, diese Funktion existiert als Mitglied-Funktion von intermediate_result! Ist es möglich, so etwas zu schreiben lexicographical_compare zu verhindern?

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

Wenn dies möglich ist und ich initialisiert, um den Multi-Index mit allen möglichen parts-Vektoren (dh in meinem Kommentar über I 24 leere Karten in meiner Datenstruktur geschoben haben würde), findet dies den richtigen Eintrag für einen bestimmten intermediate_result in konstanter Zeit (nach dem richtigen Index mit get_index Berechnung)?
Ich habe dies zu fragen, weil ich nicht ganz sehen, wie sie der random_access<> Index mit dem ordered_unique<> Index verknüpft ist ..

Aber vielen Dank für Ihre Antworten so weit !!

Answer 2

Um zwei Indizes verwenden können Sie die folgende schreiben:

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

könnten Sie verwenden composite_key für used_time auf dem ersten und vector nur bei Bedarf zu vergleichen. Abgesehen davon, bedenken Sie, dass Sie Mitglied Funktion als Index verwenden können.