Библиотека frozen для C++: Полное руководство по compile-time контейнерам

Библиотека frozen — это header-only библиотека для C++17 и новее, предоставляющая контейнеры (map, set, string), которые полностью инициализируются на этапе компиляции (compile-time). Она позволяет создавать неизменяемые (immutable) структуры данных, которые не требуют динамического выделения памяти во время выполнения. Это идеальное решение для встраиваемых систем, игровых движков, высоконагруженных серверов и любого кода, где критична производительность и предсказуемость времени выполнения.

Основная идея frozen заключается в том, что вы определяете контейнер как constexpr или constinit, и вся работа по сортировке, хешированию и построению структуры данных происходит во время компиляции. В runtime вы получаете готовый, оптимизированный контейнер, который работает с минимальными накладными расходами. Например, frozen::map использует бинарный поиск по отсортированному массиву, а frozen::unordered_map — совершенное хеширование (perfect hashing), что гарантирует O(1) доступ без коллизий.

Для разработчиков на C++ это означает: отсутствие динамической памяти (нет new/delete), отсутствие исключений (noexcept), полная потокобезопасность (так как данные только для чтения) и возможность размещения контейнеров в flash-памяти микроконтроллеров. Библиотека активно используется в проектах Facebook (ныне Meta), в компиляторах и в ядрах операционных систем.

Установка

Библиотека frozen является header-only, поэтому установка сводится к копированию заголовочных файлов в ваш проект. Самый простой способ — использовать Conan или CMake FetchContent. Ниже приведены точные команды для различных менеджеров пакетов.

Установка через Conan (рекомендуется)

conan install frozen/1.1.1@ -r conancenter
# Затем добавьте в CMakeLists.txt:
# find_package(frozen REQUIRED)
# target_link_libraries(your_target frozen::frozen)

Установка через vcpkg

vcpkg install frozen
# После установки используйте:
# find_package(frozen CONFIG REQUIRED)
# target_link_libraries(your_target frozen::frozen)

Установка через CMake FetchContent (без менеджера пакетов)

include(FetchContent)
FetchContent_Declare(
  frozen
  GIT_REPOSITORY https://github.com/serge-sans-paille/frozen.git
  GIT_TAG v1.1.1
)
FetchContent_MakeAvailable(frozen)
target_link_libraries(your_target frozen::frozen)

Ручная установка (header-only)

git clone https://github.com/serge-sans-paille/frozen.git
# Скопируйте папку frozen/include/frozen в ваш проект
# Добавьте путь к include в компилятор:
# g++ -I/path/to/frozen/include your_file.cpp -std=c++17

Быстрый старт: минимальный рабочий пример

Создайте файл example.cpp со следующим содержимым:

#include <iostream>
#include <frozen/unordered_map.h>
#include <frozen/string.h>

int main() {
    // Создаем compile-time map с совершенным хешированием
    constexpr frozen::unordered_map<frozen::string, int, 3> fruit_calories = {
        {"apple", 95},
        {"banana", 105},
        {"orange", 62}
    };

    // Поиск в runtime — O(1), без коллизий
    std::cout << "Калорийность банана: " << fruit_calories.at("banana") << "\n";

    // Проверка наличия ключа
    if (auto it = fruit_calories.find("grape"); it != fruit_calories.end()) {
        std::cout << "Виноград найден: " << it->second << "\n";
    } else {
        std::cout << "Виноград не найден\n";
    }

    // Итерация по всем элементам
    for (auto& [fruit, calories] : fruit_calories) {
        std::cout << fruit.data() << ": " << calories << " ккал\n";
    }

    return 0;
}

Скомпилируйте и запустите:

g++ -std=c++17 -O2 example.cpp -o example
./example

Ожидаемый вывод:

Калорийность банана: 105
Виноград не найден
apple: 95 ккал
banana: 105 ккал
orange: 62 ккал

Основные методы, функции и классы

Библиотека frozen предоставляет несколько ключевых контейнеров. Все они объявлены в пространстве имен frozen и требуют указания размера на этапе компиляции (как шаблонный параметр). Рассмотрим 8 основных компонентов.

1. frozen::map (упорядоченный map)

Сигнатура:

template<class Key, class Value, std::size_t N>
struct map {
    constexpr map(std::initializer_list<std::pair<Key, Value>> init);
    constexpr const Value& at(const Key& key) const;
    constexpr const_iterator find(const Key& key) const;
    constexpr bool count(const Key& key) const;
    constexpr std::size_t size() const noexcept;
    // ... итераторы begin(), end()
};

Что делает: Создает отсортированный массив пар ключ-значение. Поиск выполняется бинарным поиском за O(log N). Все данные известны на этапе компиляции.

Пример:

#include <frozen/map.h>
#include <iostream>

int main() {
    constexpr frozen::map<int, const char*, 4> status_codes = {
        {200, "OK"},
        {404, "Not Found"},
        {500, "Internal Server Error"},
        {302, "Found"}
    };

    // Поиск по ключу
    std::cout << "Код 404: " << status_codes.at(404) << "\n"; // Not Found

    // Проверка существования
    if (status_codes.count(418)) {
        std::cout << "Код 418 существует\n";
    } else {
        std::cout << "Код 418 не найден\n";
    }

    // Итерация (в порядке сортировки ключей)
    for (auto& [code, msg] : status_codes) {
        std::cout << code << ": " << msg << "\n";
    }
    // Вывод: 200: OK, 302: Found, 404: Not Found, 500: Internal Server Error
    return 0;
}

