Введение

Одним погожим днём знакомые рассказали про онлайн школу по программированию на C++. Как выяснилось, для участия нужно решить простенькое тестовое задание, правда отправлено оно было слишком поздно и от того не прошло тестовый отбор.

Постановка задачи

Необходимо по входному тексту в UTF-8 кодировке построить частотный словарь вхождений слов. Итоговый словарь должен содержать слова в порядке убывания числа вхождений, а слова с одинаковым числом вхождений должны были быть отсортированы в лексикографическом порядке.

Решение

Решение задачи началось с судорожных попыток вспомнить синтаксис плюсов - последний раз я на нём что-то писал… году в 2014 наверное. Но, так как применения ООП данная задача не требует, удалось обойтись простыми конструкциями, так что, если бы не использование STL контейнеров, то с тем же успехом код можно было бы написать на чистом C. Предложенное решение не является кросс-платформенным и работает только в Linux системах.

Раз в задании требуется поддержка UTF-8, то первым делом установим соответствующую локаль:

    std::setlocale(LC_ALL, "ru_RU.UTF-8");

Далее необходимо получить названия входных файлов:

    std::string inputFile = argv[1];
    std::string outputFile = argv[2];

После получения этой важной информации можно открыть файловые потоки

std::wifstream inputFileStream;
std::wofstream outputFileStream;

if(
    !(
    OpenInputFile(inputFile, inputFileStream)
    &&
    OpenOutputFile(outputFile, outputFileStream)
    )
)
{
    std::wcerr<<L"Не удалось открыть входной либо выходной файл"<<std::endl;
    return 1;
}

О функциях OpenInputFile, OpenOutputFile расскажу чуть позже.

Заведём вектор, в котором будем хранить результирующие значения:

std::vector<std::pair<unsigned int, std::wstring>> wordscounts;

И отработаем основной воркфлоу

FillWordsContainer(inputFileStream, wordscounts);
ReorderWords(wordscounts);
PrintResults(outputFileStream, wordscounts);

Рассмотрим каждую из функций в отдельности

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

На вход функция принимает констатные ссылки на std::pair<unsigned int, std::wstring>. Выбор такого контейнера обусловлен условиями сортировки - первоначально все данные хранились в std:map, однако в нём сортировка осуществляется по ключу.

bool WordPairCompare(const std::pair<unsigned int, std::wstring>& firstPair, const std::pair<unsigned int, std::wstring>& secondPair) 
{  
    if(firstPair.first == secondPair.first)
    {
            return std::lexicographical_compare(firstPair.second.begin(), firstPair.second.end(),
                                                        secondPair.second.begin(), secondPair.second.end());
    }

    return firstPair.first > secondPair.first;
}

FillWordsContainer - основная функция в программе, отвечающая за поиск слов в входном потоке и подсчёт числа их вхождений. Для поиска слов в тексте используется простое регулярное выражение, учитывающее UTF-8 коды русских и английских букв ([\\u0410-\\u044F\\u0042-\\u005A\\u0061-\\u0079]+).

void FillWordsContainer(std::wifstream& file, std::vector<std::pair<unsigned int, std::wstring>>& wordscounts)
{
        std::wstring currentString;
        // Регулярное выражние для поиска слов
        std::wregex wrgx(L"([\\u0410-\\u044F\\u0042-\\u005A\\u0061-\\u0079]+)"); 
        std::wsmatch match;

        while ( !file.eof())
        {
            std::getline( file, currentString );       

            while (std::regex_search(currentString, match, wrgx))
            {
                auto matchString = match.str();
                std::transform(matchString.begin(), matchString.end(), matchString.begin(), std::towlower);

                auto wcount = std::find_if( 
                    wordscounts.begin(),
                    wordscounts.end(),
                    [&matchString](const std::pair<unsigned int, std::wstring>& element)
                    { 
                        return element.second == matchString;
                    } 
                );
                
                if(wcount != wordscounts.end())
                {
                    wcount->first++;
                }
                else
                {
                    wordscounts.push_back(std::make_pair(1, matchString));
                }

                currentString = match.suffix();
            }
        }

        file.close();
}

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

ReorderWords - просто обертка над стандартной функцией sort, чтобы скрыть детали реализации.

void ReorderWords(std::vector<std::pair<unsigned int, std::wstring>>& wordscounts)
{
    std::sort(wordscounts.begin(),wordscounts.end(), WordPairCompare);
}

PrintResults - вывод результатов в выходной поток.

void PrintResults(std::wofstream& file, const std::vector<std::pair<unsigned int, std::wstring>>& wordscounts)
{
        for (auto x : wordscounts)
        {
                file << x.first  << ' ' << x.second  << std::endl;
        }

        file.close();
}

int OpenInputFile(const std::string& filename, std::wifstream& file)
{
      file.open(filename);
      file.imbue(std::locale("ru_RU.UTF-8"));

      return file.is_open();
}

int OpenOutputFile(const std::string& filename, std::wofstream& file)
{
      file.open(filename);
      file.imbue(std::locale("ru_RU.UTF-8"));

      return file.is_open();
}

Полный листинг программы можно посмотреть на GitHub

Как я тестовое задание для школы UNIGINE решал

Введение

Постановка задачи

Решение