Boost.Intrusive وunordered_map

Question

إنني أتطلع إلى استخدام خريطة غير مرتبة تدخلية.لسبب ما لا يوجد سوى مجموعة غير مرتبة في المكتبة.يوجد أيضًا جدول تجزئة متطفل ولكني لست متأكدًا من أنه يتمتع بنفس الوظيفة، كما أنه لا يحتوي على نفس الواجهة.
هل أنا مخطئ وفقدت الرابط unordered_map؟
إذا لم أكن هناك برنامج تعليمي من شأنه أن يساعدني في تنفيذ واحد؟

Answer 1

إنه سؤال مثير للاهتمام.يبدو أن Boost.Intrusive لا يوفر أي واجهة خريطة، مرتبة أو غير مرتبة.يحتوي على الكثير من أنواع التنفيذ التي ستعمل بشكل جيد كخرائط مرتبة (أشجار حمراء-سوداء، وأشجار AVL، وأشجار متباعدة) وغير مرتبة (جداول التجزئة).لكن لا توجد خرائط ولا أستطيع أن أخبرك بالسبب.

أمامك خياران كما أرى:

1. مجرد استخدام hashtable:يتم تنفيذ الحاويات غير المرتبة كجداول تجزئة (والسبب الوحيد لعدم تنفيذها مُسَمًّى hash_map هو تجنب تضارب الأسماء مع المكتبات الموجودة مسبقًا والتي تستخدم هذا الاسم بالفعل).سيعمل ذلك إذا كنت تريد إنجاز عملك.
2. إذا كنت تريد حقًا تنفيذ ما تريده بنفسك، فأنت تريد إلقاء نظرة على وصف واجهة Boost.Intrusive's unordered_set.لم ألقي نظرة على التنفيذ ولكن من المؤكد تقريبًا أنه عبارة عن غلاف حول واحد أو أكثر من أنواع الأشجار. std::set و std::map يتم تنفيذهما عادةً كمغلفات حول شجرة حمراء-سوداء (في جميع تطبيقات المكتبات القياسية التي نظرت إليها:دول مجلس التعاون الخليجي، وMSVC، وStdcxx من أباتشي).تعرف أيضًا على كيفية تغليف libstdc++ بتنفيذ الشجرة الخاصة بهم <map> و في <set>.إنها نموذجية كثيرة، ومعظمها مملة، لكن كلا النوعين يؤجلان كل العمل تقريبًا إلى الشجرة.من المؤكد أن شيئًا مشابهًا يحدث مع Boost.Intrusive unordered_set.سوف تحتاج إلى إلقاء نظرة على الاختلافات بين الخريطة وتعيين الواجهات، واستخدام ذلك كأساس للتعديل unordered_set داخل unordered_map.

لقد فعلت هذا الأخير.إنه أمر ممل بعض الشيء، وأنا أوصي بشدة بكتابة اختبارات الوحدة له (أو سرقة الاختبارات التي تأتي مع libstdc++ أو Boost.Intrusive).لكنه قابل للتنفيذ.كما أوصي بشدة بقراءة وثائق المتطلبات الخاصة بالمجموعات والخرائط، سواء في SGI (تعيين, خريطة) أو ل libstdc++

تحديث: أدركت لماذا لا يقومون بعمل الخرائط:تتطلب الحاويات المتطفلة تضمين معلومات العقدة الخاصة ببنية البيانات في نوع القيمة التي تخزنها فيها.بالنسبة للخرائط، يجب عليك القيام بذلك لكلتا القيمتين والمفاتيح.لا يعني ذلك أن هذا غير ممكن، ولكن التنفيذ القياسي لـ map يستخدم نفس النوع الداخلي مثل setافعل.ولكن تلك الأنواع الداخلية لديها فقط واحد value_type عامل:لتخزين المفاتيح والقيم، يقومون بنسخ المفتاح والقيمة إلى هذا المتغير وتخزينها في العقد.للقيام بذلك مع نوع تدخلي (أي.بدون نسخ) سيتعين عليك تعديل نوع التنفيذ هذا ليكون غير متوافق مع المجموعات:يجب عليه تخزين المراجع إلى المفاتيح والقيم بشكل منفصل.لذا، للقيام بذلك، عليك أيضًا تعديل التطبيق الذي تستخدمه (ربما hashtable).مرة أخرى، هذا ليس مستحيلًا، ولكن من المحتمل أن يحاول مصممو المكتبة تجنب تكرار التعليمات البرمجية بشكل خطير، لذا في غياب طريقة بسيطة لتنفيذ ذلك، فقد قرروا على الأرجح ترك الخرائط.

هل هذا منطقي؟

Answer 2

ولقد مضى وقت طويل منذ تم طرح هذا السؤال، ولكن أعتقد أن الناس يأتون إلى هنا يجب أن تكون مهتمة في كيفية استخدام unordered_set كخريطة. الحل هو استخدام أساليب الإدراج المتقدمة : واحد لديه فقط لتخزين مفتاح وقيمته في نفس value_type، وأدخله باستخدام <لأ href = "http://www.boost.org/doc/libs/1_50_0/doc/html/boost/intrusive/unordered_set.html#id1267354-bb "> insert_check و insert_commit .