كيف يتم تنفيذ Multi_index

Question

لدي بعض الصعوبات في فهم كيفية تنفيذ 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* القيمة التي تشير إلى الكائن المخزن في الصفيف. هل هذا جيد؟

Answer 1

يتم تقديم تفسير قصير للهيكل الأساسي هنا, ، مقتبس أدناه:

يعتمد التنفيذ على العقد المرتبطة بالمؤشرات ، تمامًا كما تقول المفضلة لديك 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 وما إلى ذلك ولكنك تحصل على الفكرة) [...

Answer 2

من الناحية النظرية ، نعم.

من ما أفهمه من Boost.Multiindex (لقد استخدمته ، لكن لم أر التنفيذ) ، مثالك مع اثنين ordered_unique ستقوم المؤشرات بالفعل بإنشاء حاوية ترابطية فرزتين (مثل std::map) التي تخزن المؤشرات/المراجع/المؤشرات في مجموعة مشتركة من employeeس.

في أي حال ، كل employee يتم تخزينه مرة واحدة فقط في الحاوية متعددة الفهرس ، في حين مزيج من map<string,employee> و map<int,employee> سوف تخزين كل موظف مرتين.

قد يكون هناك بالفعل صفيف (ديناميكي) داخل بعض الحاويات متعددة الفهرس ، ولكن هناك لا ضمان هذا صحيح:

مؤشرات الوصول العشوائي] لا توفر تواصل الذاكرة ، خاصية من std::vectorS التي يتم بها تخزين العناصر بجوار بعضها البعض في كتلة واحدة من الذاكرة.

ايضا، يعتمد Boost.Bimap على Boost.Multiindex والآخر يسمح بتمثيلات مختلفة لهيكل "العمود الفقري".

Answer 3

في الواقع لا أعتقد أنه كذلك.

بناء على ما يقع في detail/node_type.hpp. يبدو لي أن مثل أ std::map سوف تحتوي العقدة على كل من القيمة والفهرس. باستثناء أنه في هذه الحالة ، تختلف المؤشرات المختلفة عن بعضها البعض ، وبالتالي فإن تشابك العقدة قد يختلف فعليًا وفقًا للمؤشر الذي تتابعه.

أنا لست متأكدًا من ذلك ، من الصعب التحليل للرؤوس الداعمة ، ولكن سيكون من المنطقي إذا كنت تفكر في مصطلح الذاكرة:

• مخصصات أقل: تخصيص/تخصيص أسرع
• موقع ذاكرة التخزين المؤقت أفضل

وسأقدر إجابة نهائية ، إذا كان أي شخص يعرف عن الغور.