Hoe C++ Priority_queue te gebruiken?

Om de C++ priority_queue te gebruiken, moet het programma beginnen met code zoals:

Het bevat de wachtrijbibliotheek in het programma.

Om verder te kunnen lezen, moet de lezer een basiskennis van C++ hebben gehad.

Artikel Inhoud

• Basisconstructie
• Belangrijke ledenfuncties
• Andere prioriteitswachtrijfuncties
• Tekenreeksgegevens
• Andere prioriteitswachtrijconstructies
• Conclusie

Basisconstructie

De datastructuur moet eerst worden opgebouwd voordat deze kan worden gebruikt. Constructie betekent hier het instantiëren van een object uit de wachtrijklasse van de bibliotheek. Het wachtrij-object moet dan een naam hebben die de programmeur eraan heeft gegeven. De eenvoudigste syntaxis om een ​​prioriteitswachtrij te maken is:

Met deze syntaxis wordt de grootste waarde het eerst verwijderd. Een voorbeeld van de instantie is:

of

De vector en de deque zijn twee datastructuren in C++. Met beide kan een priority_queue worden gemaakt. De syntaxis om een ​​prioriteitswachtrij te maken op basis van de vectorstructuur is:

Een voorbeeld van deze instantie is:

Let op de opening tussen > en > aan het einde van de aangifte. Dit om verwarring met >> te voorkomen. De standaardvergelijkingscode is minder, wat betekent dat de grootste, en niet noodzakelijk de eerste waarde, als eerste wordt verwijderd. De creatieverklaring kan dus eenvoudig worden geschreven als:

Als de minste waarde eerst moet worden verwijderd, moet de instructie zijn:

Belangrijke ledenfuncties

De push()-functie
Deze functie duwt een waarde, die het argument is, in de prioriteit_wachtrij. Het keert leeg terug. De volgende code illustreert dit:

Deze prioriteit_wachtrij heeft 5 gehele waarden ontvangen in de volgorde 10, 30, 20, 50, 40. Als al deze elementen uit de prioriteitswachtrij moeten worden gehaald, zullen ze verschijnen in de volgorde 50, 40, 30, 20, 10.

De pop()-functie
Deze functie verwijdert uit de priority_queue de waarde met de hoogste prioriteit. Als de vergelijkingscode groter is, wordt het element met de kleinste waarde verwijderd. Als het opnieuw wordt aangeroepen, verwijdert het het volgende element met de kleinste waarde van de rest; opnieuw wordt aangeroepen, verwijdert het de volgende kleinste aanwezige waarde, enzovoort. Het keert leeg terug. De volgende code illustreert dit:

Merk op dat om een ​​lidfunctie aan te roepen, de naam van het object gevolgd moet worden door een punt en dan de functie.

De top() Functie
De pop () functie verwijdert de volgende waarde met de hoogste prioriteit, maar retourneert deze niet, zoals pop () is een lege functie. Gebruik de bovenkant() functie om de waarde met de hoogste prioriteit te kennen die vervolgens moet worden verwijderd. De bovenkant() functie retourneert een kopie van de waarde met de hoogste prioriteit in de prioriteit_wachtrij. De volgende code, waarbij de volgende waarde met de hoogste prioriteit de minste waarde is, illustreert dit:

De uitvoer is 'a' 'b' 'c' 'd' 'e'.

De lege() functie
Als een programmeur de bovenkant() functie op een lege prioriteit_wachtrij, na de succesvolle compilatie, zou hij een foutmelding ontvangen zoals:

Controleer dus altijd of de prioriteitswachtrij niet leeg is voordat u de bovenkant() functie. De leeg() member functie retourneert een bool, true, als de wachtrij leeg is, en false als de wachtrij niet leeg is. De volgende code illustreert dit:

Andere prioriteitswachtrijfuncties

De maat () Functie:
Deze functie retourneert de lengte van de prioriteitswachtrij, zoals de volgende code illustreert:

De uitvoer is 5.

