скачать хероз robin hood hashing - robin hood hashing Source Code скачать

robin hood hashing

С/С++

3.11.5

Скачать

➵ Robin_hood Неупорядоченная карта и набор

Примечание. К сожалению, у меня нет времени, чтобы продолжить разработку для этой HashMap. У меня есть достойный преемник, пожалуйста, перейдите к: ankerl::unordered_dense::{map, set}

Я потратил много времени на разработку и улучшение его robin_hood , и это хорошо работает для большинства вариантов использования. Я больше не буду делать никаких обновлений этого кода, если только они не являются PRS для критических исправлений ошибок.

robin_hood::unordered_map и robin_hood::unordered_set -это независимая платформа для замены для std::unordered_map / std::unordered_set , которая является одновременно быстрее и более эффективной памятью для действий в реальном мире.

Установка и использование

Прямое включение

Добавьте robin_hood.h в свой проект C ++.
Использовать robin_hood::unordered_map вместо std::unordered_map
Использовать robin_hood::unordered_set вместо std::unordered_set

Конан, менеджер пакетов C/C ++

Настройка вашего CMakeLists.txt (см. Документацию CONAN о том, как использовать MSBUILD, MESON и другие)

 project (myproject CXX)

add_executable ( ${PROJECT_NAME} main.cpp)

include ( ${CMAKE_BINARY_DIR} /conanbuildinfo.cmake) # Include Conan-generated file
conan_basic_setup(TARGETS) # Introduce Conan-generated targets

target_link_libraries ( ${PROJECT_NAME} CONAN_PKG::robin-hood-hashing)

Создайте conanfile.txt в вашем источнике Dir (не забудьте обновить версию)
```
 [requires]
robin-hood-hashing/3.11.5

[generators]
cmake
```
Установите и запустите Conan, затем создайте свой проект как всегда:
```
pip install conan
mkdir build
cd build
conan install ../ --build=missing
cmake ../
cmake --build .
```
Пакет robin-hood-hashing в Конане актуально актуально участниками Conan. Если версия устарела, пожалуйста, создайте проблему или запрос на подтяжку в репозитории conan-center-index .

Тесты

Пожалуйста, смотрите обширные тесты на тестах HashMaps. Короче говоря: robin_hood всегда является одним из самых быстрых карт и использует гораздо меньше памяти, чем std::unordered_map .

Выбор дизайна

Два макета памяти . Данные либо хранятся в плоском массиве, либо с узел. Доступ к unordered_flat_map чрезвычайно быстр из -за отсутствия нарушения, но ссылки на элементы не являются стабильными. Это также вызывает шипы распределения, когда карта изменяется, и потребуется много памяти для больших объектов. Карта на основе узлов имеет стабильные ссылки и указатели (не итераторы! Аналогично STD :: Unoromeded_MAP) и использует const Key в паре. Это немного медленнее из -за обороты. Выбор твой; Вы можете использовать robin_hood::unordered_flat_map или robin_hood::unordered_node_map напрямую. Если вы используете robin_hood::unordered_map он пытается выбрать макет, который кажется подходящим для ваших данных.
Пользовательский распределитель . Представление на основе узлов имеет пользовательский объемный распределитель, который пытается сделать мало распределений памяти. Вся выделенная память повторно используется, поэтому не будет никаких шипов распределения. Это тоже очень быстро.
Оптимизированный хэш . robin_hood::hash имеет пользовательские реализации для целочисленных типов и для std::string , которая очень быстрая и возвращается к std::hash для всего остального.
Зависит от хорошего хешина . Для действительно плохого хэша производительность не только разлагается, как в std::unordered_map , карта просто потерпит неудачу с std::overflow_error . На практике, используя стандартный robin_hood::hash , я никогда не видел, чтобы это происходило.