Preben wrote:
>> std::priority_queue<Configuration*, std::vector<Configuration*>,
>> std::less<Configuration*> > pq;
>>
>>
>> Hvordan vil "priority_queue" anvende std::less<Configuration*> til
>> sammenligning.
>>
>> Vil den sammenligne pointerne eller rent faktisk anvende "operator<"
>> på Configuration som objekt?
Jeg har ikke arbejdet med priority_queue før, så følgende skal tages med
forbehold:
> Og jeg er selvfølgelig interesseret i at vide hvordan jeg får den til at
> virke som en "operator<" på selve objektet.
>
> Jeg har implementeret en "operator<" på klasse Configuration:
> ---------------------------
> bool Configuration:
erator<(const Configuration& conf) const {
> return (_shortest < conf.getShortest());
> }
> ---------------------------
>
> og håber det er rigtigt...
Så vidt jeg kan se er du nødt til at lave:
class Compare
{
public:
bool operator () (const Configuration* aLhs, const Configuration* aRhs)
{
return ...;
}
};
Og oprette køen med:
std::priority_queue<Configuration*, std::vector<Configuration*>,
Compare > pq;
Jeg tror ikke du kan bruge std::less med pointere, det ville kræve
at du kunne lave en "bool operator <" der tager pointere, det kan man
vist ikke.
>
> altså hvis (x < y), så skulle jeg gerne returnere true fra ovenstående
> funktion!
>
>
> Hvis jeg indsætter 10.002 elementer i pq, som alle er initialiseret som
> følger:
> ---------------------------
> for (unsigned int i = 0; i < G.size(); ++i) {
> G[i]->setShortest(1000000000000.);
> G[i]->setParent(NULL);
> }
> s->setShortest(0);
Hvad er s, er det en pointer til et element i G[]?
> og så indsætter elementerne i køen:
> ---------------------------
> std::priority_queue<Configuration*, std::vector<Configuration*>,
> std::less<Configuration*> > pq;
> // Fill the queue
> for (unsigned int i = 0; i < G.size(); ++i) {
> pq.push(G[i]);
> }
Det er vist ikke ret effiktivt, den vil vel sortere hver gang
man indsætter et element. Jeg er heller ikke sikker på at det
er smart, da alle elementer har samme værdi?
> ---------------------------
>
> og herefter kører nedenstående:
> ---------------------------
> unsigned int t = 0;
> if (pq.top() != s) {
> std::cout << "Error: top element is not _source. Elements in
> queue: " << pq.size() << std::endl;
> while(!pq.empty()) {
> Configuration* u = pq.top();
> pq.pop();
> ++t;
> if (u == s)
Så vidt jeg kan se peger u på noget udefineret, når du har
pop'et.
> std::cout << "Dijkstra: Source found in number " << t <<
> std::endl;
> }
> }
> ---------------------------
>
>
> så fås flg. output:
> ---------------------------
> Error: top element is not _source. Elements in queue: 10002
> Dijkstra: Source found in number 9990
> ---------------------------
>
> og det er jo ikke godt, når man skal implementere f.eks. Dijkstra's
> algoritme (i mit tilfælde).
Jeg ved ikke hvad "Dijkstra's algoritme" er, måske skulle du forsøge
at forklare hvilket problem du forsøger at løse.
--
Absolutely not the best homepage on the net:
http://home20.inet.tele.dk/midgaard
But it's mine - Bertel