std::priority_queue::push

#include <queue>

Thêm một phần tử mới vào std::priority_queue. Phần tử mới sẽ được sắp xếp vào vị trí thích hợp dựa trên độ ưu tiên của nó.

void push(const value_type& val); // (1)
void push(value_type&& val);      // (2) (since C++11)

Tham số

val

• Giá trị của phần tử cần thêm vào cuối std::priority_queue.
• Phiên bản (1) nhận tham chiếu hằng (const value_type&), cho phép truyền vào một đối tượng đã tồn tại. Đối tượng sẽ được sao chép (copy) vào std::priority_queue.
• Phiên bản (2) (từ C++11) nhận tham chiếu rvalue (value_type&&), cho phép di chuyển (move) đối tượng vào std::priority_queue nếu val là một rvalue, tránh việc sao chép không cần thiết, tối ưu hiệu suất.

Giá trị trả về

Không có giá trị trả về

Đặc điểm

1. Thêm phần tử và duy trì thứ tự ưu tiên: push() thêm phần tử mới vào std::priority_queue và tự động sắp xếp lại các phần tử để đảm bảo phần tử có độ ưu tiên cao nhất luôn ở đầu queue.
2. Tăng kích thước: push() làm tăng kích thước của std::priority_queue lên 1.
3. Hỗ trợ copy và move: Phiên bản (1) thực hiện sao chép phần tử được truyền vào. Phiên bản (2) (từ C++11) hỗ trợ di chuyển (move semantics), giúp tối ưu hiệu suất khi thêm các đối tượng lớn hoặc phức tạp.
4. Dựa trên underlying container và hàm so sánh: push() của std::priority_queue sử dụng các hàm của underlying container (ví dụ: push_back() của std::vector) và hàm so sánh để sắp xếp phần tử.
5. Có thể ném ngoại lệ: Nếu việc cấp phát bộ nhớ cho phần tử mới thất bại, push() có thể ném ra ngoại lệ std::bad_alloc. Ngoài ra, nếu copy constructor (phiên bản 1) hoặc move constructor (phiên bản 2) của value_type ném ngoại lệ, push() cũng sẽ ném ngoại lệ.
6. Độ phức tạp: Độ phức tạp của push() là O(log n), với n là số phần tử trong std::priority_queue. Việc thêm phần tử cần phải duy trì cấu trúc heap của priority queue.

Ví dụ

#include <iostream>
#include <queue>

int main() {
  std::priority_queue<int> mypq;

  mypq.push(30);
  mypq.push(10);
  mypq.push(50);
  mypq.push(20);

  std::cout << "mypq after pushes:";
  while (!mypq.empty()) {
      std::cout << ' ' << mypq.top(); // Output: 50 30 20 10
      mypq.pop();
  }
  std::cout << '\n';

  return 0;
}

Move semantics:

#include <iostream>
#include <queue>
#include <string>

int main() {
  std::priority_queue<std::string> mypq;

  std::string str = "Hello";
  mypq.push(str);             // Sao chép str vào mypq
  mypq.push(std::move(str));  // Di chuyển str vào mypq (str sẽ trở thành rỗng sau lời gọi này)
  mypq.push("World");         // Tạo một đối tượng string tạm thời và di chuyển nó vào mypq

  std::cout << "str after move: " << str << '\n'; // Output: str after move: (empty string)

  return 0;
}

Các hàm liên quan

pop	Xóa phần tử có độ ưu tiên cao nhất (phần tử ở đỉnh) của std::priority_queue
size	Trả về số lượng phần tử hiện có trong std::priority_queue