unordered_dense
v4.5.0
HashMap سريع المخزنة ومكثفًا وهاشست على أساس حذف التحول الخلفي لـ Robin-Hood لـ C ++ 17 وما بعده.
الفصول 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 مع استخدام ذاكرة الذروة المنخفضة. و iterator مستقرة/المراجع على إدراج.
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_set segmented_map يتمتع التصميم المختار ببعض المزايا على std::unordered_map :
std::vector ، كل البيانات متجاورة!absl::flat_hash_mapstd::allocators ، والمخصصات المتعددة الأشكال. هناك ankerl::unordered_dense::pmr typedefs المتاحةstd::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 واستخدام الوحدة الناتجة ، على سبيل المثال SO:
clang++ -std=c++20 -I include --precompile -x c++-module src/ankerl.unordered_dense.cpp
clang++ -std=c++20 -c ankerl.unordered_dense.pcm لاستخدام الوحدة النمطية مع EG في module_test.cpp ، استخدم
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 ; هذه هي حالات التخصصات التي تخصصها bool ، char ، signed char ، unsigned char ، char8_t ، char16_t ، char32_t ، wchar_t ، short ، unsigned short ، int ، unsigned int unsigned long long long long enum std::shared_ptr<T> unsigned long long ، std::basic_string<C> ، T* std::unique_ptr<T> 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 :: adqual_to <>:
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) لدينا واجهة برمجة تطبيقات إضافية تشبه إلى حد ما واجهة برمجة تطبيقات العقدة ، ولكنها تعني حقيقة أن حاوية وصول عشوائية داخليًا:
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> لاحظ أن واجهة برمجة تطبيقات extract(key) تُرجع std::optional<value_type> فارغة عند عدم العثور على المفتاح.
[[nodiscard]] auto values() const noexcept -> value_container_type const&يعرض حاوية القيم الأساسية.
auto replace(value_container_type&& container)يتجاهل الحاوية الممنوحة داخليًا ويحل محلها بالذات. تتم إزالة العناصر غير الundique ، وسيتم إعادة ترتيب الحاوية جزئيًا عند العثور على عناصر غير unique.
يقبل unordered_dense مخصصًا مخصصًا ، ولكن يمكنك أيضًا تحديد حاوية مخصصة لهذه الوسيطة القالب. وبهذه الطريقة ، من الممكن استبدال std::vector المستخدمة داخليًا بـ EG std::deque أو أي حاوية أخرى مثل boost::interprocess::vector . هذا يدعم المؤشرات الفاخرة (على سبيل المثال Offset_PTR) ، بحيث يمكن استخدام الحاوية مع مثل EG Memory CHERSED بواسطة boost::interprocess .
الخريطة/المجموعة تدعم نوعين مختلفين دلو. يجب أن يكون الافتراضي جيدًا للجميع.
ankerl::unordered_dense::bucket_type::standardankerl::unordered_dense::bucket_type::bigsegmented_set segmented_map يوفر ankerl::unordered_dense تطبيق حاوية مخصص له متطلبات ذاكرة أقل من ناقل std::vector . الذاكرة ليست متجاورة ، لكنها يمكن تخصيص شرائح دون الحاجة إلى إعادة تخصيص جميع العناصر ونقلها. باختصار ، هذا يؤدي إلى
std::vector لأن هناك حاجة إلى عدم توجيه إضافي. فيما يلي مقارنة مع absl::flat_hash_map و ankerl::unordered_dense::map عند إدخال 10 مليون مشاركة 
Abseil هو الأسرع في هذا الاختبار الإدراج البسيط ، ويستغرق أكثر قليلاً من 0.8 ثانية. إنه استخدام ذاكرة الذروة حوالي 430 ميجابايت. لاحظ كيف ينخفض استخدام الذاكرة بعد الذروة الأخيرة ؛ عندما تنخفض إلى حوالي 290 ميجابايت ، انتهى الأمر من إعادة صياغة ويمكن أن يحرر كتلة الذاكرة المستخدمة مسبقًا.
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 لمعرفة ما إذا كانت هذه الخريطة تستخدم في أي مشاريع مفتوحة المصدر شهيرة. فيما يلي بعض المشاريع التي وجدتها. من فضلك أرسل لي ملاحظة إذا كنت تريد في تلك القائمة!
