priority_queue osztály

Olyan tárolóadagrátor, amely olyan elemek gyűjteményét tartja karban, amelyek tetején mindig a legnagyobb (vagy a legmagasabb prioritású) elem érhető el. Hozzáadhat új elemeket, eltávolíthatja vagy megvizsgálhatja a felső elemet, de közvetlenül nem férhet hozzá a gyűjtemény közepén lévő elemekhez.

Szemantika

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

Paraméterek

Type
Az elem adattípusa, amely a priority_queue.

Container
A mögöttes tároló típusa, amely a priority_queue.

Compare
Az a típus, amely egy függvényobjektumot biztosít, amely rendezési kulcsként hasonlít össze két elemértéket a relatív sorrend meghatározásához a priority_queue. Ez az argumentum nem kötelező. A bináris predikátum less<typename Container::value_type> az alapértelmezett.

Megjegyzések

Az objektum első sablonparaméterében megadott osztályelemek Type egyenértékűekvalue_type, és meg kell egyeznie a második sablonparaméter által megadott mögöttes tárolóosztály Container elemtípusával.priority_queue Az Type objektumnak hozzárendelhetőnek kell lennie, ami azt jelenti, hogy másolhatja az ilyen típusú objektumokat, és értékeket rendelhet hozzá az adott típusú változókhoz.

A priority_queue függvény összehasonlító függvényt használ annak meghatározására, hogy mely elemek rendelkeznek magasabb prioritással. Ez az összehasonlító függvény az osztály Traitsfüggvényobjektuma. A használathoz priority_queueaz elemeknek csak a kisebb operátorral (<) kell támogatniuk az összehasonlítást, hogy rendezhessék az elemeket.

Módosíthatja a mögöttes tárolótípust, amelyet a priority_queue. Ezt teljesítménybeli okokból érdemes megtennie. Az alapértelmezett beállítás általában a gyorsítótár helyének megfelelően működik, vectormivel az elemek egybefüggő tárolóban vannak tárolva, és a növekedés során kevesebb foglalást végeznek. De talán megfontolná deque , ha nagyon nagy vagy kötetlen üzenetsorokkal rendelkezik, és az elemek áthelyezése költséges. A megfelelő mögöttes tárolóosztályokról további információt a container_type talál.

Az elemek hozzáadása és eltávolítása mindkettőből priority_queue logaritmikus összetettséggel rendelkezik. Az elemek priority_queue elérése állandó összetettséggel rendelkezik.

A C++ Standard kódtár más tárolóadabrátorokat határoz meg, amelyekkel a következő elemeket tárolhatja: priority_queuestack, queueés priority_queue:

• Az stack osztály támogatja a last-in, first-out (LIFO) adatstruktúrát. Fontolja meg a lemezverem használatát: az elemeket (lemezeket) csak a verem tetejéről szúrhatja be, vizsgálhatja meg vagy távolíthatja el, amely az alaptároló végének utolsó eleme.
• Az queue osztály támogatja az első, első szintű (FIFO) adatstruktúrát. Fontolja meg az embereket egy sorban. Elemeket (személyeket) ad hozzá a vonal hátuljához, és eltávolítja őket a sor elejéről. Az első és a hátsó vonal is vizsgálható.
• Az priority_queue osztály úgy rendeli meg az elemeket, hogy a legnagyobb elem mindig a tetején legyen. Támogatja az elem beszúrását, valamint a felső elem ellenőrzését és eltávolítását.

Példák

• Ellenőrizze, hogy az priority_queue üres-e
• Előugró elemek és az üzenetsor méretének ellenőrzése
• Egyéni tárolók és összehasonlítók használata
• Elemek leküldése és a felül olvasása
• Elemek számának lekérése
• A felső elem elérése
• Az priority_queue value_type alias használata
• Felhasználó által definiált adattípus használata

Konstruktorok

Konstruktor	Description
priority_queue	priority_queue Üres vagy egy alaptároló objektum vagy más priority_queuetartomány másolatát hozza létre.

Typedefs

Típus neve	Description
container_type	Olyan típus, amely az adaptálható alaptárolót priority_queue biztosítja.
size_type	Egy aláíratlan egész számtípus, amely a priority_queue.
value_type	Olyan típus, amely az elemként tárolt objektum típusát jelöli egy priority_queue.

Tagfüggvények

Tagfüggvény	Description
empty	Ellenőrzi, hogy üres-e priority_queue .
pop	Eltávolítja a legnagyobb elemet a priority_queue felső pozícióból.
push	Elemet ad hozzá a prioritási üzenetsorhoz az elem operator<prioritása alapján.
size	A függvény elemeinek számát adja eredményül priority_queue.
top	Egy const-hivatkozást ad vissza a legnagyobb elemre a priority_queuetetején.

Requirements

Fejléc:<queue>

Namespace:std

priority_queue::container_type

Az adaptálandó alaptárolót biztosító típus.

