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

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, поскольку это слово встречается чаще остальных. Затем c, a и d. К сожалению, мы не можем запросить у ассоциативного массива ключ с максимальным значением, а потом ключ со вторым по величине значением и т.д.

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

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, чем значение b (реализация по умолчанию), но и сравнить значения a.second и b.second. Обратите внимание: все объекты являются парами «строка и ее значение счетчика», и с помощью нотации a.second мы получаем доступ к значению счетчика для слова. Таким образом, наиболее часто встречающиеся слова перемещаются в начало вектора, а наиболее редко встречающиеся — в конец.

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