Třída priority_queue

Adaptér kontejneru, který udržuje kolekci prvků, kde největší (nebo nejvyšší priorita) prvek je vždy přístupný v horní části. Můžete přidat nové prvky a odebrat nebo prozkoumat horní prvek, ale nemůžete přímo přistupovat k prvkům uprostřed kolekce.

Syntaxe

template <class Type, class Container= vector <Type>, class Compare= less <typename Container ::value_type>>
class priority_queue

Parametry

Type
Datový typ elementu priority_queue, který se má uložit do souboru .

Container
Typ základního kontejneru, který ukládá prvky pro priority_queueobjekt .

Compare
Typ, který poskytuje objekt funkce, který porovnává dvě hodnoty prvků jako klíče řazení k určení jejich relativního pořadí v priority_queue. Tento argument je nepovinný. Binární predikát less<typename Container::value_type> je výchozí.

Poznámky

Prvky třídy Type zadané v prvním parametru priority_queue šablony objektu jsou ekvivalentní value_type a musí odpovídat typu prvku v základní třídě Container kontejneru určené druhým parametrem šablony. Musí Type být přiřaditelné, což znamená, že můžete kopírovat objekty tohoto typu a přiřazovat hodnoty proměnným daného typu.

Pomocí priority_queue funkce porovnání určí, které prvky mají vyšší prioritu. Tato funkce porovnání je objektem funkce třídy Traits. Pokud chcete pracovat s priority_queueprvky, musí podporovat porovnání pouze pomocí operátoru menší než (<), aby bylo možné uspořádat prvky v pořadí.

Můžete změnit typ základního kontejneru, který priority_queuepoužívá . Můžete to udělat z důvodů výkonu. Výchozí hodnota , je obvykle nejvhodnější pro umístění mezipaměti, vectorprotože prvky jsou uloženy v souvislé úložiště a provádí méně přidělení při růstu. Možná byste ale měli zvážit deque , jestli máte velmi velké nebo nevázané fronty a pohyblivé prvky jsou nákladné. Další informace o vhodných základních třídách kontejnerů najdete v tématu container_type.

Přidání a odebrání prvků z priority_queue obou mají logaritmickou složitost. Přístup k prvkům v elementech priority_queue má konstantní složitost.

Standardní knihovna jazyka C++ definuje další adaptéry kontejneru, které můžete použít k uložení prvků v : priority_queuestack, queuea priority_queue:

• Třída stack podporuje datovou strukturu typu last-in (FIRST-out). Vezměte v úvahu zásobník plátů: můžete vkládat, kontrolovat nebo odebírat prvky (desky) pouze z horní části zásobníku, což je poslední prvek na konci základního kontejneru.
• Třída queue podporuje datovou strukturu FIFO (first-in). Zvažte lidi na řádku. Do zadní části řádku přidáte prvky (osoby) a odeberete je z přední části řádku. Přední i zadní část čáry je možné zkontrolovat.
• Třída priority_queue objednává své prvky tak, aby největší prvek byl vždy v horní části. Podporuje vložení prvku a kontrolu a odebrání horního prvku.

Examples

• Zkontrolujte, jestli je prázdný.priority_queue
• Pop – prvky a kontrola velikosti fronty
• Použití vlastních kontejnerů a porovnávačů
• Nasdílení elementů a čtení horní části
• Získání počtu prvků
• Přístup k hornímu prvku
• Použití aliasu priority_queue value_type
• Použití uživatelem definovaného datového typu

Konstruktory

Konstruktor	Popis
priority_queue	Vytvoří prázdnou priority_queue nebo je kopií rozsahu základního objektu kontejneru nebo jiného priority_queueobjektu .

Typedefs

Název typu	Popis
container_type	Typ, který poskytuje základní kontejner, který se priority_queue přizpůsobí.
size_type	Typ celého čísla bez znaménka, který může představovat počet prvků v objektu priority_queue.
value_type	Typ, který představuje typ objektu uloženého jako prvek v objektu priority_queue.

Členské funkce

Členová funkce	Popis
empty	Testuje, priority_queue jestli je prázdný.
pop	Odebere největší prvek priority_queue z nejvyšší pozice.
push	Přidá prvek do fronty priority na základě priority prvku z operator<.
size	Vrátí počet prvků v sadě priority_queue.
top	Vrátí odkaz const na největší prvek v horní části priority_queue.

