Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

[C++11] std::priority_queue ohne contains() und decreaseKey()

  • 1
  • 2

Werbeanzeige

Nox

Supermoderator

Beiträge: 5 272

Beruf: Student

  • Private Nachricht senden

11

14.02.2014, 17:11

Wir haben mal im Forum direkt getestet was am schnellsten war und ich glaube es war sogar arrays/std::vector. Musst einfach mal nach suchen.
PRO Lernkurs "Wie benutze ich eine Doku richtig"!
CONTRA lasst mal die anderen machen!
networklibbenc - Netzwerklibs im Vergleich | syncsys - Netzwerk lib (MMO-ready) | Schleichfahrt Remake | Firegalaxy | Sammelsurium rund um FPGA&Co.

Glocke

Treue Seele

  • »Glocke« ist der Autor dieses Themas

Beiträge: 341

  • Private Nachricht senden

12

16.12.2014, 11:30

Moin, gerade bin ich (mal wieder) über dieses Problem gestolpert, wollte einen neuen Thread aufmachen und dann viel mir ein ... jaa und jetzt sind wir wieder hier :D

Die Sache mit dem contains löse ich im Moment über std::find, d.h. in O(n). Allerdings fehlt mir immernoch das decreaseKey (oder increaseKey je nach dem welcher Comparator übergeben wird^^ ). Eigentlich wäre es quatsch das Rad neu zu erfinden und eine eigene priority_queue-Implementierung zu bauen .. zumindest finde ich im Standard nichts geeignetes :(

Checkmateing

Community-Fossil

Beiträge: 2 218

  • Private Nachricht senden

13

16.12.2014, 16:43

Du kannst doch einfach, ist nicht schön, ich weiß, ein std::set nehmen und für decreaseKey einfach das Element entfernen und mit neuem Wert einfügen.
Da std::priority_queue nichts anderes sein kann, als ein std::vector mit eingeschränkter Funktion, der auf sich selbst std::make_heap loshetzt, macht es in der Tat vielleicht eher Sinn, das ganze mithilfe eines std::vector zu realisieren.

C-/C++-Quelltext

 
1
2
3
4
5
6

std::vector<int> heap{1,2,3,4,5,6,7};
std::make_heap(heap.begin(), heap.end());
//Decrease key
std::pop_heap(heap.begin(), heap.end());
--*(std::prev(heap.end()));
std::push_heap(heap.begin(), heap.end());

Ansonsten musst du das Rad wohl wirklich "neu erfinden".

MfG
Check
Das gibt Übersicht! Stay gold.

Glocke

Treue Seele

  • »Glocke« ist der Autor dieses Themas

Beiträge: 341

  • Private Nachricht senden

14

16.12.2014, 17:05

Zitat von »Checkmateing«

Du kannst doch einfach, ist nicht schön, ich weiß, ein std::set nehmen und für decreaseKey einfach das Element entfernen und mit neuem Wert einfügen.
Da std::priority_queue nichts anderes sein kann, als ein std::vector mit eingeschränkter Funktion, der auf sich selbst std::make_heap loshetzt, macht es in der Tat vielleicht eher Sinn, das ganze mithilfe eines std::vector zu realisieren.

Das ganze will ich für meinen Wegfindungsalgorithmus verwenden - da ist es von Vorteil einen zusammenhängenden Datentyp zu Grunde zu legen. Bisher habe ich mit std::set gearbeitet und das ganze läuft ziemlich suboptimal.

Ich werde meine bisherige und meine neue Implementierung zum Schluss mal "gegeneinander" laufen lassen :crazy:

Zitat von »Checkmateing«

Ansonsten musst du das Rad wohl wirklich "neu erfinden".

Ich hab inzwischen ein paar Sachen implementiert und hoble noch an der Laufzeit. Damit ich decrease anwenden kann, brauche ich Random Access auf meine Knoten. Wenn ich Random Access habe, lässt sich auch contains() gut implementieren.

Da ich für meine Anwendung 2D-Koordinaten (unsigned int) auf einer begrenzten Map (d.h. max_width und max_height) verwende, kann ich prinzipiell über eine bijektive Abbildung (Koordinaten auf den Index, innerhalb der Queue) bauen mit

C-/C++-Quelltext

 
1

std::size_t index = pos.x + map_size.x * pos.y;

sofern alle Positionen stehts innerhalb der MapBounds liegen. Da bijektiv, sollte dieses "Hashing" effektiv kollisionsfrei ablaufen - vorausgesetzt ich habe ein Array zur Speicherung der Abbildungen ("Inhaltsverzeichnis" :D) der Art..

C-/C++-Quelltext

 
1

std::vector<int> pos_to_index; // -1 = not existing

mit Größe map_size.x * map_size.y, so dass ich mit pos_to_index[hash(pos)] auf den Index innerhalb der eigentlichen std::vector<Pos> heap zugreifen kann.

Das ganze funktioniert - führt aber dazu, dass ich bei insert, decrease und extract jeweils Buch führen muss... Und im Moment macht mir mein extract (genauer: "heapify" nach dem Enfernen) Sorgen .. aber das wird :D

Werbeanzeige

  • 1
  • 2

Ähnliche Themen