Хеш-таблица и C++20

Скрытый текст

Пожалуйста не относитесь к этой статье как к утверждению в реализации той или иной сигнатуры для внутрянки хеш-мапы, это лишь мой взгляд на возможность использовать разные интересные фичи из C++20 для реализации популярной структуры данных.

Для нормального усвоения этой статьи необходимо понимать, как работает стандартная реализация хеш-мапы (язык в целом не важен, но мы же здесь все собрались только ради одного..).

Не будем тянуть, перейдем к реализации хеш-мапы с использованием «приколюх» из C++20!

1. Первое, что мне приглянулось — это концепты.

С их помощью мы будем валидировать типы.

Можем проверить, вызвана ли хеш-функция для ключа и поддерживает ли компаратор прозрачное сравнение:

#include <concepts>  template <typename Hash, typename Key> concept ValidHasher = requires(Hash h, Key k) {     { h(k) } -> std::convertible_to<std::size_t>; };  template <typename Equal, typename Key> concept TransparentEqual = requires(Equal eq, Key k, const char* s) {     { eq(k, k) } -> std::convertible_to<bool>;     { eq(k, s) } -> std::convertible_to<bool>; // Прозрачность };

В первом случае проверяем хеш-функцию с помощью concept.
Вот очень интересная статья по концептам от Яндекс практикума.

Во втором случае проверяем прозрачность компаратора
Вот статья про компараторы: Подводные камни компараторов в С++,

2. Обновлённый шаблон класса с requires

Для простоты понимания были вырезаны всякие разные сложные буквосочетания из опенсорсной реализации STL, что бы было понятно и читаемо:

template <     typename Key,     typename Value,     typename Hash = std::hash<Key>,     typename KeyEqual = std::equal_to<>,     typename Allocator = std::allocator<std::pair<const Key, Value>> > requires ValidHasher<Hash, Key> &&            TransparentEqual<KeyEqual, Key> class hash_map {     // остальное как и должно быть... };

Что же нам это дает?

• Если передать невалидный хеш или компаратор — ошибка будет на этапе компиляции.

• Нормальные сообщения об ошибках.

Круто-же да?

едем дальше, 3. if constexpr

Для оптимизации (да, приколюха из C++17, но все таки хочу добавить это)

template <typename K> void insert(K&& key, Value&& value) {     if constexpr (std::is_trivially_copyable_v<Value>) {         // Быстрая вставка для простых типов (int, double и т.д.)         buckets.emplace_back(std::forward<K>(key), std::forward<Value>(value));     } else {         // Медленная, но безопасная для сложных типов         buckets.emplace_back(std::piecewise_construct,                            std::forward_as_tuple(std::forward<K>(key)),                            std::forward_as_tuple(std::forward<Value>(value)));     } }

Этот простой пример демонстрирует работу с разной логикой для trivially-copyable типов.
Здесь мне нечего добавить, идем дальше!

4. std::remove_cvref_t — «Чистим» типы от мусора

Убираем const, volatile и ссылки (&, &&) из типа:

template <typename K> void insert(K&& key) {     using CleanKey = std::remove_cvref_t<K>; // Удалили const, &, volatile     static_assert(std::is_same_v<CleanKey, std::string>, "Должен быть std::string!");     // ... }

Тебе принесли const pizza&, но ты не можешь это скушать, распаковываем с помощью std::remove_cvref_tи ты можешь наслаждаться своей pizzaбезо всяких непонятных оберток.

5. Ranges — «Ленивые» диапазоны

Можно ознакомиться в статье про них!
Мы сможем работать с коллекциями (как vector, list) через «ленивые» операции.
Можем вставлять кучу элементов сразу из любого диапазона (даже из файла или бесконечного генератора!)

hash_map<std::string, int> map;  // Вставляем элементы из vector (обычный способ) std::vector<std::pair<std::string, int>> data = {{"a", 1}, {"b", 2}}; map.insert_range(data);  // Или даже из файла (если data — ленивый range) auto data_from_file = read_file_lines("data.txt") | std::views::transform(parse_line); map.insert_range(data_from_file);

Ну, а что, зачем нам бесконечные for'ы? Получаем вполне интересную русскую рулетку с сюрпризами в каждом заряде!

6. consteval — «Вычисли это на этапе компиляции!»

Если вкратце, то функция, помеченная как consteval, обязана выполняться на этапе компиляции.

Возникает вопрос — а зачем мне это в хеш-мапе??

Ответ: если есть хеш-функция, которая всегда возвращает одно и то же для одних и тех же ключей, её можно вычислить заранее.
Вспоминаю всякие коды Хаффмана и сразу понимаю, что вещь то интересная, примечательная.

struct MagicHasher {     consteval size_t operator()(const std::string& s) const {         return s.size() * 100; // вычисляется при компиляции     } };  hash_map<std::string, int, MagicHasher> map; map["hello"] = 42; // Хеш для "hello" вычислен при компиляции

Считай, что у тебя завтра контрольная по интегралам, а ты вместо заучивания табличных или их ручного выведения, просто выписываешь их себе в шпору и довольный идешь на экзамен надеясь не спалиться!)

7. std::span — «Безопасный указатель на массив»

std::span — это «обёртка» над массивом или vector, которая знает его размер и не даёт выйти за границы.
Нам это нужно, что бы безопасно передавать подмассивы данных из коллекций (да, например vector):

void add_from_span(std::span<const std::pair<Key, Value>> data) {     for (const auto& [key, value] : data) {         insert(key, value);     } }  std::vector<std::pair<std::string, int>> big_data(1000); // Добавим только первые 10 элементов map.add_from_span(std::span{big_data.data(), 10});

Выглядит сносно, правда!? Главное, что мы можем применить это на практике (и, конечно, не только в нашей хеш-мапе). С такой реализацией не нужно передавать пару указатель + размер с риском вылететь за границы.

Делаем код оптимизированнее и безопаснее с C++20, продолжаем!

8. Корутины — «Ленивая загрузка значений»

Вот познавательная статья про корутины.
Теперь можем «подгружать» данные по мере обращения к ним!

#include <coroutine>  template <typename Key, typename Value> struct LazyValue {     struct promise_type { /*...*/ }; // Опустим реализацию     std::coroutine_handle<promise_type> handle;      Value operator()() {         if (!handle.done()) handle.resume();         return handle.promise().value;     } };  hash_map<std::string, LazyValue<int>> lazy_map; lazy_map["some_data"] = load_data_from_internet();  // Загрузится только при вызове lazy_map["some_data"]()

Представь, что заказал проект на C++, а его начнут делать только когда ты им позвонишь перед дедлайном.. круто-же, нет??

9. [[no_unique_address]] — «Сжимаем пустые объекты»

Если есть пустые объекты (например, аллокатор без состояния), компилятор может их оптимизировать.
Так мы уменьшаем размер класса, если Hash или KeyEqual — пустые.

template <typename Key, typename Value, typename Hash, typename KeyEqual> class hash_map {     Hash hash_fn;     KeyEqual key_eq;     [[no_unique_address]] Allocator alloc; // Может исчезнуть, если пустой };

Это можно сравнить с утилизацией коробок из под пиццы для хранения в холодильнике, зачем они там нужны?

Например, стандартные хеш-функции (std::hash<T>) для примитивов (int, char*) часто не содержат состояния, а так же кастомные хешеры без паролей (например, возвращается key % 10)

Так же это могут быть компараторы, стандартные компараторы (std::equal_to<>, std::less<>) почти всегда пустые. Ну и так же пользовательские, которые не имеют состояния (например всякие сравниватели строчек)).

Наконец аллокаторы. В стандартном std::allocator все методы статические (он не содержит полей). И, конечно, пользовательские аллокаторы без состояния.

Объект можно проверить ну «пустоту» с помощью std::is_empty:

static_assert(std::is_empty_v<DummyHasher>, "хешер пустой"); static_assert(std::is_empty_v<CaseInsensitiveCompare>, "компаратор пустой"); static_assert(std::is_empty_v<std::allocator<int>>, "аллокатор пустой");

Важно понимать, что [[no_unique_address]] не сработает, если объект — часть наследника (это связано с выравниванием), или если где-то берется адрес
этого объекта &hash_fn,тогда компилятор будет считать адрес «важным» и у нас ничего не выйдет. Кстати это используют и в STL.

10. std::atomic_ref — «Потокобезопасность без мьютексов»

выкладка из cppreference.
будем поддерживать атомарные операции над объектами (если поддерживается платформой). Можно сделать lock-free версию для определённых операций:

#include <atomic>  template <typename Key, typename Value> class thread_safe_hash_map {     std::vector<std::pair<std::atomic<Key>, std::atomic<Value>>> data;          void insert(Key key, Value value) {         std::atomic_ref<Key>(key).store(key);     } };

Конечно, здесь я уже разошелся, но я думаю было достаточно наглядно и правдоподобно, как по мне. Надеюсь вам понравилась статья, я очень старался над ее написанием.
Хочу оставить пожелание всем начинающим программистам: пишите код хорошо, пишите его с кайфом! 🙂

Буду рад конструктивной дискуссии в комментариях, увидимся в следующей статье!