Požadavky

Záhlaví:<queue>

Obor názvů:std

priority_queue::container_type

Typ, který poskytuje základní kontejner, který se má přizpůsobit.

typedef Container container_type;

Poznámky

Typ je synonymem pro parametr Containeršablony .

Vhodné základní třídy kontejneru pro priority_queue zahrnutí deque třídy, výchozí vector třídy nebo jakéhokoli jiného sekvence kontejneru, který podporuje operace front, push_backa pop_back a iterátor náhodného přístupu. Adaptér kontejneru zapouzdřuje základní třídu kontejneru a zveřejňuje pouze omezenou sadu funkcí člena kontejneru sekvence jako veřejné rozhraní.

Příklad deklarace a použití container_typenajdete v tématu Použití vlastních kontejnerů a porovnávačů.

priority_queue::empty

Testuje, jestli priority_queue je prázdný.

bool empty() const;

Návratová hodnota

true priority_queue pokud je prázdný; false pokud priority_queue je neprázdný.

Příklad: Zkontrolujte, jestli priority_queue je prázdný.

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;

   // Declares priority_queues with default deque base container
   priority_queue <int> q1, s2;

   q1.push(1);

   if (q1.empty())
      cout << "The priority_queue q1 is empty." << endl;
   else
      cout << "The priority_queue q1 is not empty." << endl;

   if (s2.empty())
      cout << "The priority_queue s2 is empty." << endl;
   else
      cout << "The priority_queue s2 is not empty." << endl;
}

The priority_queue q1 is not empty.
The priority_queue s2 is empty.

priority_queue::pop

Odebere největší prvek priority_queue z nejvyšší pozice.

void pop();

Poznámky

Aby priority_queue bylo možné tuto člennou funkci používat, musí být neprázdná. Horní část priority_queue vždy obsahuje největší prvek v kontejneru.

Příklad: Prvky pop a velikost kontroly

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;
   priority_queue <int> q1, s2;

   q1.push(10);
   q1.push(20);
   q1.push(30);

   priority_queue <int>::size_type i, iii;
   i = q1.size();
   cout << "The priority_queue length is " << i << "." << endl;

   const int& ii = q1.top();
   cout << "The element at the top of the priority_queue is " << ii << "." << endl;

   q1.pop();

   iii = q1.size();
   cout << "After a pop, the priority_queue length is " << iii << "." << endl;

   const int& iv = q1.top();
   cout << "After a pop, the element at the top of the " << "priority_queue is " << iv << "." << endl;
}

The priority_queue length is 3.
The element at the top of the priority_queue is 30.
After a pop, the priority_queue length is 2.
After a pop, the element at the top of the priority_queue is 20.

priority_queue::priority_queue

Vytvoří prázdnou priority_queue nebo zkopíruje rozsah ze základního objektu kontejneru nebo z jiného priority_queueobjektu .

priority_queue();

explicit priority_queue(const Traits& _comp);

priority_queue(const Traits& _comp, const container_type& _Cont);

priority_queue(const priority_queue& right);

template <class InputIterator>
priority_queue(InputIterator first, InputIterator last);

template <class InputIterator>
priority_queue(InputIterator first, InputIterator last, const Traits& _comp);

template <class InputIterator>
priority_queue(InputIterator first, InputIterator last, const Traits& _comp, const container_type& _Cont);

Parametry

_comp
Porovnávací funkce typu constTraits použitá k seřazení prvků v souboru priority_queue, který ve výchozím nastavení porovnává funkci základního kontejneru.

_Cont
Základní kontejner, ze kterého má být sestavená priority_queue kopie.

right
Z priority_queue nichž sestavená sada má být kopií.

first
Pozice prvního prvku v oblasti prvků, které se mají zkopírovat.

last
Pozice prvního prvku nad rozsah prvků, které se mají zkopírovat.

Poznámky

Každý z prvních tří konstruktorů určuje prázdný iniciála priority_queue, druhý také určuje typ porovnávací funkce (comp), která se má použít při stanovení pořadí prvků a třetí explicitně specifikuje container_type (_Cont), která se má použít. Klíčové slovo explicit potlačí určité druhy automatického převodu typů.

