priority_queue를 반복하는 방법은 무엇입니까?

priority_queue를 반복하는 방법은 무엇입니까?

---

반복기를 사용하여 C ++에서 표준 priority_queue또는 표준 queue을 탐색 할 수 있습니까 (예 :) vector? pop을 사용하면 내 대기열이 대기열에서 제외되기 때문에 사용하고 싶지 않습니다.

도움을 주셔서 감사합니다

---

priority_queue 모든 구성원을 통한 반복을 허용하지 않습니다. 아마도 대기열의 우선 순위 순서를 무효화하는 것이 너무 쉽거나 (순회하는 요소를 수정하여) "내 직업이 아님"근거 일 수 있기 때문일 것입니다.

공식 주위 작품은을 사용하는 것입니다 vector으로 우선 순위 네스에게 자신을 대신 관리 make_heap, push_heap및 pop_heap. @Richard의 답변에서 또 다른 해결 방법 priority_queue은 protected가시성 이있는 기본 스토리지 에서 파생 된 클래스를 사용 하고 액세스하는 것 입니다.

---

이렇게 할 수 있습니다-bam! 최소한 컨테이너의 간단한 반복과 관련하여 항목이 대기열에있는 동안 반드시 "정렬 된"순서는 아닙니다.

#include <queue>
#include <cstdlib>
#include <iostream>
using namespace std;

template <class T, class S, class C>
S& Container(priority_queue<T, S, C>& q) {
    struct HackedQueue : private priority_queue<T, S, C> {
        static S& Container(priority_queue<T, S, C>& q) {
            return q.*&HackedQueue::c;
        }
    };
    return HackedQueue::Container(q);
}

int main()
{
    priority_queue<int> pq;
    vector<int> &tasks = Container(pq);

    cout<<"Putting numbers into the queue"<<endl;
    for(int i=0;i<20;i++){
        int temp=rand();
        cout<<temp<<endl;
        pq.push(temp);
    }

    cout<<endl<<"Reading numbers in the queue"<<endl;
    for(vector<int>::iterator i=tasks.begin();i!=tasks.end();i++)
        cout<<*i<<endl;

    cout<<endl<<"Taking numbers out of the queue"<<endl;
    while(!pq.empty()){
        int temp=pq.top();
        pq.pop();
        cout<<temp<<endl;
    }

    return 0;
}

---

A queue는 반복을 제외한 제한된 인터페이스를 의도적으로 제공합니다. 그러나 a queue는 deque기본 컨테이너로 a를 사용하므로 a 를 deque직접 사용하지 않는 이유는 무엇입니까?

#include <iostream>
#include <queue>
using namespace std;

int main() {
  deque<int> q;
  q.push_back(1);
  q.push_back(2);
  q.push_back(3);
  for(deque<int>::iterator it = q.begin(); it != q.end(); ++it)
    cout << *it << endl;
}

우선 순위 대기열에 대한 유사한 대답 : 아니요, 할 수 없습니다. 이 경우 vector기본적으로 a 가 사용됩니다. 두 경우 모두 기본 컨테이너에 액세스하여이를 반복 할 수 없습니다. 자세한 내용은 이 질문 을 참조하십시오 .

---

예, priority_queue의 사본을 만들고이를 반복합니다.

---

이건 불가능 해. 다른 용기를 사용해야 deque할 것입니다.

---

나는 당신의 질문에 걸림돌이 된 후에 이것을 발견했습니다. std :: priority_queue에서 상속 된 구현을 작성하여이를 수행하는 매우 간단한 방법이 있습니다. 전 14 행입니다.

http://www.linuxtopia.org/online_books/programming_books/c++_practical_programming/c++_practical_programming_189.html

---

#include <queue>
#include <iostream>

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

    pq.push_back(1);
    pq.push_back(2);
    pq.push_back(3);

    std::priority_queue<int> temp = pq;

    while (!temp.empty()) {
        std::cout << temp.top() << std::endl;
        temp.pop();
    }

    return 0;
}

---

대기열은 벡터와 완전히 다르며 다른 용도로 사용됩니다. 우선 순위 대기열은 뒷면에 직접 액세스하지 않고 단순히 정렬 된 데크입니다. 그러나 어떤 방법 으로든이 작업을 필사적으로 수행하려면 상단 / 전면 요소를 팝하고 목록 / 배열 / 벡터에 추가 한 다음 해당 요소를 큐에 다시 밀어 넣는 것입니다 (size_t i = 0; i <q.size (); i ++). 저는 자바 데이터 구조 수업을 들었고 이것이 시험 문제에 대한 답이었습니다. 게다가 내가 생각할 수있는 유일한 방법입니다.

---

이러한 답변 중 대부분은 코딩 / 많은 C ++ 신비한 기능 사용에 의존합니다. 괜찮습니다. 재미 있고 값 비싼 프로그래머에게 자금을 지원합니다. 빠르고 프로그래밍 비용이 저렴하지만 실행 비용이 더 많이 드는 직접 솔루션은 다음과 같습니다.

// 
// Only use this routine when developing code, NOT for production use!!
//
// Note. _pq is in private for a class that uses the priority queue
// and listQueue is a public method in that same class.
//
void listQueue() {

    // allocate pointer to a NEW container
    priority_queue<int>* new_pq = new  priority_queue<int>;

    while (!_pq->empty()) {

        int el = _pq->top();

        cout << "(" << el << ")" << endl;

        new_pq->push(el);

        _pq->pop();

    } // end while;

    // remove container storage
    delete(_pq);

    // viola, new container same as the old
    _pq = new_pq;

} // end of listQueue;

그건 그렇고, 특히 or 구조체에 대한 컨테이너 클래스 인 경우 priority_queue에 대한 반복자를 제공하지 않는 것은 완전히 비합리적으로 보입니다.

---

나도 같은 질문을했습니다. 우선 순위 큐의 기반이되는 데이터 구조에 도달하는 것이 매우 어렵거나 불가능하다는 것을 알았습니다. 제 경우에는 이것은 물체의 벡터였습니다.

그러나 결국 표준 템플릿 라이브러리 힙을 사용하게되었습니다. 우선 순위 대기열만큼 쉽습니다 (pq의 경우 1이 아닌 푸시 및 팝에 두 가지 명령이 필요함). 그렇지 않으면 동작이 동일 해 보이며 수정하지 않으면 기본 데이터 구조를 얻을 수 있습니다. .

---

C++ priority_queue does not offer a .begin() pointer (like vector would do) that you can use to iterate over it.

If you want to iterate over the priority queue to search for whether it contains a value then maybe create a wrapper priority queue and use a hash set to keep track of what you have in the queue.

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_;
};

---

For basic purposes, a std::multiset will give you similar properties but with the ability to iterate:

• Items sorted, custom Less can be defined
• Keys can occur multiple times
• Quick to access and remove first item

---

I had the same problem, where I wanted to iterate over a priority queue without dequeuing (hence destroying my queue). I made it work for me by recasting my priority_queue pointer to a pointer to a vector (as my priority_queue uses vector as its container). Here is how it looks like:

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
    ...
    ..
    .
 };

Now since I am using reinterpret_cast, people can argue about type-safety. But in this case I am sure about all other functions accessing/changing the queue (all of which are safe).. and I feel this is a much better way than copying the content of whole queue to some other container.

I was actually expecting static_cast to work.. as priority_queue is adaptor over container (vector in our case), but it doesnt and I had to use reinterpret_cast.

참고URL : https://stackoverflow.com/questions/4484767/how-to-iterate-over-a-priority-queue