Partage
  • Partager sur Facebook
  • Partager sur Twitter

priority_queue ordre top

    30 novembre 2021 à 8:53:59

    Bonjour a tous,
    j'ai un problème avec l'ordre de la file .

    le code : 

    struct Element {
        std::string data;
        unsigned short priority;
        bool operator<(const Element& rhs) const {
            std::cout << "** goog **" << std::endl;
            return this->priority < rhs.priority;
        }
        
    };
    
    struct comparator {
        bool operator()(const Element * a, const Element *b) {
            return (a->priority < b->priority);
        }
    };
    
    int main()
    {
        std::cout <<"========== create =========="<<std::endl;
        
        std::priority_queue<Element*, std::vector<Element*>, comparator> priority_queue;
        
        priority_queue.push(new Element{"1",1});
        priority_queue.push(new Element{"2",1});
        priority_queue.push(new Element{"3",1});
        priority_queue.push(new Element{"4",2});
        priority_queue.push(new Element{"5",2});
        priority_queue.push(new Element{"6",2});
        
        std::cout <<"========== test =========="<<std::endl;
        for(ushort i = 0;i<6;i++){
            Element *element = priority_queue.top();
            std::cout <<element->data<<" : "<<element->priority<<'\n';
            priority_queue.pop();
            priority_queue.push(element);
        }
        
        return 0;
    }

    résultat :

    ========== create ==========
    ========== test ==========
    4 : 2
    6 : 2
    4 : 2
    6 : 2
    4 : 2
    6 : 2
    
    alors que le résultat attendu est :
    ========== create ==========
    ========== test ==========
    4 : 2
    5 : 2
    6 : 2
    4 : 2
    5 : 2
    6 : 2
    

    je ne comprend pas j'ai l’impression qu'il ce comporte plus comme une plie qu'une file .

    Merci d'avance .

    • Partager sur Facebook
    • Partager sur Twitter
      30 novembre 2021 à 9:12:07

      Salut

      • Premièrement, pas de pointeurs nus.
      • Deuxièmement, ushort n'existe pas

      Je pense que ton parcours n'est pas cohérent. Une priority_queue n'est pas random-accessible. Le seul moyen de la parcourir est de faire une boucle tant que c'est pas vide :

          while (!priority_queue.empty()) {
              Element *element = priority_queue.top();
              std::cout <<element->data<<" : "<<element->priority<<'\n';
              priority_queue.pop();
          }
      

      Et dans mon cas j'ai comme résultat :

      4 : 2
      6 : 2
      5 : 2
      3 : 1
      2 : 1
      1 : 1
      




      • Partager sur Facebook
      • Partager sur Twitter

      l'azerty est aux dispositions ce que subversion est aux SCM

        30 novembre 2021 à 9:25:29

        Salut markand,

        • Premièrement, pas de pointeurs nus.

        Il n'y a pas de pointeur null ce conteneur sera dans un object qui s'occupera de la mémoire.

        • Deuxièmement, ushort n'existe pas

        Désolé je juste abréger sa veut dire "unsigned short". 

        • Je pense que ton parcours n'est pas cohérent.

        Que veut tu dire ?

        • Le seul moyen de la parcourir est de faire une boucle tant que c'est pas vide

        je ne peut pas me permettre de tout parcourir il y aura beaucoup tros élément a terme .

        -
        Edité par di20 30 novembre 2021 à 9:26:55

        • Partager sur Facebook
        • Partager sur Twitter
          30 novembre 2021 à 17:34:52

          Bonjour,

          Une priority_queue garantit que le prochain élément sorti est le plus grand. En cas d'égalité, elle peut retourner celui qu'il veut.
          En interne les données sont stockées sous la forme d'une "heap", donc l'ordre initial  n'est pas garanti, ce qui est garanti est de sortir toujours l'élément le plus grand tout en étant plus rapide qu'un système trié. Ici, elle fournit toujours un élément qui la la priorité 2, elle fait son boulot!

          Si ton objectif est de garder l'ordre initial, tu peux utiliser un std::vector trié (tu insères les données à la position indiquée par un std::binary_search(), et tu extraits les données par un pop_back()). Ça force une insertion triée qui est un peu plus lente qu'une heap mais ça garde l'ordre initial.

          • Partager sur Facebook
          • Partager sur Twitter

          En recherche d'emploi.

            1 décembre 2021 à 13:11:26

            di20 a écrit:

            • Premièrement, pas de pointeurs nus.

            Il n'y a pas de pointeur null ce conteneur sera dans un object qui s'occupera de la mémoire.


            J'ai dit NUS pas NULL.

            di20 a écrit:

            • Le seul moyen de la parcourir est de faire une boucle tant que c'est pas vide

            je ne peut pas me permettre de tout parcourir il y aura beaucoup tros élément a terme .

            Je pense que dans ce cas tu ne saisis pas l'utilité de la priority_queue. C'est pas un conteneur à parcourir, c'est un conteneur dont le but est de dépiler dans l'ordre.

            • Partager sur Facebook
            • Partager sur Twitter

            l'azerty est aux dispositions ce que subversion est aux SCM

            priority_queue ordre top

            × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
            • Editeur
            • Markdown