De swap()-functie
Als twee priority_queues van hetzelfde type en dezelfde grootte zijn, kunnen ze door deze functie worden verwisseld, zoals de volgende code laat zien:

De uitvoer is:

 5  4  3  2  1
 50  40  30  20 ​​ 10

De emplace()-functie
De plaats() functie is vergelijkbaar met de push-functie. De volgende code illustreert dit:

De uitvoer is:

50 40 30 20 10

Tekenreeksgegevens

Bij het vergelijken van tekenreeksen moet de tekenreeksklasse worden gebruikt en niet het directe gebruik van de letterlijke tekenreeksen, omdat het pointers zou vergelijken en niet de daadwerkelijke tekenreeksen. De volgende code laat zien hoe de tekenreeksklasse wordt gebruikt:

De uitvoer is:

 tekstboek  liniaal  potlood  pen  oefenboek

Andere prioriteitswachtrijconstructies

Expliciete creatie van een vector
Een prioriteitswachtrij kan expliciet worden gemaakt op basis van een vector, zoals de volgende code laat zien:

De output is: 50 40 30 20 10. Deze keer moet ook de vectorheader worden opgenomen. De argumenten voor de constructorfunctie nemen de begin- en eindwijzers van de vector. Het gegevenstype voor de vector en het gegevenstype voor de prioriteit_wachtrij moeten hetzelfde zijn.

Om de minste waarde de prioriteit te geven, zou de verklaring voor de constructor zijn:

Expliciete creatie vanuit een array
Een prioriteitswachtrij kan expliciet worden gemaakt op basis van een array, zoals de volgende code laat zien:

De output is: 50 40 30 20 10. De argumenten voor de constructorfunctie nemen de start- en eindpointers van de array. arr retourneert de startpointer, arr+5 retourneert de pointer net voorbij de array, en 5 is de grootte van de array. Het gegevenstype voor de array en het gegevenstype voor de prioriteit_wachtrij moeten hetzelfde zijn.

Om de minste waarde de prioriteit te geven, zou de verklaring voor de constructor zijn:

Opmerking: in C++ wordt de prioriteit_wachtrij eigenlijk een adapter genoemd, niet alleen een container.

Aangepaste vergelijkingscode

Alle waarden in de prioriteitswachtrij oplopend of allemaal aflopend hebben, is niet de enige optie voor de prioriteitswachtrij. Een lijst met 11 gehele getallen voor een maximale heap is bijvoorbeeld:

88, 86, 87, 84, 82, 79,74, 80, 81,,, 64, 69

De hoogste waarde is 88. Dit wordt gevolgd door twee getallen: 86 en 87, die kleiner zijn dan 88. De rest van de getallen zijn kleiner dan deze drie getallen, maar niet echt in orde. Er zijn twee lege cellen in de lijst. De nummers 84 en 82 zijn kleiner dan 86. De nummers 79 en 74 zijn kleiner dan 87. De nummers 80 en 81 zijn kleiner dan 84. De nummers 64 en 69 zijn kleiner dan 79.

De plaatsing van de nummers volgt de max-heap-criteria - zie later. Om een ​​dergelijk schema voor de prioriteit_wachtrij te bieden, moet de programmeur zijn eigen vergelijkingscode opgeven - zie later.

Conclusie

Een C++ priority_queue is een first-in-first-out wachtrij. De ledenfunctie, duw(), voegt een nieuwe waarde toe aan de wachtrij. De ledenfunctie, bovenkant(), leest de hoogste waarde in de wachtrij. De ledenfunctie, pop (), verwijdert zonder de hoogste waarde van de wachtrij terug te geven. De ledenfunctie, leeg(), controleert of de wachtrij leeg is. De prioriteit_wachtrij verschilt echter van de wachtrij doordat deze een prioriteitsalgoritme volgt. Het kan het grootst zijn, van de eerste tot de laatste, of de minste, van de eerste tot de laatste. De criteria (algoritme) kunnen ook door de programmeur worden gedefinieerd.