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 !
Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Insérer au bon endroit dans un <vector> trié
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
Et t'as regardé du côté de std::multiset ?
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.
Boh, encore ça dépend de la taille du vecteur... Ca se trouve il manipule que des vecteurs tout petits.
Tu peut aussi utiliser un heap
http://r0d.developpez.com/articles/algos-stl/#LII-C-6
Un "heap" est un arbre binaire de recherche. C'est ce que sont std::set, std::multiset, std::map et std::multimap.
En gros oui. A la différence qu 'il peut utiliser un vector et donc des avantage qui peut l'intêresser.Envoyé par loufoque
Mais bon c'est juste une autre option.
A lui de voir si ca peut l'intéresser
Heu, pas trop, un tas n'implique pas une relation d'ordre totale entre les éléments de l'arbre !
Un tas est un arbre binaire ordonné verticalement, alors que l'ABR classique est ordonné horizontalement.
Avec un tas, tu ne peux que trouver le maximum (ou le minimum) selon la convention utilisé, mais pas le minimum (et le maximum respectivement).
Ah oui pardon.
Merci à tous.
Quand j'utilise des std::vector ils sont la plupart du temps assez statiques. Il est rare que je doive insérer des éléments dans un std::vector trié.
Je l'ai choisi dans ce cas-ci au lieu du multiset car le vector ne contient que quelques dizaines d'éléments.
Répondre avec citation
Partager