Dela via

priority_queue klass

En containeradapter som underhåller en samling element där det största elementet (eller högsta prioritet) alltid är tillgängligt längst upp. Du kan lägga till nya element och ta bort eller undersöka det översta elementet, men du kan inte komma åt element direkt i mitten av samlingen.

Syntax

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

Parameterar

Type
Den elementdatatyp som ska lagras i priority_queue.

Container
Typen av den underliggande containern som lagrar elementen priority_queueför .

Compare
Den typ som tillhandahåller ett funktionsobjekt som jämför två elementvärden som sorteringsnycklar för att fastställa deras relativa ordning i priority_queue. Det här argumentet är valfritt. Det binära predikatet less<typename Container::value_type> är standardvärdet.

Anmärkningar

Element i klassen Type som anges i den första mallparametern för value_type ett priority_queue objekt motsvarar och måste matcha elementtypen i den underliggande containerklassen Container som anges av den andra mallparametern. Type Måste vara tilldelningsbar, vilket innebär att du kan kopiera objekt av den typen och tilldela värden till variabler av den typen.

Använder priority_queue en jämförelsefunktion för att avgöra vilka element som har högre prioritet. Den här jämförelsefunktionen är ett funktionsobjekt för klassen Traits. Om du vill arbeta med priority_queuebehöver dina element bara ha stöd för jämförelse med mindre än-operatorn (<) så att de kan ordna elementen i ordning.

Du kan ändra den underliggande containertyp som används av priority_queue. Du kanske vill göra det av prestandaskäl. Standardvärdet , vectorär vanligtvis bäst för cachelokalitet eftersom element lagras i sammanhängande lagring och gör färre allokeringar när de växer. Men du kanske skulle överväga deque om du har mycket stora eller obundna köer och att flytta element är dyrt. Mer information om lämpliga underliggande containerklasser finns i container_type.

Att lägga till och ta bort element från båda priority_queue har logaritmisk komplexitet. Att komma åt element i en priority_queue har konstant komplexitet.

C++-standardbiblioteket definierar andra containeradapter som du kan använda för att lagra elementen i : priority_queuestack, queueoch priority_queue:

  • Klassenstack stöder en lifo-datastruktur (last-in, first-out). Överväg en stack med plattor: du kan infoga, inspektera eller ta bort element (plattor) endast från toppen av stacken, som är det sista elementet i slutet av bascontainern.
  • Klassenqueue stöder en först-i-först-ut-datastruktur (FIFO). Tänk på människor i en rad. Du lägger till element (personer) på baksidan av linjen och tar bort dem från framsidan av linjen. Både framsidan och baksidan av en linje kan inspekteras.
  • Klassen priority_queue beställer sina element så att det största elementet alltid är högst upp. Det stöder infogning av ett element och kontroll och borttagning av det översta elementet.

Examples

Konstruktörer

Konstruktor Description
priority_queue Konstruerar ett priority_queue som är tomt eller som är en kopia av ett intervall av ett bascontainerobjekt eller ett annat priority_queue.

Typedefs

Typnamn Description
container_type En typ som tillhandahåller bascontainern som priority_queue anpassas.
size_type En osignerad heltalstyp som kan representera antalet element i en priority_queue.
value_type En typ som representerar den typ av objekt som lagras som ett element i en priority_queue.

Medlemsfunktioner

Medlemsfunktion Description
empty Testar om är priority_queue tom.
pop Tar bort det största elementet från priority_queue den översta positionen.
push Lägger till ett element i prioritetsköen baserat på prioriteten för elementet från operator<.
size Returnerar antalet element i priority_queue.
top Returnerar en const-referens till det största elementet överst i priority_queue.

Kravspecifikation

Rubrik:<queue>

Namespace:std

priority_queue::container_type

En typ som tillhandahåller bascontainern som ska anpassas.

typedef Container container_type;

Anmärkningar

Typen är en synonym för mallparametern Container.

Lämpliga underliggande containerklasser för priority_queue inkluderar deque klass, standardklassvector eller någon annan sekvenscontainer som stöder åtgärderna fronti , push_backoch pop_back och en iterator för slumpmässig åtkomst. Containeradaptern kapslar in den underliggande containerklassen och exponerar endast en begränsad uppsättning sekvenscontainermedlemsfunktioner som ett offentligt gränssnitt.

