так как предложений одинаковой длины может быть довольно много. Но это не проблема, поскольку мы задействуем контейнер std::multimap, который легко справляется с совпадающими ключами. Данный контейнер хранит ключи
в упорядоченном виде, что позволяет нам вывести предложения в порядке возрастания их длины.
Дополнительная информация
После того как мы считали весь файл в одну большую строку, мы проходим по ней и создаем копию каждого предложения. Однако это не обязательно, ведь можно воспользоваться std::string_view; данный вопрос мы рассмотрим далее в книге.
Еще один способ получить строки между двумя соседними точками — задействовать класс std::regex_iterator, который мы также рассмотрим несколько позже.
Реализуем личный список текущих дел с помощью std::priority_queue
Класс std::priority_queue — еще один класс-адаптер для контейнеров, как и std::stack. Он является оболочкой для другой структуры данных (по умолчанию это std::vector) и предоставляет для нее интерфейс очереди. Т.е. элементы можно помещать туда и выталкивать оттуда пошагово. Все, что было помещено туда раньше, раньше очередь и покинет. Обычно данный принцип обозначается как FIFO (first in, first out — «первый вошел — первый вышел»). Он полностью противоположен принципу работы стека, где последний помещенный элемент будет вытолкнут первым.
Несмотря на то что мы описали, как работает контейнер std::queue, в текущем разделе будет показана работа контейнера std::priority_queue. Он особенный, поскольку не только имеет характеристики FIFO, но и объединяет их с приоритетами. Иными словами, содержимое, по сути, разбивается на подочереди, работающие по принципу FIFO, которые упорядочены в соответствии с указанным для них приоритетом.
Как это делается
В данном примере мы создадим простую структуру, которая может служить в качестве списка текущих дел. Для сокращения программы мы не будем анализировать входные данные и сконцентрируемся на std::priority_queue. Поэтому просто заполняем очередь с приоритетом на основе неупорядоченного списка элементов, имеющих приоритет и описание. Затем считываем их как из структуры данных, работающей по принципу очереди FIFO, где все элементы сгруппированы по приоритетам отдельных элементов.
1. Сначала включим некоторые заголовочные файлы. Контейнер std::priority_queue располагается в заголовочном файле <queue>:
#include <iostream>
#include <queue>
#include <tuple>
#include <string>
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). Это бы понравилось самым ленивым из нас!)
Глава 3
Итераторы
В этой
