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

Question

[dalbio]

Вообщем я искал в интернете,но там везде разные реализации,и я не понимаю,зачем написано что-нибудь,поэтому я обращаюсь к вам за помощью,помогите,пожалуйста.
Пример:
priority_queue , cmp > min;
(зачем в объявлении вектор?,можно ли cmp написать в виде

bool cmp(const int&a,const int&b){
     return a<b;
}

если нельзя,то какие альтернативы?

Comments

[Евгений Шатунов]

dalbio , что именно тебе не понятно?
Покажи, что именно ты искал и что именно ты находил. Какие именно реализации разные и почему они тебе не подходят?

[dalbio]

Евгений Шатунов, priority_queue <int , vector<int>, cmp > min; (зачем в объявлении вектор?,можно ли cmp написать в виде

bool cmp(const int&a,const int&b){
     return a<b;
}

если нельзя,то какие альтернативы?

Answer 1

[Wataru]

Смотрим в документацию.

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

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

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

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

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