هل يمكن استخدام Set_intersection مع Hash_set في C ++؟

Question

أنا أتحسب التقاطع والاتحاد والاختلافات في مجموعات. لدي TYPEDEF من النوع الخاص بي:

typedef set<node_type> node_set;

عندما يتم استبداله

typedef hash_set<node_type> node_set;

النتائج مختلفة. إنه برنامج معقد، وقبل أن أبدأ في التصحيح - هل أفعل ذلك بشكل صحيح؟ عندما أستخدم الوظائف مثل هذا:

set_intersection(v_higher.begin(), v_higher.end(), neighbors[w].begin(), neighbors[w].end(), 
            insert_iterator<node_set>(tmp1, tmp1.begin()));

• يجب أن يعملوا بسلاسة مع كل من مجموعة و hash_set؟

Answer 1

لا أعتقد ذلك.

واحدة من الشرط ما قبل set_intersection يكون:

• [first1, last1) يكون أمر بترتيب تصاعدي وفقا ل operator<. وبعد وهذا هو، لكل زوج من المحفين i و j في [first1, last1) مثل ذلك i يسبق j, *j < *i هو زائف.

ال hash_set (و unordered_set) غير مرتبة، لذلك لا يمكن أن تكون الحالة المطلوبة راضية.

يرى TR1 :: Undered_set الاتحاد والتقاطع حول كيفية التقاطع unordered_setس.

Answer 2

انا ذاهب الى الذهاب مع لا. تذكر hash_set ليس C ++ قياسي ولا سيكون أبدا، إنه امتداد أقدم لم يعد مدعوما. تسمى الأحدث "خرائط التجزئة" unordered_set و unordered_map, ، متوفر في TR1، دفعة، و C ++ 0x.

السبب في أنه لا هو ذلك set_intersection يتطلب أن يتم فرز بيانات الإدخال. بالذين، السبب في أن خريطة التجزئة سريعة جدا هي أن تتخلى عن الطلب. من الواضح أن هذا واضح تحت الاسم unordered_set. وبعد لذلك لا يمكن تحقيق الشرط المسبق بشكل موثوق.

Answer 3

لا، لا يمكنك استخدام set_intersection لأن set_intersection يتطلب أن يتم طلب المجموعتين (باستخدام نفس الطلب). لم يتم طلب مجموعات التجزئة بأي شكل من الأشكال. في C ++ 0x سوف يسمى في الواقع unordered_set.