unordered_dense
v4.5.0
Быстрый и плотный хэшмап и хешсет, основанный на удалении смены Robin-Hood назад для C ++ 17 и позже.
Классы ankerl::unordered_dense::map и ankerl::unordered_dense::set (почти) замены замены std::unordered_map и std::unordered_set . Хотя у них нет такими сильными гарантиями итератора / эталонной стабильности, они, как правило, намного быстрее.
Кроме того, есть ankerl::unordered_dense::segmented_map и ankerl::unordered_dense::segmented_set с более низким пиковым использованием памяти. и стабильный итератор/ссылки на вставку.
ankerl::unordered_dense::hashis_transparentstd::hashauto extract() && -> value_container_typeextract() отдельные элементы[[nodiscard]] auto values() const noexcept -> value_container_type const&auto replace(value_container_type&& container)ankerl::unordered_dense::bucket_type::standardankerl::unordered_dense::bucket_type::bigsegmented_map и segmented_set Выбранный дизайн имеет несколько преимуществ по сравнению с std::unordered_map :
std::vector Все данные смежны!absl::flat_hash_mapstd::allocators и полиморфные распределители. Есть ankerl::unordered_dense::pmr typedefs доступенstd::vector To boost::interprocess::vector или любой другой совместимый контейнер случайного доступа.std::vector .Там нет бесплатного обеда, так что есть несколько недостатков:
const Key в std::pair<Key, Value> Расположение установки по умолчанию /usr/local .
Клонировать хранилище и запустите эти команды в клонированной папке:
mkdir build && cd build
cmake ..
cmake --build . --target install Подумайте о настройке префикса установки, если вы не хотите устанавливать unordered_dense System, например, так:
mkdir build && cd build
cmake -DCMAKE_INSTALL_PREFIX:PATH= ${HOME} /unordered_dense_install ..
cmake --build . --target installЧтобы использовать установленную библиотеку, добавьте это в свой проект:
find_package (unordered_dense CONFIG REQUIRED)
target_link_libraries (your_project_name unordered_dense::unordered_dense) ankerl::unordered_dense поддерживает C ++ 20 модулей. Просто компилируйте src/ankerl.unordered_dense.cpp и используйте полученный модуль, например, так:
clang++ -std=c++20 -I include --precompile -x c++-module src/ankerl.unordered_dense.cpp
clang++ -std=c++20 -c ankerl.unordered_dense.pcm Чтобы использовать модуль с EG в module_test.cpp , используйте
import ankerl.unordered_dense;и компилировать, например
clang++ -std=c++20 -fprebuilt-module-path=. ankerl.unordered_dense.o module_test.cpp -o main Простой демонстрационный скрипт можно найти в test/modules .
ankerl::unordered_dense::hash - это быстрый и высокий качественный хэш, основанный на Wyhash. Карта/набор ankerl::unordered_dense отличается между хэшами высокого качества (хороший эффект лавины) и плохим качеством. Хэши с хорошим качеством содержит специальный маркер:
using is_avalanching = void ; Это случаи для специализаций bool , char , signed char , unsigned char , char8_t , char16_t , char32_t , wchar_t , short , unsigned short , int , unsigned int , long , long long , unsigned long , unsigned long long , T* , std::unique_ptr<T> std::shared_ptr<T> enum , std::basic_string<C> : и std::basic_string_view<C> .
Предполагается, что хэши, которые не содержат такого маркера, имеют плохое качество и получают дополнительный шаг микширования внутри реализации карты/набора.
Рассмотрим простой пользовательский тип ключа:
struct id {
uint64_t value{};
auto operator ==(id const & other) const -> bool {
return value == other. value ;
}
};Самая простая реализация хэша - это:
struct custom_hash_simple {
auto operator ()(id const & x) const noexcept -> uint64_t {
return x. value ;
}
};Это можно использовать, например, с
auto ids = ankerl::unordered_dense::set<id, custom_hash_simple>(); Поскольку custom_hash_simple не имеет using is_avalanching = void; Маркер считается плохим качеством, а дополнительное смешивание x.value автоматически предоставляется внутри набора.
Вернемся к примеру id , мы можем легко реализовать хэш более высокого качества:
struct custom_hash_avalanching {
using is_avalanching = void ;
auto operator ()(id const & x) const noexcept -> uint64_t {
return ankerl::unordered_dense::detail::wyhash::hash (x. value );
}
}; Мы знаем, что wyhash::hash имеет высокое качество, поэтому мы можем добавить, using is_avalanching = void; что делает карту/установку непосредственно использовать возвращенное значение.
ankerl::unordered_dense::hash Вместо создания нового класса вы также можете специализировать ankerl::unordered_dense::hash :
template <>
struct ankerl ::unordered_dense::hash<id> {
using is_avalanching = void ;
[[nodiscard]] auto operator ()(id const & x) const noexcept -> uint64_t {
return detail::wyhash::hash (x. value );
}
};is_transparent Эта карта/набор поддерживает гетерогенные перегрузки, как описано в P2363, расширяющих ассоциативные контейнеры с оставшимися гетерогенными перегрузками, которые предназначены для C ++ 26. Это имеет перегрузки для find , count , contains , equal_range (см. P0919r3), erase (см. P2077R2) и try_emplace , insert_or_assign , operator[] , at и insert и emplace для наборов (см. P2363R3).
Для того, чтобы гетерогенные перегрузки оказали влияние, как hasher , так и key_equal должны иметь набор атрибута is_transparent .
Вот пример реализации, которая используется с любыми типами строк, которые конвертируются для std::string_view (например, char const* и std::string ):
struct string_hash {
using is_transparent = void ; // enable heterogeneous overloads
using is_avalanching = void ; // mark class as high quality avalanching hash
[[nodiscard]] auto operator ()(std::string_view str) const noexcept -> uint64_t {
return ankerl::unordered_dense::hash<std::string_view>{}(str);
}
}; Чтобы использовать этот хэш, вам нужно указать его как тип, а также key_equal с is_transparent как std :: eval_to <>:
auto map = ankerl::unordered_dense::map<std::string, size_t , string_hash, std::equal_to<>>(); Для получения дополнительной информации см. Примеры в test/unit/transparent.cpp .
std::hash Когда доступна реализация для std::hash пользовательского типа, это автоматически используется и предполагается, что она имеет плохое качество (таким образом, используется std::hash , но выполняется дополнительный шаг микширования).
Когда тип имеет уникальное представление объекта (без прокладки, тривиально копируемое), можно просто хэшировать память объекта. Рассмотрим простой класс
struct point {
int x{};
int y{};
auto operator ==(point const & other) const -> bool {
return x == other. x && y == other. y ;
}
};Быстрый и высококачественный хэш можно легко предоставить так:
struct custom_hash_unique_object_representation {
using is_avalanching = void ;
[[nodiscard]] auto operator ()(point const & f) const noexcept -> uint64_t {
static_assert (std::has_unique_object_representations_v<point>);
return ankerl::unordered_dense::detail::wyhash::hash (&f, sizeof (f));
}
}; В дополнение к стандартному API std::unordered_map (см. Https://en.cppreference.com/w/cpp/container/unordered_map), у нас есть дополнительный API, который несколько похож на API узла, но использует факт, что мы используем случайный контейнер для случайного доступа:
auto extract() && -> value_container_type Извлекает внутренне используемый контейнер. *this опорожняется.
extract() отдельные элементы Аналогично erase() у меня есть API Call extract() . Он ведет себя точно так же, как erase , за исключением того, что возвращаемое значение - это перемещенный элемент, который удаляется из контейнера:
auto extract(const_iterator it) -> value_typeauto extract(Key const& key) -> std::optional<value_type>template <class K> auto extract(K&& key) -> std::optional<value_type> Обратите внимание, что API extract(key) возвращает std::optional<value_type> , который пуст, когда ключ не найден.
[[nodiscard]] auto values() const noexcept -> value_container_type const&Разоблачает базовый контейнер значений.
auto replace(value_container_type&& container)Отбрасывает внутренний удерживаемый контейнер и заменяет его на то, что прошло. Неоникальные элементы удаляются, и контейнер будет частично переупорядочен, когда будут обнаружены элементы, не являющиеся аникурными элементами.
unordered_dense принимает пользовательский выделений, но вы также можете указать пользовательский контейнер для этого аргумента шаблона. Таким образом, можно заменить внутреннюю используемую std::vector на EG std::deque или любой другой контейнер, например, boost::interprocess::vector . Это поддерживает причудливые указатели (например, offset_ptr), поэтому контейнер можно использовать с помощью, например, общей памятью, предоставленной boost::interprocess .
Карта/набор поддерживает два разных типа ведра. По умолчанию должно быть полезно практически для всех.
ankerl::unordered_dense::bucket_type::standardankerl::unordered_dense::bucket_type::bigsegmented_map и segmented_set ankerl::unordered_dense provides a custom container implementation that has lower memory requirements than the default std::vector . Память не является смежной, но она может распределять сегменты без необходимости перераспределять и перемещать все элементы. Таким образом, это приводит к
std::vector , потому что необходима дополнительная косметика. Вот сравнение с absl::flat_hash_map и ankerl::unordered_dense::map при вставке 10 миллионов записей 
Abseil является самым быстрым для этого простого вставки, занимая чуть более 0,8 секунды. Это пиковое использование памяти составляет около 430 МБ. Обратите внимание, как использование памяти снижается после последнего пика; Когда он опускается до ~ 290 МБ, он закончил перефразирование и может освободить ранее используемый блок памяти.
ankerl::unordered_dense::segmented_map не имеет этих пиков и вместо этого имеет плавное увеличение использования памяти. Обратите внимание, что в памяти все еще есть внезапные падения и увеличение, потому что необходимая структура данных индексации по -прежнему необходимо увеличить с фиксированным фактором. Но из -за хранения данных в отдельном контейнере мы можем сначала освободить старую структуру данных, а затем выделить новую, большую структуру индексации; Таким образом, у нас нет пиков.
Карта/набор имеет две структуры данных:
std::vector<value_type> , который содержит все данные. Карта/установленные итераторы - это просто std::vector<value_type>::iterator ! Всякий раз, когда добавляется элемент, он является emplace_back к вектору. Ключ хэшируется, а вход (ведро) добавляется в соответствующем месте в массиве ведра. В ведро есть эта структура:
struct Bucket {
uint32_t dist_and_fingerprint;
uint32_t value_idx;
};Каждое ведро хранит 3 вещи:
dist_and_fingerprint )dist_and_fingerprint )Эта структура специально разработана для стратегии разрешения столкновения Робин-Хэнд с удалением сменной смены.
Ключ хэшируется, и массив ведра обыскивается, если он имеет запись в этом месте с этим отпечатками пальца. При обнаружении сравнивается ключ в векторе данных, а когда равное возвращается значение.
Поскольку все данные хранятся в векторе, удаления немного сложнее:
value_idx перемещенного элемента. Это требует еще одного поиска. 2023-09-10 я быстро поиск на GitHub, чтобы увидеть, используется ли эта карта в любых популярных проектах с открытым исходным кодом. Вот некоторые из проектов, которые я нашел. Пожалуйста, пришлите мне записку, если хотите в этом списке!
