[STL] optimisation d une fonction de recherche dans un set

j aimerais optimiser cette foncton de recherrche avec des algo de la STL si possible. --> :recherch: <-- lol :fou:

Des idées d'implementation ?

merci d'avance

le conteneur :

Code:

---

1 2	typedef std::set<CNCMClic *,CNCMClicCompare> TClicArray; TClicArray m_ClicArray;

---

la fonction de recherche :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

bool CMAClasse::GetClic(T_CLIC _ClicNumber,TClicArray::const_iterator & _itClic) { //TODO optimize this search for(_itClic = m_ClicArray.begin();_itClic!=m_ClicArray.end();_itClic++) { if((*_itClic)->GetClicID() == _ClicNumber) { return true; } } _itClic = m_ClicArray.end(); return false; }

---

Deux possibilités.

Soit ton set est ordonné par le membre recherché (ClicID) et tu peux tirer partie du temps de recherche logarithmique.

Soit ton set est ordonné par autre chose, et je vois mal comment tu pourras aller plus vite qu'en faisant un parcours séquentiel.

Sinon, il faut se tourner vers des conteneurs plus évolués (y en a un dans boost il me semble).

Citation:

---

Envoyé par Laurent Gomila

Soit ton set est ordonné par le membre recherché (ClicID) et tu peux tirer partie du temps de recherche logarithmique.

---

c'est le cas en effet, comment tirer parti du temps de recherche en log ?

Si tu as une liste triée, pourquoi ne pas utiliser une map dont la clé derait ClicId? L'avantage c'est que l'accés serait direct, même pas besoin de recherche.

Citation:

---

c'est le cas en effet, comment tirer parti du temps de recherche en log ?

---

En utilisant la fonction set::find. Bon là où ça peut être pas très pratique, c'est qu'il faut absolument lui passer un élément (donc un CNCMClic* défini avec le ClicID recherché).

Citation:

---

Si tu as une liste triée, pourquoi ne pas utiliser une map dont la clé derait ClicId? L'avantage c'est que l'accés serait direct, même pas besoin de recherche.

---

Lorsque la clé fait partie de l'élément, il vaut mieux std::set, avec std::map tu aurais une duplication de celle-ci. Et puis un accès dans un std::map suppose forcément une recherche ;)

Citation:

---

Envoyé par Laurent Gomila

Et puis un accès dans un std::map suppose forcément une recherche ;)

---

Et oui, logique. C'est l'opérateur [] qui m'a trompé. Il ressemble tellement à un accés sur un tableau... :oops:

Les tables de hachages par contre (qui ne sont pas encore dans le standard) proposent un accès presque direct.