@dalbio

Как задать приоритетную очередь с пользовательским cmp?

Вообщем я искал в интернете,но там везде разные реализации,и я не понимаю,зачем написано что-нибудь,поэтому я обращаюсь к вам за помощью,помогите,пожалуйста.
Пример:
priority_queue , cmp > min;
(зачем в объявлении вектор?,можно ли cmp написать в виде
bool cmp(const int&a,const int&b){
     return a<b;
}

если нельзя,то какие альтернативы?
  • Вопрос задан
  • 472 просмотра
Решения вопроса 1
wataru
@wataru Куратор тега C++
Разработчик на С++, экс-олимпиадник.
Смотрим в документацию.

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

Дефолтный контейнер - vector и компаратор стандартный std::less, поэтому работает просто priority_queue, например.

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

Однако, если вам надо поменять только компаратор (третий параметр), то передать второй параметр тоже придется. Ну, вот перепутали порядок параметров разработчики стандарта. Нельзя задать компаратор, не задав и контейнер. Поэтому, надо писать там vector<> во втором параметре.

Edit. Там же в документации написано, что компаратор должен возвращать true, если первый элемент строго меньше второго. Ваш пример компаратора - похоже правильный. Однако, учтите, что очередь выдает сначала максимальный элемент. Т.е, если вам нужна очередь на минимум, то вам надо поменять знак в компараторе.
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы