Diminuer complexite pour la recherche de valeur dans un vector

Bonjour,

Voila j'ai en fait un type vector qui peut atteindre une très grande taille n.
A un moment je dois rechercher une valeur dans ce vector, et cela doit être effectue n fois.
Ce que je fais en ce moment est quelque chose de ce genre ou t est de type vector avec des doublons.

Code:

---

1 2 3 4 5

int a = 2; for(int i = 0 ; i < n ; i++) if(t[i] == a) return i;

---

Cette recherche de valeur a une complexité O(n) et j'aimerais la baisser au mieux a un ordre O(1). J'ai vu qu'il y avait le type map mais je ne sais pas si c'est la solution optimale.

Je souhaiterais connaitre votre avis la dessus avant de me lancer. :P
Merci !

Si les valeurs de ton vecteur ne sont pas ordonnancées d'une certaine façon je ne vois pas trop comment tu pourrais réduire la complexité.

J'imagine que tout le monde aimerait faire du O(1)...

Les set et multiset on une fonction find() en O(n*log(n)).
Tu ne trouveras pas mieux.

Tu peux obtenir une complexité d'accés moyenne en temps constant en utilisant une table de Hashage (unordered_set en C++2011 pas exemple). Il faut cependant qu'il existe une fonction de hashage pour tes objets.

Sinon tu peux peut-etre réduire ce temps de recherche si tu t'assures que ton vecteur reste trié par exemple, en appliquant un dichotomie la complexité devrait dimunué (logarithmique peut-etre, calcul à faire). A voir si le coup pour assurer ce trie tout le long du programme n'est pas trop élévé par rapport à l'utilisation d'une recherche linéaire.

Et enfin tu peux utiliser un conteneur associatif (typiquement set) qui t'assure un complexité logarithmique (et non quasi-linéaire, qui est moins bon que linéaire, comme l'a indiqué oodini). Et ca doit globalement revenir à utiliser un conteneur séquentiel en assurant en permanence qu'il est trié.

Je vous remercie pour vos conseils.
Je vais en tester quelques-uns et je vous tiens au courant ;)