stl: priority_queue не сортирует одинаковые приоритетные элементы в порядке FIFO - PullRequest
Новая
       46

stl: priority_queue не сортирует одинаковые приоритетные элементы в порядке FIFO

0 голосов
/ 25 апреля 2019

У меня есть следующий код для реализации C ++ STL priority_queue. Но приоритетные очереди должны располагать идентичные приоритетные элементы в порядке FIFO. Тем не менее, вывод кода предлагает по-другому. Мне известно, что приоритетные очереди внутренне зависят от куч, и, учитывая кучу, выходные данные действительны, хотя и нарушают базовую концепцию очереди. 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <time.h>
#include <sys/time.h>
#include <iostream> 
#include <queue> 

using namespace std; 

typedef struct data{
    int pri;
    char dat[30];

/*
    bool operator<(const data *rhs) const
    {
        return this->pri < rhs->pri;
    }
*/
}data_t;

struct compare{
    bool operator()(const data_t *ptr1, const data_t *ptr2) const
    {
        return ptr1->pri > ptr2->pri;
    }
};

void showpq(priority_queue <data_t*, vector<data_t*>, compare> gq) 
{ 
    priority_queue <data_t*, vector<data_t*>, compare> g = gq; 
    while (!g.empty()) 
    { 
        cout << "\n\t" << g.top()->dat; 
        g.pop(); 
    } 
    cout << '\n'; 
} 

int main () 
{ 
    data_t myList[10] = {{53, "Seqn: 0  Pri: 53"}, 
             {27, "Seqn: 1  Pri: 27"}, 
             {22, "Seqn: 2  Pri: 22"},
             {77, "Seqn: 3  Pri: 77"},
             {52, "Seqn: 4  Pri: 52"},
             {22, "Seqn: 5  Pri: 22"},
             {35, "Seqn: 6  Pri: 35"},
             {68, "Seqn: 7  Pri: 68"},
             {80, "Seqn: 8  Pri: 80"},
             {20, "Seqn: 9  Pri: 20"}};
    priority_queue <data_t*, vector<data_t*>, compare> gquiz; 
    srand(time(NULL));
    for(int i=0; i<10; i++){
#if 0
        myList[i].pri = 1 + ( rand() % 100 );
        sprintf(myList[i].dat, "Val: %d\tPri: %d", i, myList[i].pri);
#endif
        gquiz.push(&myList[i]); 
    }

    cout << "The priority queue gquiz is : "; 
    showpq(gquiz); 

    cout << "\ngquiz.size() : " << gquiz.size(); 
    cout << "\ngquiz.top() : " << gquiz.top()->dat; 


    cout << "\ngquiz.pop() : "; 
    gquiz.pop(); 
    showpq(gquiz); 

    return 0; 
}

При сборке и выполнении кода выше я вижу следующий вывод: 

The priority queue gquiz is :
        Seqn: 9  Pri: 20
        Seqn: 5  Pri: 22
        Seqn: 2  Pri: 22
        Seqn: 1  Pri: 27
        Seqn: 6  Pri: 35
        Seqn: 4  Pri: 52
        Seqn: 0  Pri: 53
        Seqn: 7  Pri: 68
        Seqn: 3  Pri: 77
        Seqn: 8  Pri: 80

gquiz.size() : 10
gquiz.top() : Seqn: 9  Pri: 20
gquiz.pop() :
        Seqn: 5  Pri: 22
        Seqn: 2  Pri: 22
        Seqn: 1  Pri: 27
        Seqn: 6  Pri: 35
        Seqn: 4  Pri: 52
        Seqn: 0  Pri: 53
        Seqn: 7  Pri: 68
        Seqn: 3  Pri: 77
        Seqn: 8  Pri: 80

Из вышесказанного мы видим, что: Seqn: 5 и Seqn:2 оба имеют приоритет как 22, но, конечно, seqn: 2 ставится перед Seqn: 5. Но во время pop seqn: 5 появляется раньше, чем Seqn: 2. С переменными размерами набора данных порядок Seqn: 2 и Seqn: 5 непредсказуем.

Как сохранить порядок FIFO в таком случае и почему поведение отличается?

...