C++17 STL Стандартная библиотека шаблонов - читать бесплатно онлайн полную версию книги автора Яцек Галовиц (Глава 2 Контейнеры STL) #4

Глава 2 Контейнеры STL

В этой главе:

□ использование идиомы erase-remove для контейнера

std::vector

;

□ удаление элементов из неотсортированного контейнера

std::vector

за время O(1);

□ получение доступа к экземплярам класса

std::vector

быстрым или безопасным способом;

□ поддержка экземпляров класса

std::vector

в отсортированном состоянии;

□ вставка элементов в контейнер

std::map:

эффективно и в соответствии с условиями;

□ исследование новой семантики подсказок для вставки элементов с помощью метода

std::map::insert

;

□ эффективное изменение ключей элементов

std::map

;

□ применение контейнера

std::unordered_map

для пользовательских типов;

□ отбор повторно встречающихся слов из пользовательского ввода и вывод их на экран в алфавитном порядке с помощью контейнера

std::set

;

□ реализация простого ОПН-калькулятора с использованием контейнера

std::stack

;

□ подсчет частоты встречаемости слов с применением контейнера

std::map

;

□ реализация вспомогательного инструмента для поиска очень длинных предложений в текстах с помощью

std::multimap

;

□ реализация личного списка текущих дел с помощью

std::priority_queue

Введение

В стандартной библиотеке С++ появилось большое количество стандартных контейнеров. Контейнер всегда содержит набор данных или объектов. Достоинство контейнеров в том, что их можно применять практически для всех объектов, поэтому нужно только выбрать правильные контейнеры для конкретного приложения. STL предоставляет стеки, автоматически увеличивающиеся векторы, ассоциативные массивы и т.д. Таким образом, можно сконцентрироваться на нашем приложении и не изобретать велосипед. В целом каждому программисту С++ не повредит знакомство со всеми контейнерами.

Все контейнеры, предоставляемые STL, можно разделить на такие категории, которые подробнее рассматриваются в следующем разделе:

□ непрерывные хранилища;

□ списки;

□ деревья поиска;

□ хеш-таблицы;

□ адаптеры контейнеров.

Рассмотрим более подробно каждый из пунктов.

Непрерывные хранилища

Самый простой способ хранения объектов — поместить их рядом друг с другом в одном большом фрагменте памяти. Произвольный доступ к такому фрагменту выполняется за время O(1).

Это проще всего сделать так: воспользоваться контейнером

std::array

(он представляет собой обертку для обычных массивов в стиле C). Вам практически всегда следует выбирать их вместо обычных массивов, поскольку это не потребует никаких усилий, но работать станет комфортнее и безопаснее. Как и в случае с обычными массивами, массивы STL имеют фиксированный размер, определяемый при создании.

Контейнер

std::vector

вступает в дело, когда вам нужно хранилище, похожее на массив, но с изменяемой длиной. Он использует память из кучи для хранения объектов. Если при добавлении элемента в вектор происходит превышение размера вектора, то все элементы автоматически перемещаются в более крупный фрагмент вновь выделенной памяти, старый же фрагмент удаляется. Более того, если новый элемент помещается между двумя старыми, то может даже перемещать существующие элементы в памяти. При удалении элемента из середины вектора класс vector автоматически сдвинет оставшиеся элементы так, чтобы закрыть получившуюся дыру.

Добавление (или удаление) в начало (или конец) контейнера

std::vector

сразу многих объектов может повлечь выполнение большого количества операций выделения памяти для получения пространства, а также потенциально затратных операций по перемещению объектов. В таких ситуациях стоит воспользоваться контейнером

std::deque

(deque («дек») расшифровывается как double-ended queue (двусторонняя очередь)). Объекты хранятся в непрерывных фрагментах памяти, которые не зависят друг от друга. Это позволяет быстро увеличивать размер дека, поскольку объекты, расположенные в таких фрагментах памяти, не будут перемещаться, когда выделяется память для нового фрагмента и размещается в начале или конце контейнера.

Хранение списков

Контейнер

std::list

представляет собой классический двухсвязный список. Ни больше ни меньше. Если вам нужно выполнять обход списка только в одном направлении, то больше подойдет контейнер

std::forward_list

— он быстрее работает и занимает меньше места, поскольку в нем хранятся лишь указатели на следующий элемент. Пройти список можно только последовательно, за время O(n). Вставку и удаление элементов в заданную позицию можно выполнить за время O(1).

Деревья поиска

Если для объектов характерен естественный порядок, такой, что их можно отсортировать с использованием математического отношения

, то их можно поддерживать в этом же порядке с помощью деревьев поиска. Из названия следует: конкретный элемент дерева легко находится благодаря ключу поиска, что дает возможность выполнять эту операцию за время O(log(n)).

В STL есть несколько видов таких деревьев, самым простым является

std::set

— в нем хранятся уникальные сортируемые объекты.

Контейнер

std::map

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

std::map

в качестве ассоциативного контейнера. Как и в случае с контейнером

std::set

, все ключи в дереве должны быть в единственном экземпляре.

Контейнеры

std::multiset

std::multimap

являются частными случаями контейнеров, показанных выше, для которых отсутствует требование уникальности ключей.

Хеш-таблицы

Деревья поиска не единственный способ реализации ассоциативных контейнеров. В хеш-таблицах элементы можно найти за время O(1), но они игнорируют естественный порядок элементов, поэтому не так просто пройти по упорядоченному списку. Пользователь может изменять размеры хеш-таблицы, можно даже выбрать отдельно хеш-функцию, что немаловажно, поскольку от этого зависят производительность и потребление памяти.

Контейнеры

std::unordered_set

std::unordered_map

весьма похожи на

std::set

std::map

, что можно утверждать на основании их взаимозаменяемости.

Как и реализации поисковых деревьев, у обоих контейнеров есть «коллеги»

std::unordered_multiset

std::unordered_multimap

, которые не имеют ограничения на уникальность объектов/ключей, поэтому можно хранить несколько элементов для одного ключа.

Адаптеры контейнеров

Массивы, списки, деревья и хеш-таблицы не единственный способ хранения данных и получения к ним доступа. Еще есть стеки, очереди и т.д. Аналогично тому, как более сложные структуры могут быть реализованы с использованием более примитивных, в STL такие структуры создаются благодаря следующим классам — адаптерам контейнеров:

std::stack

std::queue

std::priority_queue

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

std::stack

реализации с

std::vector

на

std::deque

Используем идиому erase-remove для контейнера std::vector

Многие программисты-новички узнают о существовании класса

std::vector

, который в основном работает как автоматически увеличивающийся массив, и останавливаются на этом. Далее они лишь ищут в документации сведения о том, как решать конкретные задачи, например удалять элементы. Такого рода использование контейнеров STL не задействует и сотой доли их возможностей в создании чистого, удобного в сопровождении и быстрого кода.

Текущий раздел посвящен вопросу удаления элементов из середины объекта вектора. Если элемент исчезает из вектора и при этом он находился между другими элементами, то все элементы, стоящие справа от него, должны сместиться на одну позицию влево (в результате время выполнения операции составляет O(n)). Многие начинающие программисты будут решать задачу с помощью цикла, ведь это так просто. К сожалению, при этом они, скорее всего, упустят потенциальные возможности оптимизации. В конечном счете цикл, написанный вручную, не быстрее и не читабельнее, чем способ решения задачи средствами STL, которые мы еще рассмотрим далее.

Как это делается

В этом примере мы наполним объект класса

std::vector

целыми числами, а затем выбросим из него конкретные элементы. При этом мы воспользуемся корректным способом удаления нескольких элементов из вектора.

1. Конечно, прежде чем начинать что-то делать, включим некоторые заголовочные файлы:

#include

#include

#include

2. Далее мы объявляем, что будем использовать пространство имен

std

, чтобы поменьше печатать:

using namespace std;

3. Теперь создадим вектор, состоящий из целых чисел, и заполним его некими числами:

int main()

  vector v {1, 2, 3, 2, 5, 2, 6, 2, 4, 8};

4. Удалим некоторые элементы. Что именно? В нашем примере много значений

, удалим их:

  const auto new_end (remove(begin(v), end(v), 2));

5. Что интересно, это был лишь первый шаг. Вектор все еще имеет прежний размер. Мы укоротим его по-настоящему, написав такую строку:

  v. erase(new_end, end(v));

