Discussion :

[ZaaN]

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

Des idées d'implementation ?

merci d'avance

le conteneur :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

la fonction de recherche :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Laurent Gomila]

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

[ZaaN]

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 ?

[r0d]

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.

[Laurent Gomila]

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é).

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

[r0d]

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

[Laurent Gomila]

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