unordered_dense
v4.5.0
C ++ 17以降のRobin-Hood Backward Shift削除に基づいて、高速で密に保存されたハッシュマップとハッシュセット。
クラスankerl::unordered_dense::map and ankerl::unordered_dense::set 、 std::unordered_mapおよびstd::unordered_setの（ほぼ）ドロップインの交換です。彼らは強力なイテレーター /参照安定性の保証を持っていませんが、通常ははるかに高速です。
さらに、 ankerl::unordered_dense::segmented_mapおよびankerl::unordered_dense::segmented_setが低いピークメモリ使用量があります。および挿入の安定したイテレータ/参照。
ankerl::unordered_dense::hashis_transparentを使用した不均一な過負荷std::hashへの自動フォールバックauto extract() && -> value_container_typeextract()単一要素[[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およびsegmented_set選択したデザインには、 std::unordered_map ：
std::vectorに保存されます、すべてのデータは隣接しています！absl::flat_hash_mapと同じ球場で、非常に高速な挿入とルックアップ速度std::allocatorsおよびPolymorphic Allocatorsの完全なサポート。 ankerl::unordered_dense::pmr typedefsが利用可能ですstd::vectorからboost::interprocess::vectorまたはその他の互換性のあるランダムアクセスコンテナを切り替えることができます。std::vectorを表示できるデバッガーで簡単に見ることができます。無料のランチはないので、いくつかの欠点があります：
std::pair<Key, Value>のconst Keyありませんデフォルトのインストール場所は/usr/localです。
リポジトリをクローンし、クローン化されたフォルダーでこれらのコマンドを実行します。
mkdir build && cd build
cmake ..
cmake --build . --target install unordered_denseシステムを大きくインストールしたくない場合は、インストールプレフィックスの設定を検討してください。
mkdir build && cd build
cmake -DCMAKE_INSTALL_PREFIX:PATH= ${HOME} /unordered_dense_install ..
cmake --build . --target installインストールされているライブラリを利用するには、これをプロジェクトに追加します。
find_package (unordered_dense CONFIG REQUIRED)
target_link_libraries (your_project_name unordered_dense::unordered_dense)ankerl::unordered_dense C ++ 20モジュールをサポートしています。 src/ankerl.unordered_dense.cppをコンパイルして、結果のモジュールを使用するだけです。
clang++ -std=c++20 -I include --precompile -x c++-module src/ankerl.unordered_dense.cpp
clang++ -std=c++20 -c ankerl.unordered_dense.pcm module_test.cppでEGを持つモジュールを使用するには、使用してください。
import ankerl.unordered_dense;EGでコンパイルします
clang++ -std=c++20 -fprebuilt-module-path=. ankerl.unordered_dense.o module_test.cpp -o main簡単なデモスクリプトはtest/modulesにあります。
ankerl::unordered_dense::hash 、wyhashに基づいた高速で高品質のハッシュです。 ankerl::unordered_denseマップ/セットは、高品質（良好な雪崩効果）と悪い品質のハッシュを区別します。良質のハッシュには、特別なマーカーが含まれています。
using is_avalanching = void ;これは、Specializations bool 、 char 、 signed char 、 unsigned char 、 char8_t 、 char16_t 、 char32_t 、 wchar_t enum short 、 unsigned short int unsigned unsigned int 、 long 、 unsigned long long long unsigned long long 、 T* std::shared_ptr<T> std::unique_ptr<T> std::basic_string<C>およびstd::basic_string_view<C> 。
そのようなマーカーを含まないハッシュは、品質が悪いと想定されており、マップ/セットの実装内で追加の混合ステップを受け取ります。
シンプルなカスタムキータイプを検討してください。
struct id {
uint64_t value{};
auto operator ==(id const & other) const -> bool {
return value == other. value ;
}
};ハッシュの最も単純な実装は次のとおりです。
struct custom_hash_simple {
auto operator ()(id const & x) const noexcept -> uint64_t {
return x. value ;
}
};これは、で使用できます
auto ids = ankerl::unordered_dense::set<id, custom_hash_simple>(); custom_hash_simple using is_avalanching = void;マーカーそれは品質が悪いと考えられており、 x.valueの追加の混合はセット内で自動的に提供されます。
id例に戻ると、高品質のハッシュを簡単に実装できます。
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 );
}
}; wyhash::hashは高品質であることがわかっているため、 using is_avalanching = void;これにより、マップ/セットが返された値を直接使用します。
ankerl::unordered_dense::hash新しいクラスを作成する代わりに、 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を使用した不均一な過負荷このマップ/セットは、C ++ 26を標的とする残りの不均一な過負荷との連想容器を拡張するP2363で説明されているように、不均一な過負荷をサポートします。これには、 find 、 count 、 contains 、 equal_range （p0919r3を参照）、 erase （p2077r2を参照）、およびtry_emplace 、 insert_or_assign 、 operator[] 、 at 、and＆ insert for set（p2363r3を参照）の過emplaceがあります。
不均一な過負荷が影響を受けるためには、 hasherとkey_equal両方が属性をis_transparentセットにする必要があります。
以下は、 std::string_view （ char const*および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);
}
};このハッシュを使用するには、タイプとして指定する必要があります。また、std :: equal_to <>のようなis_transparentを使用したkey_equalでも必要です。
auto map = ankerl::unordered_dense::map<std::string, size_t , string_hash, std::equal_to<>>();詳細については、 test/unit/transparent.cppの例を参照してください。
std::hashへの自動フォールバックカスタムタイプのstd::hashの実装が利用可能な場合、これは自動的に使用され、品質が悪いと想定されます（したがって、 std::hashが使用されますが、追加の混合ステップが実行されます）。
タイプに一意のオブジェクト表現がある場合（パディングなし、些細なコピー可能）、オブジェクトのメモリをハッシュするだけです。簡単なクラスを検討してください
struct point {
int x{};
int y{};
auto operator ==(point const & other) const -> bool {
return x == other. x && y == other. y ;
}
};高速で高品質のハッシュは、ように簡単に提供できます。
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));
}
};標準のstd::unordered_map api（https://en.cppreference.com/w/cpp/container/unordered_mapを参照）に加えて、ノードAPIに多少似た追加のAPIがありますが、ランダムアクセスコンテナを使用しているという事実を活用しています。
auto extract() && -> value_container_type内部で使用されている容器を抽出します。 *this空になっています。
extract()単一要素erase()と同様に、API呼び出しextract()があります。 return値がコンテナから削除された移動要素であることを除いて、それはeraseとまったく同じ動作をします。
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> extract(key) APIは、キーが見つからないときに空であるstd::optional<value_type>を返すことに注意してください。
[[nodiscard]] auto values() const noexcept -> value_container_type const&基礎となる値のコンテナを公開します。
auto replace(value_container_type&& container)内部に保持されている容器を破棄し、それを通過したものに置き換えます。非ユニークな要素が削除され、非ユニーク要素が見つかった場合、コンテナは部分的に並べ替えられます。
unordered_denseカスタムアロケーターを受け入れますが、そのテンプレート引数のカスタムコンテナを指定することもできます。そうすれば、内部で使用されているstd::vectorを、 std::dequeまたはboost::interprocess::vectorのような他のコンテナに置き換えることができます。これにより、派手なポインター（Offset_ptrなど）がサポートされるため、コンテナはboost::interprocessによって提供される共有メモリなどで使用できます。
マップ/セットは、2つの異なるバケットタイプをサポートしています。デフォルトは、ほとんどすべての人に適しているはずです。
ankerl::unordered_dense::bucket_type::standardankerl::unordered_dense::bucket_type::bigsegmented_mapおよびsegmented_set ankerl::unordered_denseデフォルトのstd::vectorよりもメモリ要件が低いカスタムコンテナの実装を提供します。メモリは隣接するものではありませんが、すべての要素を再割り当てして移動することなく、セグメントを割り当てることができます。要約すると、これはにつながります
std::vectorと比較してわずかに遅いインデックス作成が必要です。 absl::flat_hash_mapとankerl::unordered_dense::mapとの比較は次のとおりです。 
Abseilは、この単純な挿入テストで最も速く、0.8秒以上かかります。ピークメモリ使用量は約430 MBです。最後のピークの後にメモリの使用量がどのように下がるかに注意してください。 〜290MBになると、再ハッシュが終了し、以前に使用されたメモリブロックを解放できます。
ankerl::unordered_dense::segmented_mapはこれらのピークがなく、代わりにメモリ使用量がスムーズに増加します。インデックス作成データ構造のニーズは、固定係数によって増加する必要があるため、メモリには突然の低下と増加がまだあります。しかし、データを別のコンテナに保持するため、最初に古いデータ構造を解放し、次に新しいより大きなインデックス構造を割り当てることができます。したがって、ピークはありません。
マップ/セットには2つのデータ構造があります。
std::vector<value_type>すべてのデータを保持します。マップ/セットイテレーターはstd::vector<value_type>::iterator ！要素が追加されるたびに、それはベクトルへのemplace_backです。キーはハッシュドで、エントリ（バケット）がバケットアレイの対応する場所に追加されます。バケットにはこの構造があります。
struct Bucket {
uint32_t dist_and_fingerprint;
uint32_t value_idx;
};各バケットには3つのものが保存されます。
dist_and_fingerprintの3つの最も重要なバイト）dist_and_fingerprintで最も低い有意なバイト）この構造は、衝突解像度戦略のために特に設計されています。
キーはハッシュされ、その場所にその場所にエントリがある場合、バケットアレイが検索されます。見つかった場合、データベクトルのキーが比較され、等しい場合は値が返されます。
すべてのデータはベクトルに保存されるため、撤回はもう少し複雑です。
value_idx更新します。これには別の検索が必要です。 2023-09-10に、GitHubで簡単に検索して、このマップが人気のあるオープンソースプロジェクトで使用されているかどうかを確認しました。ここに私が見つけたプロジェクトのいくつかがあります。そのリストに必要な場合は、メモを送ってください！
