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 .

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

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

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.

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.