Làm thế nào để có được một phần tử không phải là const từ priority_queue với các đối tượng do người dùng định nghĩa?

Question

std::priority_queue::top trả về giá trị không đổi. Tuy nhiên, tôi muốn xóa phần tử trên khỏi hàng đợi ưu tiên và có thể sửa đổi nó ở một nơi khác.

priority_queue<SomeClass, vector<SomeClass>, SomeClassCompare > pQueue; 
... 
SomeClass *toBeModified = &(pQueue.top()); 
pQueue.pop(); 
toBeModified->setMember(3); // I would like to do this 

Có cách nào tôi có thể lấy phần tử hàng đầu từ hàng đợi ưu tiên (và xóa khỏi hàng đợi) và sửa đổi nó như tôi muốn không?

Answer 1

Bộ chứa tiêu chuẩn và bộ điều hợp vùng chứa có ngữ nghĩa giá trị. Khi bạn đẩy một phần tử vào hàng đợi, một bản sao sẽ được tạo. Khi bạn loại bỏ một đối tượng khỏi hàng đợi, đối tượng đó sẽ bị hủy.

Thậm chí nếu top() sẽ trả lại cho bạn một tham chiếu đến không const, tham chiếu đó sẽ trở nên lúng túng ngay khi bạn xóa phần tử khỏi hàng đợi và hủy bỏ nó sẽ dẫn đến hành vi không xác định.

này cho biết, std::priority_queue trả về cho bạn một tham chiếu đến const để ngăn cản bạn rối tung (cố ý hoặc vô ý) với trật tự nội bộ của mình - đó là khá nhiều lý do tương tự tại sao chìa khóa của container kết hợp như std::map và std::set là const .

gì bạn có thể làm, thay vào đó, là xây dựng một bản sao giá trị trả về bởi top(), sửa đổi bản sao đó, loại bỏ bản gốc, và đẩy các bản sao vào hàng đợi:

SomeClass obj = pQueue.top(); 
pQueue.pop(); 
obj.setMember(42); 
pQueue.push(std::move(obj)); // You can move obj into the queue if you no more need it 

Nếu bạn cần ngữ nghĩa tham chiếu, mặt khác, bạn sẽ phải đẩy con trỏ vào hàng đợi (có thể là con trỏ thông minh, tùy thuộc vào trường hợp sử dụng của bạn) và cung cấp tiêu chí đặt hàng tùy chỉnh phù hợp. các đối tượng mà họ trỏ đến.

Trong trường hợp này, hãy cẩn thận không sửa đổi các thuộc tính đó trong thời gian chạy theo cách có thể làm cho thứ tự của chúng khác nhau. Điều đó được tính là "gây rối với thứ tự nội bộ của vùng chứa" và sẽ dẫn đến hành vi không xác định.

Answer 2

Tôi không nghĩ rằng ngữ nghĩa giá trị đóng vai trò ít nhất ở đây. Tất cả các vùng chứa khác có cùng ngữ nghĩa giá trị và hầu như tất cả chúng đều cung cấp front() với tham chiếu có thể thay đổi.

Có một lý do chính xác tại sao priority_queue không cho phép sửa đổi thành phần top(): điều này là do yếu tố cụ thể đứng đầu bởi vì nó đã đủ điều kiện như vậy, theo giá trị hiện tại của nó. Các phần tử trong hàng đợi ưu tiên là luôn được sắp xếp theo tiêu chí so sánh được định cấu hình cho hàng đợi (toán tử < theo mặc định). Bằng cách thay đổi phần tử, bạn có khả năng phá hủy điều kiện này và khiến tất cả các hoạt động sử dụng điều kiện tiên quyết được sắp xếp sẽ gây ra hành vi không xác định.

Tóm lại, lý do tại sao priority_queue không cho phép sửa đổi các phần tử được chứa chính xác giống như trong trường hợp set và các phím cho map.

Tôi hiểu rằng bạn có thể có một số phương pháp so sánh chuyên dụng, bạn sử dụng trường có chứa giá trị để so sánh và bạn sẽ sửa đổi bất kỳ nội dung nào của đối tượng, ngoại trừ trường dữ liệu này. Bằng cách này bạn không vi phạm các yêu cầu của thứ tự sắp xếp. Có hai điều bạn có thể làm:

1. Làm cho các bộ phận của bạn cần được sửa đổi là mutable. Bằng cách này, bạn có thể lấy phần tử bằng cách top() và sửa đổi nội dung có thể thay đổi, mặc dù đây là const.

2. Tạo lớp xếp hàng ưu tiên của riêng bạn bằng cách lấy ra std::priority_queue. Trường này có một trường có tên là c (trong mục được bảo vệ), chứa tham chiếu đến vùng chứa cơ bản - và vùng chứa cơ sở thay vì luôn có phương thức front() truy cập cùng một thành phần như top() trong priority_queue. Vì sự an toàn của riêng bạn, tuy nhiên, bạn nên tạo trường khóa const, do đó nó được đặt trong khi xây dựng và không bao giờ bị thay đổi - chỉ để giảm thiểu rủi ro.

Ah, và vấn đề này không thể được giải quyết bằng cách sử dụng các đối tượng trỏ chuột sẽ chính xác là cùng một hằng số. Những "ngữ nghĩa tham chiếu" cũng sẽ không giúp bạn bằng bất kỳ cách nào vì nếu bạn muốn có một phương pháp so sánh chuyên dụng, nó sẽ phải xem xét nội dung của đối tượng và cách này bạn sẽ có cùng một vấn đề. Điều này sẽ giúp bạn, nếu bạn dựa vào chỉ đơn giản là so sánh giá trị con trỏ, nhưng tôi muốn nghi ngờ điều này có thể là một giải pháp cho 99% trường hợp.