كيف يتم تنفيذ Multi_index
-
25-09-2019 - |
سؤال
لدي بعض الصعوبات في فهم كيفية تنفيذ Boost.MultiIndex. لنقول إن لدي ما يلي:
typedef multi_index_container<
employee,
indexed_by<
ordered_unique<member<employee, std::string, &employee::name> >,
ordered_unique<member<employee, int, &employee::age> >
>
> employee_set;
أتصور أن لدي مجموعة واحدة ، Employee[]
, ، الذي يخزن في الواقع employee
الكائنات ، وخرائط
map<std::string, employee*>
map<int, employee*>
مع الاسم والعمر كمفاتيح. كل خريطة لديها employee*
القيمة التي تشير إلى الكائن المخزن في الصفيف. هل هذا جيد؟
المحلول
يتم تقديم تفسير قصير للهيكل الأساسي هنا, ، مقتبس أدناه:
يعتمد التنفيذ على العقد المرتبطة بالمؤشرات ، تمامًا كما تقول المفضلة لديك std::set
التنفيذ. سأوضح قليلاً على هذا: أ std::set
عادة ما يتم تنفيذها كـ RB Tree حيث تبدو العقد
struct node
{
// header
color c;
pointer parent,left,right;
// payload
value_type value;
};
حسنا ، أ multi_index_container
العقدة هي أساسا "multinode" مع العديد من الرؤوس مثل المؤشرات وكذلك الحمولة. على سبيل المثال ، أ multi_index_container
مع اثنين من المؤشرات المطلوبة يستخدمون عقدة داخلية تبدو
struct node
{
// header index #0
color c0;
pointer parent0,left0,right0;
// header index #1
color c1;
pointer parent1,left1,right2;
// payload
value_type value;
};
(الواقع أكثر تعقيدًا ، يتم إنشاء هذه العقد من خلال بعض metaprogramming وما إلى ذلك ولكنك تحصل على الفكرة) [...
نصائح أخرى
من الناحية النظرية ، نعم.
من ما أفهمه من Boost.Multiindex (لقد استخدمته ، لكن لم أر التنفيذ) ، مثالك مع اثنين ordered_unique
ستقوم المؤشرات بالفعل بإنشاء حاوية ترابطية فرزتين (مثل std::map
) التي تخزن المؤشرات/المراجع/المؤشرات في مجموعة مشتركة من employee
س.
في أي حال ، كل employee
يتم تخزينه مرة واحدة فقط في الحاوية متعددة الفهرس ، في حين مزيج من map<string,employee>
و map<int,employee>
سوف تخزين كل موظف مرتين.
قد يكون هناك بالفعل صفيف (ديناميكي) داخل بعض الحاويات متعددة الفهرس ، ولكن هناك لا ضمان هذا صحيح:
مؤشرات الوصول العشوائي] لا توفر تواصل الذاكرة ، خاصية من
std::vector
S التي يتم بها تخزين العناصر بجوار بعضها البعض في كتلة واحدة من الذاكرة.
ايضا، يعتمد Boost.Bimap على Boost.Multiindex والآخر يسمح بتمثيلات مختلفة لهيكل "العمود الفقري".
في الواقع لا أعتقد أنه كذلك.
بناء على ما يقع في detail/node_type.hpp
. يبدو لي أن مثل أ std::map
سوف تحتوي العقدة على كل من القيمة والفهرس. باستثناء أنه في هذه الحالة ، تختلف المؤشرات المختلفة عن بعضها البعض ، وبالتالي فإن تشابك العقدة قد يختلف فعليًا وفقًا للمؤشر الذي تتابعه.
أنا لست متأكدًا من ذلك ، من الصعب التحليل للرؤوس الداعمة ، ولكن سيكون من المنطقي إذا كنت تفكر في مصطلح الذاكرة:
- مخصصات أقل: تخصيص/تخصيص أسرع
- موقع ذاكرة التخزين المؤقت أفضل
وسأقدر إجابة نهائية ، إذا كان أي شخص يعرف عن الغور.