Čtvrtý konstruktor určuje kopii priority_queue right.

Poslední tři konstruktory zkopírují rozsah [first, last) určitého kontejneru a používají hodnoty k inicializaci priority_queue s rostoucí explicitností při zadávání typu porovnávací funkce třídy Traits a container_type.

Příklad: Použití vlastních kontejnerů a porovnávačů

// compile with: /EHsc
#include <queue>
#include <vector>
#include <deque>
#include <list>
#include <iostream>

int main()
{
   using namespace std;

   // Declares a priority_queue with a default vector base container
   priority_queue <int> q1;
   cout << "q1 = ( ";
   while (!q1.empty())
   {
      cout << q1.top() << " ";
      q1.pop();
   }
   cout << ")" << endl;

   // Declares a priority_queue with nondefault deque base container
   priority_queue <int, deque <int>> q2;
   q2.push(5);
   q2.push(15);
   q2.push(10);
   cout << "q2 = ( ";
   while (!q2.empty())
   {
      cout << q2.top() << " ";
      q2.pop();
   }
   cout << ")" << endl;
   cout << "After printing, q2 has " << q2.size() << " elements." << endl;

   // Declares a priority_queue with a vector base container and specifies that
   // the comparison function greater is to be used for ordering elements
   priority_queue <int, vector<int>, greater<int>> q3;
   q3.push(2);
   q3.push(1);
   q3.push(3);
   cout << "q3 = ( ";
   
   while (!q3.empty())
   {
      cout << q3.top() << " ";
      q3.pop();
   }
   cout << ")" << endl;

   // Declares a priority_queue and initializes it with elements copied from another
   // container by first inserting elements into q1 and then copying q1 elements into q4
   q1.push(100);
   q1.push(200);
   priority_queue <int> q4(q1);
   cout << "q4 = ( ";
   while (!q4.empty())
   {
      cout << q4.top() << " ";
      q4.pop();
   }
   cout << ")" << endl;

   // Creates an auxiliary vector object v5 to be used to initialize q5
   vector <int> v5;
   vector <int>::iterator v5_Iter;
   v5.push_back(10);
   v5.push_back(30);
   v5.push_back(20);
   cout << "v5 = ( " ;
   for (v5_Iter = v5.begin() ; v5_Iter != v5.end() ; v5_Iter++)
   {
      cout << *v5_Iter << " ";
   }
   cout << ")" << endl;

   // Declares and initializes a priority_queue q5 by copying the
   // range v5[ first,  last) from vector v5
   priority_queue <int> q5(v5.begin(), v5.begin() + 2);
   cout << "q5 = ( ";
   while (!q5.empty())
   {
      cout << q5.top() << " ";
      q5.pop();
   }
   cout << ")" << endl;

   // Declares a priority_queue q6 with a comparison function greater and
   // initializes q6 by copying the range v5[ first,  last) from vector v5
   priority_queue <int, vector<int>, greater<int>> q6(v5.begin(), v5.begin() + 2);
   cout << "q6 = ( ";
   while (!q6.empty())
   {
      cout << q6.top() << " ";
      q6.pop();
   }
   cout << ")" << endl;
}

priority_queue::push

Přidá prvek do fronty priority na základě priority prvku z operator<.

void push(const Type& val);

Parametry

val
Prvek, který chcete přidat na začátek priority_queuesouboru .

Poznámky

Horní část kontejneru priority_queue obsahuje největší prvek.

Příklad: Nasdílení elementů a čtení horní části

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;
   priority_queue<int> q1;

   q1.push(10);
   q1.push(30);
   q1.push(20);

   priority_queue<int>::size_type i;
   i = q1.size();
   cout << "The priority_queue length is " << i << "." << endl;

   const int& ii = q1.top();
   cout << "The element at the top of the priority_queue is " << ii << "." << endl;
}

The priority_queue length is 3.
The element at the top of the priority_queue is 30.

priority_queue::size

Vrátí počet prvků v sadě priority_queue.

size_type size() const;

Návratová hodnota

Aktuální délka priority_queue.

