بحث غير متجانس في الحاويات الترابطية في C ++

تعمل الحاويات الترابطية C ++ مع نوع مفتاح معين. للبحث عنها باستخدام مفتاح من هذا النوع ( std :: string ، std :: string_view ، const char * ) ، يمكن أن نتحمل خسائر كبيرة في الأداء. في هذه المقالة ، سأوضح لك كيفية تجنب ذلك باستخدام ميزة بحث غير متجانسة تمت إضافتها مؤخرًا.

وجود حاوية std :: map <std :: string، int> يجب أن يتم إعلامنا بالتكلفة العالية المحتملة عند البحث (وبعض العمليات الأخرى باستخدام مفتاح كمعامل ) عليها بأسلوب c.find ("hello world") . الحقيقة هي أن كل هذه العمليات تتطلب افتراضيًا مفتاحًا من النوع المطلوب ، وفي حالتنا يكون هو std :: string . نتيجة لذلك ، عند استدعاء find ، نحتاج إلى إنشاء مفتاح من النوع std :: string ضمنيًا من const char * ، مما سيكلفنا في أحسن الأحوال memcpy إضافية (إذا كان تطبيق المكتبة القياسي الخاص بنا يحتوي على "تحسين سلسلة صغيرة" والمفتاح قصير) ، و أيضا strlen اضافية(ما لم يخمن المترجم أو ليس لديه طريقة لحساب طول السطر في وقت الترجمة). في أسوأ الحالات ، سيتعين عليك الدفع بالكامل: من خلال تخصيص الذاكرة وتحريرها من الكومة لمفتاح مؤقت في مكان يبدو مسطحًا ، وقد يكون هذا بالفعل مشابهًا لوقت البحث نفسه.

يمكننا تجنب العمل غير الضروري مع البحث غير المتجانس. تم إضافة وظائف لتشغيلها الصحيحة للحاويات أمر ( مجموعة ، مولتيست ، خريطة ، multimap ) في جميع أماكن مماثلة منذ C ++ 14 مستوى وغير مرتبة حاويات ( unordered_set ، unordered_multiset ، unordered_map ، unordered_multimap ) منذ C ++ 20.

//  C++14      
iterator find(const Key& key);
const_iterator find(const Key& key) const;

//   C++14      
template < class K > iterator find(const K& x);
template < class K > const_iterator find(const K& x) const;

ولكن ، كما هو الحال دائمًا ، في C ++ ، هناك مشكلة في هذا المكان ، واسمه هو المقارنة الافتراضية. المقارن الافتراضي لـ std :: map <std :: string، int> هو std :: less <std :: string> الذي تم إعلان وظيفة المقارنة الخاصة به على النحو التالي:

//  T    , .. std::string
bool operator()(const T& lhs, const T& rhs) const;

لا يمكن استخدامه لمقارنتنا غير المتجانسة ، لأنه لا يزال لديه نفس المشاكل (تحتاج إلى إنشاء نوع معين من المفاتيح). يأتي التخصص std :: less <void> للإنقاذ ، وهو خالي من هذه المشاكل.

template <>
struct less<void> {
    using is_transparent = void;

    template < class T, class U >
    bool operator()(T&& t, U&& u) const {
        return std::forward<T>(t) < std::forward<U>(u);
    }
};

شيء من هذا القبيل يبدو مثل هذا التخصص، فاتني نقطة مع constexprو noexceptالبساطة من الوصف.

في علامة is_transparent يقول الحاويات التي هذه المقارنة هي قادرة على المقارنة غير المتجانسة والتي وظائف البحث غير المتجانسة الجديدة تصبح متاحة على ذلك.

, operator<(const std::string&, const char*) :

std::map<std::string, int, std::less<>> c;
c.find("hello world");

, , , operator< . - , , std::thread std::set std::thread::id.

struct thread_compare {
    using is_transparent = void;

    bool operator()(const std::thread& a, const std::thread& b) const {
        return a.get_id() < b.get_id();
    }

    bool operator()(const std::thread& a, std::thread::id b) const {
        return a.get_id() < b;
    }

    bool operator()(std::thread::id a, const std::thread& b) const {
        return a < b.get_id();
    }
};

//      
std::set<std::thread, thread_compare> threads;

//     id
threads.find(std::this_thread::get_id());

حسنًا ، لا تنس أن هذا لا يتعلق فقط بالوظيفة find. فقط هذه المخاوف وظائف: count، equal_range، lower_bound، upper_boundو contains.

بحث غير متجانس سعيد ، عزيزي القارئ!