Bagikan melalui

kelas priority_queue

Adaptor kontainer yang mempertahankan kumpulan elemen di mana elemen terbesar (atau prioritas tertinggi) selalu dapat diakses di bagian atas. Anda dapat menambahkan elemen baru dan menghapus atau memeriksa elemen teratas, tetapi Anda tidak dapat langsung mengakses elemen di tengah koleksi.

Sintaks

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

Parameter

Type
Jenis data elemen untuk disimpan di priority_queue.

Container
Jenis kontainer yang mendasar yang menyimpan elemen untuk priority_queue.

Compare
Jenis yang menyediakan objek fungsi yang membandingkan dua nilai elemen sebagai kunci pengurutan untuk menentukan urutan relatifnya di priority_queue. Argumen ini bersifat opsional. Predikat less<typename Container::value_type> biner adalah default.

Keterangan

Elemen kelas Type yang ditentukan dalam parameter priority_queue templat pertama objek setara dengan dan harus cocok dengan value_type jenis elemen di kelas Container kontainer yang mendasar yang ditentukan oleh parameter templat kedua. harus dapat ditetapkan, yang berarti Anda dapat menyalin objek dari jenis tersebut Type dan menetapkan nilai ke variabel jenis tersebut.

menggunakan priority_queue fungsi perbandingan untuk menentukan elemen mana yang memiliki prioritas yang lebih tinggi. Fungsi perbandingan ini adalah objek fungsi kelas Traits. Untuk bekerja dengan priority_queue, elemen Anda hanya perlu mendukung perbandingan menggunakan operator kurang dari (<) sehingga dapat mengatur elemen secara berurutan.

Anda dapat mengubah jenis kontainer yang mendasar yang digunakan oleh priority_queue. Anda mungkin ingin melakukannya karena alasan performa. Defaultnya, vector, biasanya paling baik untuk lokalitas cache karena elemen disimpan dalam penyimpanan yang berdampingan, dan melakukan lebih sedikit alokasi saat tumbuh. Tetapi mungkin Anda akan mempertimbangkan deque apakah Anda memiliki antrean yang sangat besar atau tidak terbatas dan elemen bergerak mahal. Untuk informasi selengkapnya tentang kelas kontainer yang mendasar yang sesuai, lihat container_type.

Menambahkan dan menghapus elemen dari priority_queue keduanya memiliki kompleksitas logaritma. Mengakses elemen dalam memiliki kompleksitas konstan priority_queue .

Pustaka Standar C++ menentukan adaptor kontainer lain yang dapat Anda gunakan untuk menyimpan elemen di priority_queue: stack, queue, dan priority_queue:

  • Kelas stack mendukung struktur data last-in, first-out (LIFO). Pertimbangkan tumpukan pelat: Anda dapat menyisipkan, memeriksa, atau menghapus elemen (pelat) hanya dari bagian atas tumpukan, yang merupakan elemen terakhir di akhir kontainer dasar.
  • Kelas queue mendukung struktur data first-in, first-out (FIFO). Pertimbangkan orang-orang dalam satu baris. Anda menambahkan elemen (orang) ke bagian belakang garis dan menghapusnya dari depan garis. Baik bagian depan maupun belakang garis dapat diperiksa.
  • Kelas priority_queue memesan elemennya sehingga elemen terbesar selalu berada di bagian atas. Ini mendukung penyisipan elemen dan inspeksi dan penghapusan elemen teratas.

Examples

Konstruktor

Konstruktor Deskripsi
priority_queue Membangun priority_queue yang kosong atau yang merupakan salinan dari rentang objek kontainer dasar atau lainnya priority_queue.

Typedefs

Nama jenis Deskripsi
container_type Jenis yang menyediakan kontainer dasar yang priority_queue disesuaikan.
size_type Jenis bilangan bulat yang tidak ditandatangani yang dapat mewakili jumlah elemen dalam priority_queue.
value_type Jenis yang mewakili jenis objek yang disimpan sebagai elemen dalam priority_queue.

Fungsi anggota

Fungsi anggota Deskripsi
empty Menguji apakah priority_queue kosong.
pop Menghapus elemen terbesar dari priority_queue posisi atas.
push Menambahkan elemen ke antrean prioritas berdasarkan prioritas elemen dari operator<.
size Mengembalikan jumlah elemen dalam priority_queue.
top Mengembalikan referensi const ke elemen terbesar di bagian priority_queueatas .

Persyaratan

Header:<queue>

kumpulan nama XML: std

priority_queue::container_type

Jenis yang menyediakan kontainer dasar yang akan diadaptasi.

typedef Container container_type;

Keterangan

Jenisnya adalah sinonim untuk parameter Containertemplat .

