أفضل حاوية للفهرسة المزدوجة

Question

ما هي أفضل طريقة (في C++) لإعداد حاوية تسمح بالفهرسة المزدوجة؟على وجه التحديد، لدي قائمة بالكائنات، كل منها مفهرسة بواسطة مفتاح (ربما متعددة لكل مفتاح).وهذا يعني وجود خريطة متعددة.ومع ذلك، تكمن المشكلة في ذلك في أنه قد يكون البحث أسوأ من البحث الخطي للعثور على موقع كائن ما.أفضل تجنب تكرار البيانات، لذا فإن جعل كل كائن يحتفظ بإحداثياته ​​الخاصة ويضطر إلى تحريك نفسه في الخريطة سيكون أمرًا سيئًا (ناهيك عن أن نقل الكائن الخاص بك قد يستدعي بشكل غير مباشر المدمر الخاص بك أثناء وجوده في وظيفة عضو!).أفضّل بعض الحاويات التي تحافظ على فهرس عن طريق مؤشر الكائن والإحداثيات، وأن تضمن الكائنات نفسها مراجع/مؤشرات مستقرة.بعد ذلك، يمكن لكل كائن تخزين مكرر للفهرس (بما في ذلك الإحداثيات)، وتجريده بشكل كافٍ، ومعرفة مكانه.يبدو أن Boost.MultiIndex هي أفضل فكرة، ولكنها مخيفة جدًا ولا أريد أن تكون كائناتي الفعلية بحاجة إلى الثبات.

ماذا تنصح؟

يحرر:يبدو Boost Bimap لطيفًا، لكن هل يوفر فهرسة مستقرة؟أي أنه إذا قمت بتغيير الإحداثيات، فإن الإشارات إلى العناصر الأخرى يجب أن تظل صالحة.السبب وراء رغبتي في استخدام المؤشرات للفهرسة هو أن الكائنات ليس لها ترتيب جوهري، ويمكن أن يظل المؤشر ثابتًا أثناء تغير الكائن (مما يسمح باستخدامه في Boost MultiIndex، والذي يوفر IIRC فهرسة مستقرة).

Answer 1

أقوم بعدة افتراضات بناءً على كتابتك:

• المفاتيح رخيصة للنسخ والمقارنة
• يجب أن يكون هناك نسخة واحدة فقط من الكائن في النظام
• قد يشير نفس المفتاح إلى العديد من الكائنات، ولكن كائن واحد فقط يتوافق مع مفتاح معين (واحد لأكثر)
• تريد أن تكون قادرًا على البحث بكفاءة عن الكائنات التي تتوافق مع مفتاح معين، وأي مفتاح يتوافق مع كائن معين

أود أن أقترح:

• استخدم قائمة مرتبطة أو حاوية أخرى للاحتفاظ بقائمة عامة بجميع الكائنات الموجودة في النظام.يتم تخصيص الكائنات في القائمة المرتبطة.
• اصنع واحدا std::multimap<Key, Object *> يقوم بتعيين المفاتيح لمؤشرات الكائن، والإشارة إلى الموقع الأساسي الوحيد في القائمة المرتبطة.
• افعل واحدًا مما يلي:
  • اصنع واحدا std::map<Object *, Key> الذي يسمح بالبحث عن المفتاح المرتبط بكائن معين.تأكد من تحديث التعليمات البرمجية الخاصة بك لهذه الخريطة عند تغيير المفتاح.(قد يكون هذا أيضًا std::multimap إذا كنت بحاجة إلى علاقة متعدد إلى متعدد.)
  • إضافة متغير عضو إلى Object الذي يحتوي على التيار Key (السماح بعمليات البحث O(1)).تأكد من تحديث التعليمات البرمجية الخاصة بك لهذا المتغير عند تغيير المفتاح.

نظرًا لأن كتابتك ذكرت "الإحداثيات" كمفاتيح، فقد تكون مهتمًا أيضًا بقراءة الاقتراحات على أسرع طريقة لمعرفة ما إذا كان الإحداثي ثلاثي الأبعاد مستخدمًا بالفعل.

Answer 2

من الصعب أن تفهم بالضبط ما الذي تفعله به، ولكن يبدو أنه بمثابة تعزيز com.bimap هو ما تريد.إنها تعمل بشكل أساسي على تعزيز الفهارس المتعددة باستثناء حالة استخدام محددة، كما أنها أسهل في الاستخدام.يسمح بالبحث السريع بناءً على العنصر الأول أو العنصر الثاني.لماذا تبحث عن موقع كائن ما على الخريطة من خلال عنوانه؟استخدم التجريد واتركه يقوم بكل العمل نيابةً عنك.مجرد ملاحظة:التكرار على جميع العناصر في الخريطة هو O(N) لذلك سيكون من المضمون O(N) (ليس أسوأ) للبحث عن الطريقة التي تفكر في القيام بها.

Answer 3

يتمثل أحد الخيارات في استخدام خريطتين std::maps تشيران إلى Shared_ptrs.شيء من هذا القبيل قد يجعلك تذهب:

template<typename T, typename K1, typename K2>
class MyBiMap
{
public:
    typedef boost::shared_ptr<T> ptr_type;

    void insert(const ptr_type& value, const K1& key1, const K2& key2)
    {
        _map1.insert(std::make_pair(key1, value));
        _map2.insert(std::make_pair(key2, value));
    }

    ptr_type find1(const K1& key)
    {
        std::map<K1, ptr_type >::const_iterator itr = _map1.find(key);
        if (itr == _map1.end())
            throw std::exception("Unable to find key");
        return itr->second;
    }

    ptr_type find2(const K2& key)
    {
        std::map<K2, ptr_type >::const_iterator itr = _map2.find(key);
        if (itr == _map2.end())
            throw std::exception("Unable to find key");
        return itr->second;
    }

private:
    std::map<K1, ptr_type > _map1;
    std::map<K2, ptr_type > _map2;
};

يحرر:لقد لاحظت للتو متطلبات الخرائط المتعددة، وهذا لا يزال يعبر عن الفكرة لذا سأتركها.