Привіт усім. Сьогодні поділюсь з вами одним цікавим методом або ж алгоритмом, який попався мені під час того, як Я вчився своєму Ремеслу. Цей метод відноситься до проблеми обчислення кількості входжень певних (або усіх) символів в рядку цих самих символів. Тобто, скільки разів кожна окрема буква алфавіту, попадається в цілому масиві цих букв. Давайте спочатку, для простоти, переглянемо задачу на обрахунок однієї букви з довільного масиву. І які методи ми тут можемо використати? Очевидним рішенням буде, звичайно, використання алгоритму лінійного пошуку без інваріанти, оскільки нам необхідно обчислити усі входження однієї букви в масиві, а не найпершого її примірника. Тобто:
  1. ми спочатку створюємо масив довільного вмісту;
  2. після цього визначаємо, кількість входжень якого саме символу нам необхідно обрахувати;
  3. описуємо цикл, в якому маємо індексну змінну в якості ітератора для масиву (точніше для його перебору) і, власне головне, змінну, яка буде містити в собі значення кількості входжень.
Програма, за поданим вище планом, може виглядати наступним чином:
#include <iostream> /* ввід/вивід */
#include <string.h> /* функція strlen */
using namespace std ; /* щоб не писати "std::" */

/* неповторна і єдина */
int main (int argc, char** argv)
{
    /* оголошуємо і ініціалізовуємо масив символів */
    const char* Array = "I love programming" ;
    
    /* оголошуємо ітератор і обрахункову змінну */
    unsigned int iter, /* ітератор */
                 cscount ; /* змінна, у якій буде міститись значення кількості */
                 
    /* змінна в якій міститься буква (її ASCII код) */
    /* кількість якої ми бажаємо обчислити */
    /* її можна зчитувати і за допомогою об'єкта cin або функції scanf */
    char cs = 'g' ;
                 
    /* основна магія тут */
    for (iter=0, cscount=0; /* ініціалізовуємо усі змінні в нульове значення */
         iter<strlen(Array); /* умова "охорони" циклу (не виходимо за межі масиву) */
         ++iter) /* з кожним кроком інкрементуємо значення ітератора */
    {
        /* перевіряємо, чи поточне значення масиву (код символу) 
        ** співпадає з бажаним */
        if (Array[iter]==cs)
        {
            /* якщо так - додаємо одиницю до обрахункової змінної */
            ++ cscount ;
        }
        /* якщо ні - нічого не робимо */
    }
    
    /* виводимо кількість на екран */
    cout << "Count of char '" << cs << "' in string \"" 
         << Array << "\" is: " << cscount << endl ;
    
    /* завершуємо виконання програми */
    return 0 ;
}
Після компілювання і виконання даної програми, ми можемо побачити на екрані наступне (в даному випадку вищенаведений код знаходиться у файлі "single_char_count.cxx", компілятором являється GCC g++, а вихідний виконуваний файл ми називаємо "file"): single_char_count

Обрахунок усіх символів

