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

После того как мы считали весь файл в одну большую строку, мы проходим по ней и создаем копию каждого предложения. Однако это не обязательно, ведь можно воспользоваться 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 располагается в заголовочном файле :

#include

#include

#include

#include

2. Как же мы сохраняем элементы списка дел в очереди с приоритетом? Проблема заключается в том, что нельзя просто добавить элемент и дополнительно прикрепить к нему приоритет. Очередь с приоритетом попытается использовать естественный порядок всех элементов очереди. Можно реализовать собственную структуру todo_item и задать для нее число, указывающее на приоритет, и строку с описанием дела, а затем реализовать оператор сравнения <, чтобы впоследствии упорядочить данные элементы. Или же можно просто задействовать тип std::pair; это позволит объединить два свойства в одном типе, при этом сравнение уже реализовано за нас:

int main()

{

  using item_type = std::pair;

3. Сейчас у нас имеется новый тип item_type, содержащий число, описывающее приоритет, и строку-описание. Поэтому создадим экземпляр очереди с приоритетом, в которой будут находиться такие элементы:

  std::priority_queue q;

4. Теперь заполним эту очередь разными элементами, имеющими разные приоритеты. Нам следует предоставить неструктурированный список, а затем очередь с приоритетом укажет, что сделать и в каком порядке. Например, если нужно прочитать комикс и выполнить домашнюю работу, то последняя должна находиться выше в списке. К сожалению, класс std::priority_queue не имеет конструктора, принимающего списки инициализации, который мы могли бы использовать для заполнения очереди. (Это сработало бы, примени мы вектор или обычный список.) Так что сначала определим список и заполним его на следующем этапе:

  std::initializer_list 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