robin map
v1.3.0
Die Robin-Map-Bibliothek ist eine C++-Implementierung einer schnellen Hash-Map und eines Hash-Sets mit offener Adressierung und linearem Robin-Hood-Hashing mit Rückwärtsverschiebungslöschung zur Auflösung von Kollisionen.
Es werden vier Klassen bereitgestellt: tsl::robin_map , tsl::robin_set , tsl::robin_pg_map und tsl::robin_pg_set . Die ersten beiden sind schneller und nutzen eine Zweierpotenz-Wachstumspolitik, die letzten beiden nutzen stattdessen eine Prime-Wachstumspolitik und kommen besser mit einer schlechten Hash-Funktion zurecht. Verwenden Sie die Prime-Version, wenn die Möglichkeit besteht, dass sich Muster in den unteren Bits Ihres Hashs wiederholen (z. B. wenn Sie Zeiger mit einer Identitäts-Hash-Funktion speichern). Weitere Informationen finden Sie unter GrowthPolicy.
Ein Benchmark von tsl::robin_map im Vergleich zu anderen Hash-Maps finden Sie hier. Auf dieser Seite finden Sie auch einige Ratschläge dazu, welche Hash-Tabellenstruktur Sie für Ihren Anwendungsfall ausprobieren sollten (nützlich, wenn Sie sich mit den Implementierungen mehrerer Hash-Tabellen im tsl -Namespace etwas auskennen).
Nur-Header-Bibliothek, fügen Sie einfach das Include-Verzeichnis zu Ihrem Include-Pfad hinzu und schon kann es losgehen. Wenn Sie CMake verwenden, können Sie auch das exportierte Ziel tsl::robin_map aus CMakeLists.txt verwenden.
Schnelle Hash-Tabelle, überprüfen Sie den Benchmark auf einige Zahlen.
Unterstützung für nur verschiebbare und nicht standardmäßig konstruierbare Schlüssel/Werte.
Unterstützung für heterogene Suchvorgänge, die die Verwendung von find mit einem anderen Typ als Key ermöglichen (z. B. wenn Sie eine Karte haben, die std::unique_ptr<foo> als Schlüssel verwendet, können Sie „ foo* oder std::uintptr_t als Schlüsselparameter verwenden find ohne einen std::unique_ptr<foo> zu konstruieren, siehe Beispiel).
Es besteht keine Notwendigkeit, einen Sentinel-Wert aus den Schlüsseln zu reservieren.
Möglichkeit, den Hash-Wert zusammen mit dem gespeicherten Schlüsselwert zu speichern, um das erneute Aufbereiten und Suchen zu beschleunigen, wenn die Berechnung des Hashs oder der Schlüsselgleichheitsfunktionen teuer ist. Beachten Sie, dass Hash auch dann gespeichert werden kann, wenn nicht explizit danach gefragt wird, wenn die Bibliothek erkennen kann, dass er aufgrund der Ausrichtung keinen Einfluss auf die Größe der Struktur im Speicher hat. Weitere Informationen finden Sie im StoreHash-Vorlagenparameter.
Wenn der Hash vor einer Suche bekannt ist, kann er als Parameter übergeben werden, um die Suche zu beschleunigen (siehe Parameter precalculated_hash in der API).
Unterstützung für effiziente Serialisierung und Deserialisierung (Einzelheiten finden Sie im Beispiel und in den serialize/deserialize in der API).
Die Bibliothek kann mit deaktivierten Ausnahmen verwendet werden (über die Option -fno-exceptions auf Clang und GCC, ohne /EH -Option auf MSVC oder einfach durch Definition TSL_NO_EXCEPTIONS ). std::terminate wird als Ersatz für die throw -Anweisung verwendet, wenn Ausnahmen deaktiviert sind.
API, die std::unordered_map und std::unordered_set sehr ähnlich ist.
std::unordered_map tsl::robin_map versucht, eine ähnliche Schnittstelle wie std::unordered_map zu haben, es bestehen jedoch einige Unterschiede.
Die starke Ausnahmegarantie gilt nur , wenn die folgende Anweisung wahr ist std::is_nothrow_swappable<value_type>::value && std::is_nothrow_move_constructible<value_type>::value (wobei value_type Key für tsl::robin_set und std::pair<Key, T> ist std::pair<Key, T> für tsl::robin_map ). Andernfalls kann die Struktur in einem undefinierten Zustand enden, wenn während des Austauschs oder der Verschiebung eine Ausnahme ausgelöst wird. Beachten Sie, dass gemäß dem Standard auch ein value_type mit einem NoException-Kopierkonstruktor und keinem Verschiebungskonstruktor diese Bedingung erfüllt und somit die starke Ausnahmegarantie für die Struktur garantiert (siehe API für Details).
Der Typ Key und im Falle einer Karte auch T muss austauschbar sein. Sie müssen außerdem kopier- und/oder verschiebbar sein.
Die Iterator-Invalidierung verhält sich nicht auf die gleiche Weise. Jeder Vorgang, der die Hash-Tabelle ändert, macht sie ungültig (Einzelheiten finden Sie in der API).
Verweise und Zeiger auf Schlüssel oder Werte in der Karte werden auf die gleiche Weise ungültig gemacht wie Iteratoren auf diese Schlüssel-Werte.
Für Iteratoren von tsl::robin_map geben operator*() und operator->() eine Referenz und einen Zeiger auf const std::pair<Key, T> zurück, anstatt dass std::pair<const Key, T> den Wert ergibt T nicht veränderbar. Um den Wert zu ändern, müssen Sie die value() Methode des Iterators aufrufen, um eine veränderbare Referenz zu erhalten. Beispiel:
tsl::robin_map<int, int> map = {{1, 1}, {2, 1}, {3, 1}};for(auto it = map.begin(); it != map.end() ; ++it) {//it->second = 2; // Illegalit.value() = 2; // OK} Keine Unterstützung für einige Bucket-bezogene Methoden (wie bucket_size , bucket , ...).
Diese Unterschiede gelten auch zwischen std::unordered_set und tsl::robin_set .
Thread-Sicherheitsgarantien sind die gleichen wie bei std::unordered_map/set (dh es ist möglich, mehrere Leser ohne Schreiber zu haben).
Die Bibliothek unterstützt mehrere Wachstumsrichtlinien über den Vorlagenparameter GrowthPolicy . Die Bibliothek stellt drei Richtlinien zur Verfügung, Sie können jedoch bei Bedarf problemlos Ihre eigenen implementieren.
tsl::rh::power_of_two_growth_policy. Von tsl::robin_map/set verwendete Standardrichtlinie. Diese Richtlinie hält die Größe des Bucket-Arrays der Hash-Tabelle auf eine Zweierpotenz. Diese Einschränkung ermöglicht es der Richtlinie, die Verwendung der langsamen Modulo-Operation zum Zuordnen eines Hashs zu einem Bucket zu vermeiden. Statt hash % 2 n verwendet sie hash & (2 n - 1) (siehe schnelles Modulo). Schnell, aber dies kann zu vielen Kollisionen mit einer schlechten Hash-Funktion führen, da das Modulo mit einer Zweierpotenz am Ende nur die höchstwertigen Bits maskiert.
tsl::rh::prime_growth_policy. Von tsl::robin_pg_map/set verwendete Standardrichtlinie. Die Richtlinie hält die Größe des Bucket-Arrays der Hash-Tabelle auf einer Primzahl. Wenn Sie einen Hash einem Bucket zuordnen, führt die Verwendung einer Primzahl als Modulo zu einer besseren Verteilung des Hashs über die Buckets, selbst bei einer schlechten Hash-Funktion. Damit der Compiler die Modulo-Operation optimieren kann, verwendet die Richtlinie eine Nachschlagetabelle mit konstanten Primzahlen-Modulos (Einzelheiten siehe API). Langsamer als tsl::rh::power_of_two_growth_policy , aber sicherer.
tsl::rh::mod_growth_policy. Die Richtlinie vergrößert die Karte um einen anpassbaren Wachstumsfaktor, der im Parameter übergeben wird. Anschließend wird einfach der Modulo-Operator verwendet, um einen Hash einem Bucket zuzuordnen. Langsamer, aber flexibler.
Um Ihre eigene Richtlinie zu implementieren, müssen Sie die folgende Schnittstelle implementieren.
struct custom_policy {// Wird beim Erstellen und erneuten Aufbereiten der Hash-Tabelle aufgerufen. min_bucket_count_in_out ist der Mindest-Bucket//, den die Hash-Tabelle benötigt. Die Richtlinie kann sie bei Bedarf auf eine höhere Anzahl von Buckets ändern // und die Hash-Tabelle verwendet diesen Wert als Bucket-Anzahl. Wenn 0 Bucket abgefragt wird, muss der Wert// bei 0 bleiben.explicit custom_policy(std::size_t& min_bucket_count_in_out); // Den Bucket [0, Bucket_count()) zurückgeben, zu dem der Hash gehört. // Wenn Bucket_count() 0 ist, muss es immer 0 zurückgeben.std::size_t Bucket_for_hash(std::size_t Hash) const noexclusive; // Gibt die Anzahl der Buckets zurück, die beim nächsten Wachstum verwendet werden sollenstd::size_t next_bucket_count() const; // Maximale Anzahl von Buckets, die von der Richtlinie unterstützt werdenstd::size_t max_bucket_count() const; // Wachstumsrichtlinie zurücksetzen, als ob die Richtlinie mit einer Bucket-Anzahl von 0 erstellt worden wäre.// Nach einem Clear muss die Richtlinie immer 0 zurückgeben, wenn Bucket_for_hash() aufgerufen wird.void clear() noexclusive;
}Um Robin-Map zu verwenden, fügen Sie einfach das Include-Verzeichnis zu Ihrem Include-Pfad hinzu. Es handelt sich um eine reine Header- Bibliothek.
Wenn Sie CMake verwenden, können Sie auch das exportierte Ziel tsl::robin_map aus CMakeLists.txt mit target_link_libraries verwenden.
# Beispiel, bei dem das Robin-Map-Projekt in einem Verzeichnis eines Drittanbieters gespeichert istadd_subdirectory(third-party/robin-map)target_link_libraries(your_target PRIVATE tsl::robin_map)
Wenn das Projekt über make install installiert wurde, können Sie auch find_package(tsl-robin-map REQUIRED) anstelle von add_subdirectory verwenden.
Die Bibliothek ist in vcpkg und conan verfügbar. Es ist auch in den Paket-Repositorys von Debian, Ubuntu und Fedora vorhanden.
Der Code sollte mit jedem C++17-Standard-kompatiblen Compiler funktionieren.
Zum Ausführen der Tests benötigen Sie die Boost-Testbibliothek und CMake.
Git-Klon https://github.com/Tessil/robin-map.gitcd robin-map/tests mkdir buildcd build cmake .. cmake --build ../tsl_robin_map_tests
Die API finden Sie hier.
Alle Methoden sind noch nicht dokumentiert, aber sie replizieren das Verhalten derjenigen in std::unordered_map und std::unordered_set , sofern nicht anders angegeben.
#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}};
Karte["c"] = 3;
Karte["d"] = 4;
map.insert({"e", 5});
map.erase("b"); for(auto it = map.begin(); it != map.end(); ++it) {//it->second += 2; // Nicht gültig.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 << „Gefunden „a“.“ << std::endl;
} const std::size_t precalculated_hash = std::hash<std::string>()("a");// Wenn wir den Hash bereits vorher kennen, können wir ihn als Parameter übergeben, um Lookups zu beschleunigen.if( map.find("a", precalculated_hash) != map.end()) {
std::cout << „Gefunden „a“ mit Hash „ << precalculated_hash << „.“ << std::endl;
}
/* * Die Berechnung des Hashs und der Vergleich zweier std::string kann langsam sein. * Wir können den Hash jedes std::string in der Hash-Map speichern, um * die Einfügungen und Suchvorgänge zu beschleunigen, indem wir StoreHash auf true setzen. */
tsl::robin_map<std::string, int, std::hash<std::string>,
std::equal_to<std::string>,
std::allocator<std::pair<std::string, int>>, true> map2;
map2["a"] = 1;
map2["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> 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;
}
} Heterogene Überladungen ermöglichen die Verwendung anderer Typen als Key für Such- und Löschvorgänge, sofern die verwendeten Typen hashbar und mit Key vergleichbar sind.
Um die heterogenen Überladungen in tsl::robin_map/set zu aktivieren, muss die qualifizierte ID KeyEqual::is_transparent gültig sein. Es funktioniert genauso wie für std::map::find . Sie können entweder std::equal_to<> verwenden oder Ihr eigenes Funktionsobjekt definieren.
Sowohl KeyEqual als auch Hash müssen in der Lage sein, mit den verschiedenen Typen umzugehen.
#include <funktional>#include <iostream>#include <string>#include <tsl/robin_map.h>struct Employee {employee(int id, std::string name) : m_id(id), m_name(std::move (Name)) {
} // Entweder nehmen wir die Komparatoren in die Klasse auf und verwenden „std::equal_to<>“...friend bool Operator==(const Employee& empl, int empl_id) {return empl.m_id == empl_id;
} Freund Bool Operator==(int empl_id, const Employee& empl) {return empl_id == empl.m_id;
} Freund Bool Operator==(const Employee& Empl1, Const Employee& Empl2) {return empl1.m_id == empl2.m_id;
}
int m_id;
std::string m_name;
};// ... oder wir implementieren eine separate Klasse zum Vergleichen von Mitarbeitern.struct equal_employee {using is_transparent = void; bool Operator()(const Employee& empl, int empl_id) const {return empl.m_id == empl_id;
} bool Operator()(int empl_id, const Employee& empl) const {return empl_id == empl.m_id;
} bool Operator()(const Employee& Empl1, Const Employee& Empl2) const {return empl1.m_id == empl2.m_id;
}
};struct hash_employee {
std::size_t Operator()(const Employee& Empl) const {return std::hash<int>()(empl.m_id);
}
std::size_t Operator()(int id) const {return std::hash<int>()(id);
}
};int main() {// Verwenden Sie std::equal_to<>, wodurch die Parameter automatisch abgeleitet und weitergeleitet werden: stsl::robin_map<employee, int, hash_employee, std::equal_to<>> map;
map.insert({employee(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);// Benutzerdefiniertes KeyEqual verwenden, das ein is_transparent-Mitglied hat typetsl::robin_map<employee, int, hash_employee, equal_employee> map2;
map2.insert({employee(4, "Johnny Doe"), 2004});// 2004std::cout << map2.at(4) << std::endl;
}Die Bibliothek bietet eine effiziente Möglichkeit, eine Karte oder einen Satz zu serialisieren und zu deserialisieren, sodass er in einer Datei gespeichert oder über das Netzwerk gesendet werden kann. Dazu muss der Benutzer ein Funktionsobjekt sowohl für die Serialisierung als auch für die Deserialisierung bereitstellen.
struct serializer {// Muss die folgenden Typen für U unterstützen: std::int16_t, std::uint32_t, // std::uint64_t, float und std::pair<Key, T>, wenn eine Karte oder ein Schlüssel für / verwendet wird. / a set.template<typename U>void Operator()(const U& value);
}; struct deserializer {// Muss die folgenden Typen für U unterstützen: std::int16_t, std::uint32_t, // std::uint64_t, float und std::pair<Key, T>, wenn eine Karte oder ein Schlüssel für / verwendet wird. / a set.template<typename U>
U-Operator()();
};Beachten Sie, dass die Implementierung die binäre Kompatibilität (Endianness, Float-Binärdarstellung, Größe von int, ...) der Typen, die sie serialisiert/deserialisiert, den bereitgestellten Funktionsobjekten überlässt, wenn Kompatibilität erforderlich ist.
Weitere Details zu den serialize und deserialize finden Sie in der API.
#include <cassert>#include <cstdint>#include <fstream>#include <type_traits>#include <tsl/robin_map.h>class serializer {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>& value) {
(*this)(value.first);
(*this)(value.second);
}private:std::ofstream m_ostream;
};class Deserializer {public:deserializer(const char* file_name) {
m_istream.Exceptions(m_istream.badbit | m_istream.failbit | m_istream.eofbit);
m_istream.open(file_name, std::ios::binary);
} template<Klasse T>
T-Operator()() {
T-Wert;deserialisieren(Wert); Rückgabewert;
}
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";
{
Serializer serial(file_name);
map.serialize(serial);
}
{
deserializer dserial(file_name);auto map_deserialized = tsl::robin_map<std::int64_t, std::int64_t>::deserialize(dserial); behaupten(map == map_deserialized);
}
{
Deserialisierer dserial(file_name); /** * Wenn die serialisierte und deserialisierte Karte Hash-kompatibel sind (siehe Bedingungen in der API), * beschleunigt das Setzen des Arguments auf „true“ den Deserialisierungsprozess, da wir nicht * den Hash jedes Schlüssels neu berechnen müssen. Wir wissen auch, wie viel Platz jeder Eimer benötigt. */const bool hash_kompatible = true;auto map_deserialized =
tsl::robin_map<std::int64_t, std::int64_t>::deserialize(dserial, hash_kompatible); behaupten(map == map_deserialized);
}
}Es ist möglich, eine Serialisierungsbibliothek zu verwenden, um das Boilerplate zu vermeiden.
Im folgenden Beispiel wird die Boost-Serialisierung mit dem Boost-zlib-Komprimierungsstream verwendet, um die Größe der resultierenden serialisierten Datei zu reduzieren. Das Beispiel erfordert C++20 aufgrund der Verwendung der Template-Parameterlistensyntax in Lambdas, kann aber an weniger aktuelle Versionen angepasst werden.
#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 { namespace serialization {template<class Archive, class Key, class T> void serialize(Archive & ar, tsl::robin_map<Key, T>& map, const unsigned int version) {split_free(ar, Karte, Version);
}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 auto& v) { ar & v; };
map.serialize(serializer);
}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 & u; gib dich zurück; };
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* file_name = "robin_map.data";
{
std::ofstream ofs;
ofs.Exceptions(ofs.badbit | ofs.failbit);
ofs.open(file_name, std::ios::binary);
boost::iostreams::filtering_ostream fo;
fo.push(boost::iostreams::zlib_compressor());
fo.push(ofs);
boost::archive::binary_oarchive oa(fo);
oa << Karte;
}
{
std::ifstream ifs;
ifs.Exceptions(ifs.badbit | ifs.failbit | ifs.eofbit);
ifs.open(file_name, std::ios::binary);
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; behaupten(map == map_deserialized);
}
} Bemerkenswert sind zwei potenzielle Leistungsprobleme im Zusammenhang mit tsl::robin_map und tsl::robin_set :
Schlechte Hashes . Hash-Funktionen, die viele Kollisionen erzeugen, können zu folgendem überraschenden Verhalten führen: Wenn die Anzahl der Kollisionen einen bestimmten Schwellenwert überschreitet, wird die Hash-Tabelle automatisch erweitert, um das Problem zu beheben. In degenerierten Fällen hat diese Erweiterung jedoch möglicherweise keinen Einfluss auf die Kollisionszahl und führt zu einem Fehlermodus, bei dem eine lineare Einfügungsfolge zu einem exponentiellen Speicherwachstum führt.
Dieser Fall wurde hauptsächlich bei Verwendung der Standard-Potenz-von-Zwei-Wachstumsstrategie mit dem Standard-STL std::hash<T> für arithmetische Typen T beobachtet, bei denen es sich häufig um eine Identität handelt! Ein Beispiel finden Sie in Ausgabe Nr. 39. Die Lösung ist einfach: Verwenden Sie eine bessere Hash-Funktion und/oder tsl::robin_pg_set / tsl::robin_pg_map .
Elementlöschung und niedrige Lastfaktoren . tsl::robin_map und tsl::robin_set spiegeln die STL-Map/Set-API wider, die eine iterator erase(iterator) -Methode verfügbar macht, die ein Element an einer bestimmten Position entfernt und einen gültigen Iterator zurückgibt, der auf das nächste Element zeigt.
Um dieses neue Iteratorobjekt zu erstellen, muss zum nächsten nicht leeren Bucket in der Tabelle gewechselt werden. Dies kann ein teurer Vorgang sein, wenn die Hash-Tabelle einen niedrigen Auslastungsfaktor hat (z. B. wenn capacity() viel größer als size() ist).
Die erase() Methode verkleinert und hasht die Tabelle außerdem nie erneut, da dies durch die Spezifikation dieser Funktion nicht zulässig ist. Eine lineare Folge zufälliger Entfernungen ohne dazwischenliegende Einfügungen kann dann zu einem entarteten Fall mit quadratischen Laufzeitkosten führen.
In solchen Fällen wird oft nicht einmal ein Iterator-Rückgabewert benötigt, sodass die Kosten völlig unnötig sind. Sowohl tsl::robin_set als auch tsl::robin_map stellen daher eine alternative Löschmethode void erase_fast(iterator) bereit, die keinen Iterator zurückgibt, um zu vermeiden, dass das nächste Element gefunden werden muss.
Der Code ist unter der MIT-Lizenz lizenziert. Weitere Informationen finden Sie in der LICENSE-Datei.
