robin map
v1.3.0
Pustaka robin-map adalah implementasi C++ dari peta hash cepat dan kumpulan hash menggunakan pengalamatan terbuka dan hashing robin hood linier dengan penghapusan pergeseran mundur untuk menyelesaikan tabrakan.
Empat kelas disediakan: tsl::robin_map , tsl::robin_set , tsl::robin_pg_map dan tsl::robin_pg_set . Dua kebijakan pertama lebih cepat dan menggunakan kebijakan pertumbuhan kekuatan dua, sedangkan dua kebijakan terakhir menggunakan kebijakan pertumbuhan prima dan mampu mengatasi fungsi hash yang buruk dengan lebih baik. Gunakan versi prime jika ada kemungkinan pola berulang di bit bawah hash Anda (misalnya, Anda menyimpan pointer dengan fungsi hash identitas). Lihat GrowthPolicy untuk detailnya.
Tolok ukur tsl::robin_map terhadap peta hash lainnya dapat ditemukan di sini. Halaman ini juga memberikan beberapa saran tentang struktur tabel hash mana yang harus Anda coba untuk kasus penggunaan Anda (berguna jika Anda agak bingung dengan beberapa implementasi tabel hash di namespace tsl ).
Pustaka khusus header, cukup tambahkan direktori penyertaan ke jalur penyertaan Anda dan Anda siap berangkat. Jika Anda menggunakan CMake, Anda juga dapat menggunakan target yang diekspor tsl::robin_map dari CMakeLists.txt.
Tabel hash cepat, periksa patokan untuk beberapa angka.
Dukungan untuk kunci/nilai yang dapat dibangun hanya-pindah dan non-default.
Dukungan untuk pencarian heterogen yang memungkinkan penggunaan find dengan tipe yang berbeda dari Key (misalnya jika Anda memiliki peta yang menggunakan std::unique_ptr<foo> sebagai kunci, Anda dapat menggunakan foo* atau std::uintptr_t sebagai parameter kunci untuk find tanpa membuat std::unique_ptr<foo> , lihat contoh).
Tidak perlu mencadangkan nilai sentinel apa pun dari kunci.
Kemungkinan untuk menyimpan nilai hash bersama dengan nilai kunci yang disimpan untuk pengulangan dan pencarian yang lebih cepat jika fungsi hash atau kunci yang setara mahal untuk dihitung. Perhatikan bahwa hash dapat disimpan meskipun tidak ditanyakan secara eksplisit ketika perpustakaan dapat mendeteksi bahwa hash tidak akan berdampak pada ukuran struktur di memori karena penyelarasan. Lihat parameter template StoreHash untuk detailnya.
Jika hash diketahui sebelum pencarian, dimungkinkan untuk meneruskannya sebagai parameter untuk mempercepat pencarian (lihat parameter precalculated_hash di API).
Dukungan untuk serialisasi dan deserialisasi yang efisien (lihat contoh dan metode serialize/deserialize di API untuk detailnya).
Pustaka dapat digunakan dengan pengecualian dinonaktifkan (melalui opsi -fno-exceptions di Clang dan GCC, tanpa opsi /EH di MSVC atau cukup dengan mendefinisikan TSL_NO_EXCEPTIONS ). std::terminate digunakan sebagai pengganti instruksi throw ketika pengecualian dinonaktifkan.
API sangat mirip dengan std::unordered_map dan std::unordered_set .
std::unordered_map tsl::robin_map mencoba memiliki antarmuka yang mirip dengan std::unordered_map , tetapi ada beberapa perbedaan.
Jaminan pengecualian yang kuat hanya berlaku jika pernyataan berikut ini benar std::is_nothrow_swappable<value_type>::value && std::is_nothrow_move_constructible<value_type>::value (di mana value_type adalah Key untuk tsl::robin_set dan std::pair<Key, T> untuk tsl::robin_map ). Jika tidak, jika pengecualian dilemparkan selama pertukaran atau pemindahan, struktur mungkin akan berada dalam keadaan tidak terdefinisi. Perhatikan bahwa sesuai standar, value_type dengan konstruktor salinan noException dan konstruktor no move juga memenuhi kondisi ini dan dengan demikian akan menjamin jaminan pengecualian yang kuat untuk struktur tersebut (lihat API untuk detailnya).
Tipe Key , dan juga T dalam hal map, harus dapat ditukar. Mereka juga harus dapat disalin dan/atau dipindahkan.
Pembatalan iterator tidak berperilaku dengan cara yang sama, operasi apa pun yang mengubah tabel hash akan membatalkannya (lihat API untuk detailnya).
Referensi dan penunjuk ke kunci atau nilai di peta tidak valid dengan cara yang sama seperti iterator ke nilai kunci ini.
Untuk iterator tsl::robin_map , operator*() dan operator->() mengembalikan referensi dan pointer ke const std::pair<Key, T> alih-alih std::pair<const Key, T> yang membuat nilai T tidak dapat dimodifikasi. Untuk mengubah nilai, Anda harus memanggil metode value() dari iterator untuk mendapatkan referensi yang bisa diubah. Contoh:
tsl::robin_map<int, int> peta = {{1, 1}, {2, 1}, {3, 1}};for(auto it = map.begin(); it != map.end() ; ++it) {//it->detik = 2; // Ilegal.nilai() = 2; // Oke} Tidak ada dukungan untuk beberapa metode terkait bucket (seperti bucket_size , bucket , ...).
Perbedaan ini juga berlaku antara std::unordered_set dan tsl::robin_set .
Jaminan keamanan thread sama dengan std::unordered_map/set (yaitu memungkinkan memiliki banyak pembaca tanpa penulis).
Pustaka ini mendukung berbagai kebijakan pertumbuhan melalui parameter templat GrowthPolicy . Tiga kebijakan disediakan oleh perpustakaan tetapi Anda dapat dengan mudah menerapkan kebijakan Anda sendiri jika diperlukan.
tsl::rh::power_of_two_growth_policy. Kebijakan default yang digunakan oleh tsl::robin_map/set . Kebijakan ini menjaga ukuran susunan keranjang tabel hash menjadi pangkat dua. Batasan ini memungkinkan kebijakan menghindari penggunaan operasi modulo lambat untuk memetakan hash ke bucket, alih-alih hash % 2 n , kebijakan ini menggunakan hash & (2 n - 1) (lihat modulo cepat). Cepat tetapi ini dapat menyebabkan banyak tabrakan dengan fungsi hash yang buruk karena modulo dengan kekuatan dua pada akhirnya hanya menutupi bit paling signifikan.
tsl::rh::prime_growth_policy. Kebijakan default yang digunakan oleh tsl::robin_pg_map/set . Kebijakan ini menjaga ukuran susunan keranjang tabel hash tetap pada bilangan prima. Saat memetakan hash ke sebuah bucket, menggunakan bilangan prima sebagai modulo akan menghasilkan distribusi hash yang lebih baik di seluruh bucket bahkan dengan fungsi hash yang buruk. Untuk memungkinkan kompiler mengoptimalkan operasi modulo, kebijakan menggunakan tabel pencarian dengan modulo bilangan prima konstan (lihat API untuk detailnya). Lebih lambat dari tsl::rh::power_of_two_growth_policy tetapi lebih aman.
tsl::rh::mod_growth_policy. Kebijakan ini mengembangkan peta dengan faktor pertumbuhan yang dapat disesuaikan dan dimasukkan ke dalam parameter. Kemudian cukup gunakan operator modulo untuk memetakan hash ke bucket. Lebih lambat namun lebih fleksibel.
Untuk menerapkan kebijakan Anda sendiri, Anda harus mengimplementasikan antarmuka berikut.
struct custom_policy {// Dipanggil pada konstruksi dan pengulangan tabel hash, min_bucket_count_in_out adalah bucket minimum// yang dibutuhkan tabel hash. Kebijakan ini dapat mengubahnya ke jumlah keranjang yang lebih banyak jika diperlukan // dan tabel hash akan menggunakan nilai ini sebagai jumlah keranjang. Jika 0 keranjang ditanyakan, maka nilai// harus tetap pada 0.explicit custom_policy(std::size_t& min_bucket_count_in_out); // Mengembalikan bucket [0, bucket_count()) yang berisi hash. // Jika bucket_count() adalah 0, ia harus selalu mengembalikan 0.std::size_t bucket_for_hash(std::size_t hash) const nokecuali; // Mengembalikan jumlah keranjang yang harus digunakan pada pertumbuhan berikutnyastd::size_t next_bucket_count() const; // Jumlah maksimum keranjang yang didukung oleh policystd::size_t max_bucket_count() const; // Reset kebijakan pertumbuhan seolah-olah kebijakan dibuat dengan jumlah keranjang 0.// Setelah dihapus, kebijakan harus selalu menghasilkan 0 ketika bucket_for_hash() dipanggil.void clear() nokecuali;
}Untuk menggunakan robin-map, cukup tambahkan direktori penyertaan ke jalur penyertaan Anda. Ini adalah perpustakaan khusus header .
Jika Anda menggunakan CMake, Anda juga dapat menggunakan target yang diekspor tsl::robin_map dari CMakeLists.txt dengan target_link_libraries .
# Contoh dimana proyek robin-map disimpan di direktori pihak ketigaadd_subdirectory(third-party/robin-map)target_link_libraries(your_target PRIVATE tsl::robin_map)
Jika proyek telah diinstal melalui make install , Anda juga dapat menggunakan find_package(tsl-robin-map REQUIRED) alih-alih add_subdirectory .
Perpustakaan tersedia dalam vcpkg dan conan. Itu juga ada di repositori paket Debian, Ubuntu dan Fedora.
Kode harus bekerja dengan kompiler yang memenuhi standar C++17.
Untuk menjalankan pengujian, Anda memerlukan pustaka Boost Test dan CMake.
git clone https://github.com/Tessil/robin-map.gitcd robin-map/tests mkdir buildcd build buatlah.. cmake --build ../tsl_robin_map_tests
API dapat ditemukan di sini.
Semua metode belum didokumentasikan, namun meniru perilaku yang ada di std::unordered_map dan std::unordered_set , kecuali jika ditentukan lain.
#include <cstdint>#include <iostream>#include <string>#include <tsl/robin_map.h>#include <tsl/robin_set.h>int main() {
tsl::robin_map<std::string, int> peta = {{"a", 1}, {"b", 2}};
peta["c"] = 3;
peta["d"] = 4;
peta.masukkan({"e", 5});
peta.erase("b"); for(auto it = map.begin(); it != map.end(); ++it) {//it->detik += 2; // Tidak valid.it.value() += 2;
} // {d, 6} {a, 3} {e, 7} {c, 5}untuk(const auto& nilai_kunci : peta) {
std::cout << "{" << nilai_kunci.pertama << ", " << nilai_kunci.kedua << "}" << std::endl;
}
if(peta.menemukan("a") != peta.akhir()) {
std::cout << "Ditemukan "a"." << std::endl;
} const std::size_t precalculated_hash = std::hash<std::string>()("a");// Jika kita sudah mengetahui hashnya sebelumnya, kita bisa meneruskannya dalam parameter untuk mempercepat pencarian.if( map.find("a", precalculated_hash) != map.end()) {
std::cout << "Ditemukan "a" dengan hash " << precalculated_hash << "." << std::endl;
}
/* * Menghitung hash dan membandingkan dua std::string mungkin lambat. * Kita dapat menyimpan hash setiap std::string di peta hash untuk membuat * penyisipan dan pencarian lebih cepat dengan menyetel StoreHash ke true. */
tsl::robin_map<std::string, int, std::hash<std::string>,
std::sama dengan<std::string>,
std::allocator<std::pair<std::string, int>>, true> map2;
peta2["a"] = 1;
peta2["b"] = 2; // {a, 1} {b, 2}untuk(const otomatis& nilai_kunci : peta2) {
std::cout << "{" << nilai_kunci.pertama << ", " << nilai_kunci.kedua << "}" << std::endl;
}
tsl::robin_set<int> set;
set.masukkan({1, 9, 0});
set.masukkan({2, -1, 9}); // {0} {1} {2} {9} {-1}untuk(const otomatis& kunci : set) {
std::cout << "{" << kunci << "}" << std::endl;
}
} Kelebihan beban heterogen memungkinkan penggunaan tipe lain selain Key untuk operasi pencarian dan penghapusan selama tipe yang digunakan dapat di-hash dan sebanding dengan Key .
Untuk mengaktifkan kelebihan beban heterogen di tsl::robin_map/set , ID yang memenuhi syarat KeyEqual::is_transparent harus valid. Cara kerjanya sama seperti untuk std::map::find . Anda dapat menggunakan std::equal_to<> atau menentukan objek fungsi Anda sendiri.
Baik KeyEqual dan Hash harus mampu menangani tipe yang berbeda.
#include <fungsional>#include <iostream>#include <string>#include <tsl/robin_map.h>struct karyawan {employee(int id, std::string name): m_id(id), m_name(std::move (nama)) {
} // Entah kita memasukkan pembanding ke dalam kelas dan menggunakan `std::equal_to<>`...friend bool operator==(const Employee& empl, int empl_id) {return empl.m_id == empl_id;
} teman bool operator==(int empl_id, const karyawan& empl) {return empl_id == empl.m_id;
} teman bool operator==(const karyawan& empl1, const karyawan& empl2) {return empl1.m_id == empl2.m_id;
}
int m_id;
std::string m_name;
};// ... atau kita menerapkan kelas terpisah untuk membandingkan Employee.struct equal_employee {using is_transparent = void; bool operator()(const karyawan& empl, int empl_id) const {return empl.m_id == empl_id;
} bool operator()(int empl_id, const karyawan& empl) const {return empl_id == empl.m_id;
} bool operator()(const karyawan& empl1, const karyawan& empl2) const {return empl1.m_id == empl2.m_id;
}
};struct hash_employee {
std::size_t operator()(const karyawan& karyawan) const {return std::hash<int>()(empl.m_id);
}
std::size_t operator()(int id) const {kembalikan std::hash<int>()(id);
}
};int main() {// Gunakan std::equal_to<> yang secara otomatis akan menyimpulkan dan meneruskan parametertsl::robin_map<employee, int, hash_employee, std::equal_to<>> map;
map.insert({karyawan(1, "John Doe"), 2001});
map.insert({karyawan(2, "Jane Doe"), 2002});
map.insert({karyawan(3, "John Smith"), 2003});// John Smith 2003auto it = map.find(3);if(it != map.end()) {
std::cout << it->first.m_name << " " << it->kedua << std::endl;
}
map.erase(1);// Gunakan KeyEqual khusus yang memiliki anggota is_transparent typetsl::robin_map<employee, int, hash_employee, equal_employee> map2;
map2.insert({karyawan(4, "Johnny Doe"), 2004});// 2004std::cout << map2.at(4) << std::endl;
}Pustaka menyediakan cara yang efisien untuk membuat serialisasi dan deserialisasi peta atau kumpulan sehingga dapat disimpan ke file atau dikirim melalui jaringan. Untuk melakukannya, pengguna harus menyediakan objek fungsi untuk serialisasi dan deserialisasi.
struct serializer {// Harus mendukung tipe berikut untuk U: std::int16_t, std::uint32_t, // std::uint64_t, float dan std::pair<Key, T> jika peta digunakan atau Kunci untuk / / satu set.template<typename U>void operator()(const U& nilai);
}; struct deserializer {// Harus mendukung tipe berikut untuk U: std::int16_t, std::uint32_t, // std::uint64_t, float dan std::pair<Key, T> jika peta digunakan atau Kunci untuk / / satu set.template<nama ketik U>
kamu operator()();
};Perhatikan bahwa implementasinya meninggalkan kompatibilitas biner (endianness, representasi biner float, ukuran int, ...) dari tipe yang diserialkan/deserialisasi di tangan objek fungsi yang disediakan jika kompatibilitas diperlukan.
Detail lebih lanjut mengenai metode serialize dan deserialize dapat ditemukan di 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.pengecualian(m_ostream.badbit | m_ostream.failbit);
m_ostream.open(nama_file, std::ios::biner);
} templat<kelas T, nama ketik std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr>void operator()(const T& value) {
m_ostream.write(reinterpret_cast<const char*>(&nilai), sizeof(T));
} batal operator()(const std::pair<std::int64_t, std::int64_t>& nilai) {
(*ini)(nilai.pertama);
(*ini)(nilai.detik);
}pribadi:std::ofstream m_ostream;
};deserializer kelas {public:deserializer(const char* nama_file) {
m_istream.pengecualian(m_istream.badbit | m_istream.failbit | m_istream.eofbit);
m_istream.open(nama_file, std::ios::biner);
} templat<kelas T>
T operator()() {
Nilai T;deserialisasi(nilai); nilai kembalian;
}
pribadi:template<kelas T, ketik nama std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr>void deserialize(T& value) {
m_istream.read(reinterpret_cast<char*>(&nilai), sizeof(T));
} void deserialize(std::pair<std::int64_t, std::int64_t>& value) {deserialize(value.first);deserialize(value.second);
}pribadi:std::ifstream m_istream;
};int main() {const tsl::robin_map<std::int64_t, std::int64_t> peta = {{1, -1}, {2, -2}, {3, -3}, {4, -4}};
const char* nama_file = "robin_map.data";
{
serialisasi serial(nama_file);
peta.serialisasi(serial);
}
{
deserializer dserial(nama_file);auto map_deserialized = tsl::robin_map<std::int64_t, std::int64_t>::deserialize(dserial); menegaskan(peta == map_deserialized);
}
{
deserializer dserial(nama_file); /** * Jika peta serial dan deserialisasi kompatibel dengan hash (lihat ketentuan di API), * menyetel argumen ke true akan mempercepat proses deserialisasi karena kita tidak perlu * menghitung ulang hash setiap kunci. Kami juga mengetahui berapa banyak ruang yang dibutuhkan setiap ember. */const bool hash_kompatibel = true;auto map_deserialized =
tsl::robin_map<std::int64_t, std::int64_t>::deserialize(dserial, hash_kompatibel); menegaskan(peta == map_deserialized);
}
}Dimungkinkan untuk menggunakan perpustakaan serialisasi untuk menghindari boilerplate.
Contoh berikut menggunakan Boost Serialization dengan aliran kompresi Boost zlib untuk mengurangi ukuran file serial yang dihasilkan. Contoh ini memerlukan C++20 karena penggunaan sintaks daftar parameter templat di lambda, tetapi dapat disesuaikan ke versi yang lebih baru.
#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, map, version);
}template<arsip kelas, Kunci kelas, kelas T>batal disimpan(Arsip & ar, const tsl::robin_map<Key, T>& map, const unsigned int /*version*/) {auto serializer = [&ar](const otomatis& v) { ar & v; };
peta.serialize(serializer);
}template<arsip kelas, Kunci kelas, kelas T>void load(Arsip & ar, tsl::robin_map<Key, T>& map, const unsigned int /*version*/) {auto deserializer = [&ar]<typename U >() { kamu; ar & kamu; kembalikan kamu; };
peta = tsl::robin_map<Key, T>::deserialize(deserializer);
}
}}int utama() {
tsl::robin_map<std::int64_t, std::int64_t> peta = {{1, -1}, {2, -2}, {3, -3}, {4, -4}};
const char* nama_file = "robin_map.data";
{
std::ofstream;
ofs.pengecualian(ofs.badbit | ofs.failbit);
ofs.open(nama_file, std::ios::biner);
boost::iostreams::filtering_ostream untuk;
fo.push(boost::iostreams::zlib_compressor());
fo.push(ofs);
boost::archive::binary_oarchive oa(fo);
oa << peta;
}
{
std::ifstream jika;
ifs.pengecualian(ifs.badbit | ifs.failbit | ifs.eofbit);
ifs.open(nama_file, std::ios::biner);
boost::iostreams::filtering_istream fi;
fi.push(boost::iostreams::zlib_decompressor());
fi.push(jika);
boost::archive::binary_iarchive ia(fi);
tsl::robin_map<std::int64_t, std::int64_t> map_deserialized;
ia >> map_deserialized; menegaskan(peta == map_deserialized);
}
} Dua potensi kendala kinerja yang melibatkan tsl::robin_map dan tsl::robin_set perlu diperhatikan:
Hash yang buruk . Fungsi hash yang menghasilkan banyak tabrakan dapat menyebabkan perilaku mengejutkan berikut: ketika jumlah tabrakan melebihi ambang batas tertentu, tabel hash akan otomatis diperluas untuk memperbaiki masalah. Namun, dalam kasus yang mengalami degenerasi, perluasan ini mungkin tidak berpengaruh pada jumlah tabrakan, menyebabkan mode kegagalan di mana urutan penyisipan linier menyebabkan pertumbuhan penyimpanan secara eksponensial.
Kasus ini terutama diamati ketika menggunakan strategi pertumbuhan kekuatan dua default dengan STL default std::hash<T> untuk tipe aritmatika T , yang sering kali merupakan identitas! Lihat edisi #39 sebagai contoh. Solusinya sederhana: gunakan fungsi hash yang lebih baik dan/atau tsl::robin_pg_set / tsl::robin_pg_map .
Penghapusan elemen dan faktor beban rendah . tsl::robin_map dan tsl::robin_set mencerminkan STL map/set API, yang memperlihatkan metode iterator erase(iterator) yang menghapus elemen pada posisi tertentu, mengembalikan iterator valid yang menunjuk ke elemen berikutnya.
Membangun objek iterator baru ini memerlukan berjalan ke keranjang kosong berikutnya dalam tabel, yang bisa menjadi operasi yang mahal ketika tabel hash memiliki faktor muatan rendah (yaitu, ketika capacity() jauh lebih besar dari size() ).
Selain itu, metode erase() tidak pernah menyusutkan & meng-hash ulang tabel karena hal ini tidak diizinkan oleh spesifikasi fungsi ini. Urutan linier dari penghapusan acak tanpa penyisipan perantara kemudian dapat menyebabkan kasus yang merosot dengan biaya waktu proses kuadrat.
Dalam kasus seperti ini, nilai pengembalian iterator seringkali tidak diperlukan, sehingga biayanya sama sekali tidak diperlukan. Oleh karena itu, baik tsl::robin_set dan tsl::robin_map menyediakan metode penghapusan alternatif void erase_fast(iterator) yang tidak mengembalikan iterator untuk menghindari keharusan menemukan elemen berikutnya.
Kode ini dilisensikan di bawah lisensi MIT, lihat file LISENSI untuk detailnya.