typedef Container container_type;

Megjegyzések

A típus a Containersablonparaméter szinonimája.

Megfelelő alapul szolgáló tárolóosztályok az priority_queuedeque osztály, az alapértelmezett vector osztály vagy bármely más, a , push_backés pop_back egy véletlenszerű hozzáférésű iterátor műveleteit fronttámogató szekvenciatárolókhoz. A tárolóadaptor beágyazza a mögöttes tárolóosztályt, és a szekvenciatároló-tag csak korlátozott halmazát teszi elérhetővé nyilvános interfészként.

Példa a deklarálhatóságra és a használatra container_type: Egyéni tárolók és összehasonlítók használata

priority_queue::empty

Ellenőrzi, hogy egy priority_queue üres-e.

bool empty() const;

Visszaadott érték

true ha az priority_queue üres; false ha az priority_queue nincs megadva.

Példa: Ellenőrizze, hogy az priority_queue üres-e

// 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

Eltávolítja a legnagyobb elemet a priority_queue felső pozícióból.

void pop();

Megjegyzések

A priority_queue tagfüggvény használatához nem lehet használható. A mindig felső priority_queue része a tároló legnagyobb elemét tartalmazza.

Példa: Előugró elemek és a méret ellenőrzése

// 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

priority_queue Üres vagy egy alaptároló-objektumból vagy egy másikból priority_queuemásolt tartományt hoz létre.

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);

Paraméterek

_comp
A típus constTraits összehasonlítási függvénye, amely az alaptároló elemeinek sorrendjére priority_queueszolgál, amely alapértelmezés szerint az alaptároló függvényének összehasonlítására szolgál.

_Cont
Az alaptároló, amelynek a felépítése priority_queue másolat.

right
A priority_queue létrehozott készlet másolatnak minősül.

first
A másolandó elemek tartományának első elemének pozíciója.

last
Az első elem helye a másolandó elemek tartományán túl.

Megjegyzések

Az első három konstruktor mindegyike egy üres kezdőbetűt priority_queuehatároz meg, a második pedig az elemek sorrendjének meghatározásához használandó összehasonlító függvény típusát (comp), a harmadik pedig a container_type használni kívánt (_Cont) értéket. A kulcsszó explicit letilt bizonyos típusú automatikus típuskonvertálást.

A negyedik konstruktor megadja a példányt.priority_queue right

Az utolsó három konstruktor kimásolja egy tároló tartományát [first, last) , és az értékekkel inicializál egy priority_queue növekvő explicititást az osztály Traits és container_typea .

Példa: Egyéni tárolók és összehasonlítók használata

// 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

Elemet ad hozzá a prioritási üzenetsorhoz az elem operator<prioritása alapján.

void push(const Type& val);

Paraméterek

val
A hozzáfűzendő elem a priority_queuefelső részen.

Megjegyzések

A felső része a priority_queue tároló legnagyobb elemét tartalmazza.

Példa: Elemek leküldése és a felül olvasása

// 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

A függvény elemeinek számát adja eredményül priority_queue.

size_type size() const;

Visszaadott érték

priority_queueA .

Példa: Az elemek számának lekérése a 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

Egy aláíratlan egész számtípus, amely egy priority_queue.

typedef typename Container::size_type size_type;

Megjegyzések

Ez a típus az alaptároló szinonimája size_type , amelyet a priority_queue rendszer adaptál.

Példa: A felső elem elérése

A deklarálásához és használatához size_typelásd : Az elemek számának lekérése

priority_queue::top

Egy const-hivatkozást ad vissza a legnagyobb elemre a priority_queuetetején.

const_reference top() const;

Visszaadott érték

A függvény által Traits meghatározott legnagyobb elemre mutató hivatkozás, amely a priority_queue.

Megjegyzések

A priority_queue tagfüggvény használatához nem lehet használható.

Példa: A felső elem lekérése 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

Olyan típus, amely az elemként tárolt objektum típusát jelöli egy priority_queue.

typedef typename Container::value_type value_type;

Megjegyzések

Ez a típus az alaptároló szinonimája value_type , amelyet a priority_queue rendszer adaptál.

Példa: Az priority_queue value_type alias használata

// 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élda: Felhasználó által definiált adattípus használata

A felhasználó által definiált típuselemekkel való használathoz priority_queue meg kell adnia az elemek összehasonlításának módját. Megadhatja operator< a típust, vagy megadhat egy egyéni összehasonlító függvényobjektumot.

Az alábbi példa egy priority_queue objektumokat tároló Task objektumot mutat be, prioritási szint szerint rendezve. A magasabb prioritású értékeket tartalmazó tevékenységek az üzenetsor tetején találhatók.

// 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

Megjegyzések

Ha eltérő rendezést szeretne (például alacsonyabb értékeket), adjon meg egy egyéni összehasonlítót:

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;

Lásd még

Szálbiztonság a C++ standard kódtárban
C++ standard kódtár referenciája