Как найти значение в Pirority_queue, которое содержит пару <int, int>?

Question

Обычно мы можем определить, присутствует ли значение в очереди приоритетов, используя heap.find (значение).Если его нет, он вернет end ().

Теперь у меня есть очередь приоритетов, которая определяется следующим образом:

priority_queue<pair<int,int>, vector<pair<int,int>>, fun> min_heap;

Я хочу выяснить, существует ли пара в этом на основестоимости в паре.Как это найти?

Answer 1

Вы можете создать приоритетную очередь tmp того же типа, передавая исходный PQ конструктору для копирования элементов, тогда, конечно, вы можете проверять верх и всплывающее окно, пока не найдете нужную пару или новый PQ не будет пустым:

pair<int, int> wantedPair = {5, 3};
bool found = false;
priority_queue<pair<int,int>, vector<pair<int,int>>, fun> tmp(min_heap);
while(tmp.empty() == false) {
    if (wantedPair == tmp.top()) {
        found = true;
        break;
    }

    tmp.pop();
}

Вы можете создать шаблонную функцию для поиска, если хотите использовать ее более одного раза с различными типами PQ.

Answer 2

std::priority_queue не дает никакого доступа к элементам, кроме верхнего, и не допускает внешнего доступа к нижележащему контейнеру.Поэтому, если вам нужна очередь с повторяющимися приоритетами, вы должны что-то написать самостоятельно.Вы можете создать что-то вроде этого:

template <class T, class Container = std::vector<T>, class Compare = std::less<typename Container::value_type>>
class IterableQueue : public std::priority_queue<T, Container, Compare>
{
public:
  using std::priority_queue<T, Container, Compare>::priority_queue;

  const Container& container() const { return this->c; }
};

Обратите внимание, что вообще плохая идея публично наследовать от контейнеров стандартной библиотеки (как в моем примере выше), потому что у них нет виртуальных деструкторов и, следовательно,разрешить преобразование в базовый контейнер потенциально опасно.

В рабочем коде было бы лучше использовать частное наследование и публиковать (посредством using объявлений) элементы, которые вы хотите получить доступными (по сути, только все из них).

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