Discussion :

[camboui]

J'ai un vector trié et j'aimerais savoir s'il existe une fonction d'insertion toute faite ou si je dois faire d'abord une recherche avec std::lower_bound() puis un std::vector::insert() à l'endroit trouvé.
Merci !

[Sylvain Togni]

Ben non, mais v.insert(lower_bound(v.begin(), v.end(), x), x), franchement, c'est pas cher payé.

[HanLee]

Et si ton vecteur doit toujours être trié, tu peux utiliser un std::set, plutôt que payer à chaque fois pour les décalages.

[camboui]

Sauf que le std::set n'accepte pas les doublons.

Je connais encore trop peu les fonctions <algorithm> de la stl. De plus j'utilise souvent des tableaux de références, de pointeurs, de pointeur de pointeurs... Alors il m'arrive de patauger dans les prédicats, les valeurs de retour, les iterator, const_iterator, etc. Et puis j'ai la (bonne ou mauvaise ?) habitude de vérifier les valeurs de retour des fonctions. Bref, parfois rien qu'avec 5 lignes de code j'attrappe une grosse tête

La solution de Sylvain me convient très bien. Et d'ailleurs ça marche bien, merci

[HanLee]

Et t'as regardé du côté de std::multiset ?

[loufoque]

Insérer un élément au milieu d'un vecteur est en O(n).
Insérer un élément au milieu d'un ABR est en O(log n).

Le choix est vite fait.