robin map
v1.3.0
La bibliothèque robin-map est une implémentation C++ d'une carte de hachage rapide et d'un ensemble de hachage utilisant l'adressage ouvert et le hachage robin des bois linéaire avec suppression par décalage vers l'arrière pour résoudre les collisions.
Quatre classes sont fournies : tsl::robin_map , tsl::robin_set , tsl::robin_pg_map et tsl::robin_pg_set . Les deux premiers sont plus rapides et utilisent une politique de croissance en puissance de deux, les deux derniers utilisent plutôt une politique de croissance principale et sont capables de mieux gérer une mauvaise fonction de hachage. Utilisez la version principale s'il existe un risque de répétition de modèles dans les bits inférieurs de votre hachage (par exemple, vous stockez des pointeurs avec une fonction de hachage d'identité). Voir GrowthPolicy pour plus de détails.
Un benchmark de tsl::robin_map par rapport à d'autres cartes de hachage peut être trouvé ici. Cette page donne également quelques conseils sur la structure de table de hachage que vous devriez essayer pour votre cas d'utilisation (utile si vous êtes un peu perdu avec les multiples implémentations de tables de hachage dans l'espace de noms tsl ).
Bibliothèque d'en-tête uniquement, ajoutez simplement le répertoire d'inclusion à votre chemin d'inclusion et vous êtes prêt à partir. Si vous utilisez CMake, vous pouvez également utiliser la cible exportée tsl::robin_map à partir du fichier CMakeLists.txt.
Table de hachage rapide, vérifiez le benchmark pour certains chiffres.
Prise en charge des clés/valeurs constructibles à déplacement uniquement et non par défaut.
Prise en charge des recherches hétérogènes permettant l'utilisation de find avec un type différent de Key (par exemple, si vous avez une carte qui utilise std::unique_ptr<foo> comme clé, vous pouvez utiliser un foo* ou un std::uintptr_t comme paramètre de clé pour find sans construire de std::unique_ptr<foo> , voir exemple).
Pas besoin de réserver une valeur sentinelle aux clés.
Possibilité de stocker la valeur de hachage à côté de la valeur-clé stockée pour un rehachage et une recherche plus rapides si le hachage ou les fonctions égales de clé sont coûteux à calculer. Notez que le hachage peut être stocké même s'il n'est pas demandé explicitement lorsque la bibliothèque peut détecter qu'il n'aura aucun impact sur la taille de la structure en mémoire en raison de l'alignement. Voir le paramètre de modèle StoreHash pour plus de détails.
Si le hachage est connu avant une recherche, il est possible de le passer en paramètre pour accélérer la recherche (voir paramètre precalculated_hash dans l'API).
Prise en charge d'une sérialisation et d'une désérialisation efficaces (voir l'exemple et les méthodes serialize/deserialize dans l'API pour plus de détails).
La bibliothèque peut être utilisée avec les exceptions désactivées (via l'option -fno-exceptions sur Clang et GCC, sans option /EH sur MSVC ou simplement en définissant TSL_NO_EXCEPTIONS ). std::terminate est utilisé en remplacement de l'instruction throw lorsque les exceptions sont désactivées.
API très similaire à std::unordered_map et std::unordered_set .
std::unordered_map tsl::robin_map essaie d'avoir une interface similaire à std::unordered_map , mais certaines différences existent.
La garantie d'exception forte n'est valable que si l'instruction suivante est vraie std::is_nothrow_swappable<value_type>::value && std::is_nothrow_move_constructible<value_type>::value (où value_type est Key pour tsl::robin_set et std::pair<Key, T> pour tsl::robin_map ). Sinon, si une exception est levée lors de l'échange ou du déplacement, la structure peut se retrouver dans un état indéfini. Notez que selon la norme, un value_type avec un constructeur de copie nosauf et aucun constructeur de déplacement satisfait également à cette condition et garantira ainsi une forte garantie d'exception pour la structure (voir API pour plus de détails).
Le type Key , ainsi que T en cas de map, doivent être échangeables. Ils doivent également pouvoir être copiés et/ou déplacés.
L'invalidation des itérateurs ne se comporte pas de la même manière, toute opération modifiant la table de hachage les invalide (voir API pour plus de détails).
Les références et pointeurs vers des clés ou valeurs dans la carte sont invalidés de la même manière que les itérateurs vers ces clés-valeurs.
Pour les itérateurs de tsl::robin_map , operator*() et operator->() renvoient une référence et un pointeur vers const std::pair<Key, T> au lieu de std::pair<const Key, T> créant la valeur T non modifiable. Pour modifier la valeur, vous devez appeler la méthode value() de l'itérateur pour obtenir une référence mutable. Exemple:
tsl::robin_map<int, int> map = {{1, 1}, {2, 1}, {3, 1}};for(auto it = map.begin(); it != map.end() ; ++it) {//it->seconde = 2; // Illégalit.value() = 2; // D'accord} Aucune prise en charge de certaines méthodes liées aux buckets (comme bucket_size , bucket , ...).
Ces différences s'appliquent également entre std::unordered_set et tsl::robin_set .
Les garanties de sécurité des threads sont les mêmes que celles std::unordered_map/set (c'est-à-dire qu'il est possible d'avoir plusieurs lecteurs sans écrivain).
La bibliothèque prend en charge plusieurs politiques de croissance via le paramètre de modèle GrowthPolicy . Trois politiques sont fournies par la bibliothèque mais vous pouvez facilement mettre en œuvre la vôtre si nécessaire.
tsl :: rh :: power_of_two_growth_policy. Politique par défaut utilisée par tsl::robin_map/set . Cette stratégie maintient la taille du tableau de compartiments de la table de hachage à une puissance de deux. Cette contrainte permet à la politique d'éviter l'utilisation de l'opération modulo lente pour mapper un hachage à un compartiment, au lieu du hash % 2 n , elle utilise hash & (2 n - 1) (voir modulo rapide). Rapide mais cela peut provoquer beaucoup de collisions avec une mauvaise fonction de hachage car le modulo avec une puissance de deux ne masque finalement que les bits les plus significatifs.
tsl :: rh :: prime_growth_policy. Politique par défaut utilisée par tsl::robin_pg_map/set . La politique maintient la taille du tableau de compartiments de la table de hachage à un nombre premier. Lors du mappage d'un hachage sur un compartiment, l'utilisation d'un nombre premier comme modulo entraînera une meilleure répartition du hachage entre les compartiments, même avec une fonction de hachage médiocre. Pour permettre au compilateur d'optimiser le fonctionnement modulo, la politique utilise une table de recherche avec des modulos à nombres premiers constants (voir API pour plus de détails). Plus lent que tsl::rh::power_of_two_growth_policy mais plus sécurisé.
tsl :: rh :: mod_growth_policy. La stratégie agrandit la carte selon un facteur de croissance personnalisable passé en paramètre. Il utilise ensuite simplement l'opérateur modulo pour mapper un hachage à un compartiment. Plus lent mais plus flexible.
Pour implémenter votre propre politique, vous devez implémenter l'interface suivante.
struct custom_policy {// Appelé lors de la construction et du rehachage de la table de hachage, min_bucket_count_in_out est le bucket minimum // dont la table de hachage a besoin. La stratégie peut la modifier en un nombre de compartiments plus élevé si nécessaire // et la table de hachage utilisera cette valeur comme nombre de compartiments. Si 0 bucket est demandé, alors la valeur // doit rester à 0.explicit custom_policy(std::size_t& min_bucket_count_in_out); // Renvoie le bucket [0, bucket_count()) auquel appartient le hachage. // Si bucket_count() vaut 0, il doit toujours renvoyer 0.std::size_t bucket_for_hash(std::size_t hash) const nosauf; // Renvoie le nombre de buckets qui doivent être utilisés lors du prochain Growthstd::size_t next_bucket_count() const; // Nombre maximum de buckets pris en charge par Policystd::size_t max_bucket_count() const ; // Réinitialise la politique de croissance comme si la politique avait été créée avec un nombre de compartiments de 0.// Après un effacement, la politique doit toujours renvoyer 0 lorsque bucket_for_hash() est appelé.void clear() nosauf;
}Pour utiliser robin-map, ajoutez simplement le répertoire include à votre chemin d'inclusion. Il s'agit d'une bibliothèque d'en-tête uniquement .
Si vous utilisez CMake, vous pouvez également utiliser la cible exportée tsl::robin_map à partir du CMakeLists.txt avec target_link_libraries .
# Exemple où le projet robin-map est stocké dans un répertoire tiersadd_subdirectory(third-party/robin-map)target_link_libraries(your_target PRIVATE tsl::robin_map)
Si le projet a été installé via make install , vous pouvez également utiliser find_package(tsl-robin-map REQUIRED) au lieu de add_subdirectory .
La bibliothèque est disponible en vcpkg et conan. Il est également présent dans les référentiels de packages Debian, Ubuntu et Fedora.
Le code doit fonctionner avec n’importe quel compilateur conforme à la norme C++17.
Pour exécuter les tests, vous aurez besoin de la bibliothèque Boost Test et de CMake.
git clone https://github.com/Tessil/robin-map.gitcd robin-map/tests mkdir buildcd construire cmfaire .. cmake --build ../tsl_robin_map_tests
L'API peut être trouvée ici.
Toutes les méthodes ne sont pas encore documentées, mais elles reproduisent le comportement de celles de std::unordered_map et std::unordered_set , sauf indication contraire.
#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}};
carte["c"] = 3;
carte["d"] = 4;
map.insert({"e", 5});
map.erase("b"); for(auto it = map.begin(); it != map.end(); ++it) {//it->second += 2; // Non valid.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 << "J'ai trouvé "a"." << std :: endl;
} const std::size_t precalculated_hash = std::hash<std::string>()("a");// Si on connaît déjà le hachage à l'avance, on peut le passer en paramètre pour accélérer les recherches.if( map.find("a", precalculated_hash) != map.end()) {
std::cout << ""a" trouvé avec le hachage " << precalculated_hash << "." << std :: endl;
}
/* * Le calcul du hachage et la comparaison de deux std::string peuvent être lents. * Nous pouvons stocker le hachage de chaque std::string dans la carte de hachage pour accélérer * les insertions et les recherches en définissant StoreHash sur 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;
carte2["a"] = 1;
carte2["b"] = 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> ensemble ;
set.insert({1, 9, 0});
set.insert({2, -1, 9}); // {0} {1} {2} {9} {-1}for(const auto& key : set) {
std::cout << "{" << clé << "}" << std::endl;
}
} Les surcharges hétérogènes permettent l'utilisation d'autres types que Key pour les opérations de recherche et d'effacement tant que les types utilisés sont hachables et comparables à Key .
Pour activer les surcharges hétérogènes dans tsl::robin_map/set , l'identifiant qualifié KeyEqual::is_transparent doit être valide. Cela fonctionne de la même manière que pour std::map::find . Vous pouvez soit utiliser std::equal_to<> , soit définir votre propre objet fonction.
KeyEqual et Hash devront être capables de gérer les différents types.
#include <fonctionnel>#include <iostream>#include <string>#include <tsl/robin_map.h>struct employe {employee(int id, std::string name) : m_id(id), m_name(std::move (nom)) {
} // Soit on inclut les comparateurs dans la classe et on utilise `std::equal_to<>`...friend bool Operator==(const employ& empl, int empl_id) {return empl.m_id == empl_id;
} ami bool Operator==(int empl_id, const employé& empl) {return empl_id == empl.m_id;
} ami bool Operator==(const employé& empl1, const employé& empl2) {return empl1.m_id == empl2.m_id;
}
int m_id;
std :: chaîne m_name ;
};// ... ou nous implémentons une classe distincte pour comparer les employés.struct equal_employee {using is_transparent = void; bool Operator()(const employé& empl, int empl_id) const {return empl.m_id == empl_id;
} bool Operator()(int empl_id, const employé& empl) const {return empl_id == empl.m_id;
} bool Operator()(const employé& empl1, const employé& empl2) const {return empl1.m_id == empl2.m_id;
}
};struct hash_employee {
std::size_t Operator()(const employé& empl) const {return std::hash<int>()(empl.m_id);
}
std::size_t Operator()(int id) const {return std::hash<int>()(id);
}
};int main() {// Utilisez std::equal_to<> qui déduira et transmettra automatiquement les paramètrestsl::robin_map<employee, int, hash_employee, std::equal_to<>> map;
map.insert({employé(1, "John Doe"), 2001});
map.insert({employee(2, "Jane Doe"), 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->second << std::endl;
}
map.erase(1);// Utiliser un KeyEqual personnalisé qui a un membre is_transparent typetsl::robin_map<employee, int, hash_employee, égal_employee> map2;
map2.insert({employee(4, "Johnny Doe"), 2004});// 2004std::cout << map2.at(4) << std::endl;
}La bibliothèque fournit un moyen efficace de sérialiser et de désérialiser une carte ou un ensemble afin qu'il puisse être enregistré dans un fichier ou envoyé via le réseau. Pour ce faire, l'utilisateur doit fournir un objet fonction pour la sérialisation et la désérialisation.
struct sérialiseur {// Doit prendre en charge les types suivants pour U : std::int16_t, std::uint32_t, // std::uint64_t, float et std::pair<Key, T> si une carte est utilisée ou Key pour / / un set.template<typename U>void Operator()(const U& value);
} ; struct deserializer {// Doit prendre en charge les types suivants pour U : std::int16_t, std::uint32_t, // std::uint64_t, float et std::pair<Key, T> si une carte est utilisée ou Key pour / / un set.template<typename U>
Opérateur U()();
} ;Notez que l'implémentation laisse la compatibilité binaire (endianisme, représentation binaire flottante, taille de int, ...) des types qu'elle sérialise/désérialise entre les mains des objets fonction fournis si la compatibilité est requise.
Plus de détails concernant les méthodes serialize et deserialize peuvent être trouvés dans l'API.
#include <cassert>#include <cstdint>#include <fstream>#include <type_traits>#include <tsl/robin_map.h>sérialiseur de classe {public:serializer(const char* file_name) {
m_ostream.exceptions(m_ostream.badbit | m_ostream.failbit);
m_ostream.open(file_name, std::ios::binary);
} template<class T, typename std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr>void Operator()(const T& value) {
m_ostream.write(reinterpret_cast<const char*>(&value), sizeof(T));
} void Operator()(const std::pair<std::int64_t, std::int64_t>& valeur) {
(*this)(value.first);
(*this)(valeur.seconde);
}private:std::ofstream m_ostream;
};désérialiseur de classe {public:deserializer(const char* nom_fichier) {
m_istream.exceptions(m_istream.badbit | m_istream.failbit | m_istream.eofbit);
m_istream.open(file_name, std::ios::binary);
} modèle<classe T>
Opérateur T()() {
Valeur T; désérialiser (valeur); valeur de retour ;
}
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* nom_fichier = "robin_map.data";
{
série du sérialiseur (nom_fichier);
map.serialize(série);
}
{
deserializer dserial(file_name);auto map_deserialized = tsl::robin_map<std::int64_t, std::int64_t>::deserialize(dserial); assert(map == map_deserialized);
}
{
désérialiseur dserial (nom_fichier); /** * Si les cartes sérialisées et désérialisées sont compatibles avec le hachage (voir conditions dans l'API), * définir l'argument sur true accélère le processus de désérialisation car nous n'avons pas * pour recalculer le hachage de chaque clé. Nous savons également de combien d’espace chaque seau a besoin. */const bool hash_compatible = true;auto map_deserialized =
tsl::robin_map<std::int64_t, std::int64_t>::deserialize(dserial, hash_compatible); assert(map == map_deserialized);
}
}Il est possible d'utiliser une bibliothèque de sérialisation pour éviter le passe-partout.
L'exemple suivant utilise Boost Serialization avec le flux de compression Boost zlib pour réduire la taille du fichier sérialisé résultant. L'exemple nécessite C++20 en raison de l'utilisation de la syntaxe de liste de paramètres de modèle dans lambdas, mais il peut être adapté à des versions moins récentes.
#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 /sérialisation/split_free.hpp>#include <boost/serialization/utility.hpp>#include <cassert>#include <cstdint>#include <fstream>#include <tsl/robin_map.h>namespace boost { sérialisation de l'espace de noms {template<class Archive, class Key, class T> void sérialiser (Archive & ar, tsl::robin_map<Key, T>& map, const version int non signée) {split_free(ar, carte, version);
}template<class Archive, class Key, class T>void save(Archive & ar, const tsl::robin_map<Key, T>& map, const unsigned int /*version*/) {sérialiseur automatique = [&ar](const auto& v) { ar & v; } ;
map.serialize(sérialiseur);
}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 u; ar & toi; reviens-toi; } ;
map = tsl::robin_map<Key, T>::deserialize(deserializer);
}
}}int main() {
tsl::robin_map<std::int64_t, std::int64_t> map = {{1, -1}, {2, -2}, {3, -3}, {4, -4}} ;
const char* nom_fichier = "robin_map.data";
{
std :: ofstream ofs ;
ofs.exceptions(ofs.badbit | ofs.failbit);
ofs.open (nom_fichier, std :: ios :: binaire);
boost::iostreams::filtering_ostream fo;
fo.push(boost::iostreams::zlib_compressor());
fo.push(ofs);
boost::archive::binary_oarchive oa(fo);
ou << carte ;
}
{
std :: ifstream si ;
ifs.exceptions(ifs.badbit | ifs.failbit | ifs.eofbit);
ifs.open (nom_fichier, std :: ios :: binaire);
boost::iostreams::filtering_istream fi;
fi.push(boost::iostreams::zlib_decompressor());
fi.push(ifs);
boost::archive::binary_iarchive ia(fi);
tsl::robin_map<std::int64_t, std::int64_t> map_deserialized;
ia >> map_deserialized; assert(map == map_deserialized);
}
} Il convient de noter deux pièges potentiels en termes de performances impliquant tsl::robin_map et tsl::robin_set :
Mauvais hachages . Les fonctions de hachage qui produisent de nombreuses collisions peuvent conduire au comportement surprenant suivant : lorsque le nombre de collisions dépasse un certain seuil, la table de hachage s'agrandit automatiquement pour résoudre le problème. Cependant, dans les cas dégénérés, cette expansion peut n'avoir aucun effet sur le nombre de collisions, provoquant un mode de défaillance dans lequel une séquence linéaire d'insertion conduit à une croissance exponentielle du stockage.
Ce cas a principalement été observé lors de l'utilisation de la stratégie de croissance puissance de deux par défaut avec le STL par défaut std::hash<T> pour les types arithmétiques T , qui est souvent une identité ! Voir le numéro 39 pour un exemple. La solution est simple : utilisez une meilleure fonction de hachage et/ou tsl::robin_pg_set / tsl::robin_pg_map .
Effacement des éléments et faibles facteurs de charge . tsl::robin_map et tsl::robin_set reflètent l'API STL map/set, qui expose une méthode iterator erase(iterator) qui supprime un élément à une certaine position, renvoyant un itérateur valide qui pointe vers l'élément suivant.
La construction de ce nouvel objet itérateur nécessite de passer au prochain compartiment non vide de la table, ce qui peut être une opération coûteuse lorsque la table de hachage a un faible facteur de charge (c'est-à-dire lorsque capacity() est beaucoup plus grande que size() ).
De plus, la méthode erase() ne réduit jamais et ne hache à nouveau la table car cela n'est pas autorisé par la spécification de cette fonction. Une séquence linéaire de suppressions aléatoires sans insertions intermédiaires peut alors conduire à un cas dégénéré avec un coût d’exécution quadratique.
Dans de tels cas, une valeur de retour d’itérateur n’est souvent même pas nécessaire, le coût est donc totalement inutile. tsl::robin_set et tsl::robin_map fournissent donc une méthode d'effacement alternative void erase_fast(iterator) qui ne renvoie pas d'itérateur pour éviter d'avoir à trouver l'élément suivant.
Le code est sous licence MIT, voir le fichier LICENSE pour plus de détails.