Ett exempel på hur du deklarerar och använder container_typefinns i Använda anpassade containrar och jämförelseverktyg

priority_queue::empty

Testar om en priority_queue är tom.

bool empty() const;

Returvärde

true om är priority_queue tom; false om är priority_queue nonempty.

Exempel: Kontrollera om är priority_queue tom

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

Tar bort det största elementet från priority_queue den översta positionen.

void pop();

Anmärkningar

Måste priority_queue vara icke-lydigt för att använda den här medlemsfunktionen. Överst i innehåller priority_queue alltid det största elementet i containern.

Exempel: Pop-element och kontrollstorlek

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

Skapar ett priority_queue som är tomt eller som kopierar ett intervall från ett bascontainerobjekt eller från ett annat priority_queue.

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

Parameterar

_comp
Jämförelsefunktionen av typen constTraits som används för att sortera elementen priority_queuei , som standard jämför bascontainerns funktion.

_Cont
Den bascontainer som den konstruerade priority_queue ska vara en kopia av.

right
Som priority_queue den konstruerade uppsättningen ska vara en kopia av.

first
Positionen för det första elementet i området med element som ska kopieras.

last
Positionen för det första elementet utöver det område av element som ska kopieras.

Anmärkningar

Var och en av de tre första konstruktorerna anger en tom initial priority_queue, den andra anger också vilken typ av jämförelsefunktion (comp) som ska användas för att fastställa ordningen på elementen och den tredje anger uttryckligen den container_type (_Cont) som ska användas. explicit Nyckelordet utelämnar vissa typer av automatisk typkonvertering.

Den fjärde konstruktorn anger en kopia av priority_queue right.

De tre sista konstruktorerna kopierar intervallet [first, last) för en viss container och använder värdena för att initiera en priority_queue med ökad explicititet när du anger typen av jämförelsefunktion för klassen Traits och container_type.

Exempel: Använda anpassade containrar och jämförelseverktyg

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

Lägger till ett element i prioritetsköen baserat på prioriteten för elementet från operator<.

void push(const Type& val);

Parameterar

val
Elementet som ska läggas till överst i priority_queue.

Anmärkningar

Överst i priority_queue innehåller det största elementet i containern.

Exempel: Push-överföra element och läsa överst

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

Returnerar antalet element i priority_queue.

size_type size() const;

Returvärde

Den aktuella längden på priority_queue.

Exempel: Hämta antalet element i 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

En osignerad heltalstyp som representerar antalet element i en priority_queue.

typedef typename Container::size_type size_type;

Anmärkningar

Den här typen är synonym för bascontainern size_type som priority_queue anpassas.

Exempel: Få åtkomst till det översta elementet

Ett exempel på hur du deklarerar och använder size_typefinns i Hämta antalet element

priority_queue::top

Returnerar en const-referens till det största elementet överst i priority_queue.

const_reference top() const;

Returvärde

En referens till det största elementet, som bestäms av Traits funktionen, objektet för priority_queue.

Anmärkningar

Måste priority_queue vara icke-lydigt för att använda den här medlemsfunktionen.

Exempel: Hämta det översta elementet i 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

En typ som representerar den typ av objekt som lagras som ett element i en priority_queue.

typedef typename Container::value_type value_type;

Anmärkningar

Den här typen är synonym för bascontainern value_type som priority_queue anpassas.

Exempel: Använd aliaset 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.

Exempel: Använda en användardefinierad datatyp

Om du vill använda priority_queue med användardefinierade typelement måste du ange ett sätt att jämföra elementen. Du kan antingen definiera operator< för din typ eller ange ett anpassat jämförelsefunktionsobjekt.

I följande exempel visas en priority_queue som lagrar Task objekt, ordnade efter prioritetsnivå. Uppgifter med högre prioritetsvärden finns överst i kön.

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

Anmärkningar

Om du vill ha olika sortering (till exempel lägre värden först) anger du en anpassad jämförelse:

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;

Se även

Trådsäkerhet i C++-standardbiblioteket
Referens för C++-standardbibliotek

  • Last updated on