Lấy các phần tử `std :: priority_queue` theo thứ tự ngược lại?

Question

Tôi đã viết một số phương thức truy vấn lân cận K-lân cận, xây dựng danh sách các điểm gần điểm truy vấn nhất định. Để duy trì danh sách hàng xóm đó, tôi sử dụng std::priority_queue sao cho phần tử trên cùng là hàng xóm xa nhất đến điểm truy vấn. Bằng cách này tôi biết nếu tôi nên đẩy phần tử mới hiện đang được kiểm tra (nếu ở khoảng cách nhỏ hơn so với hàng xóm xa nhất hiện tại) và có thể bật() thành phần xa nhất khi hàng đợi ưu tiên của tôi có nhiều hơn K phần tử.

Cho đến nay, tất cả đều tốt. Tuy nhiên, khi tôi xuất ra các yếu tố, tôi muốn đặt chúng từ xa nhất đến xa nhất. Hiện tại, tôi chỉ cần bật tất cả các phần tử từ hàng đợi ưu tiên và đặt chúng trên vùng chứa đầu ra (thông qua trình lặp), kết quả là một chuỗi các điểm được sắp xếp từ xa nhất đến gần nhất, vì vậy, tôi gọi std::reverse trên trình lặp đầu ra phạm vi.

Là một ví dụ đơn giản, đây là một tuyến tính-tìm kiếm sử dụng những ưu tiên hàng đợi (rõ ràng, các phương pháp truy vấn gần nhất, hàng xóm thực tế tôi sử dụng còn lâu mới phức tạp hơn):

template <typename DistanceValue, 
      typename ForwardIterator, 
      typename OutputIterator, 
      typename GetDistanceFunction, 
      typename CompareFunction> 
    inline 
    OutputIterator min_dist_linear_search(ForwardIterator first, 
             ForwardIterator last, 
             OutputIterator output_first, 
             GetDistanceFunction distance, 
             CompareFunction compare, 
             std::size_t max_neighbors = 1, 
             DistanceValue radius = std::numeric_limits<DistanceValue>::infinity()) { 
    if(first == last) 
     return output_first; 

    typedef std::priority_queue< std::pair<DistanceValue, ForwardIterator>, 
           std::vector< std::pair<DistanceValue, ForwardIterator> >, 
           detail::compare_pair_first<DistanceValue, ForwardIterator, CompareFunction> > PriorityQueue; 

    PriorityQueue output_queue = PriorityQueue(detail::compare_pair_first<DistanceValue, ForwardIterator, CompareFunction>(compare)); 

    for(; first != last; ++first) { 
     DistanceValue d = distance(*first); 
     if(!compare(d, radius)) 
     continue; 

     output_queue.push(std::pair<DistanceValue, ForwardIterator>(d, first)); 

     while(output_queue.size() > max_neighbors) 
     output_queue.pop(); 

     if(output_queue.size() == max_neighbors) 
     radius = output_queue.top().first; 
    }; 

    OutputIterator it = output_first; 
    while(!output_queue.empty()) { 
     *it = *(output_queue.top().second); 
     output_queue.pop(); ++it; 
    }; 
    std::reverse(output_first, it); 
    return it; 
    }; 

Trên đây là tất cả dandy ngoại trừ một điều: nó đòi hỏi loại đầu ra-iterator là hai chiều và về cơ bản chỉ vào một thùng chứa được phân bổ trước. Bây giờ, thực hành lưu trữ đầu ra trong một phạm vi được quy định bởi một số vòng lặp đầu ra là tuyệt vời và khá chuẩn quá (ví dụ: std::copy và các thuật toán STL khác là ví dụ tốt về điều đó). Tuy nhiên, trong trường hợp này, tôi muốn có thể chỉ yêu cầu một loại trình chuyển tiếp đầu ra phía trước, điều này sẽ làm cho nó có thể sử dụng các trình lặp vòng lặp ngược như những trình cung cấp cho các container STL và iostream.

