Bonne structure de données pour la recherche d'un mappage d'ID vers un ensemble d'éléments (C++)

Question

Pas d'accentuation, juste STL s'il vous plaît.

J'ai un mappage Foo * de classe à un ensemble de pointeurs de classe ID.

et j'ai besoin de mapper un pointeur sur une instance d'ID à une classe FOO.

dire que j'ai cette fonction:

void FindXXX(const ID* pID) 
{ 

/*find the containing FOO class quickly, but not at expense of an ugly code*/ 

} 

en ce moment je la carte chaque ID * à * toto ayant ainsi quelque chose comme ça

carte myMap; ce que je pense est un peu laide et redondant.

S'il vous plaît suggèrent

Answer 1

en ce moment je mapper chaque ID * à FOO * ainsi avoir quelque chose comme ça

carte myMap; ce que je pense est un peu moche et redondant.

Je suppose que vous avez quelque chose comme ceci:

map<ID*, Foo*> myMap; 

Pourquoi serait-ce laid?

Answer 2

Sons comme un travail pour std :: carte, mais vos remarques semblent indiquer que vous ne voulez pas utiliser un, est-ce vrai?

std::map <key_type, data_type, [comparison_function]> 

Answer 3

Eh bien, cela dépend de la taille des deux ensembles (ID * et foo *). Je suppose que vous avez #ID >> #FOO, et #FOO assez grand pour ne pas justifier la recherche linéaire à travers eux.

Je suppose ID < -> Foo est un mappage un-à-plusieurs.

Vous pouvez stocker la cartographie comme un ensemble>> et les trier cette façon: l'ensemble est trié dans l'ordre croissant d'ID * (ordre de valeur de pointeur serait bien) l'ensemble> est trié dans l'ordre croissant du valeur du premier identifiant * dans la seconde de la paire.

Lors de la recherche, vous devez trouver la plage de Foo * qui a un ensemble où le premier ID * a une valeur (pointeur) inférieure à l'élément recherché, et la dernière une valeur plus élevée. Cela se traduira par un ensemble d'objets beaucoup plus petit, espérons-le, sur leur ensemble. Passez ensuite ces étapes et trouvez celle qui contient l'ID * que vous recherchez.

Vous aurez besoin d'un comparateur pour la paire> comme ceci:

typedef Item pair<Foo*, set<ID*> >; 

// Sorter in ascending order of first ID*, then ascending order of last ID* 
struct IDOrdering: public binary_function<Item, Item, bool> { 
    bool operator()(const Item& lhs, const Item& rhs) { 
    return *(lhs.second.begin()) < *(rhs.second.begin()) 
     || *(lhs.second.rbegin()) < *(rhs.second.rbegin()); 
    } 
}; 


// your global map 
set<Item, FirstIDOrdering> myMap; 
typedef set<Item, FirstIDOrdering>::iterator ItemIterator; 

// search for the item 
Foo* FindXXX(const ID* pId) { 
    Item criterion; 
    criterion.second.insert(pId); 
    ItemIterator start = myMap.lower_bound(criterion); 
    while (start != myMap.end() && *(start->second.rbegin()) > pId) { 
    if (start->second.count(pId)) 
     return start->first; 
    } 
    return NULL; 
} 

Vous pouvez enregistrer une mémoire ici, comme * Foo * et ID sont stockés qu'une seule fois, mais il est au prix d'une certaine complexité et probablement une performance. Notez que cet exemple ne prend pas en compte toutes les sortes de cas de bordure (listes vides), et vous devez être prudent lors de l'insertion d'un nouvel élément dans myMap global, car vous pouvez ajouter un nouvel ID * à la liste d'une paire <>, mais vous devez vous assurer que tout l'ensemble est à nouveau trié, afin que la recherche fonctionne réellement.Il est cependant difficile de savoir ce qui serait le mieux pour vous, car il y a très peu d'informations sur ce que vous essayez d'atteindre: est le Foo * dans les millions, l'ID * dans les millions, est cette fonction résoudre ID * à Foo * appelé souvent? Dans une section critique de performance de votre système? Tout cela est utile pour faire des compromis sur la lisibilité, la complexité et la performance du code.