unordered_dense
v4.5.0
HashMap และ Hashset ที่จัดเก็บอย่างรวดเร็วและหนาแน่นขึ้นอยู่กับการลบ Shift Robin-Hood ย้อนหลังสำหรับ C ++ 17 และหลังจากนั้น
คลาส ankerl::unordered_dense::map และ ankerl::unordered_dense::set คือ (เกือบ) การแทนที่แบบดรอปอินของ std::unordered_map และ std::unordered_set ในขณะที่พวกเขาไม่มีการรับประกันความเสถียรของตัววนซ้ำ / การอ้างอิงที่แข็งแกร่ง แต่โดยทั่วไปแล้วพวกเขามักจะเร็วกว่า มาก
นอกจากนี้ยังมี ankerl::unordered_dense::segmented_map และ ankerl::unordered_dense::segmented_set ด้วยการใช้หน่วยความจำสูงสุด และตัววนซ้ำที่เสถียร/การอ้างอิงบนแทรก
ankerl::unordered_dense::hashis_transparentstd::hashauto 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_mapstd::allocators และ polymorphic allocators มี ankerl::unordered_dense::pmr typedefsstd::vector เพื่อ boost::interprocess::vector หรือคอนเทนเนอร์สุ่มที่เข้ากันได้อื่น ๆstd::vectorไม่มีอาหารกลางวันฟรีดังนั้นจึงมีข้อเสียเล็กน้อย:
const Key ใน std::pair<Key, Value> ตำแหน่งการติดตั้งเริ่มต้นคือ /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 ใช้
import ankerl.unordered_dense;และรวบรวมด้วยเช่น
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 /Set แตกต่างระหว่างแฮชที่มีคุณภาพสูง (เอฟเฟกต์ avalanching ที่ดี) และคุณภาพไม่ดี แฮชที่มีคุณภาพดีมีเครื่องหมายพิเศษ:
using is_avalanching = void ; นี่เป็นกรณีสำหรับความเชี่ยวชาญ bool , char , signed char , unsigned char , char8_t , char16_t , char32_t , wchar_t , short enum unsigned short , unsigned int int int unsigned long , long std::unique_ptr<T> long long , unsigned long long , std, std::shared_ptr<T> 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 แผนที่/ชุดนี้รองรับการโอเวอร์โหลดที่แตกต่างกันตามที่อธิบายไว้ใน p2363 ขยายคอนเทนเนอร์เชื่อมโยงกับการโอเวอร์โหลดที่แตกต่างกันที่เหลือซึ่งมีเป้าหมายสำหรับ C ++ 26 สิ่งนี้มีมากเกินไปสำหรับ find count , contains , equal_range (ดู p0919r3), erase (ดู p2077r2) และ try_emplace , insert_or_assign , operator[] , at และ insert & emplace สำหรับชุด (ดู P2363R3)
สำหรับการโอเวอร์โหลดที่แตกต่างกันที่จะส่งผลกระทบต่อทั้ง 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);
}
}; ในการใช้ประโยชน์จากแฮชนี้คุณจะต้องระบุว่าเป็นประเภทและยังมี key_equal ด้วย is_transparent เช่น std :: equal_to <>:
auto map = ankerl::unordered_dense::map<std::string, size_t , string_hash, std::equal_to<>>(); สำหรับข้อมูลเพิ่มเติมดูตัวอย่างใน test/unit/transparent.cpp . 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 เพิ่มเติมที่ค่อนข้างคล้ายกับ Node API แต่ใช้ประโยชน์จากความจริงที่ว่า
auto extract() && -> value_container_type สกัดภาชนะที่ใช้ภายใน *this ว่างเปล่า
extract() องค์ประกอบเดียว คล้ายกับ erase() ฉันมี extract() มันทำงานเหมือนกันกับ 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> โปรดทราบว่า API extract(key) ส่งคืน std::optional<value_type> ที่ว่างเปล่าเมื่อไม่พบคีย์
[[nodiscard]] auto values() const noexcept -> value_container_type const&เปิดเผยคอนเทนเนอร์ค่าพื้นฐาน
auto replace(value_container_type&& container)ทิ้งภาชนะที่จัดขึ้นภายในและแทนที่ด้วยที่ผ่านไป องค์ประกอบที่ไม่ใช่ unique จะถูกลบออกและคอนเทนเนอร์จะถูกจัดลำดับใหม่บางส่วนเมื่อพบองค์ประกอบที่ไม่ซ้ำกัน
unordered_dense ยอมรับการจัดสรรที่กำหนดเอง แต่คุณสามารถระบุคอนเทนเนอร์ที่กำหนดเองสำหรับอาร์กิวเมนต์เทมเพลตนั้น ด้วยวิธีนี้มันเป็นไปได้ที่จะแทนที่ std::vector ที่ใช้ภายในด้วยเช่น std::deque หรือภาชนะอื่น ๆ เช่น boost::interprocess::vector สิ่งนี้รองรับพอยน์เตอร์แฟนซี (เช่น Offset_ptr) ดังนั้นคอนเทนเนอร์สามารถใช้กับหน่วยความจำที่ใช้ร่วมกันเช่น boost::interprocess
แผนที่/ชุดรองรับสองประเภทที่แตกต่างกัน ค่าเริ่มต้นควรจะดีสำหรับทุกคน
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 เมื่อแทรก 10 ล้านรายการ 
Abseil เร็วที่สุดสำหรับการทดสอบการแทรกอย่างง่ายนี้ใช้เวลานานกว่า 0.8 วินาที การใช้หน่วยความจำสูงสุดประมาณ 430 MB สังเกตว่าการใช้หน่วยความจำลดลงหลังจากจุดสูงสุดครั้งสุดท้ายอย่างไร เมื่อมันลงไปที่ ~ 290MB มันได้ทำการปรับปรุงใหม่และสามารถปลดปล่อยบล็อกหน่วยความจำที่ใช้ก่อนหน้านี้ได้
ankerl::unordered_dense::segmented_map ไม่มียอดเขาเหล่านี้และแทนที่จะมีการใช้หน่วยความจำเพิ่มขึ้นอย่างราบรื่น หมายเหตุยังคงมีการลดลงอย่างฉับพลันและเพิ่มขึ้นในหน่วยความจำเนื่องจากโครงสร้างข้อมูลการจัดทำดัชนียังคงต้องเพิ่มขึ้นตามปัจจัยคงที่ แต่เนื่องจากการเก็บข้อมูลในคอนเทนเนอร์แยกต่างหากเราจึงสามารถปลดปล่อยโครงสร้างข้อมูลเก่าให้เป็นอิสระก่อนจากนั้นจัดสรรโครงสร้างการจัดทำดัชนีที่ใหญ่กว่าใหม่ ดังนั้นเราจึงไม่มียอดเขา
แผนที่/ชุดมีสองโครงสร้างข้อมูล:
std::vector<value_type> ซึ่งเก็บข้อมูลทั้งหมด MAP/SET Iterators เป็นเพียง std::vector<value_type>::iterator ! เมื่อใดก็ตามที่มีการเพิ่มองค์ประกอบจะเป็น emplace_back ไปยังเวกเตอร์ คีย์คือแฮชและมีการเพิ่มรายการ (ถัง) ที่ตำแหน่งที่สอดคล้องกันในอาร์เรย์ถัง ถังมีโครงสร้างนี้:
struct Bucket {
uint32_t dist_and_fingerprint;
uint32_t value_idx;
};แต่ละถังเก็บ 3 สิ่ง:
dist_and_fingerprint )dist_and_fingerprint )โครงสร้างนี้ได้รับการออกแบบมาเป็นพิเศษสำหรับกลยุทธ์การแก้ไขการชน Robin-Hood Hashing ด้วยการลบกะย้อนหลัง
กุญแจถูกแฮชและอาร์เรย์ที่เก็บข้อมูลจะถูกค้นหาหากมีรายการที่ตำแหน่งนั้นด้วยลายนิ้วมือนั้น เมื่อพบคีย์ในเวกเตอร์ข้อมูลจะถูกเปรียบเทียบและเมื่อเท่ากันค่าจะถูกส่งคืน
เนื่องจากข้อมูลทั้งหมดถูกเก็บไว้ในเวกเตอร์การลบจึงซับซ้อนกว่าเล็กน้อย:
value_idx ขององค์ประกอบที่ย้าย สิ่งนี้ต้องใช้การค้นหาอื่น เมื่อวันที่ 2023-09-10 ฉันทำการค้นหาอย่างรวดเร็วเกี่ยวกับ GitHub เพื่อดูว่าแผนที่นี้ใช้ในโครงการโอเพ่นซอร์สยอดนิยมหรือไม่ นี่คือบางส่วนของโครงการที่ฉันพบ กรุณาส่งข้อความถึงฉันหากคุณต้องการในรายการนั้น!