Vì vậy, điều này sẽ giảm xuống để đảo ngược hàng đợi ưu tiên trước khi bán phá giá nội dung trong trình vòng lặp đầu ra. Vì vậy, đây là những lựa chọn tốt hơn tôi đã có thể đưa ra:

• Tạo một std::vector, đổ nội dung ưu tiên hàng đợi trong nó, và đổ các yếu tố vào đầu ra-iterator sử dụng một reverse- iterator trên vectơ.

• Thay thế std::priority_queue bằng vùng chứa được sắp xếp (ví dụ: std::multimap) rồi đổ nội dung vào trình vòng lặp đầu ra bằng cách sử dụng thứ tự truyền tải thích hợp.

Có tùy chọn hợp lý nào khác không?

Tôi đã từng sử dụng std::multimap trong lần triển khai trước đó của thuật toán này và các thuật toán khác, như tùy chọn thứ hai của tôi ở trên. Tuy nhiên, khi tôi chuyển sang std::priority_queue, hiệu suất đạt được là đáng kể. Vì vậy, tôi không muốn sử dụng tùy chọn thứ hai, vì nó thực sự có vẻ như bằng cách sử dụng một hàng đợi ưu tiên để duy trì danh sách các hàng xóm là tốt hơn nhiều so với dựa vào một mảng được sắp xếp. Btw, tôi cũng đã thử một số std::vector mà tôi duy trì được sắp xếp với std::inplace_merge, tốt hơn nhiều so với nhiều lần nhưng không khớp với hàng đợi ưu tiên.

Đối với tùy chọn đầu tiên, đó là lựa chọn tốt nhất của tôi vào thời điểm này, có vẻ như lãng phí với tôi khi phải thực hiện việc truyền dữ liệu kép này (hàng đợi -> vectơ -> đầu ra). Tôi chỉ có xu hướng nghĩ rằng phải có một cách đơn giản hơn để làm điều này ... một cái gì đó mà tôi đang thiếu ..

Tùy chọn đầu tiên thực sự không phải là xấu trong ứng dụng này (xem xét sự phức tạp của thuật toán đi trước nó), nhưng nếu có một mẹo để tránh việc truyền bộ nhớ kép này, tôi muốn biết về nó.

Answer 1

Sự cố được giải quyết!

Tôi là một tên ngốc ... Tôi biết tôi đã bỏ lỡ điều gì đó hiển nhiên. Trong trường hợp này, hàm std::sort_heap(). reference page thậm chí có một ví dụ thực hiện chính xác những gì tôi cần (và kể từ khi std::priority_queue chỉ được triển khai trong vùng chứa truy cập ngẫu nhiên và các hàm đống (pop_heap, push_heap, make_heap), nó không có sự khác biệt thực sự nào khi sử dụng các hàm này một cách trực tiếp tại chỗ của lớp std::priority_queue). Tôi không biết làm thế nào tôi có thể đã bỏ lỡ điều đó.

Dù sao, tôi hy vọng điều này sẽ giúp bất kỳ ai có cùng vấn đề.

Answer 2

Một ý tưởng bẩn, mà vẫn sẽ được đảm bảo để làm việc, sẽ là như sau:

std::priority_queue<int, std::vector<int>, std::less<int> > queue; 
queue.push(3); 
queue.push(5); 
queue.push(9); 
queue.push(2); 

// Prints in reverse order. 
int* front = const_cast<int*>(&queue.top()); 
int* back = const_cast<int*>(front + queue.size()); 
std::sort(front, back); 
while (front < back) { 
    printf("%i ", *front); 
    ++front; 
} 

Nó có thể được lưu ý rằng việc phân loại tại chỗ có thể sẽ phá vỡ các hàng đợi.

Answer 3

tại sao bạn không chỉ cần chỉ định các chức năng so sánh đối diện trong việc kê khai:

#include <iostream> 
#include <queue> 
#include <vector> 
#include <functional> 

int main() { 
    std::priority_queue<int, std::vector<int>, std::greater<int> > pq; 
    pq.push(1); 
    pq.push(10); 
    pq.push(15); 
    std::cout << pq.top() << std::endl; 
}