Тепер перейдемо до цікавішого методу, який можна використовується для обчислення усіх символів в масиві (замість масиву, Ви також можете використовувати об'єкт класу std::string). Він базується в наступному:
  1. виконуємо практично усі підготовлювані дії з попереднього прикладу;
  2. але в якості системи обрахунку кожної букви, ми будемо використовувати масив потужністю 256 значень (для усіх можливих ASCII символів), а в якості індексів даного масиву - значення кодів символів (символи в пам'яті зберігаються в якості чисел) з масиву.
Розглянемо програму, яка реалізовує даний метод.
#include <iostream> /* ввід/вивід */
#include <string.h> /* функція strlen */
using namespace std ; /* щоб не писати "std::" */

const unsigned int Alenght = 256 ;

/* неповторна і єдина */
int main (int argc, char** argv)
{
    /* оголошуємо і ініціалізовуємо масив символів */
    const char* Array = "I love programming" ;
    
    /* оголошуємо ітератор і обрахункову змінну */
    unsigned int iter; /* ітератор */
                 
    /* змінна-масив для зберігання значень кількостей */
    unsigned int Ccounts [Alenght] ;
    
    /* ініціалізовуємо усю пам'ять в значення нуля */
    memset (&Ccounts, 0, Alenght*sizeof(unsigned int)) ;
                 
    /* основна магія тут */
    for (iter=0; /* ініціалізовуємо ітератор в нульове значення */
         iter<strlen(Array); /* умова "охорони" циклу (не виходимо за межі масиву) */
         ++iter) /* з кожним кроком інкрементуємо значення ітератора */
    {
        /* збільшуємо значення елемента масиву Ccounts на одиницю 
        ** за значенням коду символу елемента масиву Array 
        ** в якості індексу масиву Ccounts */
        ++ Ccounts [ Array[iter] ] ;
    }
    
    /* виводимо кількість на екран */
    for (iter=0; iter<Alenght; ++iter)
    {
        /* перевіряємо, чи значення елементу не нульове 
        ** (ми ж не бажаємо бачити повідомлення про нульове входження
        **  символу, яких більшість з 256 значень) */
        if (Ccounts[iter]>0)
        {
            cout << "symbol '" << (char)iter << "' has " 
            << Ccounts[iter] << " occurences" << endl ;
        }
    }
    
    /* завершуємо виконання програми */
    return 0 ;
}
Компілюємо її своїм улюбленим компілятором (у мене це GCC), виконуємо її у терміналі (файл з кодом називається "all_char_count.cxx") і бачимо наступну картину: all_char_count Найпершим ми бачимо символ пробілу з кодом 32 (в шістнадцятковій 0x20), після нього будуть йти усі великі літери алфавіту (в нашому випадку це англійська літера 'I') і в подальшому усі символи малого регістру, які мають найбільші коди (в нашому випадку значення кодів знаходиться між 0x61 для 'a', і 0x76 для 'v' в шістнадцятковій системі числення).

Проблема

Проблема в даному методі полягає саме в кодуванні символів. А дане кодування символів, себто коди ASCII не задовільняють наші потреби в обрахуванні кількості символів Української абетки, хіба-що Ви використовуєте кодування KOI8-U. Моя ОС використовує кодування UTF-8, тому Я не можу використовувати стандартний тип "char", який вміщує один байт даних. Для обчислення символів при використанні кодування UTF-8 (взагалі-то UTF-8 це не система кодування символів, а лише представлення стандарту UNICODE, про що Я напишу пізніше) нам необхідно використовувати спеціальний тип wchar_t, який вміщує в Unix-подібних ОС 4 байти (необхідних для UTF-8), а у ОС сімейства Windows, яка використовує UTF-16 для таких цілей, 2 байти. Ще однією проблемою в даному методі, являється пам'ять. Для обрахунку символів ASCII потрібно всього 256 значень (потужність типу "char" - 1 байт = 28 значень), на що ми можемо закрити очі в даному випадку. Але ми вже не можемо ігнорувати кількість елементів для обрахунку усіх можливих значень з проміжку у 4 байти. Тобто, для того щоб обрахувати кількість символів з рядка UNICODE, нам знадобиться 232=4 294 967 296 елементів масиву, кожен з яких повинен мати 4 байти (це в межах даного методу).

Рішення

Вирішенням вищенаведених проблем буде використання типу "wchar_t" і такого чудового контейнера з бібліотеки STL, як "map". Даним контейнером бібліотеки STL, ми реалізовуємо ідею економії пам'яті, яка полягає у тому, що її виділення відбувається тільки за необхідності. Тобто віртуально, ми маємо в пам'яті усю множину елементів, але по-факту, у нас виділені тільки необхідні. В найгіршому випадку, великий текст тільки Українськими символами може потребувати 33 елементи для самих символів плюс з десяток елементів для символів пунктуації (і можливо десяток елементів для цифр). "map" - це асоціативний список. Кожен елемент даного списку містить два значення: first - це ключ до елемента і "second" - для самого значення елементу. Map являється шаблонним контейнером, отже обидва значення (ключ і його "асоціація") можуть мати довільний тип (число, рядок, буква, користувацький тип і т.д.). Вставка нових елементів в контейнер відбувається за константний час, оскільки він реалізований за допомогою зв'язаного списку (ітератори даного типу не підтримують операції "<" і ">"). Усі елементи об'єкта "map" зберігаються в сортованому порядку, що дозволяє швидко знаходити необхідні. Вищенаведена програма з використанням об'єкта "map" може виглядати наступним чином:
#include <iostream> /* ввід/вивід */
#include <string> /* wstring */
#include <map> /* ! */
using namespace std ; /* щоб не писати "std::" */

/* неповторна і єдина */
int main (int argc, char** argv)
{
    /* оголошуємо і ініціалізовуємо масив символів */
    //const wchar_t* Array = L"Я обожнюю програмування!" ;
    wstring Array = L"Я обожнюю програмування!" ;
    
    /* оголошуємо ітератор і обрахункову змінну */
    unsigned int iter; /* ітератор */
                 
    /* змінна-масив для зберігання значень кількостей */
    map<wchar_t, unsigned int> Ccounts ;
                 
    /* основна магія тут */
    for (iter=0; /* ініціалізовуємо ітератор в нульове значення */
         iter<Array.size(); /* умова "охорони" циклу (не виходимо за межі масиву) */
         ++iter) /* з кожним кроком інкрементуємо значення ітератора */
    {
        /* збільшуємо значення елемента масиву Ccounts на одиницю 
        ** за значенням коду символу елемента масиву Array 
        ** в якості індексу масиву Ccounts */
        ++ Ccounts [ Array[iter] ] ; 
        /* оператор "[]" автоматично додає в список елемент
        ** якщо такого ще не існує */
    }
    
    /* виводимо кількість на екран */
    
    /* спеціальний внутрішній тип ітераторів для map */
    map<wchar_t, unsigned int>::iterator jter ;
    
    /* цикл виведення результатів */
    for (jter=Ccounts.begin(); jter!=Ccounts.end(); ++jter)
    {
        cout << "symbol '" << (*jter).first << "' "  << " has "
        << (*jter).second << " occurences" << endl ;
    }
    
    /* завершуємо виконання програми */
    return 0 ;
}
Після виконання програми, ми можемо побачити наступне: map_all_char_count В даній програмі ми також використовуємо спеціальний клас wstring - це такий ж тип, як і string, але для використання разом з "wchar_t". На жаль, побачити які саме букві відповідає кількість неможливо, оскільки необхідно мати функції перетворення символів з UTF-16 у, зрозумілу терміналу, UTF-8, написання яких виходить за межі даної статті (Рядок "Я обожнюю програмування" автоматично перетворюється компілятором з кодування UTF-8 файлу коду у UTF-16 завдяки лідируючій букві "L" перед відкривання символу подвійних лапок, без якої змінна-об'єкт Array буде містити спотворені дані). Але ми можемо побачити, що символу пробіла (код 32 десяткове) відповідає два входження, знаку оклику (код 33 десяткове) - одне, далі йдуть коди букв в порядку зростання: для 'а' (код 1071 десяткове) одне входження, для 'б' (код 1072 десяткове) - два і т.д. В загальному, передостанній і останній методи використовують хеш-таблиці.