2. Контейнеры и алгоритмы STL

Цель

Получить базовые навыки использования алгоритмов и контейнеров стандартной библиотеки C++.
Реализовать и покрыть тестами алгоритм Soundex.
Реализовать утилиту для группировки фонетически близких имен с выводом в машиночитаемом формате (json или xml).

cpp-labs
|-- src/libcsc/libcsc/soundex
|   |-- soundex.cpp
|   `-- soundex.hpp
|-- src/soundex_groupby/soundex_groupby
|   `-- main.cpp
`-- test/libcsc/libcsc
    `-- soundex.cpp

Ход работы

Реализация soundex

Реализуйте функцию для вычисления фонетического хеша строки:

uint32_t soundex_hash(std::string_view str);

При реализации алгоритма не пишите циклы, по максимуму пользуйтесь стандартными алгоритмами: Algorithms library.

В этой части ограничтесь unconstrained версиями алгоритмов, т.е. из пространства имен std, а не std::ranges.

Алгоритм:

Запоминается первая буква слова.
Удаляются все вхождения h и w (за исключением первой буквы слова).
Согласные заменяются на цифры от 1 до 6, причём похожим по звучанию буквам соответствуют одинаковые цифры:
- b, f, p, v → 1
- c, g, j, k, q, s, x, z → 2
- d, t → 3
- l → 4
- m, n → 5
- r → 6
Любая последовательность одинаковых цифр сокращается до одной такой цифры.
Удаляются все a, e, i, o, u, y (за исключением первой буквы слова).
Заменяется первый символ буквой, запомненной на шаге 1, делая её заглавной.
Итоговая строка обрезается до первых четырёх символов. Если длина строки меньше требуемой, недостающие символы заменяются знаком 0.

Покрытие тестами

Все как обычно: классы эквивалентности, граничные значения.

Обработка файла

Напишите утилиту, которая:

Парсит csv-файл names2020.csv.
Группирует имена из файла по их soundex-хешам.
Выводит результат в машиночитаемом формате в соответствии со своим вариантом. Вывод должен быть стабильным:
- Хеши должны быть отсортированы по возрастанию.
- Имена внутри каждого списка также должны быть отсортированы.

Способ ввода и вывода данных (stdin/stdout/файлы) остается на ваше усмотрение, но выбор должен быть аргументирован. Считаем, что утилита для продакшена, хардкод не допускается.

Формат входного файла:

<name>,<gender>,<count>

Можете воспользоваться любой библиотекой для парсинга csv или с помощью стандартных алгоритмов отделить первое поле.

Варианты вывода:

json

Библиотека: nlohmann/json

Пример вывода:

{
  "A000": [
    "Aya",
    "Ayah",
    ...
  ],
  "A100": [
    "Ava",
    "Abby",
    ...
  ],
  ...
  "Z653": [
    "Zerenity"
  ],
  "Z660": [
    "Zorawar",
    "Zarrar"
  ]
}

xml

Библиотека: zeux/pugixml

Пример вывода:

<?xml version="1.0"?>
<soundex>
  <names hash="A000">
    <name>Aya</name>
    <name>Ayah</name>
    ...
  </names>
  <names hash="A100">
    <name>Ava</name>
    <name>Abby</name>
    ...
  </names>
  ...
  <names hash="Z653">
    <name>Zerenity</name>
  </names>
  <names hash="Z660">
    <name>Zorawar</name>
    <name>Zarrar</name>
  </names>
</soundex>

Необязательная часть: ranges

Для C++20 была разработана библиотека ericniebler/range-v3.

В этой части работы реализуйте тот же алгоритм soundex с помощью этой библиотеки. Многие функции не вошли в стандарт, поэтому стоит воспользоваться реализацией Эрика Ниблера. Весь алгоритм (или большая часть) может быть записан в виде одной композиции views, см. Composability в документации.

Сравните результат работы двух реализаций. Сравните производительность.