C++17 STL Стандартная библиотека шаблонов - Яцек Галовиц

так как предложений одинаковой длины может быть довольно много. Но это не проблема, поскольку мы задействуем контейнер 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

Итераторы

В этой