unordered_dense
v4.5.0
Hashmap dan hashset yang disimpan dengan cepat & padat berdasarkan penghapusan pergeseran robin-hood ke belakang untuk C ++ 17 dan yang lebih baru.
Kelas ankerl::unordered_dense::map dan ankerl::unordered_dense::set adalah penggantian drop-in std::unordered_map dan std::unordered_set . Meskipun mereka tidak memiliki jaminan stabilitas iterator / referensi yang kuat, mereka biasanya jauh lebih cepat.
Selain itu, ada ankerl::unordered_dense::segmented_map dan ankerl::unordered_dense::segmented_set dengan penggunaan memori puncak yang lebih rendah. dan Iterator/Referensi yang stabil di Insert.
ankerl::unordered_dense::hashis_transparentstd::hashauto extract() && -> value_container_typeextract() elemen tunggal[[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 dan segmented_set Desain yang dipilih memiliki beberapa keunggulan dibandingkan std::unordered_map :
std::vector , semua data berdekatan!absl::flat_hash_mapstd::allocators , dan Polymorphic Alocators. Ada ankerl::unordered_dense::pmr typedef tersediastd::vector untuk boost::interprocess::vector atau wadah akses acak yang kompatibel.std::vector .Tidak ada makan siang gratis, jadi ada beberapa kelemahan:
const Key di std::pair<Key, Value> Lokasi instalasi default adalah /usr/local .
Kloning repositori dan jalankan perintah -perintah ini di folder yang dikloning:
mkdir build && cd build
cmake ..
cmake --build . --target install Pertimbangkan mengatur awalan instal jika Anda tidak ingin menginstal sistem unordered_dense yang luas, seperti itu:
mkdir build && cd build
cmake -DCMAKE_INSTALL_PREFIX:PATH= ${HOME} /unordered_dense_install ..
cmake --build . --target installUntuk memanfaatkan perpustakaan yang diinstal, tambahkan ini ke proyek Anda:
find_package (unordered_dense CONFIG REQUIRED)
target_link_libraries (your_project_name unordered_dense::unordered_dense) ankerl::unordered_dense mendukung modul C ++ 20. Cukup kompilasi src/ankerl.unordered_dense.cpp dan gunakan modul yang dihasilkan, misalnya seperti itu:
clang++ -std=c++20 -I include --precompile -x c++-module src/ankerl.unordered_dense.cpp
clang++ -std=c++20 -c ankerl.unordered_dense.pcm Untuk menggunakan modul dengan misalnya di module_test.cpp , gunakan
import ankerl.unordered_dense;dan dikompilasi dengan misalnya
clang++ -std=c++20 -fprebuilt-module-path=. ankerl.unordered_dense.o module_test.cpp -o main Skrip demo sederhana dapat ditemukan dalam test/modules .
ankerl::unordered_dense::hash adalah hash berkualitas cepat dan tinggi, berdasarkan Wyhash. ankerl::unordered_dense peta/set membedakan antara hash dengan kualitas tinggi (efek longsor yang baik) dan kualitas buruk. Hash dengan kualitas yang baik mengandung penanda khusus:
using is_avalanching = void ; Ini adalah kasus -kasus untuk spesialisasi bool , char , signed char , unsigned char , char8_t , char16_t , char32_t , wchar_t , short , tidak ditandatangani pendek, int , unsigned short , long , long long , unsigned int , unsigned long , unsigned long long , T* , t*, t*, std::unique_ptr<T> , std :: sharping: t share, t*, t*, std :: unik_ptr <t>, std :: sharping: t sharped: t* t* t* t* t* t* t* ,: unial_ptr <t>, std :: sharping: t sharped: t* t* t* t* t* t* t* t* t* T* , std::basic_string<C> std::shared_ptr<T> , std :: shiT: t shoTed: t t enum t t* dan std::basic_string_view<C> .
Hash yang tidak mengandung penanda seperti itu dianggap berkualitas buruk dan menerima langkah pencampuran tambahan di dalam implementasi peta/set.
Pertimbangkan tipe kunci kustom sederhana:
struct id {
uint64_t value{};
auto operator ==(id const & other) const -> bool {
return value == other. value ;
}
};Implementasi hash paling sederhana adalah ini:
struct custom_hash_simple {
auto operator ()(id const & x) const noexcept -> uint64_t {
return x. value ;
}
};Ini bisa digunakan misalnya
auto ids = ankerl::unordered_dense::set<id, custom_hash_simple>(); Karena custom_hash_simple tidak memiliki using is_avalanching = void; Marker dianggap kualitas buruk dan pencampuran tambahan x.value secara otomatis disediakan di dalam set.
Kembali ke contoh id , kami dapat dengan mudah menerapkan hash berkualitas lebih tinggi:
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 );
}
}; Kita tahu wyhash::hash berkualitas tinggi, jadi kita dapat menambahkan using is_avalanching = void; yang membuat peta/set langsung menggunakan nilai yang dikembalikan.
ankerl::unordered_dense::hash Alih -alih membuat kelas baru, Anda juga dapat mengkhususkan 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 Peta/set ini mendukung kelebihan heterogen seperti yang dijelaskan dalam P2363 memperluas kontainer asosiatif dengan kelebihan heterogen yang tersisa yang ditargetkan untuk C ++ 26. Ini memiliki kelebihan beban untuk find , count , contains , equal_range (lihat p0919r3), erase (lihat p2077r2), dan try_emplace , insert_or_assign , operator[] , at , dan insert & emplace untuk set (lihat p2363r3).
Agar kelebihan yang heterogen dapat mempengaruhi, baik hasher dan key_equal perlu memiliki atribut is_transparent Set.
Berikut adalah contoh implementasi yang dapat digunakan dengan jenis string apa pun yang dapat dikonversi ke std::string_view (misalnya char const* dan 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);
}
}; Untuk memanfaatkan hash ini, Anda harus menentukannya sebagai tipe, dan juga key_equal dengan is_transparent seperti std :: equal_to <>:
auto map = ankerl::unordered_dense::map<std::string, size_t , string_hash, std::equal_to<>>(); Untuk informasi lebih lanjut, lihat contoh dalam test/unit/transparent.cpp .
std::hash Ketika implementasi untuk std::hash dari jenis kustom tersedia, ini secara otomatis digunakan dan dianggap berkualitas buruk (dengan demikian std::hash digunakan, tetapi langkah pencampuran tambahan dilakukan).
Ketika jenisnya memiliki representasi objek yang unik (tidak ada bantalan, dapat disalin secara sepele), seseorang dapat hash memori objek. Pertimbangkan kelas sederhana
struct point {
int x{};
int y{};
auto operator ==(point const & other) const -> bool {
return x == other. x && y == other. y ;
}
};Hash yang cepat dan berkualitas tinggi dapat dengan mudah disediakan seperti itu:
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));
}
}; Selain std::unordered_map API (lihat https://en.cppreference.com/w/cpp/container/unordered_map) Kami memiliki API tambahan yang agak mirip dengan API node, tetapi memanfaatkan fakta bahwa kami menggunakan wadah akses acak secara internal:
auto extract() && -> value_container_type Mengekstrak wadah yang digunakan secara internal. *this dikosongkan.
extract() elemen tunggal Mirip dengan erase() Saya memiliki extract() . Berperilaku persis sama dengan erase , kecuali bahwa nilai pengembalian adalah elemen yang dipindahkan yang dihapus dari wadah:
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> Perhatikan bahwa API extract(key) mengembalikan std::optional<value_type> yang kosong saat kunci tidak ditemukan.
[[nodiscard]] auto values() const noexcept -> value_container_type const&Memperlihatkan wadah nilai yang mendasarinya.
auto replace(value_container_type&& container)Buang wadah yang dipegang secara internal dan menggantinya dengan yang dilewati. Elemen non-unik dihilangkan, dan wadah akan sebagian dipesan ulang ketika elemen non-unik ditemukan.
unordered_dense menerima alokasi khusus, tetapi Anda juga dapat menentukan wadah khusus untuk argumen templat itu. Dengan begitu dimungkinkan untuk menggantikan std::vector yang digunakan secara internal dengan misalnya std::deque atau wadah lain seperti boost::interprocess::vector . Ini mendukung pointer mewah (misalnya OFFSET_PTR), sehingga wadah dapat digunakan dengan memori bersama EG yang disediakan oleh boost::interprocess .
Peta/set mendukung dua jenis ember yang berbeda. Standarnya harus bagus untuk hampir semua orang.
ankerl::unordered_dense::bucket_type::standardankerl::unordered_dense::bucket_type::bigsegmented_map dan segmented_set ankerl::unordered_dense menyediakan implementasi kontainer khusus yang memiliki persyaratan memori yang lebih rendah daripada std::vector default. Memori tidak berdekatan, tetapi dapat mengalokasikan segmen tanpa harus merealokasi dan memindahkan semua elemen. Singkatnya, ini mengarah ke
std::vector karena tidak langsung diperlukan. Berikut adalah perbandingan terhadap absl::flat_hash_map dan ankerl::unordered_dense::map saat memasukkan 10 juta entri 
Abseil tercepat untuk tes penyisipan sederhana ini, membutuhkan waktu lebih dari 0,8 detik. Penggunaan memori puncaknya adalah sekitar 430 MB. Perhatikan bagaimana penggunaan memori turun setelah puncak terakhir; Ketika turun ke ~ 290MB telah selesai mengulangi dan dapat membebaskan blok memori yang sebelumnya digunakan.
ankerl::unordered_dense::segmented_map tidak memiliki puncak ini, dan sebaliknya memiliki peningkatan penggunaan memori yang lancar. Perhatikan masih ada penurunan mendadak & peningkatan memori karena kebutuhan struktur data pengindeksan masih perlu meningkat dengan faktor tetap. Tetapi karena menyimpan data dalam wadah terpisah, kami dapat terlebih dahulu membebaskan struktur data lama, dan kemudian mengalokasikan struktur pengindeksan baru yang lebih besar; Jadi kita tidak memiliki puncak.
Peta/set memiliki dua struktur data:
std::vector<value_type> yang menyimpan semua data. peta/set iterator hanya std::vector<value_type>::iterator ! Setiap kali elemen ditambahkan, itu adalah emplace_back ke vektor. Kuncinya hashed, dan entri (ember) ditambahkan di lokasi yang sesuai di array bucket. Bucket memiliki struktur ini:
struct Bucket {
uint32_t dist_and_fingerprint;
uint32_t value_idx;
};Setiap bucket menyimpan 3 hal:
dist_and_fingerprint )dist_and_fingerprint )Struktur ini dirancang khusus untuk strategi resolusi tabrakan Robin-Hood Hashing dengan penghapusan pergeseran ke belakang.
Kuncinya hash dan array ember dicari jika memiliki entri di lokasi itu dengan sidik jari itu. Ketika ditemukan, kunci dalam vektor data dibandingkan, dan bila sama nilainya dikembalikan.
Karena semua data disimpan dalam vektor, pemindahan sedikit lebih rumit:
value_idx dari elemen yang dipindahkan. Ini membutuhkan pencarian lain. Pada 2023-09-10 saya melakukan pencarian cepat di GitHub untuk melihat apakah peta ini digunakan dalam proyek open source populer. Berikut adalah beberapa proyek yang saya temukan. Tolong kirimkan saya catatan jika Anda ingin dalam daftar itu!
