robin map
v1.3.0
ไลบรารี robin-map คือการใช้งาน C ++ ของแมปแฮชที่รวดเร็วและชุดแฮชโดยใช้การกำหนดที่อยู่แบบเปิดและการแฮชโรบินฮูดเชิงเส้นพร้อมการลบกะแบบย้อนกลับเพื่อแก้ไขการชนกัน
มีคลาสสี่คลาส: tsl::robin_map , tsl::robin_set , tsl::robin_pg_map และ tsl::robin_pg_set สองอันแรกเร็วกว่าและใช้พลังของนโยบายการเติบโตสองอัน สองอันสุดท้ายใช้นโยบายการเติบโตที่สำคัญแทน และสามารถรับมือได้ดีขึ้นด้วยฟังก์ชันแฮชที่ไม่ดี ใช้เวอร์ชันไพรม์หากมีโอกาสที่จะเกิดรูปแบบซ้ำในบิตล่างของแฮชของคุณ (เช่น คุณกำลังจัดเก็บพอยน์เตอร์ด้วยฟังก์ชันแฮชข้อมูลเฉพาะตัว) ดูนโยบายการเติบโตสำหรับรายละเอียด
คุณสามารถดู เกณฑ์มาตรฐาน ของ tsl::robin_map เทียบกับแผนที่แฮชอื่นๆ ได้ที่นี่ หน้านี้ยังให้คำแนะนำบางประการเกี่ยวกับโครงสร้างตารางแฮชที่คุณควรลองใช้สำหรับกรณีการใช้งานของคุณ (มีประโยชน์หากคุณหลงลืมไปเล็กน้อยกับการใช้งานตารางแฮชหลายตารางในเนมสเปซ tsl )
ไลบรารี่เฉพาะส่วนหัว เพียงเพิ่มไดเร็กทอรี include ลงในพาธรวมของคุณ เท่านี้ก็พร้อมใช้งานแล้ว หากคุณใช้ CMake คุณยังสามารถใช้เป้าหมายที่ส่งออก tsl::robin_map จาก CMakeLists.txt ได้อีกด้วย
ตารางแฮชด่วน ตรวจสอบเกณฑ์มาตรฐานสำหรับตัวเลขบางตัว
รองรับคีย์/ค่าที่สร้างได้เฉพาะการย้ายเท่านั้นและไม่ใช่ค่าเริ่มต้น
รองรับการค้นหาแบบต่างกันที่อนุญาตให้ใช้ find ด้วยประเภทที่แตกต่างจาก Key (เช่น หากคุณมีแผนที่ที่ใช้ std::unique_ptr<foo> เป็นคีย์ คุณสามารถใช้ foo* หรือ std::uintptr_t เป็นพารามิเตอร์คีย์เพื่อ find โดยไม่ต้องสร้าง std::unique_ptr<foo> ดูตัวอย่าง)
ไม่จำเป็นต้องจองค่าแมวมองจากคีย์
ความเป็นไปได้ที่จะจัดเก็บค่าแฮชควบคู่ไปกับคีย์-ค่าที่เก็บไว้เพื่อการแฮชใหม่ที่รวดเร็วขึ้นและค้นหาว่าแฮชหรือฟังก์ชันที่เท่ากันของคีย์นั้นมีราคาแพงในการคำนวณหรือไม่ โปรดทราบว่าแฮชอาจถูกจัดเก็บแม้ว่าจะไม่ได้ถามอย่างชัดเจนเมื่อไลบรารีตรวจพบว่าจะไม่มีผลกระทบต่อขนาดของโครงสร้างในหน่วยความจำเนื่องจากการจัดตำแหน่ง ดูพารามิเตอร์เทมเพลต StoreHash สำหรับรายละเอียด
หากทราบแฮชก่อนการค้นหา ก็สามารถส่งผ่านเป็นพารามิเตอร์เพื่อเร่งการค้นหาได้ (ดูพารามิเตอร์ precalculated_hash ใน API)
รองรับการทำให้ซีเรียลไลซ์และการดีซีเรียลไลซ์มีประสิทธิภาพ (ดูตัวอย่างและวิธี serialize/deserialize ใน API สำหรับรายละเอียด)
ไลบรารีสามารถใช้งานได้โดยปิดใช้งานข้อยกเว้น (ผ่านตัวเลือก -fno-exceptions บน Clang และ GCC โดยไม่มีตัวเลือก /EH บน MSVC หรือเพียงแค่กำหนด TSL_NO_EXCEPTIONS ) std::terminate ใช้แทนคำสั่ง throw เมื่อข้อยกเว้นถูกปิดใช้งาน
API คล้ายกับ std::unordered_map และ std::unordered_set อย่างใกล้ชิด
std::unordered_map tsl::robin_map พยายามให้มีอินเทอร์เฟซคล้ายกับ std::unordered_map แต่มีความแตกต่างบางประการ
การรับประกันข้อยกเว้นที่รัดกุมจะคงไว้เฉพาะ ในกรณีที่คำสั่งต่อไปนี้เป็นจริง std::is_nothrow_swappable<value_type>::value && std::is_nothrow_move_constructible<value_type>::value (โดยที่ value_type เป็น Key สำหรับ tsl::robin_set และ std::pair<Key, T> สำหรับ tsl::robin_map ) มิฉะนั้น หากมีข้อยกเว้นเกิดขึ้นระหว่างการสลับหรือการย้าย โครงสร้างอาจจบลงในสถานะที่ไม่ได้กำหนด โปรดทราบว่าตามมาตรฐานนั้น value_type ที่มีตัวสร้างการคัดลอก noยกเว้น และไม่มีตัวสร้างการย้ายก็เป็นไปตามเงื่อนไขนี้เช่นกัน และจะรับประกันการรับประกันข้อยกเว้นที่แข็งแกร่งสำหรับโครงสร้าง (ดู 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->วินาที = 2; // Illegalit.value() = 2; // ตกลง} ไม่รองรับวิธีการบางอย่างที่เกี่ยวข้องกับที่เก็บข้อมูล (เช่น bucket_size , bucket , ... )
ความแตกต่างเหล่านี้ยังใช้ระหว่าง std::unordered_set และ tsl::robin_set
การรับประกันความปลอดภัยของเธรดจะเหมือนกับ std::unordered_map/set (เช่น เป็นไปได้ที่จะมีตัวอ่านหลายตัวโดยไม่มีตัวเขียน)
ไลบรารีรองรับนโยบายการเติบโตหลายรายการผ่านพารามิเตอร์เทมเพลต GrowthPolicy ห้องสมุดมีนโยบายสามประการให้ไว้ แต่คุณสามารถนำไปใช้เองได้อย่างง่ายดายหากจำเป็น
tsl::rh::power_of_two_growth_policy นโยบายเริ่มต้นที่ใช้โดย tsl::robin_map/set นโยบายนี้จะรักษาขนาดของอาร์เรย์ที่เก็บข้อมูลของตารางแฮชให้มีกำลัง 2 ข้อจำกัดนี้อนุญาตให้นโยบายหลีกเลี่ยงการใช้การดำเนินการแบบโมดูโลที่ช้าเพื่อแมปแฮชกับที่เก็บข้อมูล แทนที่จะเป็น hash % 2 n แต่จะใช้ hash & (2 n - 1) (ดูโมดูโลแบบเร็ว) รวดเร็ว แต่สิ่งนี้อาจทำให้เกิดการชนกันมากมายด้วยฟังก์ชันแฮชที่ไม่ดี เนื่องจากโมดูโลที่มีกำลังสองเท่านั้นที่จะปกปิดบิตที่สำคัญที่สุดในตอนท้าย
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_t bucket_for_hash(std::size_t hash) const noException เสมอ // คืนจำนวนที่เก็บข้อมูลที่ควรใช้ใน next Growthstd::size_t next_bucket_count() const; // จำนวนที่เก็บข้อมูลสูงสุดที่รองรับโดย Policystd::size_t max_bucket_count() const; // รีเซ็ตนโยบายการเติบโตราวกับว่านโยบายถูกสร้างขึ้นโดยมีจำนวนบัคเก็ตเป็น 0// หลังจากเคลียร์แล้ว นโยบายจะต้องคืนค่า 0 เสมอเมื่อ bucket_for_hash() ถูกเรียก.void clear() noException;
-หากต้องการใช้ robin-map เพียงเพิ่มไดเร็กทอรีรวมลงในพาธรวมของคุณ มันเป็นห้องสมุด ส่วนหัวเท่านั้น
หากคุณใช้ CMake คุณยังสามารถใช้เป้าหมายที่ส่งออก tsl::robin_map จาก CMakeLists.txt ด้วย target_link_libraries
# ตัวอย่างที่โครงการ robin-map ถูกเก็บไว้ในไดเร็กทอรีบุคคลที่สามadd_subdirectory(third-party/robin-map)target_link_libraries(your_target PRIVATE tsl::robin_map)
หากโปรเจ็กต์ได้รับการติดตั้งผ่าน make install คุณยังสามารถใช้ find_package(tsl-robin-map REQUIRED) แทน add_subdirectory
ห้องสมุดมีอยู่ใน vcpkg และ conan นอกจากนี้ยังมีอยู่ในที่เก็บแพ็คเกจ Debian, Ubuntu และ Fedora
รหัสควรทำงานร่วมกับคอมไพเลอร์ที่เป็นไปตามมาตรฐาน C ++ 17
หากต้องการรันการทดสอบ คุณจะต้องมีไลบรารี Boost Test และ CMake
โคลนคอมไพล์ https://github.com/Tessil/robin-map.gitcd robin-map/tests mkdir buildcd สร้าง มะ.. 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> map = {{"a", 1}, {"b", 2}};
แผนที่ ["ค"] = 3;
แผนที่ ["d"] = 4;
map.insert({"e", 5});
map.erase("b"); สำหรับ (อัตโนมัติ it = map.begin(); it != map.end(); ++it) {//it->second += 2; // Not valid.it.value() += 2;
} // {d, 6} {a, 3} {e, 7} {c, 5}สำหรับ(const auto& key_value : map) {
std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
-
if(map.find("a") != map.end()) {
std::cout << "พบ "a" << มาตรฐาน::endl;
} const std::size_t precalculated_hash = std::hash<std::string>()("a");// ถ้าเรารู้แฮชไว้ล่วงหน้าแล้ว เราสามารถส่งผ่านมันในพารามิเตอร์เพื่อเร่งการค้นหา ถ้า ( map.find("a", precalculated_hash) != map.end()) {
std::cout << "พบ "a" ที่มีแฮช " << precalculated_hash << "" << มาตรฐาน::endl;
-
/* * การคำนวณแฮชและการเปรียบเทียบสอง std::string อาจช้า * เราสามารถจัดเก็บแฮชของสตริง std::string แต่ละรายการในแมปแฮชเพื่อให้ * ส่วนแทรกและการค้นหาเร็วขึ้นโดยการตั้งค่า StoreHash เป็นจริง -
tsl::robin_map<std::string, int, std::hash<std::string>,
มาตรฐาน::equal_to<std::string>,
std::allocator<std::pair<std::string, int>>, true> map2;
map2["a"] = 1;
map2["ข"] = 2; // {a, 1} {b, 2}สำหรับ (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}สำหรับ (const auto& คีย์ : set) {
std::cout << "{" << คีย์ << "}" << std::endl;
-
- การโอเวอร์โหลดที่แตกต่างกันทำให้สามารถใช้ประเภทอื่นนอกเหนือจาก Key ในการค้นหาและลบได้ ตราบใดที่ประเภทที่ใช้นั้นสามารถแฮชได้และเทียบเคียงได้กับ Key
หากต้องการเปิดใช้งานโอเวอร์โหลดต่างกันใน tsl::robin_map/set รหัสที่ผ่านการรับรอง KeyEqual::is_transparent จะต้องถูกต้อง มันทำงานในลักษณะเดียวกับ std::map::find คุณสามารถใช้ std::equal_to<> หรือกำหนดวัตถุฟังก์ชันของคุณเองได้
ทั้ง KeyEqual และ Hash จะต้องสามารถจัดการกับประเภทที่แตกต่างกันได้
#include <ฟังก์ชันการทำงาน>#include <iostream>#include <string>#include <tsl/robin_map.h>พนักงาน struct {พนักงาน(int id, std::string name) : m_id(id), m_name(std::move (ชื่อ)) {
} // ไม่ว่าเราจะรวมตัวเปรียบเทียบไว้ในคลาสแล้วเราใช้ `std::equal_to<>`...friend bool โอเปอเรเตอร์==(const Employee& empl, int empl_id) {return empl.m_id == empl_id;
} ตัวดำเนินการบูลเพื่อน ==(int empl_id, const พนักงาน& empl) {return empl_id == empl.m_id;
} ตัวดำเนินการบูลเพื่อน ==(const พนักงาน& empl1, const พนักงาน& empl2) {return empl1.m_id == empl2.m_id;
-
int m_id;
มาตรฐาน::สตริง m_name;
};// ... หรือเราใช้คลาสแยกต่างหากเพื่อเปรียบเทียบ Employee.struct equal_employee {using is_transparent = void; ตัวดำเนินการบูล () (const พนักงาน & empl, int empl_id) const {return empl.m_id == empl_id;
} ตัวดำเนินการบูล () (int empl_id, const พนักงาน & empl) const {return empl_id == empl.m_id;
} ตัวดำเนินการบูล () (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<> ซึ่งจะอนุมานและส่งต่อพารามิเตอร์ tsl::robin_map<employee, int, hash_employee, std::equal_to<>> map โดยอัตโนมัติ;
map.insert({พนักงาน(1, "จอห์น โด"), 2001});
map.insert({พนักงาน(2, "เจน โด"), 2002});
map.insert({พนักงาน(3, "John Smith"), 2003});// John Smith 2003auto it = map.find(3);if(it != map.end()) {
std::cout << it->first.m_name << " " << it->วินาที << std::endl;
-
map.erase(1);// ใช้ KeyEqual แบบกำหนดเองซึ่งมีสมาชิก is_transparent typetsl::robin_map<employee, int, hash_employee, equal_employee> map2;
map2.insert({พนักงาน(4, "จอห์นนี่โด"), 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> หากใช้แผนที่หรือคีย์สำหรับ / / a set.template<typename U>ตัวดำเนินการโมฆะ()(const U& value);
- struct deserializer {// ต้องรองรับประเภทต่อไปนี้สำหรับ U: std::int16_t, std::uint32_t, // std::uint64_t, float และ std::pair<Key, T> หากใช้แผนที่หรือคีย์สำหรับ / / a set.template<ประเภทชื่อ U>
ตัวดำเนินการ U()();
-โปรดทราบว่าการใช้งานจะทิ้งความเข้ากันได้แบบไบนารี (endianness, การแทนไบนารีแบบลอยตัว, ขนาดของ int, ...) ของประเภทที่ทำให้เป็นอนุกรม/ดีซีเรียลไลซ์อยู่ในมือของออบเจ็กต์ฟังก์ชันที่ให้มา หากจำเป็นต้องมีความเข้ากันได้
รายละเอียดเพิ่มเติมเกี่ยวกับวิธี serialize และ deserialize มีอยู่ใน 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.ข้อยกเว้น(m_ostream.badbit | m_ostream.failbit);
m_ostream.open(file_name, std::ios::binary);
} เทมเพลต<คลาส T, ชื่อประเภท std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr>ตัวดำเนินการโมฆะ()(const T& ค่า) {
m_ostream.write(reตีความ_cast<const char*>(&value), ขนาดของ(T));
} ตัวดำเนินการเป็นโมฆะ()(const std::pair<std::int64_t, std::int64_t>& value) {
(*สิ่งนี้)(value.first);
(*สิ่งนี้)(value.วินาที);
} ส่วนตัว: std::ofstream m_ostream;
};คลาสดีซีเรียลไลเซอร์ {สาธารณะ:deserializer(const char* file_name) {
m_istream.ข้อยกเว้น(m_istream.badbit | m_istream.failbit | m_istream.eofbit);
m_istream.open(file_name, std::ios::binary);
} เทมเพลต<คลาส T>
ตัวดำเนินการ T()() {
ค่า T; ดีซีเรียลไลซ์ (ค่า); ค่าส่งคืน;
-
ส่วนตัว: เทมเพลต <คลาส T, ชื่อประเภท std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr>การดีซีเรียลไลซ์เป็นโมฆะ (ค่า T&) {
m_istream.read(reตีความ_cast<char*>(&value), ขนาดของ(T));
} เป็นการดีซีเรียลไลซ์เป็นโมฆะ (std::pair<std::int64_t, std::int64_t>& value) {ดีซีเรียลไลซ์ (value.first);ดีซีเรียลไลซ์ (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* file_name = "robin_map.data";
-
ซีเรียลไลเซอร์ซีเรียล (file_name);
แผนที่.ซีเรียลไลซ์(อนุกรม);
-
-
deserializer dserial(file_name);auto map_deserialized = tsl::robin_map<std::int64_t, std::int64_t>::deserialize(dserial); ยืนยัน (แผนที่ == map_deserialized);
-
-
ดีซีเรียลไลเซอร์ dserial (file_name); /** * หากแผนที่แบบซีเรียลไลซ์และดีซีเรียลไลซ์เข้ากันได้กับแฮช (ดูเงื่อนไขใน API) * ตั้งค่าอาร์กิวเมนต์ให้เร่งกระบวนการดีซีเรียลไลซ์ให้เร็วขึ้นเนื่องจากเราไม่มี * เพื่อคำนวณแฮชของแต่ละคีย์ใหม่ เรายังรู้ด้วยว่าแต่ละถังต้องการพื้นที่เท่าใด */const bool hash_เข้ากันได้กับ = true; auto map_deserialized =
tsl::robin_map<std::int64_t, std::int64_t>::deserialize(dserial, hash_เข้ากันได้กับ); ยืนยัน (แผนที่ == map_deserialized);
-
-คุณสามารถใช้ไลบรารีการทำให้เป็นซีเรียลไลซ์ได้เพื่อหลีกเลี่ยงไม่ให้มีการสร้างซีเรียลไลซ์
ตัวอย่างต่อไปนี้ใช้ Boost Serialization พร้อมกับสตรีมการบีบอัด Boost zlib เพื่อลดขนาดของไฟล์ซีเรียลไลซ์ที่ได้ ตัวอย่างต้องใช้ C++20 เนื่องจากการใช้ไวยากรณ์รายการพารามิเตอร์เทมเพลตใน lambdas แต่สามารถปรับให้เข้ากับเวอร์ชันล่าสุดที่น้อยกว่าได้
#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 /การทำให้เป็นอนุกรม/split_free.hpp>#include <boost/serialization/utility.hpp>#include <cassert>#include <cstdint>#include <fstream>#include <tsl/robin_map.h>การเพิ่มเนมสเปซ { การทำให้เป็นอนุกรมเนมสเปซ {เทมเพลต <เอกสารถาวรคลาส, คีย์คลาส, คลาส T> เป็นโมฆะทำให้เป็นอนุกรม (ไฟล์เก็บถาวร & ar, tsl::robin_map <Key, T>& map, const เวอร์ชัน int ที่ไม่ได้ลงนาม) {split_free (ar, แผนที่, เวอร์ชัน);
}เทมเพลต <class Archive, คีย์คลาส, คลาส T> บันทึกเป็นโมฆะ (Archive & ar, const tsl::robin_map <Key, T>& map, const int ที่ไม่ได้ลงนาม /*version*/) {auto serializer = [&ar](const อัตโนมัติ& v) { ar & v; -
แผนที่.ซีเรียลไลซ์(ซีเรียลไลเซอร์);
}เทมเพลต <class Archive, คีย์คลาส, คลาส T> โหลดเป็นโมฆะ (Archive & ar, tsl::robin_map <Key, T>& map, const unsigned int /*version*/) {auto deserializer = [&ar]<typename U >() { คุณ คุณ; คุณ & คุณ; กลับมาหาคุณ; -
map = tsl::robin_map<คีย์, T>::deserialize(ดีซีเรียลไลเซอร์);
-
}}int main() {
tsl::robin_map<std::int64_t, std::int64_t> แผนที่ = {{1, -1}, {2, -2}, {3, -3}, {4, -4}};
const char* file_name = "robin_map.data";
-
มาตรฐาน::ของกระแสของ;
ofs.ข้อยกเว้น (ofs.badbit | ofs.failbit);
ofs.open(file_name, std::ios::binary);
เพิ่ม :: iostreams :: filtering_ostream สำหรับ;
fo.push(เพิ่ม::iostreams::zlib_compressor());
fo.push(ของ);
เพิ่ม :: เก็บถาวร :: binary_oarchive oa (สำหรับ);
โอเอ << แผนที่;
-
-
มาตรฐาน::ifstream ifs;
ifs.ข้อยกเว้น (ifs.badbit | ifs.failbit | ifs.eofbit);
ifs.open(file_name, std::ios::binary);
เพิ่ม :: iostreams :: filtering_istream fi;
fi.push(เพิ่ม::iostreams::zlib_decompressor());
fi.push(ifs);
เพิ่ม :: เก็บถาวร :: binary_iarchive ia (fi);
tsl::robin_map<std::int64_t, std::int64_t> map_deserialized;
ia >> map_deserialized; ยืนยัน (แผนที่ == map_deserialized);
-
- ข้อผิดพลาดด้านประสิทธิภาพที่อาจเกิดขึ้นสองประการที่เกี่ยวข้องกับ tsl::robin_map และ tsl::robin_set เป็นสิ่งที่น่าสังเกต:
แฮชที่ไม่ดี ฟังก์ชันแฮชที่ทำให้เกิดการชนกันหลายครั้งสามารถนำไปสู่พฤติกรรมที่น่าประหลาดใจดังต่อไปนี้: เมื่อจำนวนการชนกันเกินเกณฑ์ที่กำหนด ตารางแฮชจะขยายโดยอัตโนมัติเพื่อแก้ไขปัญหา อย่างไรก็ตาม ในกรณีที่เสื่อมลง ส่วนขยายนี้อาจ ไม่ส่งผล ต่อจำนวนการชนกัน ทำให้เกิดโหมดความล้มเหลวที่ลำดับการแทรกเชิงเส้นนำไปสู่การเติบโตของพื้นที่จัดเก็บข้อมูลแบบเอ็กซ์โพเนนเชียล
กรณีนี้ส่วนใหญ่ได้รับการสังเกตเมื่อใช้กลยุทธ์การเติบโตกำลังสองเริ่มต้นกับ STL std::hash<T> เริ่มต้นสำหรับประเภทเลขคณิต T ซึ่งมักจะเป็นเอกลักษณ์! ดูปัญหา #39 เป็นตัวอย่าง วิธีแก้ปัญหานั้นง่ายมาก: ใช้ฟังก์ชันแฮชที่ดีกว่าและ/หรือ tsl::robin_pg_set / tsl::robin_pg_map
การลบองค์ประกอบและปัจจัยโหลดต่ำ tsl::robin_map และ tsl::robin_set จำลอง STL map/set API ซึ่งเปิดเผยวิธี iterator erase(iterator) ที่จะลบองค์ประกอบที่ตำแหน่งใดตำแหน่งหนึ่ง โดยส่งคืนตัววนซ้ำที่ถูกต้องซึ่งชี้ไปยังองค์ประกอบถัดไป
การสร้างออบเจ็กต์ตัววนซ้ำใหม่นี้จำเป็นต้องเดินไปที่บัคเก็ตที่ไม่ว่างถัดไปในตาราง ซึ่งอาจถือเป็นการดำเนินการที่มีราคาแพงเมื่อตารางแฮชมี ปัจจัยโหลด ต่ำ (เช่น เมื่อ capacity() มีขนาดใหญ่กว่า size() มาก)
นอกจากนี้ เมธอด erase() จะไม่ย่อขนาดและแฮชตารางใหม่ เนื่องจากไม่ได้รับอนุญาตตามข้อกำหนดของฟังก์ชันนี้ ลำดับเชิงเส้นตรงของการลบแบบสุ่มโดยไม่มีการแทรกระดับกลางสามารถนำไปสู่กรณีที่เสื่อมลงโดยมีต้นทุนรันไทม์กำลังสอง
ในกรณีเช่นนี้ ค่าส่งกลับตัววนซ้ำมักไม่จำเป็นด้วยซ้ำ ดังนั้นต้นทุนจึงไม่จำเป็นเลย ดังนั้นทั้ง tsl::robin_set และ tsl::robin_map จึงจัดให้มีวิธีการลบแบบอื่น void erase_fast(iterator) ที่ไม่ส่งคืนตัววนซ้ำเพื่อหลีกเลี่ยงการค้นหาองค์ประกอบถัดไป
รหัสนี้ได้รับอนุญาตภายใต้ใบอนุญาต MIT โปรดดูรายละเอียดในไฟล์ LICENSE
