Скрытый текст
Пожалуйста не относитесь к этой статье как к утверждению в реализации той или иной сигнатуры для внутрянки хеш-мапы, это лишь мой взгляд на возможность использовать разные интересные фичи из 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 типов.
Здесь мне нечего добавить, идем дальше!
(для тех, кто уже понял, что здесь не так -> да, здесь действительно есть спорный момент, я прошу вас почитать комментарии, там все обсуждено и сделаны определенные выводы, большое спасибо, Дорогой читатель! (p.s я надеюсь сама идея использования if constexpr вам понятна, чтобы использовать это в своих проектах))
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.
ED: В C++17 можно использовать compressed_pair<> https://www.boost.org/doc/libs/1_86_0/libs/utility/doc/html/utility/utilities/compressed_pair.html как некоторую альтернативу, она основана на EBO (спасибо @zool_of_bears)
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);
}
};Конечно, здесь я уже разошелся, но я думаю было достаточно наглядно и правдоподобно, как по мне. Надеюсь вам понравилась статья, я очень старался над ее написанием.
Хочу оставить пожелание всем начинающим программистам: пишите код хорошо, пишите его с кайфом! :-)
Буду рад конструктивной дискуссии в комментариях, увидимся в следующей статье!
