robin map
v1.3.0
Библиотека robin-map — это C++ реализация быстрой хеш-карты и хеш-набора с использованием открытой адресации и линейного хеширования Робин Гуда с удалением обратного сдвига для разрешения коллизий.
Предоставляются четыре класса: tsl::robin_map , tsl::robin_set , tsl::robin_pg_map и tsl::robin_pg_set . Первые два работают быстрее и используют политику роста степени двойки, последние два вместо этого используют политику простого роста и способны лучше справляться с плохой хеш-функцией. Используйте основную версию, если есть вероятность повторения шаблонов в младших битах вашего хеша (например, вы храните указатели с помощью идентификационной хэш-функции). Подробности см. в разделе GrowthPolicy.
Сравнительный анализ tsl::robin_map с другими хэш-картами можно найти здесь. На этой странице также даются некоторые советы о том, какую структуру хэш-таблицы следует использовать в вашем случае (полезно, если вы немного запутались в реализации нескольких хеш-таблиц в пространстве имен tsl ).
Библиотека только для заголовков, просто добавьте каталог включения в свой путь включения, и все готово. Если вы используете CMake, вы также можете использовать экспортированную цель tsl::robin_map из файла CMakeLists.txt.
Быстрая хеш-таблица, проверьте тест на наличие некоторых чисел.
Поддержка конструктивного ключа/значения, доступного только для перемещения, и нестандартного.
Поддержка гетерогенных поисков, позволяющих использовать find с типом, отличным от Key (например, если у вас есть карта, которая использует std::unique_ptr<foo> в качестве ключа, вы можете использовать foo* или std::uintptr_t в качестве ключевого параметра для find без создания std::unique_ptr<foo> , см. пример).
Нет необходимости резервировать какие-либо контрольные значения для ключей.
Возможность хранить хэш-значение вместе с сохраненным значением ключа для более быстрого повторного хеширования и поиска, если вычисление хеш-функций или функций, равных ключу, требует больших затрат. Обратите внимание, что хэш может быть сохранен, даже если его не запрашивают явно, когда библиотека может обнаружить, что он не окажет влияния на размер структуры в памяти из-за выравнивания. Подробности смотрите в параметре шаблона StoreHash.
Если хэш известен перед поиском, его можно передать в качестве параметра, чтобы ускорить поиск (см. параметр precalculated_hash в API).
Поддержка эффективной сериализации и десериализации (подробную информацию см. в примере и методах serialize/deserialize в API).
Библиотеку можно использовать с отключенными исключениями (с помощью опции -fno-exceptions в Clang и GCC, без опции /EH в MSVC или просто путем определения TSL_NO_EXCEPTIONS ). std::terminate используется вместо инструкции throw , когда исключения отключены.
API очень похож на std::unordered_map и std::unordered_set .
std::unordered_map tsl::robin_map пытается иметь интерфейс, похожий на std::unordered_map , но существуют некоторые различия.
Строгая гарантия исключения действует только Key std::is_nothrow_swappable<value_type>::value && std::is_nothrow_move_constructible<value_type>::value случае tsl::robin_set std::pair<Key, T> следующее value_type истинно std::pair<Key, T> для tsl::robin_map ). В противном случае, если во время замены или перемещения возникнет исключение, структура может оказаться в неопределенном состоянии. Обратите внимание, что согласно стандарту, value_type с конструктором копирования noException и конструктором перемещения без конструктора перемещения также удовлетворяет этому условию и, таким образом, гарантирует строгую гарантию исключений для структуры (подробности см. в API).
Тип Key , а также T в случае карты должны быть заменяемыми. Они также должны быть допускающими копирование и/или перемещение.
Недействительность итераторов работает по-другому: любая операция, изменяющая хеш-таблицу, делает их недействительными (подробности см. в API).
Ссылки и указатели на ключи или значения в карте становятся недействительными так же, как итераторы на эти ключи-значения.
Для итераторов tsl::robin_map operator*() и operator->() возвращают ссылку и указатель на const std::pair<Key, T> вместо std::pair<const Key, T> создавая значение T не подлежит изменению. Чтобы изменить значение, вам нужно вызвать метод value() итератора, чтобы получить изменяемую ссылку. Пример:
tsl::robin_map<int, int> map = {{1, 1}, {2, 1}, {3, 1}};for(auto it = map.begin(); it != map.end() ; ++it) {//it->секунда = 2; // Illegalit.value() = 2; // Хорошо} Нет поддержки некоторых методов, связанных с сегментами (например, bucket_size , bucket , ...).
Эти различия также применимы между std::unordered_set и tsl::robin_set .
Гарантии потокобезопасности такие же, как и у std::unordered_map/set (т.е. возможно иметь несколько читателей без записи).
Библиотека поддерживает несколько политик роста с помощью параметра шаблона GrowthPolicy . Библиотека предоставляет три политики, но при необходимости вы можете легко реализовать свои собственные.
tsl::rh::power_of_two_growth_policy. Политика по умолчанию, используемая tsl::robin_map/set . Эта политика сохраняет размер массива сегментов хеш-таблицы равным степени двойки. Это ограничение позволяет политике избежать использования медленной операции по модулю для сопоставления хеша с сегментом. Вместо hash % 2 n используется hash & (2 n - 1) (см. быстрый модуль). Быстро, но это может вызвать множество коллизий из-за плохой хеш-функции, поскольку модуль со степенью двойки в конечном итоге маскирует только самые значимые биты.
tsl::rh::prime_growth_policy. Политика по умолчанию, используемая tsl::robin_pg_map/set . Политика сохраняет размер массива сегментов хеш-таблицы простым числом. При сопоставлении хеша с сегментом использование простого числа по модулю приведет к лучшему распределению хеша по сегментам даже при плохой хеш-функции. Чтобы позволить компилятору оптимизировать операцию по модулю, политика использует таблицу поиска с постоянными простыми числами по модулю (подробности см. в API). Медленнее, чем tsl::rh::power_of_two_growth_policy , но более безопасно.
tsl::rh::mod_growth_policy. Политика увеличивает карту на настраиваемый коэффициент роста, передаваемый в параметре. Затем он просто использует оператор по модулю, чтобы сопоставить хеш с сегментом. Медленнее, но более гибко.
Чтобы реализовать собственную политику, вам необходимо реализовать следующий интерфейс.
struct custom_policy {// Вызывается при построении и перехешировании хеш-таблицы, min_bucket_count_in_out – это минимальное количество сегментов//, необходимое хеш-таблице. При необходимости политика может изменить его на большее количество сегментов // и хеш-таблица будет использовать это значение в качестве счетчика сегментов. Если запрашивается 0 сегментов, то значение// должно оставаться равным 0.explicit custom_policy(std::size_t& min_bucket_count_in_out); // Возвращаем сегмент [0, Bucket_count()), которому принадлежит хэш. // Если Bucket_count() равен 0, он всегда должен возвращать 0.std::size_t Bucket_for_hash(std::size_t hash) const noException; // Возвращаем количество сегментов, которые следует использовать при следующем ростеstd::size_t next_bucket_count() const; // Максимальное количество сегментов, поддерживаемое policystd::size_t max_bucket_count() const; // Сбрасываем политику роста, как если бы политика была создана со счетчиком сегментов, равным 0. // После очистки политика всегда должна возвращать 0 при вызове Bucket_for_hash().void Clear() noException;
}Чтобы использовать robin-map, просто добавьте каталог включения в свой путь включения. Это библиотека только для заголовков .
Если вы используете CMake, вы также можете использовать экспортированную цель tsl::robin_map из CMakeLists.txt с помощью target_link_libraries .
# Пример, где проект robin-map хранится в стороннем каталогеadd_subdirectory( Third-party/robin-map)target_link_libraries(your_target PRIVATE tsl::robin_map)
Если проект был установлен с помощью make install , вы также можете использовать find_package(tsl-robin-map REQUIRED) вместо add_subdirectory .
Библиотека доступна в vcpkg и conan. Он также присутствует в репозиториях пакетов Debian, Ubuntu и Fedora.
Код должен работать с любым компилятором, соответствующим стандарту C++17.
Для запуска тестов вам понадобится библиотека Boost Test и CMake.
git clone https://github.com/Tessil/robin-map.gitcd robin-map/tests сборка mkdir buildcd сделай .. cmake --build ../tsl_robin_map_tests
API можно найти здесь.
Все методы еще не документированы, но они повторяют поведение методов в std::unordered_map и std::unordered_set , если не указано иное.
#include <cstdint>#include <iostream>#include <string>#include <tsl/robin_map.h>#include <tsl/robin_set.h>int main() {
tsl::robin_map<std::string, int> map = {{"a", 1}, {"b", 2}};
карта["с"] = 3;
карта["д"] = 4;
map.insert({"e", 5});
map.erase("б"); for(auto it = map.begin(); it != map.end(); ++it) {//it->секунда += 2; // Недействительно.it.value() += 2;
} // {d, 6} {a, 3} {e, 7} {c, 5}for(const auto& key_value : map) {
std::cout << "{" << key_value.first << ", " << key_value. Second << "}" << std::endl;
}
if(map.find("a") != map.end()) {
std::cout << "Найдено "a"." << станд::эндл;
} const std::size_t precalculated_hash = std::hash<std::string>()("a");// Если мы уже знаем хеш заранее, мы можем передать его в качестве параметра для ускорения поиска.if( map.find("a", precalculated_hash) != map.end()) {
std::cout << "Найдено "a" с хешем " << precalculated_hash << "." << станд::эндл;
}
/* * Вычисление хеша и сравнение двух std::string может быть медленным. * Мы можем хранить хэш каждого std::string в хеш-карте, чтобы * ускорить вставку и поиск, установив для StoreHash значение true. */
tsl::robin_map<std::string, int, std::hash<std::string>,
std::equal_to<std::string>,
std::allocator<std::pair<std::string, int>>, true> map2;
карта2["а"] = 1;
карта2["б"] = 2; // {a, 1} {b, 2}for(const auto& key_value : map2) {
std::cout << "{" << key_value.first << ", " << key_value. Second << "}" << std::endl;
}
tsl::robin_set<int> set;
set.insert({1, 9, 0});
set.insert({2, -1, 9}); // {0} {1} {2} {9} {-1}for(const auto& key: set) {
std::cout << "{" << key << "}" << std::endl;
}
} Гетерогенные перегрузки позволяют использовать другие типы, кроме Key для операций поиска и стирания, если используемые типы хешируются и сопоставимы с Key .
Чтобы активировать гетерогенные перегрузки в tsl::robin_map/set , квалифицированный идентификатор KeyEqual::is_transparent должен быть действительным. Это работает так же, как и для std::map::find . Вы можете использовать std::equal_to<> или определить свой собственный объект функции.
И KeyEqual , и Hash должны иметь возможность работать с разными типами.
#include <functional>#include <iostream>#include <string>#include <tsl/robin_map.h>struct сотрудник {employee(int id, std::string name): m_id(id), m_name(std::move (имя)) {
} // Либо мы включаем компараторы в класс и используем `std::equal_to<>`...friend bool оператор==(const сотрудник& empl, int empl_id) {return empl.m_id == empl_id;
} Friend Booloperator==(int empl_id, const сотрудник& empl) {return empl_id == empl.m_id;
} друг bool оператор == (const сотрудник& empl1, const сотрудник& empl2) {return empl1.m_id == empl2.m_id;
}
интервал m_id;
std::string m_name;
};// ... или реализуем отдельный класс для сравнения сотрудников.struct равный_employee {using is_transparent = void; booloperator()(const сотрудник& empl, int empl_id) const {return empl.m_id == empl_id;
} Booloperator()(int empl_id, const сотрудник& empl) const {return empl_id == empl.m_id;
} bool оператор()(const сотрудник& empl1, const сотрудник& empl2) const {return empl1.m_id == empl2.m_id;
}
};struct hash_employee {
std::size_t оператор()(const сотрудник& empl) const {return std::hash<int>()(empl.m_id);
}
std::size_toperator()(int id) const {return std::hash<int>()(id);
}
};int main() {// Используйте std::equal_to<>, который автоматически выводит и пересылает параметры:tsl::robin_map<employee, int, hash_employee, std::equal_to<>> map;
map.insert({employee(1, "Джон Доу"), 2001});
map.insert({employee(2, "Джейн Доу"), 2002});
map.insert({employee(3, "John Smith"), 2003});// John Smith 2003auto it = map.find(3);if(it != map.end()) {
std::cout << it->first.m_name << " " << it->второй << std::endl;
}
map.erase(1);// Используйте собственный KeyEqual, который имеет член is_transparent typetsl::robin_map<employee, int, hash_employee,qual_employee> map2;
map2.insert({employee(4, "Джонни Доу"), 2004});// 2004std::cout << map2.at(4) << std::endl;
}Библиотека предоставляет эффективный способ сериализации и десериализации карты или набора, чтобы их можно было сохранить в файл или отправить по сети. Для этого пользователю требуется предоставить объект функции как для сериализации, так и для десериализации.
сериализатор структуры {// Должен поддерживать следующие типы для U: std::int16_t, std::uint32_t, // std::uint64_t, float и std::pair<Key, T>, если используется карта, или ключ для / / a set.template<typename U>voidoperator()(const U& value);
}; struct deserializer {// Должен поддерживать следующие типы для U: std::int16_t, std::uint32_t, // std::uint64_t, float и std::pair<Key, T>, если используется карта, или ключ для / / set.template<имя типа U>
U оператор()();
};Обратите внимание, что реализация оставляет двоичную совместимость (порядок байтов, двоичное представление с плавающей запятой, размер int,...) типов, которые она сериализует/десериализует, в руках предоставленных функциональных объектов, если совместимость требуется.
Более подробную информацию о методах serialize и deserialize можно найти в API.
#include <cassert>#include <cstdint>#include <fstream>#include <type_traits>#include <tsl/robin_map.h> сериализатор класса {public:serializer(const char* file_name) {
m_ostream.Exceptions(m_ostream.badbit | m_ostream.failbit);
m_ostream.open(имя_файла, std::ios::binary);
} template<class T, typename std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr>voidoperator()(const T& value) {
m_ostream.write(reinterpret_cast<const char*>(&value), sizeof(T));
} voidoperator()(const std::pair<std::int64_t, std::int64_t>& value) {
(*это)(value.first);
(*это)(значение.секунда);
}private:std::ofstream m_ostream;
};десериализатор класса {public:deserializer(const char* file_name) {
m_istream.Exceptions(m_istream.badbit | m_istream.failbit | m_istream.eofbit);
m_istream.open(имя_файла, std::ios::binary);
} шаблон<класс T>
Т-оператор()() {
Значение Т; десериализовать (значение); возвращаемое значение;
}
Private:template<class T, typename std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr>void deserialize(T& value) {
m_istream.read(reinterpret_cast<char*>(&value), sizeof(T));
} void deserialize(std::pair<std::int64_t, std::int64_t>& value) {deserialize(value.first);deserialize(value. Second);
}private:std::ifstream m_istream;
};int main() {const tsl::robin_map<std::int64_t, std::int64_t> map = {{1, -1}, {2, -2}, {3, -3}, {4, -4}};
const char* file_name = "robin_map.data";
{
серийный номер сериализатора (имя_файла);
карта.serialize(серийный);
}
{
десериализатор dserial(имя_файла);auto map_deserialized = tsl::robin_map<std::int64_t, std::int64_t>::deserialize(dserial); утверждать (карта == map_deserialized);
}
{
десериализатор dserial(имя_файла); /** * Если сериализованная и десериализованная карта совместима по хешу (см. условия в API), * установка аргумента в значение true ускоряет процесс десериализации, поскольку нам не нужно * пересчитывать хэш каждого ключа. Мы также знаем, сколько места нужно каждому ведру. */const bool hash_совместимый = true;auto map_deserialized =
tsl::robin_map<std::int64_t, std::int64_t>::deserialize(dserial, hash_совместимый); утверждать (карта == map_deserialized);
}
}Чтобы избежать шаблона, можно использовать библиотеку сериализации.
В следующем примере сериализация Boost используется с потоком сжатия Zlib Boost, чтобы уменьшить размер результирующего сериализованного файла. Для примера требуется C++20 из-за использования синтаксиса списка параметров шаблона в лямбда-выражениях, но его можно адаптировать к более ранним версиям.
#include <boost/archive/binary_iarchive.hpp>#include <boost/archive/binary_oarchive.hpp>#include <boost/iostreams/filter/zlib.hpp>#include <boost/iostreams/filtering_stream.hpp>#include <boost /serialization/split_free.hpp>#include <boost/serialization/utility.hpp>#include <cassert>#include <cstdint>#include <fstream>#include <tsl/robin_map.h>namespace boost { сериализация пространства имен {template<class Archive, class Key, class T> void сериализовать (Архив и ar, tsl::robin_map<Key, T>& карта, версия const без знака int) {split_free (ар, карта, версия);
}template<class Archive, class Key, class T>void save(Archive & ar, const tsl::robin_map<Key, T>& map, const unsigned int /*version*/) {auto serializer = [&ar](const авто& v) { ар & v; };
map.serialize(сериализатор);
}template<class Archive, class Key, class T>void load(Archive & ar, tsl::robin_map<Key, T>& map, const unsigned int /*version*/) {auto deserializer = [&ar]<typename U >() { U ты; ар и ты; вернуть тебя; };
карта = tsl::robin_map<Key, T>::deserialize(десериализатор);
}
}}int main() {
tsl::robin_map<std::int64_t, std::int64_t> map = {{1, -1}, {2, -2}, {3, -3}, {4, -4}};
const char* file_name = "robin_map.data";
{
std::ofstream ofs;
ofs.Exceptions(ofs.badbit | ofs.failbit);
ofs.open(имя_файла, std::ios::binary);
boost::iostreams::filtering_ostream fo;
fo.push(boost::iostreams::zlib_compressor());
fo.push(офс);
boost::archive::binary_oarchive oa(fo);
оа << карта;
}
{
std::ifstream если;
ifs.Exceptions(ifs.badbit | ifs.failbit | ifs.eofbit);
ifs.open(имя_файла, std::ios::binary);
boost::iostreams::filtering_istream фи;
fi.push(boost::iostreams::zlib_decompressor());
fi.push(если);
boost::archive::binary_iarchive ia(fi);
tsl::robin_map<std::int64_t, std::int64_t> map_deserialized;
ia >> map_deserialized; утверждать (карта == map_deserialized);
}
} Заслуживают внимания две потенциальные проблемы с производительностью, связанные с tsl::robin_map и tsl::robin_set :
Плохие хеши . Хэш-функции, которые создают множество коллизий, могут привести к следующему неожиданному поведению: когда количество коллизий превышает определенный порог, хеш-таблица автоматически расширяется, чтобы устранить проблему. Однако в ухудшенных случаях это расширение может не повлиять на количество коллизий, вызывая режим сбоя, когда линейная последовательность вставок приводит к экспоненциальному росту объема памяти.
Этот случай в основном наблюдался при использовании стратегии роста степени двойки по умолчанию с STL по умолчанию std::hash<T> для арифметических типов T , который часто является тождеством! См. пример № 39. Решение простое: используйте лучшую хеш-функцию и/или tsl::robin_pg_set / tsl::robin_pg_map .
Стирание элементов и низкие коэффициенты нагрузки . tsl::robin_map и tsl::robin_set отражают API карты/набора STL, который предоставляет метод iterator erase(iterator) , который удаляет элемент в определенной позиции, возвращая действительный итератор, указывающий на следующий элемент.
Создание этого нового объекта-итератора требует перехода к следующему непустому сегменту в таблице, что может оказаться дорогостоящей операцией, когда хеш-таблица имеет низкий коэффициент загрузки (т. е. когда capacity() намного больше, чем size() ).
Более того, метод erase() никогда не сжимает и не хэширует таблицу, поскольку это не разрешено спецификацией этой функции. Линейная последовательность случайных удалений без промежуточных вставок может затем привести к вырожденному случаю с квадратичными затратами времени выполнения.
В таких случаях возвращаемое значение итератора часто даже не требуется, поэтому затраты совершенно не нужны. Таким образом, оба tsl::robin_set и tsl::robin_map предоставляют альтернативный метод стирания void erase_fast(iterator) , который не возвращает итератор, чтобы избежать необходимости искать следующий элемент.
Код лицензируется по лицензии MIT, подробности см. в файле LICENSE.