Příklad: Získání počtu prvků v priority_queue

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;
   priority_queue <int> q1, q2;
   priority_queue <int>::size_type i;

   q1.push(1);
   i = q1.size();
   cout << "The priority_queue length is " << i << "." << endl;

   q1.push(2);
   i = q1.size();
   cout << "The priority_queue length is now " << i << "." << endl;
}

The priority_queue length is 1.
The priority_queue length is now 2.

priority_queue::size_type

Typ celého čísla bez znaménka, který představuje počet prvků v objektu priority_queue.

typedef typename Container::size_type size_type;

Poznámky

Tento typ je synonymem základního size_type kontejneru, který priority_queue se přizpůsobí.

Příklad: Přístup k hornímu prvku

Příklad deklarace a použití size_typenaleznete v tématu Získání počtu prvků.

priority_queue::top

Vrátí odkaz const na největší prvek v horní části priority_queue.

const_reference top() const;

Návratová hodnota

Odkaz na největší prvek, jak je určeno Traits funkcí, objektu priority_queue.

Poznámky

Aby priority_queue bylo možné tuto člennou funkci používat, musí být neprázdná.

Příklad: Získání horního prvku priority_queue

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;
   priority_queue<int> q1;

   q1.push(10);
   q1.push(30);
   q1.push(20);

   priority_queue<int>::size_type i;
   i = q1.size();
   cout << "The priority_queue length is " << i << "." << endl;

   const int& ii = q1.top();
   cout << "The element at the top of the priority_queue is " << ii << "." << endl;
}

The priority_queue length is 3.
The element at the top of the priority_queue is 30.

priority_queue::value_type

Typ, který představuje typ objektu uloženého jako prvek v objektu priority_queue.

typedef typename Container::value_type value_type;

Poznámky

Tento typ je synonymem základního value_type kontejneru, který priority_queue se přizpůsobí.

Příklad: Použití aliasu priority_queue value_type

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;

   // Declares priority_queues with default deque base container
   priority_queue<int>::value_type AnInt;

   AnInt = 69;
   cout << "The value_type is AnInt = " << AnInt << endl;

   priority_queue<int> q1;
   q1.push(AnInt);
   cout << "The element at the top of the priority_queue is " << q1.top() << "." << endl;
}

The value_type is AnInt = 69
The element at the top of the priority_queue is 69.

Příklad: Použití uživatelem definovaného datového typu

Chcete-li použít priority_queue s uživatelem definovanými prvky typu, musíte poskytnout způsob, jak tyto prvky porovnat. Můžete buď definovat operator< typ, nebo zadat vlastní objekt funkce porovnání.

Následující příklad ukazuje priority_queue , že ukládá Task objekty seřazené podle úrovně priority. Úkoly s vyšší prioritou jsou v horní části fronty.

// compile with: /EHsc
#include <queue>
#include <iostream>
#include <string>

struct Task
{
    int priority;
    std::string name;

    // Define operator< for priority_queue ordering
    // Returns true if this task has LOWER priority than other
    // (priority_queue puts the "largest" element at the top)
    bool operator<(const Task& other) const
    {
        return priority < other.priority;
    }
};

int main()
{
    std::priority_queue<Task> tasks;

    tasks.push({3, "Low priority task"});
    tasks.push({10, "High priority task"});
    tasks.push({5, "Medium priority task"});

    std::cout << "Processing tasks by priority:\n";
    while (!tasks.empty())
    {
        const Task& t = tasks.top();
        std::cout << "  Priority " << t.priority << ": " << t.name << "\n";
        tasks.pop();
    }
}

Processing tasks by priority:
  Priority 10: High priority task
  Priority 5: Medium priority task
  Priority 3: Low priority task

Poznámky

Pokud chcete jiné řazení (například jako první nižší hodnoty), zadejte vlastní srovnávací program:

struct ComparePriority
{
    bool operator()(const Task& a, const Task& b)
    {
        return a.priority > b.priority; // Lower priority value means higher priority
    }
};

std::priority_queue<Task, std::vector<Task>, ComparePriority> minQueue;

Viz také

Bezpečný přístup z více vláken ve standardní knihovně C++
Standardní knihovna C++ – referenční dokumentace