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 !
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 !
Ben non, mais v.insert(lower_bound(v.begin(), v.end(), x), x), franchement, c'est pas cher payé.
Et si ton vecteur doit toujours être trié, tu peux utiliser un std::set, plutôt que payer à chaque fois pour les décalages.
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![]()
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.
Partager