Kelas kontainer yang mendasar yang sesuai untuk priority_queue menyertakan deque Kelas, Kelas defaultvector, atau kontainer urutan lainnya yang mendukung operasi front, push_back, dan pop_back iterator akses acak. Adaptor kontainer merangkum kelas kontainer yang mendasarinya dan hanya mengekspos sekumpulan terbatas dari fungsi anggota kontainer urutan sebagai antarmuka publik.

Untuk contoh cara mendeklarasikan dan menggunakan container_type, lihat Menggunakan kontainer dan pembanding kustom

priority_queue::empty

Menguji apakah kosong priority_queue .

bool empty() const;

Tampilkan Nilai

true priority_queue jika kosong; false jika priority_queue tidak ada.

Contoh: Periksa apakah priority_queue kosong

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

Menghapus elemen terbesar dari priority_queue posisi atas.

void pop();

Keterangan

priority_queue harus tidak ada untuk menggunakan fungsi anggota ini. Bagian atas priority_queue selalu memegang elemen terbesar dalam kontainer.

Contoh: Elemen pop dan ukuran pemeriksaan

// 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 Membuat yang kosong atau yang menyalin rentang dari objek kontainer dasar atau dari objek kontainer lain 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);

Parameter

_comp
Fungsi perbandingan jenis constTraits yang digunakan untuk mengurutkan elemen dalam priority_queue, yang defaultnya membandingkan fungsi kontainer dasar.

_Cont
Kontainer dasar yang dibangun priority_queue akan menjadi salinan.

right
di priority_queue mana set yang dibangun adalah menjadi salinan.

first
Posisi elemen pertama dalam rentang elemen yang akan disalin.

last
Posisi elemen pertama di luar rentang elemen yang akan disalin.

Keterangan

Masing-masing dari tiga konstruktor pertama menentukan awal priority_queuekosong , yang kedua juga menentukan jenis fungsi perbandingan (comp) yang akan digunakan dalam menetapkan urutan elemen dan yang ketiga secara eksplisit menentukan container_type (_Cont) yang akan digunakan. Kata kunci explicit menekan jenis konversi jenis otomatis tertentu.

Konstruktor keempat menentukan salinan priority_queue right.

Tiga konstruktor terakhir menyalin rentang [first, last) beberapa kontainer dan menggunakan nilai untuk menginisialisasi priority_queue dengan meningkatkan eksplisititas dalam menentukan jenis fungsi perbandingan kelas Traits dan container_type.

Contoh: Menggunakan kontainer dan pembanding kustom

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

Menambahkan elemen ke antrean prioritas berdasarkan prioritas elemen dari operator<.

void push(const Type& val);

Parameter

val
Elemen yang akan ditambahkan ke bagian priority_queueatas .

Keterangan

Bagian atas priority_queue berisi elemen terbesar dalam kontainer.

Contoh: Mendorong elemen dan membaca bagian atas

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

Mengembalikan jumlah elemen dalam priority_queue.

size_type size() const;

Tampilkan Nilai

Panjang saat ini dari priority_queue.

Contoh: Mendapatkan jumlah elemen dalam 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

Jenis bilangan bulat yang tidak ditandatangani yang mewakili jumlah elemen dalam priority_queue.

typedef typename Container::size_type size_type;

Keterangan

Jenis ini adalah sinonim untuk size_type kontainer dasar yang priority_queue disesuaikan.

Contoh: Mengakses elemen teratas

Untuk contoh cara mendeklarasikan dan menggunakan size_type, lihat Mendapatkan jumlah elemen

priority_queue::top

Mengembalikan referensi const ke elemen terbesar di bagian priority_queueatas .

const_reference top() const;

Tampilkan Nilai

Referensi ke elemen terbesar, seperti yang ditentukan oleh Traits fungsi, objek dari priority_queue.

Keterangan

priority_queue harus tidak ada untuk menggunakan fungsi anggota ini.

Contoh: Mendapatkan elemen teratas dari 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

Jenis yang mewakili jenis objek yang disimpan sebagai elemen dalam priority_queue.

typedef typename Container::value_type value_type;

Keterangan

Jenis ini adalah sinonim untuk value_type kontainer dasar yang priority_queue disesuaikan.

Contoh: Gunakan alias 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.

Contoh: Menggunakan jenis data yang ditentukan pengguna

Untuk menggunakan priority_queue dengan elemen jenis yang ditentukan pengguna, Anda harus menyediakan cara untuk membandingkan elemen. Anda dapat menentukan operator< untuk jenis Anda atau menyediakan objek fungsi perbandingan kustom.

Contoh berikut menunjukkan priority_queue yang menyimpan Task objek, diurutkan berdasarkan tingkat prioritas. Tugas dengan nilai prioritas yang lebih tinggi berada di bagian atas antrean.

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

Keterangan

Jika Anda menginginkan pengurutan yang berbeda (misalnya, nilai yang lebih rendah terlebih dahulu), berikan komparator kustom:

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;

Lihat juga

Keamanan utas di Pustaka Standar C++
Referensi pustaka standar C++

  • Last updated on