Можно ли пересечь стандартный priority_queue или стандартный queue в С++ с помощью итератора (например, vector)? Я не хочу использовать pop, потому что это приводит к тому, что моя очередь будет удалена.
Спасибо за любую помощь
Как перебирать приоритет_queue?
Ответ 1
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. В любом случае вы не можете получить доступ к базовому контейнеру, чтобы перебирать их. См. этот вопрос для дальнейшего чтения.
Ответ 2
Вы можете сделать это так: 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;
}
Ответ 3
Да, сделайте копию priority_queue и повторите это.
Ответ 4
priority_queue не допускает итерации через все члены, по-видимому, потому, что было бы слишком легко аннулировать порядок приоритетов очереди (путем изменения перемещаемых элементов) или, возможно, это "не моя работа".
Официальная работа - использовать vector вместо этого и управлять приоритетом самостоятельно с помощью make_heap, push_heap и pop_heap. Еще одна проблема в ответе @Richard заключается в использовании класса, полученного из priority_queue, и доступа к базовому хранилищу с видимостью protected.
Ответ 5
Это невозможно. Вам придется использовать другой контейнер, возможно, deque будет вам лучше всего.
Ответ 6
#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;
}
Ответ 7
Очереди полностью отличаются от векторов и используются для разных целей. Приоритетные очереди - это просто отсортированные знаки без прямого доступа к спине. Однако, если вы отчаянно хотите сделать это для любого метода, то что вы можете сделать, это вытащить верхний/передний элемент, добавить его в список/массив/вектор, а затем вернуть элемент обратно в очередь для (size_t я = 0; я < q.size(); я ++). Я взял класс в java-структурах данных, и это был ответ на вопрос экзамена. Плюс это единственный метод, о котором я могу думать.
Ответ 8
Я нашел это после спотыкания по вашему вопросу. Это очень простой способ сделать это, написав реализацию, наследующую от std:: priority_queue. Это все 14 строк.
Ответ 9
У меня был тот же вопрос. Я обнаружил, что было очень сложно, возможно, невозможно добраться до структуры данных, лежащей в основе очереди приоритетов. В моем случае это был вектор объектов.
Однако я закончил использование стандартной кучи библиотеки шаблонов. Это почти так же просто, как приоритетная очередь (требуется две команды для push и pop, vs. 1 для pq), в противном случае поведение похоже одинаково а также Я могу получить базовую структуру данных, если я ее не модифицирую.
Ответ 10
С++ 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_;
};
Ответ 11
Многие из этих ответов основаны на кодировании/использовании многих тайных функций С++. Это нормально, весело и дорого стоит программистов. Прямое решение, быстрое, дешевое для программы, но более дорогостоящее для запуска:
//
// 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, особенно если это класс контейнера для a или структуры.
Ответ 12
У меня была такая же проблема, когда я хотел перебирать очередь приоритетов без удаления (следовательно, уничтожая мою очередь). Я заработал у меня, переработав указатель 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.