2. Как же мы сохраняем элементы списка дел в очереди с приоритетом? Проблема заключается в том, что нельзя просто добавить элемент и дополнительно прикрепить к нему приоритет. Очередь с приоритетом попытается использовать естественный порядок всех элементов очереди. Можно реализовать собственную структуру todo_item и задать для нее число, указывающее на приоритет, и строку с описанием дела, а затем реализовать оператор сравнения <, чтобы впоследствии упорядочить данные элементы. Или же можно просто задействовать тип std::pair; это позволит объединить два свойства в одном типе, при этом сравнение уже реализовано за нас:
int main()
{
using item_type = std::pair<int, std::string>;
3. Сейчас у нас имеется новый тип item_type, содержащий число, описывающее приоритет, и строку-описание. Поэтому создадим экземпляр очереди с приоритетом, в которой будут находиться такие элементы:
std::priority_queue<item_type> q;
4. Теперь заполним эту очередь разными элементами, имеющими разные приоритеты. Нам следует предоставить неструктурированный список, а затем очередь с приоритетом укажет, что сделать и в каком порядке. Например, если нужно прочитать комикс и выполнить домашнюю работу, то последняя должна находиться выше в списке. К сожалению, класс std::priority_queue не имеет конструктора, принимающего списки инициализации, который мы могли бы использовать для заполнения очереди. (Это сработало бы, примени мы вектор или обычный список.) Так что сначала определим список и заполним его на следующем этапе:
std::initializer_list<item_type> il {
{1, "dishes"},
{0, "watch tv"},
{2, "do homework"},
{0, "read comics"},
};
5. Теперь можно легко проитерировать по неупорядоченному списку текущих дел и вставить их по одному с помощью функции push:
for (const auto &p : il) {
q.push(p);
}
6. Все элементы будут упорядочены неявным образом, и теперь у нас есть очередь, которая выдает элементы с наивысшим приоритетом:
while(!q.empty()) {
std::cout << q.top().first << ": " << q.top().second << '\n';
q.pop();
}
std::cout << '\n';
}
7. Скомпилируем и запустим нашу программу. Она сообщает следующее: сначала мы должны выполнить домашнюю работу, а затем, после того как помоем посуду, можем посмотреть телевизор и почитать комиксы:
$ ./main
2: do homework
1: dishes
0: watch tv
0: read comics
Как это работает
Контейнер std::priority_queue очень прост в использовании. Нам понадобилось всего три функции.
1. q.push(item) помещает элемент в очередь.
2. q.top() возвращает ссылку на элемент, который первым покинет очередь.
3. q.pop() удаляет первый элемент из очереди.
Но каким образом происходит упорядочение элементов? Мы сгруппировали числа, указывающие на приоритет, и строки, описывающие элементы списка текущих дел, в объекты типа std::pair, что позволило упорядочить элементы автоматически. Если у нас есть экземпляр p типа std::pair<int, std::string>, то с помощью нотации p.first можно получить число, а благодаря нотации p.second — строку. Мы сделали это в цикле, где выводятся на экран все наши текущие дела.
Но как очередь с приоритетом узнала, что пара {2, "do homework"} важнее, чем {0, "watch tv"}? Мы ведь не говорили ей сравнивать числовую часть.
Оператор сравнения < по-разному обрабатывает разные ситуации. Предположим, у нас имеется сравнение left < right, где left и right представляют собой пары.
1. Если выполняется условие left.first != right.first, то возвращается результат сравнения left.first < right.first.
2. Если выполняется условие left.first == right.first, то возвращается результат сравнения left.second < right.second.
Таким образом можно упорядочить все, что нам угодно. Важным здесь является тот факт, что приоритет — первый член пары, а описание — второй. В противном случае контейнер std::priority_queue упорядочил бы элементы по алфавиту, а не по числам, указывающим на приоритеты. (В данном случае очередь предложит нам сначала посмотреть телевизор (watch TV), а затем, спустя какое-то время, заняться домашней работой (do homework). Это бы понравилось самым ленивым из нас!)