База знанияИзпитен център
BGБългарски
Избери език13

CKTIS / C++

std::priority_queue — приоритетна опашка

std::priority_queue предоставя достъп до елемента с най-висок приоритет, а не до първия добавен. По подразбиране най-голямата стойност е най-отгоре; std::greater<T> обръща реда.

Версия: C++23; repository compiler flag, production runtime not attested

Синтаксис

#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 от <queue> е адаптер на контейнер, който поддържа купчина, а не FIFO опашка. По подразбиране използва std::vector<T> и std::less<T>, затова top() обозначава най-голямата стойност. Вариантът със std::greater<T> обозначава най-малката и изисква <functional>.

push() добавя стойност, докато emplace() конструира елемент в контейнера и възстановява свойството на купчината. top() предоставя достъп само за четене. pop() премахва най-горния елемент и връща void: копирайте необходимата стойност преди премахването. Проверявайте empty() преди top() и pop(); и двете операции изискват непразна опашка.

Компараторът трябва да дефинира строго слабо подреждане. Compare(a, b) == true означава, че a предхожда b в това подреждане и съответно има по-нисък приоритет при извличане. Адаптерът не предоставя итератори или операция за промяна на приоритета на произволен елемент.

top() има постоянна сложност. Възстановяването на купчината при push(), emplace() и pop() изисква O(log n) сравнения. Добавянето включва и разходите на основния контейнер: преоразпределянето на паметта на стандартния std::vector<T> може да направи единичното вмъкване линейно.

Примерът извежда същите данни в низходящ и възходящ ред, като изпразва и двете опашки. Този запис е за C++23; свързаният работен проект е по-нов и не е замразен текст на C++23.

Примери

#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' : ' ');
    }
}

Резултат

7 4 1 1
1 1 4 7

Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.

Източници