6. Остановимся и выведем на экран содержимое вектора, а затем продолжим:

  for (auto i : v) {

    cout << i << ", ";

  cout << '\n';

7. Теперь удалим целый класс элементов, а не конкретные значения. Для этого сначала определим функцию-предикат, которая принимает число в качестве параметра и возвращает значение

true

, если переданное число нечетное:

  const auto odd ([](int i) { return i % 2 != 0; });

8. Используем функцию

remove_if

, передавая ей значения с помощью функции-предиката. Вместо удаления элементов за два шага теперь делаем это за один:

  v. erase(remove_if(begin(v), end(v), odd), end(v));

9. Мы удалили все нечетные элементы, но емкость вектора все еще соответствует старым десяти элементам. На последнем шаге мы сократим эту емкость до реального размера вектора. Обратите внимание: это может привести к тому, что код обслуживания вектора выделит новый фрагмент памяти, который будет иметь соответствующий размер, и переместит все элементы из старого фрагмента в новый:

  v.shrink_to_fit();

10. Теперь выведем на экран содержимое вектора после второго раунда удаления элементов и закончим с примером:

  for (auto i : v) {

    cout << i << ", ";

  cout << '\n';

11. Скомпилировав и запустив программу, вы увидите следующие строки, показывающие результат выполнения операций по удалению элементов:

$ ./main

1, 3, 5, 6, 4, 8,

6, 4, 8,

Как это работает

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

Код, удаляющий все значения

из вектора, выглядел так:

const auto new_end (remove(begin(v), end(v), 2));

v.erase(new_end, end(v));

Функции

std::begin

std::end

принимают в качестве параметра экземпляр вектора и соответственно возвращают итераторы, которые указывают на первый элемент и на позицию, находящуюся после последнего элемента, как показано на рис. 2.1.

После того как мы передадим их и значение

функции

std::remove

, она переместит все значения, кроме

, вперед точно так же, как если бы мы сделали это вручную с помощью цикла. С первого взгляда рисунок может показаться непонятным. На шаге 2 все еще можно найти значение

, а сам вектор должен был стать короче, поскольку содержал четыре таких значения. Вместо этого значения

, присутствовавшие в оригинальном массиве, встречаются дважды. Что происходит?

Рассмотрим только элементы, находящиеся в рамках диапазона от итератора

begin

, показанного на рис. 2.1, до итератора

new_end

. Элемент, на который указывает итератор

new_end

, является первым элементом за пределами диапазона, поэтому он не включается. Сконцентрировавшись на заданном участке (в нем содержатся элементы от

до

включительно), мы понимаем, что перед нами корректный диапазон, из которого удалены все значения

Здесь вступает в дело функция

erase

: мы должны указать вектору, что все элементы между итераторами

new_end

end

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

new_end

. Обратите внимание: итератор

new_end

является возвращаемым значением вызова

std::remove

, следовательно, можно просто им воспользоваться.

Заметьте: вектор выполнил больше манипуляций, нежели просто передвинул внутренний указатель. Если бы вектор состоял из более сложных объектов, то ему пришлось бы вызвать деструкторы для всех удаляемых элементов.

В конечном счете вектор выглядит так, как показано в шаге 3: считается, что его размер уменьшился. Старые элементы, лежащие вне диапазона, все еще находятся в памяти.

Чтобы вектор занимал ровно столько памяти, сколько ему нужно, в конце работы мы вызываем метод

shrink_to_fit

. Во время этого вызова выделяется ровно необходимый объем памяти, все элементы перемещаются и освобождается более крупный фрагмент памяти, который уже не нужен.

В шаге 8 мы определили функцию-предикат и использовали ее вместе с функцией

std::remove_if

. Это работает, поскольку независимо от того, какой итератор вернет функция, его можно будет безопасно применить в функции вектора

erase

. Если мы не найдем нечетных элементов, то функция

std::remove_if

не выполнит никаких действий и вернет конечный итератор. Далее вызов наподобие

v.erase(end, end);

также ни к чему не приведет.

Дополнительная информация

Функция

std::remove

работает и для других контейнеров. При ее вызове для

std::array

обратите внимание, что массив не поддерживает вызов функции erase из второго шага, поскольку вы не можете изменять его размер автоматически. Несмотря на то что функция

std::remove

, по сути, лишь перемещает элементы и не удаляет их, она пригодна для структур данных наподобие массивов, которые не могут изменять размер. При работе с массивом можно переписать значения после конечного итератора некоторыми граничными значениями, например

'\0'

для строк.

Удаляем элементы из неотсортированного объекта класса std::vector за время O(1)

Удаление элементов из середины вектора занимает O(n) времени. При этом образовавшийся промежуток должен быть заполнен: все элементы, стоящие после него, перемещаются на одну позицию влево.

Такое перемещение с сохранением порядка может оказаться затратным по времени, если перемещаемые элементы сложны и/или велики и содержат много объектов. Если порядок сохранять не требуется, можно оптимизировать процесс, как показано в этом разделе.

Как это делается

В этом примере мы заполним экземпляр класса

std::vector

некими числами, а затем реализуем функцию быстрого удаления, которая удаляет любой элемент из вектора за время O(1).

1. Сначала включим необходимые заголовочные файлы:

#include

#include

#include

2. Далее определим функцию

main

, где создадим вектор, заполненный числами:

int main()

  std::vector v {123, 456, 789, 100, 200};

3. Очередной шаг заключается в том, чтобы удалить значение с индексом

(отсчет начинается с нуля, следовательно, это будет третье число,

). Функция, которую мы будем использовать для данной задачи, еще не реализована. Мы сделаем это спустя несколько шагов. Затем выведем содержимое вектора:

  quick_remove_at(v, 2);

  for (int i : v) {

    std::cout << i << ", ";

  std::cout << '\n';

4. Теперь удалим еще один элемент. Это будет значение

. Предположим, что не знаем его индекс. Как следствие, нужно вызвать функцию

std::find

, которая принимает диапазон (наш вектор) и значение, а затем ищет позицию значения. После этого она возвращает итератор, указывающий на значение

. Мы используем его для той же функции

quick_remove_at

, но на сей раз применим перегруженную версию предыдущей, которая принимает в качестве параметров итераторы. Данная функция также не реализована.

  qu
ick_remove_at(v, std::find(std::begin(v), std::end(v), 123));

  for (int i : v) {

    std::cout << i << ", ";

  std::cout << '\n';

5. Нам осталось реализовать только две функции

quick_remove_at

. Этим и займемся. (Обратите внимание: они должны быть как минимум объявлены до функции main. Так что просто определим их там.)

Обе функции принимают ссылку на вектор, содержащий значения некоторого типа (в нашем случае это

int

), так что мы не решаем за пользователя, какой тип вектора он задействует. Для нас это будет вектор, содержащий значения типа

. Первая функция

quick_remove_at

принимает значения индекса, которые представляют собой числа, вследствие чего ее интерфейс выглядит следующим образом:

template

void quick_remove_at(std::vector &v, std::size_t idx)

6. Сейчас перейдем к самому главному — быстрому удалению элементов. При этом нужно постараться не перемещать слишком большого количества оставшихся элементов. Во-первых, просто возьмем значение последнего элемента вектора и запишем его на место элемента, который должен быть удален. Во-вторых, отбросим последний элемент. Вот и все, только два шага. Мы добавим в этот код небольшую проверку безопасности. Если значение индекса очевидным образом выходит за пределы вектора, мы не станем ничего делать. В противном случае код будет давать сбой для пустого вектора.

 if (idx < v.size()) {

   v[idx] = std::move(v.back());

   v.pop_back();

7. Другая реализация метода

quick_remove_at

работает аналогично. Вместо того чтобы принимать численный индекс, она принимает итератор для вектора

std::vector

. Получить такой обобщенный тип несложно, поскольку для контейнеров STL уже определены подобные типы.

template

void quick_remove_at(std::vector &v,

           typename std::vector::iterator it)

8. Теперь получим доступ к значению, на которое указывает итератор. Как и в другой функции, перепишем его с помощью последнего элемента вектора. Поскольку мы работаем не с числовым индексом, а с итератором, следует выполнять более аккуратную проверку на безопасность. Если итератор указывает на специальную конечную позицию, то разыменовывать его нельзя.

  if (it != std::end(v)) {

9. Внутри этого блока

if

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

   *it = std::move(v.back());

  v.pop_back();

10. Вот и все. Компиляция и запуск программы дадут следующий результат:

$ ./main

123, 456, 200, 100,

100, 456, 200,

Как это работает

Функция

quick_remove_at

довольно быстро удаляет элементы и затрагивает не слишком много других элементов. Это относительно хитроумно. По сути, она ставит последний элемент вектора на место удаляемого элемента. Несмотря на то, что последний элемент не связан с выбранным элементом, он находится в особой позиции: удаление последнего элемента занимает мало времени! Вам нужно лишь сократить размер вектора на одну позицию, и на этом все. На данном шаге элементы не перемещаются. Представить происходящее поможет рис. 2.2.

Оба шага в коде примера выглядят следующим образом:

v.at(idx) = std::move(v.back());

v.pop_back();

В версии с итераторами шаги выглядят примерно так же:

*it = std::move(v.back());

v.pop_back();

По логике, мы меняем местами выбранный и последний элементы. Но в коде мы не делаем этого, а лишь перемещаем последний элемент на место выбранного. Почему? Если бы мы действительно меняли местами элементы, нам пришлось бы сохранить выбранный элемент во временной переменной, переместить последний элемент на место выбранного, а затем сохранить временное значение в последней позиции. Это выглядит бессмысленно, поскольку мы все равно будем удалять последний элемент.

Ладно, значит, менять элементы местами бесполезно, и односторонняя перезапись нам больше подходит. Убедившись в этом, мы можем решить, что такое действие можно выполнить просто с помощью операции

*it = v.back();

, верно? Да, совершенно верно. Но представьте хранение на каждой позиции очень больших строк или даже другого вектора или ассоциативного массива — в такой ситуации эта небольшая операция присваивания приведет к очень затратной операции копирования. Вызов

std::move

, вставленный посередине (между

v.back()

), ускоряет выполнение кода. В случае со строками элемент вектора указывает на большую строку в куче. Нам не нужно ее копировать. Вместо этого при перемещении строки адрес исходной строки меняется на адрес места назначения. Исходный элемент остается прежним, но сам по себе он бесполезен, что нас устраивает, поскольку мы все равно его удаляем.

Получаем доступ к экземплярам класса std::vector быстрым или безопасным способом

Контейнер

std::vector

, возможно, является наиболее широко используемым контейнером STL, поскольку хранит данные аналогично массивам, но работать с ним гораздо удобнее. Однако неверное обращение к элементам вектора может быть опасным. Если вектор содержит 100 элементов, а наш код пытается получить доступ к элементу с индексом 123, то это, очевидно, плохо. Такая программа в лучшем случае даст сбой, поскольку подобное поведение явно указывает на ошибку в коде! Если программа не дает сбой, то мы наверняка заметим ее странное поведение, что куда хуже, чем аварийно завершившая программа. Опытный программист может добавить проверки перед непосредственным обращением к элементу вектора по индексу. Такие проверки не повышают читабельность кода, и многие разработчики не знают, что контейнер

std::vector

уже поддерживает подобные встроенные проверки!

Как это делается

В этом примере мы попытаемся двумя способами получить доступ к элементу контейнера

std::vector

, а затем рассмотрим, как можно применить их для написания более безопасных программ, не снижая читаемости кода.

1. Включим все необходимые заголовочные файлы и заполним вектор тысячей значений

, чтобы нам было с чем работать:

#include

#include

using namespace std;

int main()

  const size_t container_size {1000};

  vector v (container_size, 123);

2. Теперь обратимся к элементу, лежащему за пределами вектора, с помощью оператора

[]

  cout << "Out of range element value: "

    << v[container_size + 10] << '\n';

3. Далее обратимся к элементу, лежащему за пределами вектора, с помощью функции

at

  cout << "Out of range element value: "

    << v.at(container_size + 10) << '\n';

4. Запустим программу и посмотрим, что произойдет. Сообщение об ошибке характерно для GCC. Прочие компиляторы отправят другие, но аналогичные сообщения. Первая операция чтения будет выполнена успешно, но странным образом. Она не заставит программу дать сбой, но мы получим значение, отличное от

. Мы не можем увидеть результат второго обращения, поскольку оно намеренно сгенерировало сбой. Второй подход позволяет гораздо раньше выявить случайные выходы за границы контейнера.

Out of range element value: -726629391

terminate called after throwing an instance of 'std::out_of_range'

 what(): array::at:  n (which is 1010) >= _Nm (which is 1000)

Aborted (core dumped)

Как это работает

Контейнер

std::vector

предоставляет оператор

[]

и функцию

at

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

Оператор

[]

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

at

помогает определять ошибки, при этом вы почти не теряете в производительности.

Широко практикуется использование функции

at

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

[]

в тех местах, где важна высокая производительность.

Дополнительная информация

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

at

. Сделать это нетрудно. Мы окружим вызов функции

at

блоком

try

и определим код обработки ошибки в блоке

catch

try {

  std::cout << "Out of range element value: "

       << v.at(container_size + 10) << '\n';

} catch (const std::out_of_range &e) {

   std::cout << "Ooops, out of range access detected: "

        << e.what() << '\n';

Кстати говоря, контейнер

std::array

также предоставляет функцию

at

Сохраняем сортировку экземпляров класса std::vector

Массивы и векторы не сортируются самостоятельно. Если нам потребуется такая возможность, мы всегда можем воспользоваться структурами данных, которые предоставляют ее автоматически. Контейнер

std::vector

идеально подходит для нашего случая, ведь добавлять в него новые элементы в порядке сортировки несложно и удобно.

Как это делается

В этом примере мы заполним контейнер

std::vector

случайными словами, отсортируем их, а затем вставим дополнительные слова с учетом сортировки.

1. Сначала включим все необходимые заголовочные файлы:

#include

#include

#include

#include

#include

#include

2. Кроме того, объявим пространство имен

std

, чтобы не писать префиксы

std::

using namespace std;

3. Далее напишем небольшую функцию

main

, в которой вектор заполняется случайными строками:

int main()

  vector v {"some", "random", "words",

           "without", "order", "aaa",

           "yyy"};

4. Затем отсортируем вектор. Для этого воспользуемся некоторыми утверждениями и функцией

is_sorted

из STL, показывающей, что изначально вектор не был отсортирован, а теперь все его элементы расположены по порядку:

  assert(false == is_sorted(begin(v), end(v)));

  sort(begin(v), end(v));

  assert(true == is_sorted(begin(v), end(v)));

5. Наконец, добавим случайные слова в отсортированный вектор с помощью новой функции

insert_sorted

, которую будем реализовывать далее. Эти слова сразу нужно помещать в правильную позицию, поэтому вектор останется отсортированным:

  insert_sorted(v, "foobar");

  insert_sorted(v, "zzz");

6. Теперь реализуем функцию

insert_sorted

и расположим ее перед функцией

main:

void insert_sorted(vector &v, const string &word)

  const auto insert_pos (lower_bound(begin(v), end(v), word));

  v.insert(insert_pos, word);

7. Теперь вернемся в функцию

main

— туда, где мы остановились, — и продолжим работу, выведя содержимое вектора и увидев, что процедура вставки отработала:

  for (const auto &w : v) {

   cout << w << " ";

  cout << '\n';

8. Компиляция и запуск программы дадут следующий результат:

aaa foobar order random some without words yyy zzz

Как это работает

Вся программа построена вокруг функции

insert_sorted

, решающей задачу, которой посвящен этот раздел. Для каждой новой строки эта функция определяет позицию в отсортированном векторе (куда нужно произвести вставку), позволяющую сохранить порядок строк в векторе. Однако мы предполагаем, что вектор был отсортирован заранее. Иначе этот подход не сработает.

Позиция определяется с помощью функции STL

lower_bound

, принимающей три аргумента. Первые два из них указывают на начало и конец диапазона. В нашем случае таковым является вектор слов. Третий аргумент — вставляемое слово. Функция находит первый элемент диапазона, который больше ее третьего параметра или равен ему, и возвращает итератор, указывающий на него.

Определив правильную позицию, мы передаем ее методу

insert

контейнера

std::vector

, который принимает всего два аргумента. Первый аргумент — итератор, указывающий на позицию в векторе, в которую будет вставлен второй параметр. Очень удобно, что можно использовать итератор, возвращаемый функцией

lower_ bound

. Второй аргумент — это, конечно же, вставляемый элемент.

Дополнительная информация

Функция

insert_sorted

довольно универсальна. Если мы обобщим типы ее параметров, то она будет работать и с другими типами содержимого контейнеров, и даже для других контейнеров, таких как

std::set

std::deque

std::list

и т.д.! (Обратите внимание: контейнер

set

имеет собственную функцию-член

lower_bound

, которая делает то же самое, что и функция

std::lower_bound

, но более эффективно, поскольку создана специально для множеств.)

template

void insert_sorted(C &v, const T &item)

  const auto insert_pos (lower_bound(begin(v), end(v), item));

  v.insert(insert_pos, item);

При попытке изменить тип контейнера, приведенный в примере, с

std::vector

на что-то еще нужно учитывать следующий факт: не все контейнеры поддерживают функцию

std::sort

. Этот алгоритм предполагает использование контейнеров с произвольным доступом. Таковым, например, не является контейнер

std::list

Вставляем элементы в контейнер std::map эффективно и в соответствии с условиями

Иногда нужно заполнить ассоциативный массив парами «ключ — значение», и при выполнении данной задачи можно столкнуться с двумя ситуациями.

1. Заданный ключ не существует. В этом случае создается новая пара «ключ — значение».

2. Заданный ключ уже существует. В такой ситуации берем существующий элемент и модифицируем его.

Конечно, мы могли бы просто воспользоваться методами

insert

или

emplace

контейнера

map

и проверить успешность их выполнения. Или же нужно модифицировать существующий элемент. В обоих вышеперечисленных случаях функции

insert

emplace

создают элемент, который мы пытаемся вставить, а во втором случае только что созданный элемент отбрасывается. В обоих случаях совершается бесполезный вызов конструктора.

Начиная с С++17, в STL появилась функция

try_emplace

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

try_emplace

Как это делается

В этом примере мы реализуем приложение, которое создает ассоциативный массив на основе списка миллиардеров. В нем отображаются названия стран и ссылки на самого богатого человека, проживающего в данной стране, а также счетчик, указывающий количество миллиардеров.

1. Как всегда, включим некоторые заголовочные файлы; объявим также об использовании пространства имен

std

по умолчанию:

#include

#include

#include

#include

using namespace std;

2. Определим структуру, которая представляет миллиардеров из нашего списка:

struct billionaire {

  string name;

 double dollars;

  string country;

};

3. В функции

main

сначала определяем список миллиардеров. В мире существует множество миллиардеров, поэтому создадим краткий список, включающий самых богатых людей из отдельных стран. Этот список заранее упорядочен. Он основан на списке The World’s Billionaires («Миллиардеры мира»), создаваемом журналом Forbes и находящемся по адресу http://www.forbes.com/billionaires/list/

int main()

  list billionaires {

   {"Bill Gates", 86.0, "USA"},

   {"Warren Buffet", 75.6, "USA"},

   {"Jeff Bezos", 72.8, "USA"},

   {"Amancio Ortega", 71.3, "Spain"},

   {"Mark Zuckerberg", 56.0, "USA"},

   {"Carlos Slim", 54.5, "Mexico"},

   // ...

   {"Bernard Arnault", 41.5, "France"},

   // ...

   {"Liliane Bettencourt", 39.5, "France"},

   // ...

   {"Wang Jianlin", 31.3, "China"},

   {"Li Ka-shing", 31.2, "Hong Kong"}

   // ...

};

4. Теперь определим ассоциативный массив. В нем строка, содержащая страну, соотносится с парой. Пара включает неизменяемую копию первого миллиардера из каждой страны из нашего списка. Эти люди являются самыми богатыми жителями своей страны. Другая переменная, входящая в пару, — счетчик, который будет увеличиваться на каждого последующего миллиардера в стране:

  map> m;

5. Теперь пройдем по списку и попробуем для каждой страны заменить соответствующее значение новой парой. Пара включает ссылку на миллиардера, которого мы просматриваем в данный момент, и значение счетчика, равное

  for (const auto &b : billionaires) {

    auto [iterator, success] = m.try_emplace(b.country, b, 1);

6. При успешном выполнении данного шага не нужно больше ничего делать. Пара, для которой мы предоставили аргументы конструктора

, была создана и вставлена в ассоциативный массив. Если вставка завершилась неудачно, поскольку страна-ключ уже существует, то пара не создавалась. Очень большой размер нашей структуры, описывающей миллиардера, сэкономит время, которое пришлось бы потратить на ее копирование.

Однако в случае неудачи нам все еще нужно увеличить счетчик для заданной страны:

    if (!success) {

     iterator->second.second += 1;

7. На этом все. Теперь можно вывести на экран точное количество миллиардеров, живущих в стране, а также имя самого богатого человека для каждой из них:

  for (const auto & [key, value] : m) {

   const auto &[b, count] = value;

   cout << b.country << " : " << count

     << " billionaires. Richest is "

     << b.name << " with " << b.dollars

     << " B$\n";

8. Компиляция и запуск программы дадут следующий результат. (Конечно, он будет неполным, поскольку мы ограничили наш входной ассоциативный массив.)

$ ./efficient_insert_or_modify

China : 1 billionaires. Richest is Wang Jianlin with 31.3 B$

France : 2 billionaires. Richest is Bernard Arnault with 41.5 B$

Hong Kong : 1 billionaires. Richest is Li Ka-shing with 31.2 B$

Mexico : 1 billionaires. Richest is Carlos Slim with 54.5 B$

Spain : 1 billionaires. Richest is Amancio Ortega with 71.3 B$

USA : 4 billionaires. Richest is Bill Gates with 86 B$

Как это работает

Весь пример строится на функции

try_emplace

контейнера

std::map

, которая появилась в С++17. Она имеет следующую сигнатуру:

std::pair try_emplace(const key_type& k, Args&&... args);

Вставляемый ключ — параметр

, а связанное значение создается на основе набора параметров

args

. При успешной вставке элемента функция вернет итератор, указывающий на новый узел ассоциативного массива, объединенный в пару со значением

true

логического типа. В противном случае булева переменная в паре будет иметь значение

false

, а итератор станет указывать на элемент, с которым пересекается вставляемый элемент.

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

. Если мы уже встречали миллиардера из этой страны, то нужно получить ссылку на существующий счетчик, чтобы увеличить его. Именно это и происходит на шаге 6:

if (!success) {

  iterator->second.second += 1;

Обратите внимание: функции

insert

emplace

контейнера

std::map

работают одинаково. Основное различие между ними заключается в том, что функция

try_emplace

не будет создавать объект, связанный с ключом, если последний уже существует. Это повышает производительность в ситуациях, когда создание объектов занимает много времени.

Дополнительная информация

Наша программа продолжит работать, если мы сменим тип контейнера с

std::map

на

std::unordered_map

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

Исследуем новую семантику подсказок для вставки элементов с помощью метода std::map::insert

Поиск элементов в контейнере

std::map

занимает время O(log(n)). То же касается вставки новых элементов, поскольку позицию, на которую нужно добавить новый элемент, тоже необходимо найти. Простая вставка

М

новых элементов займет время O(M * log(n)).

Чтобы операция была более эффективной, функция вставки контейнера

std::map

принимает необязательный параметр, представляющий собой подсказку для вставки. Это, по сути, итератор, который указывает на место, близкое к будущей позиции вставляемого элемента. Если подсказка корректна, то амортизированное время вставки составит O(1).

Как это делается

В этом примере мы вставим несколько элементов в контейнер

std::map

и используем подсказки для вставки, чтобы снизить количество операций поиска.

1. Мы преобразуем строки в числа, поэтому включим заголовочные файлы для

std::map

std::string

#include

#include

#include

2. Далее создаем ассоциативный массив, в котором содержатся некие символы:

int main()

  std::map m {{"b", 1}, {"c", 2}, {"d", 3}};

3. Теперь вставим несколько элементов и для каждого из них используем подсказку для вставки. Поскольку изначально ее у нас нет, выполним первую операцию вставки, указывая на конечный итератор ассоциативного массива:

  auto insert_it (std::end(m));

4. Вставим элементы в порядке, обратном алфавитному, используя имеющуюся у нас подсказку для вставки, а затем повторно инициализируем ее значением, которое возвращает функция insert. Следующий элемент будет вставлен прямо перед подсказкой:

  for (const auto &s : {"z", "y", "x", "w"}) {

   insert_it = m.insert(insert_it, {s, 1});

5. Чтобы продемонстрировать, как не нужно решать задачу, вставим строку, которая окажется с левого края ассоциативного массива, но зададим для нее неправильную подсказку, указывающую на крайнюю правую позицию ассоциативного массива —

end

  m.insert(std::end(m), {"a", 1});

6. Наконец, просто выведем на экран полученный результат.

  for (const auto & [key, value] : m) {

   std::cout << "\"" << key << "\": " << value << ", ";

  std::cout << '\n';

7. Скомпилировав и запустив программу, мы получим следующий результат. Очевидно, ошибочная подсказка при вставке ничего не испортила, поскольку порядок ассоциативного массива все еще правильный:

"a": 1, "b": 1, "c": 2, "d": 3, "w": 1, "x": 1, "y": 1, "z": 1,

Как это работает

Единственное отличие от обычной вставки в этом примере заключается в том, что мы используем дополнительный итератор-подсказку. Кроме того, мы говорили о правильных и неправильных подсказках.

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

insert

откатится к неоптимизированной версии, которая выполнится за время O(log(n)).

Во время первой вставки у нас есть итератор, указывающий на конечный элемент ассоциативного массива, поскольку у нас нет более удачной стартовой позиции. После вставки в дерево символа

нам станет известно, что прямо перед ним будет вставлен символ

, и это вполне сгодится на роль правильной подсказки. То же применимо и к символу

, если мы будем вставлять его в дерево после добавления символа

, и т.д. Именно поэтому вы можете использовать итератор, который был возвращен последней операцией вставки, для выполнения следующей вставки.

Важно знать, что до появления С++11 подсказки для вставки считались правильными, если указывали на позицию, которая стоит перед вновь вставленным элементом.

Дополнительная информация

Что интересно, неправильная подсказка не нарушает порядок элементов в ассоциативном массиве. Как же тогда это вообще работает и что же означает выражение «амортизированное время вставки равно O(1)»?

Контейнер

std::map

обычно реализуется с применением бинарного дерева поиска. При вставке в данное дерево новый ключ сравнивается с ключами других узлов, начиная с вершины. Если ключ меньше или больше, чем ключ текущего узла, то алгоритм поиска смещается влево или вправо и опускается вниз на один узел. Выполняя такие операции, поисковый алгоритм остановится в точке, где глубина текущего дерева максимальна, и поместит туда новый узел и его ключ. Вполне возможно, что данный шаг нарушит баланс дерева, поэтому после вставки будет выполнен алгоритм перебалансировки.

Когда мы вставляем в дерево элементы, которые имеют ключи, являющиеся непосредственными соседями друг друга (например, целое число

выступает соседом целого числа

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

Если же подсказка ошибочна, то функция вставки попросту проигнорирует ее и начнет работу с выполнения алгоритма поиска. В итоге она отработает корректно, но, очевидно, медленнее.

Эффективно изменяем ключи элементов std::map

Поскольку структура данных

std::map

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

const

Такого рода ограничение разумно, поскольку пользователю будет сложнее неправильно задействовать контейнер

std::map

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

До появления С++17 нам приходилось удалять элементы, для которых нужно изменить ключ, а затем вставлять их снова. Недостаток такого подхода состоит в выполнении бесполезных выделений и высвобождений памяти, что плохо с точки зрения производительности.

Начиная с С++17 можно удалить и снова вставить элементы ассоциативного массива без повторного выделения памяти. Далее мы увидим, как это работает.

Как это делается

В этом примере мы реализуем небольшое приложение, которое упорядочивает список водителей, участвующих в вымышленной гонке, в структуре

std::map

. По мере того, как водители обходят друг друга во время гонки, нужно изменять ключи, показывающие их текущее место. Мы будем делать это в стиле С++17.

1. Начнем с того, что включим все необходимые заголовочные файлы и объявим об использовании пространства имен

std

#include

#include

using namespace std;

2. Мы выведем на экран места всех водителей до и после изменения контейнера map, поэтому реализуем вспомогательную функцию, посвященную именно этому:

template

void print(const M &m)

  cout << "Race placement:\n";

  for (const auto &[placement, driver] : m) {

   cout << placement << ": " << driver << '\n';

3. В функции

main

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

int main()

  map race_placement {

   {1, "Mario"}, {2, "Luigi"}, {3, "Bowser"},

   {4, "Peach"}, {5, "Yoshi"}, {6, "Koopa"},

   {7, "Toad"}, {8, "Donkey Kong Jr."}

};

  print(race_placement);

4. Предположим, что на одном из кругов гонки у Боузера (Bowser) произошла небольшая авария и он откатился на последнее место, а Донки Конгу — младшему (Donkey Kong Jr.) представился шанс перескочить с последнего места на третье. В данном случае сначала нужно извлечь указанные элементы из ассоциативного массива, поскольку это единственный способ манипулировать их ключами. Функция

extract

— новая возможность С++17. Она удаляет элементы из массива, притом не вызывая побочных эффектов, связанных с выделением памяти. Создадим также новую область видимости для данной задачи.

    auto a (race_placement.extract(3));

   auto b (race_placement.extract(8));

5. Теперь поменяем местами ключи Боузера и Донки Конга — младшего. Несмотря на то, что ключи элементов ассоциативного массива обычно неизменяемы (поскольку объявлены с модификатором

const

), можно изменить ключи извлеченных элементов, полученных с помощью метода

extract

    swap(a.key(), b.key());

6. Метод insert контейнера

std::map

в С++17 получил новую перегруженную версию, которая принимает дескрипторы извлеченных узлов, чтобы вставить их в контейнер, не вызывая выделения памяти:

    race_placement.insert(move(a));

   race_placement.insert(move(b));

7. Выходим из области видимости, и на этом все. Выводим на экран новые места гонщиков и позволяем приложению завершиться:

  print(race_placement);

8. Компиляция и запуск программы дадут следующий результат. Сначала мы видим изначальную расстановку гонщиков, а затем новую, которую получили после изменения позиций Боузера и Донки Конга — младшего:

$ ./mapnode_key_modification Race placement:

1: Mario

2: Luigi

3: Bowser

4: Peach

5: Yoshi

6: Koopa

7: Toad

8: Donkey Kong Jr.

Race placement:

1: Mario

2: Luigi

3: Donkey Kong Jr.

4: Peach

5: Yoshi

6: Koopa

7: Toad

8: Bowser

Как это работает

В C++17 контейнер

std::map

получил новую функцию-член

extract

. Она поставляется в двух версиях:

node_type extract(const_iterator position);

node_type extract(const key_type& x);

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

Если мы попробуем извлечь с помощью второго метода (выполняющего поиск по ключу) элемент, которого не существует, то получим пустой экземпляр типа

node_type

. Метод-член

empty()

возвращает булево значение, которое указывает, пуст ли экземпляр

node_type

. Вызов любого метода для пустого экземпляра приводит к неопределенному поведению.

После извлечения узлов можно изменить их ключи с помощью метода

key()

, который предоставляет неконстантный доступ к ключам, несмотря на то что они обычно являются неизменяемыми.

Обратите внимание: для повторного добавления узлов в ассоциативный массив нужно передать их в функцию

insert

. Это логично, поскольку функция

extract

стремится избежать создания ненужных копий и выделения памяти. Еще одно примечание: хотя мы перемещаем экземпляр типа

node_type

, на самом деле никакие значения из контейнера не перемещаются.

Дополнительная информация

Элементы ассоциативного массива, которые были извлечены с помощью метода

extract

, обычно довольно гибкие. Можно извлечь элементы из одного экземпляра типа

map

и вставить их в любой другой экземпляр типа

map

или даже

multimap

. Это верно и для контейнеров

unordered_map

unordered_multimap

, а также

set/multiset

и, соответственно,

unordered_set/unordered_multiset

Для того чтобы можно было перемещать элементы из одной структуры ассоциативного массива или множества в другую, типы ключей, значений и средство выделения памяти должны быть идентичны. Обратите внимание: даже при совпадении этих типов мы не можем перемещать элементы из map в

unordered_map

или из

set

unordered_set

Применяем контейнер std::unordered_map для пользовательских типов

Использование контейнера

std::unordered_map

вместо

std::map

подразумевает дополнительную степень свободы при выборе типа ключа. Контейнер

std::map

требует наличия между ключами естественного порядка. Таким образом элементы можно отсортировать. Но если мы хотим, например, использовать в качестве ключа математический вектор? Мы не можем сказать, что вектор (0, 1) меньше или больше вектора (1, 0). Они просто указывают в разных направлениях. Это верно для контейнера

std::unordered_map

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

==

, который будет проверять идентичность двух объектов. В данном разделе мы рассмотрим пример такой реализации.

Как это делается

В примере мы определим простую структуру

coord

, которая по умолчанию не имеет хеш-функции, поэтому нам потребуется установить ее самостоятельно. Затем задействуем ее, задав соотношение значений

coord

с числами.

1. Сначала включим все необходимое, чтобы вывести на экран и использовать контейнер

std::unordered_map

#include

#include

2. Далее определим собственную структуру, которую не так-то просто хешировать с помощью существующих хеш-функций:

struct coord {

 int x;

  int y;

};

3. Нам нужна не только хеш-функция, которая позволит использовать структуру в качестве ключа для ассоциативного массива, основанного на хеше, но и реализация оператора сравнения:

bool operator==(const coord &l, const coord &r)

  return l.x == r.x && l.y == r.y;

4. Чтобы расширить возможности хеширования, предоставляемые STL, добавим в пространство имен

std

свою специализацию шаблонной структуры

std::hash

. Оно содержит такие же псевдонимы (задаваемые с помощью

using

), как и другие специализации типа

hash

namespace std

template <>

struct hash

  using argument_type = coord;

  using result_type = size_t;

5. Основная часть данной структуры — определение функции

operator()

. Мы просто складываем значения численных членов структуры

coord

. Эта техника хеширования не самая лучшая, но для демонстрации подойдет. Хорошая хеш-функция пытается максимально равномерно распределить значения в рамках допустимого диапазона, чтобы сократить количество хеш-столкновений.

  result_type operator()(const argument_type &c) const

   return static_cast(c.x)

     + static_cast(c.y);

};

6. Теперь можно создать новый экземпляр контейнера

std::unordered_map

, который принимает в качестве ключа структуру

coord

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

std::unordered_map

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

int main()

  std::unordered_map m {{{0, 0}, 1}, {{0, 1}, 2},

                   {{2, 1}, 3}};

  for (const auto & [key, value] : m) {

   std::cout << "{(" << key.x << ", " << key.y

        << "): " << value << "} ";

  std::cout << '\n';

7. Компиляция и запуск программы дадут следующий результат:

$ ./custom_type_unordered_map

{(2, 1): 3} {(0, 1): 2} {(0, 0): 1}

Как это работает

Обычно при создании экземпляра ассоциативного массива, основанного на хеше, например

std::unordered_map

, мы пишем следующую команду:

std::unordered_map my_unordered_map;

Не вполне очевиден тот факт, что при создании компилятором контейнера уточненного типа

std::unordered_map

за кулисами творится настоящее волшебство. Поэтому взглянем на полное определение шаблонного типа:

template<

  class Key,

 class T,

  class Hash = std::hash,

 class KeyEqual = std::equal_to,

  class Allocator = std::allocator< std::pair>

> class unordered_map;

В качестве первых двух типов шаблона мы выбрали

coord

int

, здесь все просто и очевидно. Три остальных типа шаблона являются необязательными, так что автоматически заполняются существующими стандартными шаблонными классами, которые сами принимают типы шаблонов. В случае если последние аргументы заполняются значениями по умолчанию, в качестве типов шаблонов передаются те типы, которые мы указали в первых двух аргументах.

Для нас сейчас особый интерес представляет шаблонный параметр

class Hash:

когда мы не указываем явно что-то другое, он будет специализирован как

std::hash

. STL уже содержит специализации

std::hash

std::hash

std::hash

и многие другие. Эти классы знают, как работать с подобными конкретными типами, что позволяет вычислять оптимальные хеш-значения.

Однако STL пока не знает, как рассчитывать хеш-значение на основе нашей структуры

coord

. Мы лишь определили еще одну специализацию, которая знает, как это делается. Компилятор теперь может пройти по списку всех известных специализаций для контейнера

std::hash

и найти нашу реализацию, что позволит соотнести ее с типом, который мы выбрали для ключа.

Если бы мы не добавили новую специализацию

std::hash

, а назвали бы имеющуюся вместо этого

my_hash_type

, то нам пришлось бы использовать следующую строку для создания объекта:

std::unordered_map my_unordered_map;

Очевидно, что таким образом придется набирать больше кода. Кроме того, при этом подходе код тяжелее читать, в отличие от ситуации, когда компилятор самостоятельно находит правильную реализацию хеш-функции.

Отсеиваем повторяющиеся слова из пользовательского ввода и выводим их на экран в алфавитном порядке с помощью контейнера std::set

Контейнер

std::set

довольно странный. Принцип его работы похож на принцип работы контейнера

std::map

. Однако

std::set

содержит только ключи в качестве значений, а не пары «ключ — значение». Поэтому он не очень подходит для соотношения значения одного типа со значениями другого. Поскольку способы применения этого контейнера не вполне очевидны, многие разработчики даже не знают о его существовании. Они часто начинают реализовывать похожие механизмы самостоятельно, хотя в некоторых ситуациях контейнер

std::set

оказался бы отличным подспорьем.

В этом разделе будет показано, как применить контейнер

std::set

, на примере, в котором мы получаем потенциально большое количество разных элементов. Мы отфильтруем их и выведем на экран уникальные элементы.

Как это делается

В этом примере мы считаем поток слов из стандартного средства ввода. Все уникальные слова будут помещены в экземпляр класса

std::set

. Таким образом мы сможем перечислить все уникальные слова из потока[1].

1. Мы используем несколько разных типов STL, для чего включим некоторые заголовочные файлы:

#include

#include

#include

#include

2. Чтобы сэкономить немного времени на наборе текста, объявим об использовании пространства имен

std

using namespace std;

3. Теперь мы готовы писать саму программу, начинающуюся с функции

main

. В ней создается экземпляр класса

std::set

, в котором будут храниться строки:

int main()

  set s;

4. Далее получим данные от пользователя. Просто считаем их из стандартного потока ввода с помощью удобного итератора

istream_iterator

  istream_iterator it {cin};

  istream_iterator end;

5. Имея начальный и конечный итераторы, которые представляют данные, введенные пользователем, можем просто заполнить множество на основе этих данных с помощью

std::inserter

  copy(it, end, inserter(s, s.end()));

6. На этом, в общем-то, все. Чтобы увидеть, какие уникальные слова мы получили из стандартного ввода, просто выведем на экран содержимое нашего множества:

  for (const auto word : s) {

   cout << word << ", ";

  cout << '\n';

7. Скомпилируем и запустим программу с нашими входными данными. Взглянем на полученный результат, из которого были удалены все дубликаты, а уникальные слова теперь отсортированы по алфавиту:

$ echo "a a a b c foo bar foobar foo bar bar" | ./program

a, b, bar, c, foo, foobar,

Как это работает

В данной программе можно отметить два интересных момента. Первый из них состоит в том, что мы применяем итератор

std::istream_iterator

, чтобы получить доступ к данным, введенным пользователем. Второй момент: для записи этих данных в наш контейнер

std::set

мы задействуем алгоритм

std::copy

, который обернули в экземпляр класса

std::inserter

! Может показаться удивительным то, что всего одна строка кода выполняет всю работу по токенизации входных данных, помещению их во множество, отсортированное по алфавиту, и отсечению дубликатов.

std::istream_iterator

Этот класс очень интересен в тех случаях, когда мы хотим обрабатывать большие объемы однотипных данных, получаемые из потока, чему и посвящен наш пример: мы анализируем все входные данные слово за словом и помещаем их в множество в виде экземпляров класса

std::string

Итератор

std::istream_iterator

принимает один шаблонный параметр с необходимым нам типом. Мы выбрали тип

std::string

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

cin>>var;

. Конструктор принимает экземпляр класса

istream

. Стандартный поток ввода представляется глобальным объектом потока ввода

std::cin

, который вполне подходит для нашего случая.

istream_iterator it {cin};

К созданному итератору потока ввода применимы две операции. Во-первых, при разыменовании (

*it

) он возвращает текущий введенный символ. Поскольку мы указали, что итератор соотнесен с типом

std::string

с помощью шаблонного параметра, этот символ будет содержать одно слово. Во-вторых, при инкременте (

++it

) итератор переходит на следующее слово, к которому мы также можем получить доступ путем разыменования.

Но погодите, нужно быть аккуратными после выполнения операции инкремента и до разыменования. При пустом стандартном потоке ввода итератор нельзя разыменовывать. Вместо этого следует завершить цикл, в котором мы разыменовываем итератор, для получения каждого слова. Условие остановки, позволяющее узнать, что итератор стал некорректным, — сравнение с конечным итератором. Если сравнение

it==end

выполнилось, то мы дошли до последнего введенного слова.

Конечный итератор — это экземпляр

std::istream_iterator

, созданный с помощью стандартного конструктора без параметров. Он нужен для сравнения в условии остановки, проверяемом на каждой итерации цикла:

istream_iterator end;

Как только

std::cin

окажется пустым, итератор

it

обнаружит это и наше сравнение с конечным оператором вернет результат

true

std::inserter

Мы использовали пару итераторов

it

end

как итераторы для работы с входными данными в вызове

std::copy

. Третий параметр должен быть итератором для работы с выходными данными. Здесь мы не можем просто взять итератор

s.begin()

или

s.end()

. Для пустого множества они будут одинаковыми, так что нам даже нельзя разыменовать их независимо от того, делаем мы это для чтения (из) или присваивания (в).

Тут вступает в дело

std::inserter

. Это функция, возвращающая итератор

std::insert_iterator

, который ведет себя как итератор, но при этом делает что-то отличное от того, что делают обычные итераторы. Выполнение операции инкремента для данного итератора ничего не даст. Когда мы его разыменовываем и присваиваем значение, он берет контейнер, прикрепленный к нему, и добавляет в него заданное значение как новый элемент!

При создании экземпляра

std::insert_iterator

с помощью

std::inserter

вам понадобятся два параметра:

auto insert_it = inserter(s, s.end());

Здесь

— наше множество, а

s.end()

— итератор, указывающий на место, куда должен быть вставлен новый элемент. Для пустого множества, с которого и начинается наш пример, этот итератор эквивалентен

s.begin()

. В других структурах данных наподобие векторов или списков второй параметр критически важен при определении того, куда именно итератор вставки должен добавить новые элементы.

Собираем все воедино

В конце концов все волшебство происходит во время вызова метода

std::copy

copy(input_iterator_begin, input_iterator_end, insert_iterator);

Данный вызов получает следующий токен слова из потока

std::cin

с помощью входного итератора и помещает его в контейнер

std::set

. После этого он инкрементирует оба итератора и проверяет, равен ли входной итератор конечному. Если это не так, то в потоке ввода еще остаются слова, так что все повторяется.

Повторяющиеся слова отбрасываются автоматически. При наличии в множестве конкретного слова повторное его добавление эффекта не возымеет. Этим контейнер

std::set

отличается от

std::multiset

, куда можно вставить повторяющиеся записи.

Реализуем простой ОПН-калькулятор с использованием контейнера std::stack

Класс

std::stack

— класс-адаптер, который позволяет помещать в себя объекты, словно в реальную стопку объектов, а также получать их. В текущем разделе на основе этой структуры данных мы создадим калькулятор, применяющий обратную польскую нотацию, ОПН (reverse polish notation, RPN).

ОПН — это нотация, которая может служить для записи математических выражений таким образом, чтобы их было проще анализировать. В ОПН выражение

1 + 2

выглядит как

1 2 +

. Сначала идут операнды, а затем — оператор. Еще один пример: выражение

(1 + 2) * 3

в ОПН выглядит как

1 2 + 3 *

, оно уже показывает, почему подобные выражения проще анализировать, и нам не нужны скобки, чтобы определить подвыражения (рис. 2.4).

Как это делается

В этом примере мы считаем математическое выражение, записанное в формате ОПН, из стандартного потока ввода, а затем передадим его в функцию, которая вычислит его значение. Наконец, выведем на экран численный результат.

1. Мы будем использовать множество вспомогательных объектов из STL, поэтому сначала разместим несколько директив включения:

#include

#include

#include

#include

#include

#include

#include

#include

#include

2. Мы также объявляем, что используем пространство имен

std

, чтобы сэкономить немного времени, которое ушло бы на набор текста:

using namespace std;

3. Далее немедленно начнем реализовывать наш анализатор ОПН. Он станет принимать пару итераторов, указывающих на начало и конец математического выражения, передаваемого в качестве строки, которое будет проработано токен за токеном:

template

double evaluate_rpn(IT it, IT end)

4. Пока мы итерируем по токенам, нам следует запоминать все операнды до тех пор, пока мы не встретим операцию. Для этого и нужен стек. Все числа будут проанализированы и сохранены с удвоенной точностью, поэтому мы заводим стек элементов типа

double

  stack val_stack;

5. Чтобы удобным образом получить доступ к элементам стека, реализуем вспомогательную функцию. Она изменяет стек, извлекая значение с его вершины, а затем возвращает это значение. Таким образом мы сможем выполнить нашу задачу за один шаг:

  auto pop_stack ([&](){

    auto r (val_stack.top());

   val_stack.pop();

    return r;

);

6. Еще одним приготовлением будет определение всех поддерживаемых математических операций. Мы сохраним их в ассоциативный массив, где каждый токен операции будет связан с самой операцией. Операции представлены вызываемыми лямбда-выражениями, которые принимают два операнда, а затем, например, складывают или умножают их и возвращают результат:

  map ops {

    {"+", [](double a, double b) { return a + b; }},

   {"-", [](double a, double b) { return a - b; }},

    {"*", [](double a, double b) { return a * b; }},

   {"/", [](double a, double b) { return a / b; }},

    {"^", [](double a, double b) { return pow(a, b); }},

   {"%", [](double a, double b) { return fmod(a, b); }},

};

7. Теперь наконец можно проитерировать по входным данным. Предположив, что входные итераторы передали строки, мы передаем данные в новый поток

std::stringstream

токен за токеном, поскольку он может анализировать числа:

  for (; it != end; ++it) {

   stringstream ss {*it};

8. Теперь, когда у нас есть все токены, попробуем получить на их основе значение типа

double

. Если эта операция завершается успешно, то у нас появляется операнд, который мы помещаем в стек:

   if (double val; ss >> val) {

     val_stack.push(val);

9. Если же операция завершается неудачно, то перед нами нечто отличное от оператора. Это может быть только операнд. Зная, что все поддерживаемые нами операции бинарны, нужно вытолкнуть два последних операнда из стека:

   else {

     const auto r {pop_stack()};

     const auto l {pop_stack()};

10. Теперь мы получаем операнд путем разыменования итератора

it

, который возвращает строки. Обратившись в ассоциативный массив

ops

, мы получаем лямбда-объект, принимающий в качестве параметров два операнда —

    try {

     const auto & op (ops.at(*it));

     const double result {op(l, r)};

     val_stack.push(result);

11. Мы окружили математическую часть приложения блоком

try

, поэтому можем отловить потенциально возникающие исключения. Вызов функции

at

для контейнера

map

сгенерирует исключение

out_of_range

, если пользователь даст команду выполнить математическую операцию, о которой мы не знаем. В таком случае мы повторно сгенерируем другое исключение, сообщающее о том, что полученный аргумент некорректен (

invalid argument

), и содержащее строку, которая оказалась неизвестной для нас:

    catch (const out_of_range &) {

     throw invalid_argument(*it);

12. На этом все. Когда цикл прекратит свою работу, у нас в стеке будет итоговый результат. Так что мы просто вернем его. (В тот момент можно проверить, равен ли размер стека единице. Если нет, значит, некоторые операции были пропущены.)

  return val_stack.top();

13. Теперь можно воспользоваться нашим анализатором ОПН. Для этого обернем стандартный поток ввода данных с помощью пары итераторов

std::istream_iterator

и передадим его функции-анализатору ОПН. Наконец, выведем результат на экран:

int main()

  try {

   cout << evaluate_rpn(istream_iterator{cin}, {})

     << '\n';

14. Опять же эту строку мы обернули в блок

try

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

  catch (const invalid_argument &e) {

   cout << "Invalid operator: " << e.what() << '\n';

15. После компиляции программы можно с ней поэкспериментировать. Входные данные

"3 1 2 + * 2 /"

представляют собой выражение

(3 * (1 + 2) ) / 2

, которое приложение преобразует к корректному результату:

$ echo "3 1 2 + * 2 /" | ./rpn_calculator

4.5

Как это работает

Весь пример строится на помещении операндов в стек до тех пор, пока мы не найдем во входных данных операцию. В этой ситуации мы выталкиваем два последних операнда из стека, применяем к ним операцию и помещаем результат обратно в стек. Чтобы понять весь код примера, важно разобраться, как мы различаем операнды и операторы, работаем со стеком, а также выбираем и применяем правильную математическую операцию.

Работа со стеком

Мы помещаем элементы в стек с помощью функции

push

класса

std::stack

val_stack.push(val);

Выталкивание элемента из стека выглядит чуть сложнее, поскольку нам пришлось реализовывать для этого лямбда-выражение, которое принимает ссылку на объект

val_stack

. Взглянем на код, только теперь добавим к нему комментарии:

  auto pop_stack ([&](){

   auto r (val_stack.top()); // Получаем копию верхнего значения

    val_stack.pop();      // Удаляем верхнее значение

   return r;         // Возвращаем копию

);

Это лямбда-выражение необходимо для получения верхнего значения стека удаления из самого адаптера всего за один шаг. Интерфейс класса

std::stack

не позволяет делать это с помощью одного простого вызова. Однако определить лямбда-выражение нетрудно, так что теперь можно получать значения следующим образом:

double top_value {pop_stack()};

Различаем в пользовательском вводе операнды и операторы

В основном цикле функции

evaluate_rpn

мы получаем текущий токен строки из итератора и затем смотрим, является ли он операндом. Если строка может быть преобразована в переменную типа

double

, то данное число тоже операнд. Все остальные токены, которые нельзя легко преобразовать в число (например, "

"), мы считаем операторами.

Скелет кода для выполнения именно этой задачи выглядит следующим образом:

stringstream ss {*it};

if (double val; ss >> val) {

  // Это число!

} else {

  // Это что-то другое. Это операция!

Оператор потока

>>

говорит нам, является ли рассматриваемый объект числом. Сначала мы оборачиваем строку в

std::stringstream

. Затем используем способность объекта класса

stringstream

преобразовать объект типа

std::string

в переменную типа

double

, что включает в себя разбор. Если он не работает, то мы узнаем об этом, поскольку не получится преобразовать в число некий объект, который числом не является.

Выбираем и применяем нужную математическую операцию

Разобравшись, что текущий токен, полученный от пользователя, не является числом, мы предполагаем, что это операция наподобие

или

. Затем обращаемся к ассоциативному массиву ops с целью найти требуемую операцию и получить функцию, принимающую два операнда и возвращающую сумму, произведение или другой подходящий результат.

Сам тип такого массива выглядит относительно сложно:

map ops { ... };

Он соотносит строки и значения типа

double (*)(double, double)

. Что означает вторая часть данного выражения? Это описание типа читается как «указатель на функцию, которая принимает два числа типа

double

и возвращает одно». Представьте, будто часть (

) представляет собой имя функции, как, например,

double sum(double, double)

, что гораздо проще прочитать. Идея заключается в следующем: наше лямбда-выражение

[](double, double) { return /* какое-то число типа double */ }

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

Таким образом, это удобный способ запросить у ассоциативного массива корректную операцию:

const auto & op (ops.at(*it));

const double result {op(l, r)};

Ассоциативный массив неявно решает еще одну задачу. Если мы выполняем вызов

ops.at("foo")

, то в данном случае "

foo

" является корректным значением ключа, но мы не сохранили операцию с таким именем. В подобных случаях массив сгенерирует исключение, которое мы отлавливаем в нашем примере. При его перехвате мы генерируем другое исключение, чтобы представить более подробное сообщение об ошибке. Пользователь будет лучше понимать, что означает полученное исключение, сообщающее о некорректном аргументе (

invalid argument

), в отличие от исключения, гласящего о выходе за пределы контейнера. Обратите внимание: пользователь функции

evaluate_rpn

может быть незнаком с ее реализацией и поэтому не знает о том, что мы применяем ассоциативный массив.

Дополнительная информация

Поскольку функция

evaluate_rpn

принимает итераторы, ей можно легко передавать разные входные данные, не только стандартный поток ввода. Это позволяет довольно просто протестировать ее, а также адаптировать к различным источникам данных, получаемых от пользователя.

Передача в эту функцию итераторов строкового потока или вектора строк, например, выглядит следующим образом. При этом код функции

evaluate_rpn

остается без изменений:

int main()

  stringstream s {"3 2 1 + * 2 /"};

  cout << evaluate_rpn(istream_iterator{s}, {}) << '\n';

  vector v {"3", "2", "1", "+", "*", "2", "/"};

  cout << evaluate_rpn(begin(v), end(v)) << '\n';

Используйте итераторы везде, где это имеет смысл. Так вы сможете многократно применять свой код.

Подсчитываем частоту встречаемости слов с применением контейнера std::map

Контейнер

std::map

очень полезен в тех случаях, когда нужно разбить данные на категории и собрать соответствующую статистику. Прикрепляя изменяемые объекты к каждому ключу, который представляет собой категорию объектов, вы легко можете реализовать, к примеру, гистограмму, показывающую частоту встречаемости слов. Этим мы и займемся.

Как это делается

В этом примере мы считаем все данные, которые пользователь передает через стандартный поток ввода и которые, скажем, могут оказаться текстовым файлом. Мы разобьем полученный текст на слова, чтобы определить частоту встречаемости каждого слова.

1. Как обычно, включим все заголовочные файлы для тех структур данных, которые планируем использовать:

#include

#include

#include

#include

#include

2. Чтобы сэкономить немного времени на наборе, объявляем об использовании пространства имен

std

using namespace std;

3. Задействуем одну вспомогательную функцию, с помощью которой будем обрезать прикрепившиеся знаки препинания (например, запятые, точки и двоеточия):

string filter_punctuation(const string &s)

  const char *forbidden {".,:; "};

  const auto idx_start (s.find_first_not_of(forbidden));

  const auto idx_end (s.find_last_not_of(forbidden));

  return s.substr(idx_start, idx_end - idx_start + 1);

4. Теперь начнем писать саму программу. Создадим ассоциативный массив, в котором будут связаны каждое встреченное нами слово и счетчик, показывающий, насколько часто это слово встречается. Дополнительно введем переменную, которая будет содержать величину самого длинного встреченного нами слова, чтобы в конце работы программы перед выводом на экран мы могли красиво выровнять полученную таблицу:

int main()

  map words;

 int max_word_len {0};

5. Когда мы выполняем преобразование из

std::cin

в переменную типа

std::string

, поток ввода обрезает лишние пробельные символы. Таким образом мы получаем входные данные слово за словом:

  string s;

  while (cin >> s) {

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

    auto filtered (filter_punctuation(s));

7. В том случае, если текущее слово оказалось самым длинным из всех встреченных нами, обновляем переменную

max_word_len

   max_word_len = max(max_word_len, filtered.length());

8. Теперь увеличим значение счетчика в нашем ассоциативном массиве

words

. Если слово встречается в первый раз, то оно неявно добавляется в массив перед выполнением операции инкремента:

    ++words[filtered];

9. После завершения цикла мы знаем, что сохранили все уникальные слова из потока ввода в ассоциативный массив

words

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

  vector>

word_counts;

  word_counts.reserve(words.size());

  move(begin(words), end(words), back_inserter(word_counts));

10. Теперь вектор содержит все пары «слово — частота» в том же порядке, в каком они находились в ассоциативном массиве

words

. Далее отсортируем его снова, чтобы наиболее частые слова оказались в начале, а самые редкие — в конце:

  sort(begin(word_counts), end(word_counts),

   [](const auto &a, const auto &b) {

     return a.second > b.second;

);

11. Все данные выстроены в нужном порядке, поэтому отправим их на консоль. Используя манипулятор потока

std::setw

, красиво отформатируем данные с помощью отступов так, чтобы они были похожи на таблицу:

  cout << "# " << setw(max_word_len) << "" << " #\n";

  for (const auto & [word, count] : word_counts) {

   cout << setw(max_word_len + 2) << word << " #"

     << count << '\n';

12. После компиляции программы можно обработать любой текстовый файл и получить для него таблицу частоты встречаемости слов:

$ cat lorem_ipsum.txt | ./word_frequency_counter

#  #

    et #574

  dolor #302

   sed #273

  diam #273

   sit #259

  ipsum #259

...

Как это работает

Этот пример посвящен сбору всех слов в контейнере

std::map

и последующему их перемещению в контейнер

std::vector

, где они будут отсортированы для вывода на экран. Почему?

Взглянем на пример. Если мы подсчитаем частоту встречаемости слов в строке "

a a b c b b b d c c

", то получим следующее содержимое массива:

a -> 2

b -> 4

c -> 3

d -> 1

Однако мы хотели бы представить данные пользователю в другом порядке. Программа сначала должна вывести на экран b, поскольку это слово встречается чаще остальных. Затем

. К сожалению, мы не можем запросить у ассоциативного массива ключ с максимальным значением, а потом ключ со вторым по величине значением и т.д.

Здесь в игру вступает вектор. Мы указали, что в него будут входить пары, состоящие из строки и значения счетчика. Таким образом, он станет принимать именно те значения, которые хранятся в массиве:

vector> word_counts;

Далее мы заполняем вектор парами «слово — частота» с помощью алгоритма

std::move

. Он выгодно отличается от других: та часть строки, которая находится в куче, не будет продублирована, а только перемещена из ассоциативного массива в вектор. Это позволит избежать создания множества копий.

move(begin(words), end(words), back_inserter(word_counts));

В некоторых реализациях STL используется оптимизация коротких строк: если строка не слишком длинная, то в куче для нее не будет выделена память, вместо этого ее сохранят непосредственно в объекте строки. В таком случае скорость перемещения не увеличивается. Но она и не уменьшается!

Следующий интересный шаг — операция сортировки, в которой в качестве пользовательского оператора сравнения применяется лямбда-выражение:

sort(begin(word_counts), end(word_counts),

  [](const auto &a, const auto &b) { return a.second > b.second; });

Алгоритм сортировки будет принимать элементы попарно и сравнивать их, этим он ничем не отличается от других алгоритмов сортировки. Предоставляя такую лямбда-функцию, мы даем алгоритму команду не просто определить, меньше ли значение

, чем значение

(реализация по умолчанию), но и сравнить значения

a.second

b.second

. Обратите внимание: все объекты являются парами «строка и ее значение счетчика», и с помощью нотации

a.second

мы получаем доступ к значению счетчика для слова. Таким образом, наиболее часто встречающиеся слова перемещаются в начало вектора, а наиболее редко встречающиеся — в конец.

Вспомогательный стилистический редактор для поиска длинных предложений в текстах с помощью std::multimap

Когда большое количество элементов нужно сохранить в упорядоченном виде, а ключи могут встречаться несколько раз, пригодится контейнер

std::multimap

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

Как это делается

В этом примере мы считаем данные, введенные пользователем, из стандартного потока ввода, и разобьем их на предложения (а не на слова, как делали раньше). Далее поместим все предложения в контейнер

std::multimap

в паре с переменной, в которой записана их длина. После этого выведем пользователю все предложения, отсортировав их по длине.

1. Как обычно, включим все необходимые заголовочные файлы. Контейнер

std::multimap

поставляется оттуда же, откуда и контейнер

std::map

#include

#include

#include

#include

2. Мы будем применять множество функций из пространства имен

std

, поэтому объявим о его (автоматическом) использовании:

using namespace std;

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

string filter_ws(const string &s)

  const char *ws {" \r\n\t"};

  const auto a (s.find_first_not_of(ws));

  const auto b (s.find_last_not_of(ws));

  if (a == string::npos) {

   return {};

  return s.substr(a, b - a + 1);

4. Функция определения длины предложения станет принимать гигантскую строку, содержащую весь текст, и возвращать контейнер

std::multimap

, в котором будут соотнесены предложения и их длины:

multimap get_sentence_stats(const string &content)

5. Начнем с объявления структуры

multimap

, которая станет возвращаемым значением, а также нескольких итераторов. Поскольку мы создадим цикл, нам понадобится конечный итератор. Далее воспользуемся двумя итераторами, чтобы указать на две соседние точки (знаки препинания) внутри текста. Все находящееся между ними будем считать предложением.

  multimap ret;

  const auto end_it (end(content));

  auto it1 (begin(content));

  auto it2 (find(it1, end_it, '.'));

6. Итератор

it2

всегда будет указывать на одну точку дальше, чем итератор

it1

. До тех пор, пока итератор

it1

не достигнет конца текста, все будет в порядке. Второе условное выражение проверяет, действительно ли итератор

it2

указывает на позицию, стоящую на несколько символов дальше. Если это не так, то у нас не осталось непрочитанных символов.

  while (it1 != end_it && distance(it1, it2) > 0) {

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

   string s {filter_ws({it1, it2})};

8. Возможно, приложение не содержит ничего, кроме пробельных символов. В этом случае просто отбрасываем его. В противном случае установим его длину, определив количество слов. Это делается легко, поскольку все слова разделены одним

пробелом

[2]. Затем сохраняем количество слов и само предложение в контейнер

multimap

   if (s.length() > 0) {

    const auto words (count(begin(s), end(s), ' ') + 1);

    ret.emplace(make_pair(words, move(s)));

[3]

9. На следующей итерации цикла мы переводим ведущий итератор

it2

на символ точки в следующем предложении. Догоняющий итератор

it1

переводим на следующий символ относительно предыдущей позиции ведущего итератора:

   it1 = next(it2, 1);

[4]

   it2 = find(it1, end_it, '.');

10. После завершения работы цикла контейнер будет содержать все предложения, объединенные в пары с количеством слов, содержащихся в них. Наконец можно вернуть полученный результат:

  return ret;

11. Теперь воспользуемся вновь добавленной функцией. Сначала укажем

std::cin

не пропускать пробельные символы, поскольку нам нужны предложения с пробелами как единое целое. Чтобы считать весь файл, инициализируем

std::string

на основе итераторов потока ввода, которые инкапсулируют

std::cin

int main()

  cin.unsetf(ios::skipws);

  string content {istream_iterator{cin}, {}};

12. Поскольку нужен полученный контейнер

multimap

лишь для того, чтобы вывести на экран результат, помещаем вызов функции

get_sentence_stats

непосредственно в цикл и передаем ему нашу строку. В теле цикла выведем элементы построчно:

  for (const auto & [word_count, sentence]

    : get_sentence_stats(content)) {

   cout << word_count << " words: " << sentence << ".\n";

13. После компиляции кода мы можем дать приложению команду использовать содержимое любого текстового файла. Текст-пример

Lorem Ipsum

даст следующий результат. Вывод на экран довольно велик для длинных текстов с большим количеством предложений: сначала выводятся самые короткие предложения, а затем — самые длинные. В результате мы сразу видим самые длинные предложения, поскольку обычно по умолчанию на экране отображается нижняя часть вывода:

$ cat lorem_ipsum.txt | ./sentence_length

[5]

...

10 words: Nam quam nunc, blandit vel, luctus pulvinar,

hendrerit id, lorem.

10 words: Sed consequat, leo eget bibendum sodales,

augue velit cursus nunc,.

12 words: Cum sociis natoque penatibus et magnis dis

parturient montes, nascetur ridiculus mus.

17 words: Maecenas tempus, tellus eget condimentum rhoncus,

sem quam semper libero, sit amet adipiscing sem neque sed ipsum.

Как это работает

Весь этот пример посвящен разбиению большой строки на предложения, после чего мы определяем их длину и помещаем в контейнер

multimap

в упорядоченном виде. Поскольку контейнер

std::multimap

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

const auto end_it (end(content));

auto it1 (begin(content)); // (1) Начало строки

auto it2 (find(it1, end_it, '.')); // (1) Первая точка '.'

while (it1 != end_it && std::distance(it1, it2) > 0) {

  string sentence {it1, it2};

  // Что-то делаем со строкой предложения...

  it1 = std::next(it2, 1);    // Один символ справа от текущей точки '.'

 it2 = find(it1, end_it, '.'); // Следующая точка или конец строки

Взглянем на код, имея при этом в виду следующий рисунок, на котором приведены три предложения (рис. 2.5).

Итераторы

it1

it2

всегда перемещаются вперед по строке вместе. Таким образом, они всегда указывают на начало и конец одного и того же предложения. Алгоритм

std::find

заметно облегчает нам жизнь, поскольку работает по принципу «начинаем с текущей позиции, а затем возвращаем итератор, указывающий на следующий символ точки. Если такого итератора нет, то возвращаем конечный итератор».

После извлечения строки с предложением определим, сколько слов в ней содержится, а затем вставим ее в контейнер

multimap

. Мы используем количество слов в качестве ключа для элементов массива, а саму строку — как объект, связанный с данным ключом. Мы не можем воспользоваться контейнером

std::map

, так как предложений одинаковой длины может быть довольно много. Но это не проблема, поскольку мы задействуем контейнер

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

располагается в заголовочном файле

#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

Как это работает

Контейнер

std::priority_queue

очень прост в использовании. Нам понадобилось всего три функции.

q.push(item)

помещает элемент в очередь.

q.top()

возвращает ссылку на элемент, который первым покинет очередь.

q.pop()

удаляет первый элемент из очереди.

Но каким образом происходит упорядочение элементов? Мы сгруппировали числа, указывающие на приоритет, и строки, описывающие элементы списка текущих дел, в объекты типа

std::pair

, что позволило упорядочить элементы автоматически. Если у нас есть экземпляр

типа

std::pair

, 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). Это бы понравилось самым ленивым из нас!)



                

                    
    
        
            
                 ТЕЛЕГРАМ
                Канал с обзорами, анонсами новинок и книжными подборками
                 Книжный Вестник

                
                Бот для удобного поиска книг (если не нашлось на сайте)
                 Поиск книг

                
                Свежие любовные романы в удобных форматах
                 Любовные романы

                
                О психологии, саморазвитии и личностном росте
                 Саморазвитие

                
                Детективы и триллеры, все новинки
                 Детективы

                
                Фантастика и фэнтези, все новинки 
                 Фантастика

                
                Отборные классические книги 
                 Классика


            
        
        
        
        
        
        
        
        
        
            
                 ВКОНТАКТЕ
                Цитаты, афоризмы, стихи, книжные подборки, обсуждения и многое другое
                 Книжный Вестник
            
        

        
            
                 БИБЛИОТЕКИ
                Библиотека с любовными романами, которая наверняка придётся по вкусу женской части аудитории
                
                    Любовные романы

                
                Библиотека с фантастикой и фэнтези, а также смежных жанров
                
                    Фантастика

                
                Самые популярные книги в формате фб2
                 Топ фб2
                    книги




        
            
                
                    
                        Оглавление
                        
                    
                    
                         ПожаловатьсяК описанию
Оглавление
Предисловие
Темы, рассмотренные в этой книге
Что вам нужно для работы с книгой
Для кого предназначено издание
Разделы
Условные обозначения
Загрузка примеров кода
Глава 1 Новые возможности С++17
Введение
Применяем структурированные привязки (декомпозицию) для распаковки набора возвращаемых значений
Ограничиваем область видимости переменных в выражениях if и switch
Новые правила инициализатора с фигурными скобками
Разрешаем конструктору автоматически выводить полученный тип класса шаблона
Упрощаем принятие решений во время компиляции с помощью constexpr-if
Подключаем библиотеки с помощью встраиваемых переменных
Реализуем вспомогательные функции с помощью выражений свертки
Глава 2 Контейнеры STL
Введение
Используем идиому erase-remove для контейнера std::vector
Удаляем элементы из неотсортированного объекта класса std::vector за время O(1)
Получаем доступ к экземплярам класса std::vector быстрым или безопасным способом
Сохраняем сортировку экземпляров класса std::vector
Вставляем элементы в контейнер std::map эффективно и в соответствии с условиями
Исследуем новую семантику подсказок для вставки элементов с помощью метода std::map::insert
Эффективно изменяем ключи элементов std::map
Применяем контейнер std::unordered_map для пользовательских типов
Отсеиваем повторяющиеся слова из пользовательского ввода и выводим их на экран в алфавитном порядке с помощью контейнера std::set
Реализуем простой ОПН-калькулятор с использованием контейнера std::stack
Подсчитываем частоту встречаемости слов с применением контейнера std::map
Вспомогательный стилистический редактор для поиска длинных предложений в текстах с помощью std::multimap
Реализуем личный список текущих дел с помощью std::priority_queue
Глава 3 Итераторы
Введение
Создаем собственный итерабельный диапазон данных
Обеспечиваем совместимость собственных итераторов с категориями итераторов STL
Используем оболочки итераторов для заполнения обобщенных структур данных
Реализуем алгоритмы с помощью итераторов
Перебор в обратную сторону с применением обратных адаптеров для итераторов
Завершение перебора диапазонов данных с использованием ограничителей
Автоматическая проверка кода итераторов с помощью проверяемых итераторов
Создаем собственный адаптер для итераторов-упаковщиков
Глава 4 Лямбда-выражения
Введение
Динамическое определение функций с помощью лямбда-выражений
Добавляем полиморфизм путем оборачивания лямбда-выражений в std::function
Создаем функции методом конкатенации
Создаем сложные предикаты с помощью логической конъюнкции
Вызываем несколько функций с одинаковыми входными данными
Реализуем функцию transform_if с применением std::accumulate и лямбда-выражений
Генерируем декартово произведение на основе любых входных данных во время компиляции
Глава 5 Основы работы с алгоритмами STL
Введение
Копируем элементы из одних контейнеров в другие
Сортируем контейнеры
Удаляем конкретные элементы из контейнеров
Преобразуем содержимое контейнеров
Выполняем поиск элементов в упорядоченных и неупорядоченных векторах
Ограничиваем допустимые значения вектора конкретным численным диапазоном с помощью std::clamp
Находим шаблоны в строках с помощью функции std::search и выбираем оптимальную реализацию
Делаем выборку данных из крупных векторов
Выполняем перестановки во входных последовательностях
Инструмент для слияния словарей
Глава 6 Сложные случаи использования алгоритмов STL
Введение
Реализуем класс префиксного дерева с использованием алгоритмов STL
Создаем генератор поисковых подсказок с помощью префиксных деревьев
Реализуем формулу преобразования Фурье с применением численных алгоритмов STL
Определяем ошибку суммы двух векторов
Реализуем отрисовщик множества Мандельброта в ASCII
Создаем собственный алгоритм split
Создаем полезные алгоритмы на основе стандартных алгоритмов gather
Удаляем лишние пробелы между словами
Компрессия и декомпрессия строк
Глава 7 Строки, классы потоков и регулярные выражения
Введение
Создание, конкатенация и преобразование строк
Удаляем пробелы из начала и конца строк
Преимущества использования std::string без затрат на создание объектов std::string
Считываем значения из пользовательского ввода
Подсчитываем все слова в файле
Форматируем ваши выходные данные с помощью манипуляторов потока ввода-вывода
Инициализируем сложные объекты из файла вывода
Заполняем контейнеры с применением итераторов std::istream
Выводим любые данные на экран с помощью итераторов std::ostream
Перенаправляем выходные данные в файл для конкретных разделов кода
Создаем пользовательские строковые классы путем наследования std::char_traits
Токенизация входных данных с помощью библиотеки для работы с регулярными выражениями
Удобный и красивый динамический вывод чисел на экран в зависимости от контекста
Перехватываем читабельные исключения для ошибок потока std::iostream
Глава 8 Вспомогательные классы
Введение 
Преобразуем единицы измерения времени с помощью std::ratio
Выполняем преобразование между абсолютными и относительными значениями с использованием std::chrono
Безопасно извещаем о сбое с помощью std::optional
Применяем функции для кортежей
Быстрое создание структур данных с помощью std::tuple
Замена void* с использованием std::any для повышения безопасности типов
Хранение разных типов с применением std::variant
Автоматическое управление ресурсами с помощью std::unique_ptr
Автоматическое управление разделяемой памятью кучи с использованием std::shared_ptr
Работаем со слабыми указателями на разделяемые объекты
Упрощаем управление ресурсами устаревших API с применением умных указателей
Открываем доступ к разным переменным — членам одного объекта
Генерируем случайные числа и выбираем правильный генератор случайных чисел
Генерируем случайные числа и создаем конкретные распределения с помощью STL
Глава 9 Параллелизм и конкурентность 
Введение
Автоматическое распараллеливание кода, использующего стандартные алгоритмы
Приостанавливаем программу на конкретный промежуток времени
Запускаем и приостанавливаем потоки
Выполняем устойчивую к исключениям общую блокировку с помощью td::unique_lock и std::shared_lock
Избегаем взаимных блокировок с применением std::scoped_lock
Синхронизация конкурентного использования std::cout
Безопасно откладываем инициализацию с помощью std::call_once
Отправляем выполнение задач в фоновый режим с применением std::async
Реализуем идиому «производитель/потребитель» с использованием std::condition_variable
Реализуем идиому «несколько производителей/потребителей» с помощью std::condition_variable
Распараллеливание отрисовщика множества Мандельброта в ASCII с применением std::async
Небольшая автоматическая библиотека для распараллеливания с использованием std::future
Глава 10 Файловая система
Введение
Реализуем нормализатор пути файла
Получаем канонические пути к файлам из относительных путей
Составляем список всех файлов в каталоге
Инструмент текстового поиска в стиле grep
Инструмент для автоматического переименования файлов
Создаем индикатор эксплуатации диска
Подбиваем статистику о типах файлов
Инструмент для уменьшения размера папки путем замены дубликатов символьными ссылками
Об авторе
О рецензенте
Примечания
                    

                
            
        

        
            
                
                    

                    
                    
                        
                    
                
            
        

        

        

        
            
                
                    Загрузка...