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

Question

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

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

Answer 1

priority_queue не позволяет выполнять итерацию по всем элементам, предположительно потому, что было бы слишком легко аннулировать упорядочение приоритетов очереди (путем изменения элементов, которые вы пересекаете) или, возможно, это обоснование "не моей работы".

Официальный обходной путь - использовать vector и управлять приоритетом самостоятельно с помощью make_heap, push_heap и pop_heap. Другой ответ, в ответе @ Richard, заключается в использовании класса, производного от priority_queue, и доступ к базовому хранилищу, которое имеет protected видимость.

Answer 2

Ты можешь сделать это так - бац! Обратите внимание, что элементы не обязательно находятся в «отсортированном» порядке, пока они находятся в очереди, по крайней мере в отношении прямой итерации контейнера.

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

Answer 3

A queue целенаправленно предоставляет ограниченный интерфейс, который исключает итерации.Но поскольку queue использует deque в качестве основного контейнера, почему бы не использовать 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 используется по умолчанию.Ни в том, ни в другом случае вы не можете получить доступ к базовому контейнеру, чтобы перебрать их.См. этот вопрос для дальнейшего чтения.

Answer 4

Да, сделайте копию priority_queue и итерируйте по этому.

Answer 5

Я нашел это после того, как наткнулся на ваш вопрос. Есть очень простой способ сделать это, написав реализацию, унаследованную от std :: priority_queue. Это всего 14 строк.

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

Answer 6

Это невозможно. Вам придется использовать другой контейнер, вероятно, deque подойдет вам лучше.

Answer 7

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

Answer 8

Очереди полностью отличаются от векторов и используются для разных целей.Приоритетные очереди - это просто отсортированные запросы без прямого доступа к задней части.Однако, если вы отчаянно хотите сделать это для любого метода, вы можете просто вытолкнуть верхний / передний элемент, добавить его в список / массив / вектор, а затем вставить элемент обратно в очередь для0; i

Answer 9

Многие из этих ответов основаны на кодировании / использовании многих тайных функций 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;

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

Answer 10

Для базовых целей std::multiset даст вам аналогичные свойства, но с возможностью итерации:

• Элементы отсортированы, пользовательские Less могут быть определены
• Ключи могут появляться несколько раз
• Быстрый доступ и удаление первого элемента