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

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

int main()

{

  map<string, size_t> 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<int>(max_word_len, filtered.length());

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

    ++words[filtered];

  }

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

  vector<pair<string, size_t>> 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) << "<WORD>" << " #<COUNT>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

# <WORD> #<COUNT>

      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<pair<string, size_t>> 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

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

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

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

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

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