IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

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

SL & STL C++ Discussion :

Insérer au bon endroit dans un <vector> trié


Sujet :

SL & STL C++

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre éclairé
    Inscrit en
    Avril 2005
    Messages
    1 110
    Détails du profil
    Informations forums :
    Inscription : Avril 2005
    Messages : 1 110
    Par défaut 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 !

  2. #2
    Membre émérite

    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    717
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 717
    Par défaut
    Ben non, mais v.insert(lower_bound(v.begin(), v.end(), x), x), franchement, c'est pas cher payé.

  3. #3
    Membre émérite Avatar de HanLee
    Profil pro
    Inscrit en
    Mai 2004
    Messages
    738
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Rhône (Rhône Alpes)

    Informations forums :
    Inscription : Mai 2004
    Messages : 738
    Par défaut
    Et si ton vecteur doit toujours être trié, tu peux utiliser un std::set, plutôt que payer à chaque fois pour les décalages.

  4. #4
    Membre éclairé
    Inscrit en
    Avril 2005
    Messages
    1 110
    Détails du profil
    Informations forums :
    Inscription : Avril 2005
    Messages : 1 110
    Par défaut
    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

  5. #5
    Membre émérite Avatar de HanLee
    Profil pro
    Inscrit en
    Mai 2004
    Messages
    738
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Rhône (Rhône Alpes)

    Informations forums :
    Inscription : Mai 2004
    Messages : 738
    Par défaut
    Et t'as regardé du côté de std::multiset ?

  6. #6
    Expert confirmé
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Décembre 2003
    Messages
    3 549
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Décembre 2003
    Messages : 3 549
    Par défaut
    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.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. [XL-2007] insérer une ligne au meme endroit dans plusieurs feuilles
    Par tchock_nenette dans le forum Macros et VBA Excel
    Réponses: 17
    Dernier message: 03/05/2012, 09h35
  2. Inserer des lignes avec DOM : rester au bon endroit dans la page
    Par sebhm dans le forum Général JavaScript
    Réponses: 8
    Dernier message: 22/10/2009, 18h22
  3. placer des balise xml au bon endroit dans le fichier existant.
    Par calimero91 dans le forum VB 6 et antérieur
    Réponses: 6
    Dernier message: 07/01/2008, 09h43
  4. Réponses: 9
    Dernier message: 20/08/2007, 20h39
  5. Mettre le focus() au bon endroit... dans un tableau
    Par FrankOVD dans le forum Général JavaScript
    Réponses: 5
    Dernier message: 12/05/2006, 20h18

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo