robin map
v1.3.0
robin-map ライブラリは、オープン アドレッシングと、後方シフト削除によるリニア ロビン フード ハッシュを使用して衝突を解決する、高速ハッシュ マップとハッシュ セットの C++ 実装です。
tsl::robin_map 、 tsl::robin_set 、 tsl::robin_pg_map 、 tsl::robin_pg_setの 4 つのクラスが提供されています。最初の 2 つは高速で 2 のべき乗成長ポリシーを使用し、最後の 2 つは代わりにプライム成長ポリシーを使用し、貧弱なハッシュ関数にうまく対処できます。ハッシュの下位ビットでパターンが繰り返される可能性がある場合は、プライム バージョンを使用してください (たとえば、アイデンティティ ハッシュ関数を使用してポインターを保存している場合)。詳細については、「成長ポリシー」を参照してください。
他のハッシュ マップに対するtsl::robin_mapのベンチマークは、ここで見つけることができます。このページでは、自分のユースケースでどのハッシュ テーブル構造を試すべきかについてのアドバイスも提供します ( tsl名前空間での複数のハッシュ テーブルの実装について少し迷った場合に役立ちます)。
ヘッダーのみのライブラリ。インクルード ディレクトリをインクルード パスに追加するだけで準備完了です。 CMake を使用する場合は、CMakeLists.txt からエクスポートされたtsl::robin_mapターゲットを使用することもできます。
高速ハッシュ テーブル。ベンチマークでいくつかの数値を確認してください。
移動専用およびデフォルト以外の構築可能なキー/値のサポート。
異種ルックアップのサポートにより、 Keyとは異なる型でのfindの使用が可能になります (たとえば、キーとしてstd::unique_ptr<foo>使用するマップがある場合、キー パラメーターとしてfoo*またはstd::uintptr_tを使用できます)。 std::unique_ptr<foo>を構築せずにfind 。例を参照してください)。
キーからセンチネル値を予約する必要はありません。
ハッシュまたはキー等号関数の計算にコストがかかる場合、再ハッシュと検索を高速化するために、保存されたキー値と一緒にハッシュ値を保存する可能性。明示的に要求されなくても、アライメントによってメモリ内の構造体のサイズに影響が及ばないことをライブラリが検出できる場合には、ハッシュが格納される場合があることに注意してください。詳細については、StoreHash テンプレート パラメーターを参照してください。
検索前にハッシュがわかっている場合は、それをパラメータとして渡して検索を高速化できます (API のprecalculated_hashパラメータを参照)。
効率的なシリアル化と逆シリアル化のサポート (詳細については、例と API のserialize/deserializeメソッドを参照してください)。
このライブラリは、例外を無効にして使用できます (Clang および GCC では-fno-exceptionsオプションを使用するか、MSVC では/EHオプションを使用しないか、単にTSL_NO_EXCEPTIONS定義することによって)。 std::terminate例外が無効な場合にthrow命令の代わりに使用されます。
API はstd::unordered_mapおよびstd::unordered_setによく似ています。
std::unordered_mapとの違いtsl::robin_map std::unordered_mapと同様のインターフェースを持とうとしますが、いくつかの違いが存在します。
強力な例外保証は、次のステートメントが true である場合にのみ有効ですstd::is_nothrow_swappable<value_type>::value && std::is_nothrow_move_constructible<value_type>::value ( value_typeはtsl::robin_setおよびstd::pair<Key, T> Key ) std::pair<Key, T> tsl::robin_map )。そうしないと、スワップまたは移動中に例外がスローされた場合に、構造が未定義の状態になる可能性があります。標準に従って、noexc コピー コンストラクターと移動コンストラクターを持たないvalue_typeもこの条件を満たしているため、構造体の強力な例外保証が保証されることに注意してください (詳細については 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テンプレート パラメーターを通じて複数の成長ポリシーをサポートします。ライブラリによって 3 つのポリシーが提供されますが、必要に応じて独自のポリシーを簡単に実装できます。
tsl::rh::power_of_two_growth_policy。 tsl::robin_map/setによって使用されるデフォルトのポリシー。このポリシーは、ハッシュ テーブルのバケット配列のサイズを 2 の累乗に保ちます。この制約により、ポリシーはハッシュをバケットにマップするための低速モジュロ演算の使用を回避でき、 hash % 2 nの代わりにhash & (2 n - 1)を使用します (高速モジュロを参照)。高速ですが、2 の累乗のモジュロは最終的に最上位ビットのみをマスクするため、貧弱なハッシュ関数と多くの衝突が発生する可能性があります。
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_tbucket_for_hash(std::size_t hash) const noexc を返す必要があります。 // 次の Growthstd::size_t next_bucket_count() const; で使用するバケットの数を返します。 // ポリシーでサポートされるバケットの最大数std::size_t max_bucket_count() const; // ポリシーがバケット数 0 で作成されたかのように、成長ポリシーをリセットします。// クリア後、bucket_for_hash() が呼び出された場合、ポリシーは常に 0 を返す必要があります。
}robin-map を使用するには、インクルード ディレクトリをインクルード パスに追加するだけです。ヘッダーのみのライブラリです。
CMake を使用する場合は、 CMakeLists.txt からエクスポートされたtsl::robin_mapターゲットをtarget_link_librariesとともに使用することもできます。
# robin-map プロジェクトがサードパーティのディレクトリに保存されている例add_subdirectory(third-party/robin-map)target_link_libraries(your_target PRIVATE tsl::robin_map)
プロジェクトがmake installによってインストールされている場合は、 add_subdirectoryの代わりにfind_package(tsl-robin-map REQUIRED)を使用することもできます。
このライブラリは vcpkg と conan で利用できます。 Debian、Ubuntu、Fedora のパッケージ リポジトリにも存在します。
コードは、C++17 標準に準拠したコンパイラで動作する必要があります。
テストを実行するには、Boost Test ライブラリと CMake が必要です。
git clone https://github.com/Tessil/robin-map.gitcd robin-map/tests mkdir ビルドcd ビルド cmake .. 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> マップ = {{"a", 1}, {"b", 2}};
マップ["c"] = 3;
マップ["d"] = 4;
マップ.挿入({"e", 5});
マップ.消去("b"); for(auto it = map.begin(); it != map.end(); ++it) {//it->second += 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」が見つかりました。" << std::endl;
} const std::size_t precalculated_hash = std::hash<std::string>()("a");// 事前にハッシュがわかっている場合は、それをパラメータに渡して lookups を高速化できます。if( map.find("a", precalculated_hash) != map.end()) {
std::cout << "ハッシュ "< precalculated_hash << " を持つ "a" が見つかりました。" << std::endl;
}
/* * ハッシュの計算と 2 つの 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> マップ 2;
マップ2["a"] = 1;
マップ2["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.insert({1, 9, 0});
set.insert({2, -1, 9}); // {0} {1} {2} {9} {-1}for(const auto& key : set) {
std::cout << "{" << キー << "}" << std::endl;
}
}異種オーバーロードでは、使用される型がハッシュ可能でKeyと同等である限り、ルックアップおよび消去操作にKey以外の型を使用できます。
tsl::robin_map/setで異種オーバーロードをアクティブにするには、修飾 ID KeyEqual::is_transparent有効である必要があります。 std::map::findと同じように機能します。 std::equal_to<>を使用することも、独自の関数オブジェクトを定義することもできます。
KeyEqualとHash両方とも、さまざまなタイプを処理できる必要があります。
#include <function>#include <iostream>#include <string>#include <tsl/robin_map.h>structemployee {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;
} 友人 bool 演算子 ==(int empl_id, const 従業員& empl) {return empl_id == empl.m_id;
} 友人 bool 演算子 ==(const 従業員& empl1, const 従業員& empl2) {return empl1.m_id == empl2.m_id;
}
int m_id;
std::string m_name;
};// ... または、employees.struct equal_employee {using is_transparent = void; を比較するための別のクラスを実装します。 bool 演算子()(const 従業員& empl, int empl_id) const {return empl.m_id == empl_id;
bool 演算子()(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_t 演算子()(int id) const {return std::hash<int>()(id);
}
};int main() {// std::equal_to<> を使用すると、パラメータstsl::robin_map<employee, int, hash_employee, std::equal_to<>> マップが自動的に推測されて転送されます。
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->first.m_name << std::endl;
}
map.erase(1);// is_transparent メンバーを持つカスタム KeyEqual を使用します。 typetsl::robin_map<employee, int, hash_employee, equal_employee> map2;
map2.insert({employee(4, "Johnny Doe"), 2004});// 2004std::cout << map2.at(4) << std::endl;
}このライブラリは、マップまたはセットをシリアル化および逆シリアル化し、ファイルに保存したり、ネットワーク経由で送信したりするための効率的な方法を提供します。これを行うには、ユーザーはシリアル化と逆シリアル化の両方のための関数オブジェクトを提供する必要があります。
struct Serializer {// U の次の型をサポートする必要があります: std::int16_t、std::uint32_t、// std::uint64_t、float、マップが使用されている場合は std::pair<Key, T>、/ の場合は Key / 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> (マップが使用されている場合)、または Key for / / a set.template<typename 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));
void 演算子()(const std::pair<std::int64_t, std::int64_t>& 値) {
(*this)(value.first);
(*この)(値.秒);
}プライベート: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>
T 演算子()() {
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);
}プライベート:std::ifstream m_istream;
};int main() {const tsl::robin_map<std::int64_t, std::int64_t> マップ = {{1, -1}, {2, -2}, {3, -3}, {4, -4}};
const char* ファイル名 = "robin_map.data";
{
シリアライザーシリアル(ファイル名);
マップ.シリアル化(シリアル);
}
{
deserializer dserial(file_name);auto map_deserialized = tsl::robin_map<std::int64_t, std::int64_t>::deserialize(dserial); アサート(マップ == マップデシリアライズ);
}
{
デシリアライザー dserial(file_name); /** * シリアル化されたマップと逆シリアル化されたマップがハッシュ互換性がある場合 (API の条件を参照)、 * 引数を true に設定すると、 * 各キーのハッシュを再計算する必要がなくなるため、逆シリアル化プロセスが高速化されます。また、各バケットに必要なスペースの量もわかります。 */const bool hash_compatibility = true;automap_deserialized =
tsl::robin_map<std::int64_t, std::int64_t>::deserialize(dserial, hash_compatibility); アサート(マップ == マップデシリアライズ);
}
}シリアル化ライブラリを使用してボイラープレートを回避することができます。
次の例では、Boost zlib 圧縮ストリームと Boost Serialization を使用して、生成されるシリアル化ファイルのサイズを削減します。この例では、ラムダでテンプレート パラメーター リスト構文を使用するため、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 { namespace シリアル化 {template<class Archive, class Key, class T> void Serialize(アーカイブ & ar, tsl::robin_map<Key, T>& マップ, const unsigned int バージョン) {split_free(ar, マップ, バージョン);
}template<class Archive, class Key, class T>void save(Archive & ar, const tsl::robin_map<Key, T>&map, const unsigned int /*version*/) {autoserializer = [&ar](const auto&v){ar&v; };
マップ.シリアライズ(シリアライザー);
}template<class Archive, class Key, class T>voidload(Archive & ar, tsl::robin_map<Key, T>&map, const unsigned int /*version*/) {auto deserializer = [&ar]<typename U >() { うう;アー＆ユー;あなたを返してください。 };
map = tsl::robin_map<Key, T>::deserialize(デシリアライザー);
}
}}int main() {
tsl::robin_map<std::int64_t, std::int64_t> マップ = {{1, -1}, {2, -2}, {3, -3}, {4, -4}};
const char* ファイル名 = "robin_map.data";
{
std::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(ofs);
boost::archive::binary_oarchive oa(fo);
oa << マップ;
}
{
std::ifstream ifs;
ifs.Exceptions(ifs.badbit | ifs.failbit | ifs.eofbit);
ifs.open(ファイル名, 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 >> マップデシリアライズ; アサート(マップ == マップデシリアライズ);
}
}tsl::robin_mapとtsl::robin_setに関連する 2 つの潜在的なパフォーマンスの落とし穴は注目に値します。
不正なハッシュ。多くの衝突を生成するハッシュ関数は、次のような驚くべき動作を引き起こす可能性があります。衝突の数が特定のしきい値を超えると、問題を解決するためにハッシュ テーブルが自動的に拡張されます。ただし、縮退の場合、この拡張は衝突数に影響を及ぼさない可能性があり、線形挿入シーケンスによってストレージが指数関数的に増加する障害モードが発生します。
このケースは主に、算術型Tに対してデフォルトの STL std::hash<T>使用してデフォルトの 2 のべき乗成長戦略を使用するときに観察されます。これは多くの場合恒等式です。例については、問題 #39 を参照してください。解決策は簡単です。より優れたハッシュ関数やtsl::robin_pg_set / tsl::robin_pg_mapを使用します。
要素消去と低負荷率。 tsl::robin_mapとtsl::robin_set STL マップ/セット API をミラーリングしており、特定の位置にある要素を削除し、次の要素を指す有効なイテレータを返すiterator erase(iterator)メソッドを公開します。
この新しいイテレータ オブジェクトを構築するには、テーブル内の次の空ではないバケットに移動する必要があります。これは、ハッシュ テーブルの負荷率が低い場合 (つまり、 capacity()がsize()よりもはるかに大きい場合)、コストのかかる操作になる可能性があります。
さらに、 erase()メソッドは、この関数の仕様で許可されていないため、テーブルを縮小したり再ハッシュしたりすることはありません。中間挿入のないランダムな削除の線形シーケンスは、二次的な実行時間コストを伴う退化ケースにつながる可能性があります。
このような場合、イテレータの戻り値はほとんど必要ないため、コストはまったく不要です。したがって、 tsl::robin_setとtsl::robin_map両方とも、次の要素を見つける必要を避けるために反復子を返さない代替消去メソッドvoid erase_fast(iterator)を提供します。
このコードは MIT ライセンスに基づいてライセンスされています。詳細については、LICENSE ファイルを参照してください。
