Container mit zwei Indizes (oder eine Verbindung Index)

Question

Ich habe eine Klasse wie dieses

class MyClass 
{ 
    int Identifier; 
    int Context; 
    int Data; 
} 

und ich plane es in einem STL-Container zu speichern, wie

vector<MyClass> myVector; 

aber ich werde zugreifen müssen entweder durch den extenalen Index (unter Verwendung myVector[index]); und die Kombination von Identifier und Context die in diesem Fall ich eine Suche mit etwas führen würde wie

vector<MyClass>::iterator myIt; 
for(myIt = myVector.begin(); myIt != myVector.end(); myIt++) 
{ 
    if((myIt->Idenfifier == target_id) && 
     (myIt->Context == target_context)) 
     return *myIt; //or do something else... 
} 

Gibt es einen besseren Weg, die Daten zu speichern oder einen Index?

Answer 1

Boost::Multi-Index hat genau diese Funktionalität, wenn Sie sich die Boost-Abhängigkeit leisten können (nur Header). Sie würden einen random_access Index für den Array-artigen Index und entweder, hashed_non_unique, ordered_unique oder ordered_non_unique (abhängig von Ihren gewünschten Eigenschaften) mit einem Funktor verwenden, der Identifier und Kontext miteinander vergleicht.

Answer 2

Ja, aber wenn Sie Geschwindigkeit wollen, müssen Sie Raum opfern. Speichern Sie es in einer Sammlung (wie einem STL-Set) mit dem Bezeichner/Kontext als Schlüssel, und speichern Sie es gleichzeitig in einem Vektor. Natürlich möchten Sie nicht zwei Kopien der Daten selbst, also speichern Sie sie im Set mit einem Smart Pointer (auto_ptr oder variant) und speichern Sie sie im Vektor mit einem dummen Zeiger.

Answer 3

Wir müssen Ihre Verwendung kennen. Warum müssen Sie in der Lage sein, sie nach Index zu bekommen, und wie oft müssen Sie den Container nach einem bestimmten Element durchsuchen.

Wenn Sie es in einem std::set speichern, wird Ihre Suchzeit mit O (ln n) sein, aber Sie können sie nicht per Index referenzieren.

Wenn Sie eine std::vector verwenden, können Sie sie indizieren, aber Sie müssen std::find verwenden, um ein bestimmtes Element zu erhalten, das O (n) sein wird.

Aber wenn Sie einen Index benötigen, um es an andere Dinge zu übergeben, könnten Sie einen Zeiger verwenden. Verwenden Sie einen Satz für eine schnellere Suche und übergeben Sie Zeiger (keine Indizes) an bestimmte Elemente.