Что нужно для передачи контейнера в priority_queue

Question

Каждый раз, когда вы хотите использовать пользовательскую функцию сравнения для priority_queue, вы также должны передать ей контейнер. Мне кажется, вы всегда должны передать vector<T>. Теперь сначала я подумал, что это какая-то избыточность, но это не должно быть так. Какая польза от передачи контейнера priority_queue и как я могу его использовать?

Answer 1

Вы просто передаете ему базовый тип контейнера, который по умолчанию равен std::vector<T>. Если вы хотите сохранить поведение по умолчанию, то вы правы, говоря, что всегда можете пройти std::vector<T>. Вы можете также использовать std::deque<T> или любой пользовательский контейнер, который предоставляет следующие функции:

• пустого()
• размера()
• фронта()
• push_back()
• pop_back()

Но почему вы должны указать контейнер, прежде чем указывать компаратор? Ну, это просто связано с тем, как определяются параметры. container и compare оба являются параметрами по умолчанию, а container просто на первом месте. Из-за того, как работает C++, вам просто нужно передать все параметры, ведущие до compare, прежде чем вы сможете передать его, а это значит, что вы также должны пройти container. AFAIK это не имеет никакого отношения к compare что-то нужно знать о container.

Answer 2

std::priority_queue - контейнерный адаптер. На самом деле он не знает, как хранить элементы, которые вы вставляете в него; он делегирует это реальному контейнеру, например std::vector. Редко, что вы хотите использовать что-то отличное от std::vector в качестве основного контейнера, но вы можете использовать std::deque, если хотите.

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