Как перебрать приоритетную очередь? - PullRequest
Новая
       13

Как перебрать приоритетную очередь?

57 голосов
/ 19 декабря 2010

Могу ли я пройти через стандартный priority_queue или стандартный queue в c ++ с помощью итератора (например, vector)? Я не хочу использовать pop, потому что это вызывает мою очередь в очередь.

Спасибо за любую помощь

Ответы [ 13 ]

0 голосов
/ 27 мая 2017

C ++ priority_queue не предлагает указатель .begin () (как сделал бы вектор), который вы можете использовать для его итерации.

Если вы хотите перебрать очередь с приоритетами, чтобы найти, содержит ли она значение, то, возможно, создайте очередь с приоритетами обертки и используйте хэш-набор для отслеживания того, что у вас в очереди. 

class MyPriorityQueue {

   MyPriorityQueue() {}

   void push(int item) {
     if (!contains(item)){
       pq_.push(item);
       set_.emplace(item);
     }
   }
   void pop() {
     if (!empty()) {
       int top = pq_.top();
       set_.erase(top);
       pq_.pop();
     }
   }
   int top() { return pq_.top(); }
   bool contains(int item) { return set_.find(item) != set_.end(); }
   bool empty() const { return set_.empty(); }

 private:
   std::priority_queue<int> pq_;
   std::unordered_set<int> set_;
};
0 голосов
/ 27 января 2014

У меня тоже был такой же вопрос.Я обнаружил, что было очень трудно, возможно, невозможно добраться до структуры данных, лежащей в основе очереди приоритетов.В моем случае это был вектор объектов.

Однако я использовал стандартную кучу библиотек шаблонов.Это почти так же просто, как очередь с приоритетами (требуется две инструкции для push и pop, против 1 для pq), в противном случае поведение кажется идентичным, и я могу получить базовую структуру данных, если не изменю.

0 голосов
/ 20 октября 2012

У меня была та же проблема, когда я хотел перебрать приоритетную очередь без удаления очереди (следовательно, уничтожая мою очередь). Я заставил это работать для меня, переписав мой указатель priority_queue на указатель на вектор (так как мой priority_queue использует вектор в качестве своего контейнера). Вот как это выглядит: 

class PriorityQueue {
  private:
    class Element {
    int x; 
    //Other fields
    ...
    ..
    //Comparator function
    bool operator()(const Element* e1, const Element* e2) const {
        // Smallest deadline value has highest priority.
        return e1->x > e2->x;
    }
    };
    // Lock to make sure no other thread/function is modifying the queue
    // Ofcourse we can do our operation w/o lock. if we are sure what is happening in other functions
    pthread_mutex_t lock;   
    std::priority_queue<Element*, std::vector<Element*>, Element> pq;

  public:
    PriorityQueue();
    ~PriorityQueue();
    //print the all the elements of the queue
    void print_queue_elements() {
        std::vector<PriorityQueue::Element*> *queue_vector;
        //Acquire the lock
        pthread_mutex_lock(&lock);
        //recast the priority queue to vector
        queue_vector = reinterpret_cast<std::vector<PriorityQueue::Element*> *>(&pq);
        for(std::vector<PriorityQueue::Element*>::iterator it = (*queue_vector).begin(); it != (*queue_vector).end(); it++) {
            //Assuming Element class has string function
            printf("My Element %s", (*it)->string);
            //other processing with queue elements
        }
        //Release the lock
        pthread_mutex_unlock(&lock);    

    }
    //other functions possibly modifying the priority queue
    ...
    ..
    .
 };

Теперь, когда я использую reinterpret_cast, люди могут спорить о безопасности типов. Но в этом случае я уверен в том, что все остальные функции обращаются к очереди / изменяют ее (все они безопасны) ... и я считаю, что это гораздо лучший способ, чем копирование содержимого всей очереди в какой-либо другой контейнер.

Я действительно ожидал, что static_cast будет работать .. так как priority_queue является адаптером над контейнером (вектором в нашем случае), но это не так, и мне пришлось использовать reinterpret_cast.

Страница:
...