الفرز فقط باستخدام المشغل الأقل من

Question

في C ++/STL ، يتم فرز باستخدام المشغل الأقل من فقط. ليس لدي أي فكرة عن كيفية تنفيذ خوارزميات الفرز بالفعل ، أفترض أن العمليات الأخرى يتم إنشاؤها ضمنية:

a > b *equals* b < a == true
a == b *equals* !(a < b) && !(b < a)

مقارنة باستخدام وظيفة Trivalue* المقارنة ، مثل Java على سبيل المثال ، هل هذا جيد للأداء ، أو لماذا تم اتخاذ قرار التصميم هذا؟

افتراضي هو أن أي وظيفة المقارنة Trivalue لا تزال يجب أن تنفذ هذه المقارنة في حد ذاتها ، مما يؤدي إلى نفس الأداء.

** بواسطة Trivalue مقارنة الوظيفة ، أعني دالة المقارنة التي تُرجع -1 و 0 و 1 لأقل من ، متساوية وأعلى من*

تحديث:يبدو سفينة فضائية <=> يأتي المشغل في C ++ 20 ، لذا من الواضح أن اللجنة اعتقدت أن هناك جوانب سلبية لاستخدامها فقط operator<.

Answer 1

إلى حد ما ، فإن الاثنين الأخريين ضمنين ، ولكن أكثر دقة هو القول إن نوع المقارنة ليس في الواقع بحاجة إلى يتم تنفيذ مقارنات Tri-valued ، ويتم تنفيذ أنواع C ++ بطريقة لا تستخدم واحدة من أجل تقليل السلوك المطلوب للمقارنة.

سيكون من الخطأ أن تحدد STD :: SORTS واستخدامها بشكل حصري لشيء مثل هذا:

template <typename T, typename Cmp>
int get_tri_value(const T &a, const T &b, Cmp lessthan) {
    if (lessthan(a,b)) return -1;
    if (lessthan(b,a)) return 1;
    return 0;
}

... لأنك ستنتهي بخوارزمية غير فعالة من حيث عدد المكالمات lessthan. إذا لم تفعل الخوارزمية أي شيء مفيد مع الفرق بين عودة 1 وعودة 0 ، فأنت تضيع مقارنة.

يشير C ++ إلى "أوامر ضعف صارمة". إذا < هو ترتيب ضعيف صارم ، و !(a < b) && !(b < a), ، لا بالضرورة يتبع ذلك a == b. إنهم فقط "في نفس المكان" في الطلب ، و !(a < b) && !(b < a) هي علاقة معادلة. لذلك المقارنة المطلوبة بواسطة sort الطلب #٪ s فئات التكافؤ من الكائنات ، لا يوفر ترتيبًا كليًا.

الفرق الوحيد الذي يحدثه هو ما تقوله عندما !(a < b). للحصول على ترتيب إجمالي صارم ، سوف تستنتج b <= a, ، اقرأ "أقل من أو يساوي". للحصول على ترتيب ضعيف صارم ، لا يمكنك تحديد b <= a ليعني b < a || b == a وهل هذا صحيح. C ++ محسّن حول هذا ، ولأنه يتيح للمشغل الزائد ، يجب أن يكون ذلك إلى حد كبير ، نظرًا لأن المشغلين الزائدين الذين يحتاجون إلى المصطلحات من أجل إخبار المستخدمين برمزهم ما يمكن أن يتوقعوه من حيث ارتباط المشغلين. تتحدث Java عن المقارنة وتوافق الرمز المتسق مع متساوين ، وهو كل ما تحتاجه. يجب أن يتعامل C ++ مع <،> ، == ، <= ،> = ، ما بعد التعيين ، وما إلى ذلك.

C ++ يأخذ نهجًا رياضيًا نقيًا لهذا في API ، لذلك يتم تعريف كل شيء من حيث العلاقة الثنائية الوحيدة. جافا أكثر ودية في بعض النواحي ، ويفضل المقارنات ثلاثية الاتجاه حيث يكون تعريف الوحدة الأساسية (المقارنة) أكثر تعقيدًا قليلاً ، لكن المنطق الذي يؤدي منه أبسط. وهذا يعني أيضًا أن خوارزمية الفرز تحصل على مزيد من المعلومات في المقارنة ، وهو أمر مفيد أحيانًا. على سبيل المثال ، راجع تحسين "العلم الهولندي" Quicksort ، وهو فائدة عندما يكون هناك الكثير من "في نفس المكان" يكرر في البيانات.

في هذه الحالة ، فإن المقارنة بين ثلاث قيم هي زيادة السرعة. لكن C ++ يستخدم تعريفًا ثابتًا لمقارن للفرز وأيضًا ل set و map, lower_bound وهلم جرا ، والذي بالكاد يستفيد من مقارن ثلاث قيمة (ربما حفظ مقارنة واحدة ، ربما لا). أعتقد أنهم قرروا عدم تعقيد الواجهة العامة اللطيفة والمصالح لصالح مكاسب محتملة أو محدودة الكفاءة.

Answer 2

تخميني في C ++ تم القيام به فقط لتقليل تكرار التعليمات البرمجية: بمجرد تحديد مقارن OP على فئة/نوع ، لا يمكنك فقط مقارنة هذه الكائنات عن طريق كتابة <B ، ولكن أيضًا الحصول على القدرة على فرز مجموعات من مثل هذه الأشياء.

أما بالنسبة للفرز ، فنحن بحاجة فقط إلى مشغل أقل من ذلك ، لماذا تقديم أشياء إضافية؟ قون

Answer 3

إذا كنت تشير إلى STD :: SORT () ، فإن استخدامها أقل () لا يحتاج إلى الحفاظ على الطلب النسبي للعنصر المكافئ ، لذلك سيحتاج إلى مشغل أقل () ، ومشغل أكبر ضمنيًا.

في حين أن STD :: STABLE_SORT ستحافظ عليها ، لكنها أبطأ. إنها تحتاج إلى أقل () مشغل وتكرار ثنائي الاتجاه في مقابل مشغل متساوٍ () لبناء وظيفة "Trivalue" مقارنة