C++17 STL Стандартная библиотека шаблонов — страница 21 из 119

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, поскольку это слово встречается чаще остальных. Затем 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; });

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