2. frozen::unordered_map (хеш-таблица с совершенным хешированием)

Сигнатура:

template<class Key, class Value, std::size_t N>
struct unordered_map {
    constexpr unordered_map(std::initializer_list<std::pair<Key, Value>> init);
    constexpr const Value& at(const Key& key) const;
    constexpr const_iterator find(const Key& key) const;
    constexpr bool count(const Key& key) const;
    constexpr std::size_t size() const noexcept;
    // ... итераторы
};

Что делает: Использует совершенное хеширование (perfect hashing), гарантирующее O(1) поиск без коллизий. Хеш-функция вычисляется на этапе компиляции. Идеально для lookup-таблиц.

Пример:

#include <frozen/unordered_map.h>
#include <frozen/string.h>
#include <iostream>

int main() {
    constexpr frozen::unordered_map<frozen::string, int, 5> month_days = {
        {"jan", 31}, {"feb", 28}, {"mar", 31},
        {"apr", 30}, {"may", 31}
    };

    // Быстрый доступ O(1)
    std::cout << "Дней в марте: " << month_days.at("mar") << "\n";

    // Использование find
    auto it = month_days.find("jun");
    if (it == month_days.end()) {
        std::cout << "Июнь не найден\n";
    }
    return 0;
}

3. frozen::set (упорядоченное множество)

Сигнатура:

template<class Key, std::size_t N>
struct set {
    constexpr set(std::initializer_list<Key> init);
    constexpr const_iterator find(const Key& key) const;
    constexpr bool count(const Key& key) const;
    constexpr bool contains(const Key& key) const; // C++20
    constexpr std::size_t size() const noexcept;
};

Что делает: Отсортированный массив уникальных ключей. Поиск — бинарный O(log N). Полезен для проверки принадлежности к множеству.

Пример:

#include <frozen/set.h>
#include <iostream>

int main() {
    constexpr frozen::set<int, 6> primes = {2, 3, 5, 7, 11, 13};

    std::cout << "Проверка простых чисел:\n";
    for (int i = 1; i <= 15; ++i) {
        if (primes.count(i)) {
            std::cout << i << " — простое\n";
        }
    }
    return 0;
}

4. frozen::unordered_set (множество с совершенным хешированием)

Сигнатура:

template<class Key, std::size_t N>
struct unordered_set {
    constexpr unordered_set(std::initializer_list<Key> init);
    constexpr const_iterator find(const Key& key) const;
    constexpr bool count(const Key& key) const;
    constexpr std::size_t size() const noexcept;
};

Что делает: Аналог unordered_map, но хранит только ключи. Поиск O(1). Используется для быстрой проверки наличия элемента.

Пример:

#include <frozen/unordered_set.h>
#include <frozen/string.h>
#include <iostream>

int main() {
    constexpr frozen::unordered_set<frozen::string, 4> keywords = {
        "if", "else", "while", "for"
    };

    frozen::string test = "while";
    if (keywords.count(test)) {
        std::cout << test.data() << " — ключевое слово C++\n";
    }
    return 0;
}

5. frozen::string (compile-time строка)

Сигнатура:

template<std::size_t N>
struct string {
    constexpr string(const char (&str)[N + 1]); // из литерала
    constexpr const char* data() const noexcept;
    constexpr std::size_t size() const noexcept;
    constexpr char operator[](std::size_t i) const;
    constexpr bool operator==(const string& other) const;
    // ... сравнения, хеширование
};

Что делает: Обертка над C-строкой фиксированной длины. Позволяет использовать строковые литералы в compile-time контекстах. Поддерживает сравнение и хеширование.

Пример:

#include <frozen/string.h>
#include <iostream>

int main() {
    constexpr frozen::string<5> hello = "hello";
    constexpr frozen::string<5> world = "world";

    // Сравнение строк
    constexpr bool same = (hello == world);
    std::cout << "Строки равны: " << std::boolalpha << same << "\n";

    // Доступ по индексу
    std::cout << "Первый символ: " << hello[0] << "\n"; // 'h'

    // Получение C-строки
    std::cout << "Данные: " << hello.data() << "\n";
    return 0;
}

6. frozen::bitset (битовое множество фиксированного размера)

Сигнатура:

template<std::size_t N>
struct bitset {
    constexpr bitset() = default;
    constexpr bitset(std::initializer_list<std::size_t> bits);
    constexpr bool test(std::size_t pos) const;
    constexpr bitset& set(std::size_t pos);
    constexpr bitset& reset(std::size_t pos);
    constexpr std::size_t count() const noexcept;
    // ... операторы &, |, ^, ~
};

Что делает: Аналог std::bitset, но с возможностью инициализации через constexpr и с дополнительными удобствами. Хранит N бит в массиве целых чисел.

Пример:

#include <frozen/bitset.h>
#include <iostream>

int main() {
    constexpr frozen::bitset<8> flags = {1, 3, 5}; // биты 1, 3, 5 установлены

    std::cout << "Бит 3: " << flags.test(3) << "\n"; // true
    std::cout << "Бит 0: " << flags.test(0) << "\n";