unordered_dense
v4.5.0
Un hashmap et un hashset rapides et densément stockés basés sur la suppression de décalage vers l'arrière Robin-Hood pour C ++ 17 et plus tard.
Les classes ankerl::unordered_dense::map et ankerl::unordered_dense::set sont (presque) des remplacements listes de std::unordered_map et std::unordered_set . Bien qu'ils n'aient pas des garanties de stabilité itérateur / référence aussi fortes, elles sont généralement beaucoup plus rapides.
De plus, il y a ankerl::unordered_dense::segmented_map et ankerl::unordered_dense::segmented_set avec une utilisation de mémoire de pointe inférieure. et itérateur stable / références sur l'insert.
ankerl::unordered_dense::hashis_transparentstd::hashauto extract() && -> value_container_typeextract() éléments simples[[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 et segmented_set La conception choisie présente quelques avantages par rapport à std::unordered_map :
std::vector , toutes les données sont contiguës!absl::flat_hash_mapstd::allocators et les allocateurs polymorphes. Il y a ankerl::unordered_dense::pmr Typedefs disponiblestd::vector à boost::interprocess::vector ou tout autre conteneur compatible à accès aléatoire.std::vector .Il n'y a pas de déjeuner gratuit, il y a donc quelques inconvénients:
const Key dans std::pair<Key, Value> L'emplacement d'installation par défaut est /usr/local .
Clone le référentiel et exécutez ces commandes dans le dossier cloné:
mkdir build && cd build
cmake ..
cmake --build . --target install Envisagez de définir un préfixe d'installation si vous ne souhaitez pas installer un système unordered_dense large, comme ainsi:
mkdir build && cd build
cmake -DCMAKE_INSTALL_PREFIX:PATH= ${HOME} /unordered_dense_install ..
cmake --build . --target installPour utiliser la bibliothèque installée, ajoutez ceci à votre projet:
find_package (unordered_dense CONFIG REQUIRED)
target_link_libraries (your_project_name unordered_dense::unordered_dense) ankerl::unordered_dense prend en charge les modules C ++ 20. Compilez simplement src/ankerl.unordered_dense.cpp et utilisez le module résultant, par exemple:
clang++ -std=c++20 -I include --precompile -x c++-module src/ankerl.unordered_dense.cpp
clang++ -std=c++20 -c ankerl.unordered_dense.pcm Pour utiliser le module avec EG dans module_test.cpp , utilisez
import ankerl.unordered_dense;et compiler avec EG
clang++ -std=c++20 -fprebuilt-module-path=. ankerl.unordered_dense.o module_test.cpp -o main Un script de démonstration simple se trouve dans test/modules .
ankerl::unordered_dense::hash est un hachage rapide et de haute qualité, basé sur Wyhash. La carte / ensemble ankerl::unordered_dense différencie les hachages de haute qualité (bon effet d'avalanchage) et de mauvaise qualité. Les hachages de bonne qualité contiennent un marqueur spécial:
using is_avalanching = void ; Ce sont les cas pour les spécialisations bool , char , signed char , unsigned char , char8_t , char16_t , char32_t , wchar_t , short , unsigned short , int , unsigned long unsigned int , long , long long , non signé, long, unsigned long long , T* , std::unique_ptr<T> , std::shared_ptr<T> , enum , std::basic_string<C> std::basic_string_view<C> .
Les hachages qui ne contiennent pas un tel marqueur sont supposés être de mauvaise qualité et reçoivent une étape de mélange supplémentaire dans l'implémentation de la carte / ensemble.
Considérez un type de clé personnalisé simple:
struct id {
uint64_t value{};
auto operator ==(id const & other) const -> bool {
return value == other. value ;
}
};La mise en œuvre la plus simple d'un hachage est la suivante:
struct custom_hash_simple {
auto operator ()(id const & x) const noexcept -> uint64_t {
return x. value ;
}
};Cela peut être utilisé par exemple avec
auto ids = ankerl::unordered_dense::set<id, custom_hash_simple>(); Puisque custom_hash_simple n'a pas d' using is_avalanching = void; marqueur il est considéré comme de mauvaise qualité et un mélange supplémentaire de x.value est automatiquement fourni à l'intérieur de l'ensemble.
Retour à l'exemple id , nous pouvons facilement mettre en œuvre un hachage de meilleure qualité:
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 );
}
}; Nous savons que wyhash::hash est de haute qualité, nous pouvons donc ajouter using is_avalanching = void; ce qui fait que la carte / set utilise directement la valeur renvoyée.
ankerl::unordered_dense::hash Au lieu de créer une nouvelle classe, vous pouvez également spécialiser 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 Cette carte / ensemble prend en charge les surcharges hétérogènes comme décrit dans P2363 étendant les conteneurs associatifs avec les surcharges hétérogènes restantes qui sont ciblées pour C ++ 26. Cela a des surcharges pour find , count , contains , equal_range (voir p0919r3), erase (voir p2077r2) et try_emplace , insert_or_assign , operator[] , at et insert et emplace pour les ensembles (voir p2363r3).
Pour que les surcharges hétérogènes prennent l'affect, hasher et key_equal doivent avoir l'attribut is_transparent set.
Voici un exemple d'implémentation utilisable avec tous les types de chaînes convertibles en std::string_view (par exemple, char const* et 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);
}
}; Pour utiliser ce hachage, vous devrez le spécifier comme un type, et aussi un key_equal avec is_transparent comme std :: equal_to <>:
auto map = ankerl::unordered_dense::map<std::string, size_t , string_hash, std::equal_to<>>(); Pour plus d'informations, consultez les exemples de test/unit/transparent.cpp .
std::hash Lorsqu'une implémentation pour std::hash d'un type personnalisé est disponible, celle-ci est automatiquement utilisée et supposée être de mauvaise qualité (donc std::hash est utilisé, mais une étape de mélange supplémentaire est effectuée).
Lorsque le type a une représentation d'objet unique (pas de rembourrage, trivialement copyable), on peut simplement hacher la mémoire de l'objet. Considérez une classe simple
struct point {
int x{};
int y{};
auto operator ==(point const & other) const -> bool {
return x == other. x && y == other. y ;
}
};Un hachage rapide et de haute qualité peut être facilement fourni comme:
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));
}
}; En plus de l'API standard std::unordered_map (voir https://en.cppreference.com/w/cpp/container/unordered_map) Nous avons une API supplémentaire qui est quelque peu similaire à l'API du nœud, mais nous levons le fait que nous utilisons un conteneur d'accès aléatoire en interne:
auto extract() && -> value_container_type Extrait le conteneur utilisé en interne. *this est vidé.
extract() éléments simples Similaire à erase() j'ai un extract() . Il se comporte exactement de la même manière que erase , sauf que la valeur de retour est l'élément déplacé qui est supprimé du conteneur:
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> Notez que l'API extract(key) renvoie une std::optional<value_type> qui est vide lorsque la clé n'est pas trouvée.
[[nodiscard]] auto values() const noexcept -> value_container_type const&Expose le conteneur des valeurs sous-jacentes.
auto replace(value_container_type&& container)Jete le conteneur tenu en interne et le remplace par celui passé. Des éléments non uniques sont supprimés et le conteneur sera en partie réorganisé lorsque des éléments non uniques seront trouvés.
unordered_dense accepte un allocateur personnalisé, mais vous pouvez également spécifier un conteneur personnalisé pour cet argument de modèle. De cette façon, il est possible de remplacer le std::vector utilisé en interne avec par exemple std::deque ou tout autre conteneur comme boost::interprocess::vector . Cela prend en charge les pointeurs de fantaisie (par exemple OFFSET_PTR), de sorte que le conteneur peut être utilisé avec une mémoire partagée par EG fournie par boost::interprocess .
La carte / set prend en charge deux types de seaux différents. La valeur par défaut devrait être bonne pour à peu près tout le monde.
ankerl::unordered_dense::bucket_type::standardankerl::unordered_dense::bucket_type::bigsegmented_map et segmented_set ankerl::unordered_dense fournit une implémentation de conteneur personnalisée qui a des exigences de mémoire plus faibles que le std::vector par défaut. La mémoire n'est pas contigu, mais elle peut allouer des segments sans avoir à réaffecter et à déplacer tous les éléments. En résumé, cela conduit à
std::vector car une indirection supplémentaire est nécessaire. Voici une comparaison avec absl::flat_hash_map et The ankerl::unordered_dense::map lors de l'insertion de 10 millions d'entrées 
Abseil est le plus rapide pour ce test d'insertion simple, prenant un peu plus de 0,8 seconde. Son utilisation de mémoire maximale est d'environ 430 Mo. Notez comment l'utilisation de la mémoire diminue après le dernier pic; Lorsqu'il descend à ~ 290 Mo, il a terminé la rechange et pourrait libérer le bloc de mémoire précédemment utilisé.
ankerl::unordered_dense::segmented_map n'a pas ces pics et a plutôt une augmentation en douceur de l'utilisation de la mémoire. Remarque Il y a encore des chutes soudaines et des augmentations de mémoire car la structure des données d'indexation doit encore augmenter par un facteur fixe. Mais en raison de la maintenance des données dans un conteneur séparé, nous sommes en mesure de libérer d'abord l'ancienne structure de données, puis d'allouer une nouvelle structure d'indexation plus grande; Ainsi, nous n'avons pas de pics.
La carte / set a deux structures de données:
std::vector<value_type> qui contient toutes les données. Les itérateurs de carte / set ne sont que std::vector<value_type>::iterator ! Chaque fois qu'un élément est ajouté, il est emplace_back au vecteur. La clé est hachée et une entrée (seau) est ajoutée à l'emplacement correspondant dans le réseau de seau. Le seau a cette structure:
struct Bucket {
uint32_t dist_and_fingerprint;
uint32_t value_idx;
};Chaque seau stocke 3 choses:
dist_and_fingerprint )dist_and_fingerprint )Cette structure est particulièrement conçue pour la stratégie de résolution de collision Hachage de robin avec délétion de décalage vers l'arrière.
La clé est hachée et le tableau de godet est recherché s'il a une entrée à cet endroit avec cette empreinte digitale. Lorsqu'il est trouvé, la clé du vecteur de données est comparée et, lorsqu'elle est égale, la valeur est renvoyée.
Étant donné que toutes les données sont stockées dans un vecteur, les éliminations sont un peu plus compliquées:
value_idx de l'élément déplacé. Cela nécessite une autre recherche. Le 2023-09-10, j'ai fait une recherche rapide sur GitHub pour voir si cette carte est utilisée dans des projets open source populaires. Voici quelques-uns des projets que j'ai trouvés. Veuillez m'envoyer une note si vous voulez sur cette liste!
