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

 C++ Discussion :

Quel container STL utiliser pour un ensemble d'éléments dont l'ordre est arbitraire ?


Sujet :

C++

  1. #1
    Membre du Club
    Profil pro
    Étudiant
    Inscrit en
    Mai 2007
    Messages
    123
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France, Var (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mai 2007
    Messages : 123
    Points : 53
    Points
    53
    Par défaut Quel container STL utiliser pour un ensemble d'éléments dont l'ordre est arbitraire ?
    Bonjour,

    Je dois manipuler un ensemble d'éléments dont l'utilisateur peut modifier l'ordre.
    Je cherche donc à savoir quel container STL utiliser sachant que l'ordre des éléments doit pouvoir changer à la guise de l'utilisateur et comment effectuer de telles opérations.
    Chaque nouvel élément peut être ajouté au début ou à la fin du container, peut importe, il ne sera jamais inséré au milieu en tout cas. L'utilisateur pourra cependant ensuite le replacer.

    Ex: A B C D E
    A C B D E
    A C D E B
    etc...

    Je vous remercie.
    Cordialement,

  2. #2
    Expert éminent sénior
    Homme Profil pro
    Analyste/ Programmeur
    Inscrit en
    Juillet 2013
    Messages
    4 627
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Analyste/ Programmeur

    Informations forums :
    Inscription : Juillet 2013
    Messages : 4 627
    Points : 10 551
    Points
    10 551
    Par défaut
    std::deque

  3. #3
    Modérateur

    Avatar de Bktero
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    Juin 2009
    Messages
    4 481
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Loire Atlantique (Pays de la Loire)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués

    Informations forums :
    Inscription : Juin 2009
    Messages : 4 481
    Points : 13 678
    Points
    13 678
    Billets dans le blog
    1
    Par défaut
    Bonjour,

    A priorio deque semble pas mal : https://fr.cppreference.com/w/cpp/container/deque

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    std::deque<int> d;
     
    d.push_back(50);
    d.push_back(60);
    d.push_back(70);
     
    d.push_front(30);
    d.push_front(10); // not inserted at the correct position
    d.push_front(20);
     
    std::cout << "Initial" << std::endl;
    for (const auto& e :d) {
    	std::cout << e << std::endl;
    }
     
    std::swap(d[0], d[1]); // swap inverted elements
     
    std::cout << "Final" << std::endl;
    for (const auto& e :d) {
    	std::cout << e << std::endl;
    }

  4. #4
    Membre du Club
    Profil pro
    Étudiant
    Inscrit en
    Mai 2007
    Messages
    123
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France, Var (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mai 2007
    Messages : 123
    Points : 53
    Points
    53
    Par défaut
    Bonjour et merci de votre réponse.

    Je ne désire pas faire de swap entre deux éléments mais bien déplacer un seul élément afin de "l'insérer" ailleurs dans le conteneur.

  5. #5
    Expert éminent sénior
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    Octobre 2004
    Messages
    11 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : Octobre 2004
    Messages : 11 612
    Points : 30 611
    Points
    30 611
    Par défaut
    Salut,

    Par défaut, à partir du moment où tu n'as pas besoin d'un container associatif, tu vas systématiquement utiliser std::vector ou std::deque, en donnant une préférence au deuxième si tu dois régulièrement insérer un nouvel élément entre deux éléments existants.

    Si tu ne dois insérer un nouvel élément entre deux éléments existants, ou que tu peux te "contenter" d'ajouter les nouveaux éléments à la fin de la collection, std::vector fera le taf sans grosses difficultés, surtout si tu a pris soin de définir une capacité "suffisante" que pour qu'il n'ait pas besoin de l'augmenter "sans arrêt"
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  6. #6
    Modérateur

    Avatar de Bktero
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    Juin 2009
    Messages
    4 481
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Loire Atlantique (Pays de la Loire)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués

    Informations forums :
    Inscription : Juin 2009
    Messages : 4 481
    Points : 13 678
    Points
    13 678
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par Daikyo Voir le message
    Je ne désire pas faire de swap entre deux éléments mais bien déplacer un seul élément afin de "l'insérer" ailleurs dans le conteneur.
    Donc ça veut dire suppression puis ajout au milieu... Ce qu'on n'avait normalement pas à faire

    Bon ça tombe bien deque a insert() : https://fr.cppreference.com/w/cpp/co...r/deque/insert

  7. #7
    Membre du Club
    Profil pro
    Étudiant
    Inscrit en
    Mai 2007
    Messages
    123
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France, Var (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mai 2007
    Messages : 123
    Points : 53
    Points
    53
    Par défaut
    D'accord donc il n'existe rien dans la STL qui fait directement ce genre de chose, tel un std::move ou autre...
    Je dois donc le faire à la mano (suppression puis insertion), c'était ce que je voulais savoir.
    Je vous remercie!

  8. #8
    Expert éminent sénior
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    Octobre 2004
    Messages
    11 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : Octobre 2004
    Messages : 11 612
    Points : 30 611
    Points
    30 611
    Par défaut
    Citation Envoyé par Daikyo Voir le message
    D'accord donc il n'existe rien dans la STL qui fait directement ce genre de chose, tel un std::move ou autre...
    Je dois donc le faire à la mano (suppression puis insertion), c'était ce que je voulais savoir.
    Je vous remercie!
    Attention!!!

    Ta question portait à la base sur le type de conteneur / collection que tu pouvais utiliser. Il se fait que les différents conteneurs fournissent une implémentation de notions telles que
    • tableau d'élément contigus
    • pile
    • file
    • liste
    • arbre binaire

    qui présentent tous des avantages et des inconvénients en termes de complexité algorithmique des "opérations de base" (ajout, suppression, insertion, accès, recherche) :
    Tn tableau par exemple sera très efficace pour permettre l'accès à un élément donné de manière aléatoire : cela te prendra exactement le même temps de passer du troisième élément au quatrième que de passer du troisième élément au 10 000 eme (en évitant les neuf milles neuf cents et quelques qu'il y a entre les deux)

    L'ajout (après le dernier élément existant) et la suppression du dernier élément se fera également relativement vite, du moins, tant que le tableau ne devra pas augmenter sa capacité. Mais la suppression et -- surtout --l'ajout d'un élément "au beau milieu" demandera un temps proportionnels au nombre d'éléments qui devront être décalés pour "faire de la place" à l'élément qui doit être rajouté.

    La pile et la file présente les restrictions classiques des systèmes LIFO et FIFO

    La liste sera beaucoup plus efficace pour l'ajout ou la suppression d'un élément quel que soit l'endroit où elle survient (pour autant que cet endroit ait été atteint avant de la tenter), mais sera particulièrement inefficace en cas d'accès à un élément choisi de manière aléatoire, car il sera proportionnel au nombre d'élément à "traverser"

    Les arbres binaires sont particulièrement efficaces lors de la recherche, mais les autres opérations prennent énormément de temps

    std::move n'a absolument rien à voir avec ce genre de problématique, mais plutôt avec celui de (ne pas) copier un objet dont la copie prendrait "trop de temps" (ou ne serait carrément pas possible) en décidant de "vampiriser" les ressources qui le composent pour le donner à un autre élément.
    Citation Envoyé par Daikyo
    Bonjour et merci de votre réponse.

    Je ne désire pas faire de swap entre deux éléments mais bien déplacer un seul élément afin de "l'insérer" ailleurs dans le conteneur.
    tu t'exprimes mal sur ce coup, car, ce que tu veux réellement faire, ce n'est pas "déplacer" mais ... "supprimer" un élément afin de pouvoir le réinsérer ailleurs.

    Sauf si tu veux effectivement permuter deux éléments (auquel cas, il s'agit bel et bien d'un swap)

    En théorie, la notion qui présente la meilleure complexité pour les actions que tu veux entreprendre serait sans doute la liste (et son implémentation [c]std::list[/]) car insertion et suppression se font avec une complexité en temps constant (O(1) ) avec les listes.

    Le problème, c'est que, en te focalisant sur cette pair d'actions particulière, tu laisses peut-être l'arbre te cacher la forêt, et que le gain que tu obtiens pour cet action n'est pas gratuit : les autres actions seront plus lentes. je ne sais pas quelle est ta situation, mais il me semble important que tu te poses la question de savoir si le gain que tu espère vaut réellement le prix que cela va te coûter:

    Si c'est pour déplacer un élément toutes les cinq minutes, alors que tu dois accéder à un élément quelconque (qui n'est peut être pas celui qui est juste à coté de celui sur lequel tu te trouves) toutes les demis-secondes, tu perdras au change, parce que tu gagnera -- certes -- "un peu de temps" lors du déplacement de l'élément, mais tu en perdra "un max" sur le parcours "classique" des éléments de ta collection.

    La première question que tu devrais donc te poser ici -- et à laquelle seul un profilage de ton application pourra répondre -- est donc : est-ce que je passe "suffisamment de temps" à déplacer les éléments de ma collection pour que cela vaille effectivement la peine d'essayer de rendre ce processus plus rapide

    Autant dire que la réponse ne pourras -- de toutes évidences -- être "oui" que si tu passes réellement le plus clair de ton temps à exécuter de tels déplacements.

    Si ce n'est pas le cas, tu as sans doute bien plus intérêt à choisir le type de conteneur le plus adapté à l'action que tu exécute "le plus souvent" sur le conteneur
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

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

Discussions similaires

  1. Réponses: 28
    Dernier message: 23/10/2008, 16h06
  2. Quel framework javascript utiliser pour un usage particulier ?
    Par codefalse dans le forum Général JavaScript
    Réponses: 2
    Dernier message: 20/08/2008, 18h06
  3. Quels API's utiliser pour une application en rapport avec Autocad?
    Par Angelsoul dans le forum API standards et tierces
    Réponses: 3
    Dernier message: 31/07/2008, 16h21
  4. Quels outils logiciels utiliser pour faire son site ?
    Par tripper.dim dans le forum Outils
    Réponses: 36
    Dernier message: 22/05/2008, 19h39
  5. [Conception]Quel outil graphique utiliser pour schéma BDD?
    Par nicoaix dans le forum Décisions SGBD
    Réponses: 7
    Dernier message: 16/01/2006, 13h34

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