Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C++

std::priority_queue — prioritetni red

std::priority_queue omogućuje pristup elementu s najvišim prioritetom, a ne onome koji je prvi umetnut. Prema zadanim postavkama na vrhu je najveća vrijednost; std::greater<T> obrće redoslijed.

Verzija: C++23; repository compiler flag, production runtime not attested

Sintaksa

#include <functional>
#include <queue>
#include <vector>

std::priority_queue<T> q;
std::priority_queue<T, std::vector<T>, std::greater<T>> min_q;

std::priority_queue iz <queue> adapter je spremnika koji održava hrpu, a ne FIFO red. Prema zadanim postavkama koristi std::vector<T> i std::less<T>, pa top() označava najveću vrijednost. Inačica sa std::greater<T> označava najmanju vrijednost i zahtijeva <functional>.

push() umeće vrijednost, dok emplace() konstruira element u spremniku i obnavlja svojstvo hrpe. top() omogućuje pristup samo za čitanje. pop() uklanja vrh i vraća void: potrebnu vrijednost kopirajte prije uklanjanja. Prije top() i pop() provjerite empty(); obje operacije zahtijevaju neprazan red.

Komparator mora definirati strogo slabo uređenje. Compare(a, b) == true znači da a u tom uređenju prethodi elementu b te ima niži prioritet pri uklanjanju. Adapter ne izlaže iteratore ni operaciju za promjenu prioriteta proizvoljnog elementa.

top() ima konstantnu složenost. Obnavljanje hrpe tijekom push(), emplace() i pop() zahtijeva O(log n) usporedbi. Umetanje uključuje i trošak temeljnog spremnika: ponovna alokacija zadanog std::vector<T> može pojedinačno umetanje učiniti linearnim.

Primjer ispisuje iste podatke silaznim i uzlaznim redoslijedom te pritom prazni oba reda. Ovaj se zapis odnosi na C++23; povezani radni nacrt noviji je i nije zamrznuti tekst C++23.

Primjeri

#include <functional>
#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::priority_queue<int> max_q;
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_q;

    for (int value : {4, 1, 7, 1}) {
        max_q.push(value);
        min_q.push(value);
    }

    while (!max_q.empty()) {
        std::cout << max_q.top();
        max_q.pop();
        std::cout << (max_q.empty() ? '\n' : ' ');
    }
    while (!min_q.empty()) {
        std::cout << min_q.top();
        min_q.pop();
        std::cout << (min_q.empty() ? '\n' : ' ');
    }
}

Rezultat

7 4 1 1
1 1 4 7

Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.

Izvori