write - or in c++ on keyboard




الحيل المقارنة في C++ (7)

هل لديها فكرة أفضل؟ شكرا للمشاركة !

هناك alititithm القياسية لذلك:

using std::vector; // & std::begin && std::end

// if(data is equal to one of these(1,2,3,4,5,6))
/* maybe static const */vector<int> criteria{ 1, 2, 3, 4, 5, 6 };
return end(criteria) != std::find(begin(criteria), end(criteria), data);

تحرير: (الكل في مكان واحد):

bool is_equal_to_one_of_these(int data, const std::vector<int>& criteria)
{
    using std::end; using std::begin; using std::find;
    return end(criteria) != find(begin(criteria), end(criteria), data);
}

auto data_matches = is_equal_to_one_of_these(data, {1, 2, 3, 4, 5, 6});

تصحيح:

أفضل الواجهة من حيث المتجه ، بدلاً من قائمة المُهيئ ، لأنها أقوى:

std:vector<int> v = make_candidate_values_elsewhere();
auto data_matches = is_equal_to_one_of_these(data, v);

لا is_equal_to_one_of_these الواجهة (باستخدام متجه) بتحديد القيم ، حيث تتصل بـ is_equal_to_one_of_these .

صف:

class foo{
public:
    int data;
};

أريد الآن إضافة طريقة إلى هذه الفئة ، لإجراء بعض المقارنة ، لمعرفة ما إذا كانت بياناتها مساوية لواحد من الأرقام المعطاة.

بالطبع ، أستطيع أن أكتب if(data==num1|| data == num2|| data ==num3.....) ، لكن بصراحة ، أشعر بالغثيان عندما أكتب data == كل مرة if(data==num1|| data == num2|| data ==num3.....) بـ رقم.

لذلك ، آمل أن أتمكن من كتابة شيء مثل هذا:

if(data is equal to one of these(num1,num2,num3,num4,num5...))
    return true;
else
    return false;

أريد تنفيذ هذا البيان ، data is equal to one of these(num1, num2, num3, num4, num5...)

ها هي طريقتي:

#include <stdarg.h>
bool is_equal_to_one_of_these(int count,...){
    int i;
    bool equal = false;
    va_list arg_ptr;
    va_start(arg_prt,count);
    for(int x=0;x<count;x++){
        i = va_arg(arg_ptr,int);
        if( i == data ){
            equal = true;
            break;
        }
    }
    va_end(arg_ptr);
    return equal;
}

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

هل لدى أي شخص فكرة أفضل؟


الطريق السهل

الطريقة الأبسط هي كتابة مجمّع وظيفة عضو يسمى in() حول std::find مع زوج من التكرارات للبحث عن البيانات المعنية. كتبت template<class It> in(It first, It last) بسيطًا template<class It> in(It first, It last) وظيفة العضو template<class It> in(It first, It last) لذلك

template<class It>
bool in(It first, It last) const
{
    return std::find(first, last, data) != last;
}

إذا لم يكن لديك وصول إلى مصدر foo ، فيمكنك كتابة وظائف غير أعضاء في template<class T> bool in(foo const&, std::initializer_list<T>) التوقيع template<class T> bool in(foo const&, std::initializer_list<T>) وما إلى ذلك ، ومن ثم تسميتها مثل

in(f, {1, 2, 3 });

الطريق الصعب

ولكن دعنا ننتقل مع ذلك تمامًا: أضف فقط اثنين من الأحمال public الإضافية:

  • واحد يأخذ معلمة std::initializer_list التي تستدعي المعلمة السابقة مع التكرارات start begin() و end() من وسيطة قائمة مهيئ المقابلة.
  • واحدة للحاوية التعسفية كمدخلات من شأنها أن تفعل القليل من العلامة إرسال إلى اثنين من الأحمال الزائدة private من المساعد detail_in() :
    • التحميل الزائد الذي يقوم بخدعة SFINAE مع decltype(c.find(data), bool()) لنوع الإرجاع decltype(c.find(data), bool()) التي ستتم إزالتها من مجموعة التحميل الزائد إذا لم تكن الحاوية c المعنية تحتوي على وظيفة عضو find() ، bool بخلاف ذلك (يتم تحقيق ذلك من خلال استغلال عامل التشغيل الفاصلة داخل decltype )
    • حمل زائد واحد احتياطي يأخذ ببساطة begin() end() التكرارات والمفوضين إلى الأصل in() مع اثنين من التكرارات

نظرًا لأن العلامات الخاصة detail_in() تشكل التسلسل الهرمي للميراث (يشبه إلى حد كبير علامات التكرار القياسية) ، فإن الحمولة الزائدة الأولى سوف تتطابق مع الحاويات الترابطية std::set و std::unordered_set وأولاد العمومة. جميع الحاويات الأخرى ، بما في ذلك C-arrays ، std::array ، std::vector و std::list ، ستطابق التحميل الزائد الثاني.

#include <algorithm>
#include <array>
#include <initializer_list>
#include <type_traits>
#include <iostream>
#include <set>
#include <unordered_set>
#include <vector>

class foo
{
public:
    int data;

    template<class It>
    bool in(It first, It last) const
    {
        std::cout << "iterator overload: ";
        return std::find(first, last, data) != last;
    }

    template<class T>
    bool in(std::initializer_list<T> il) const
    {
        std::cout << "initializer_list overload: ";
        return in(begin(il), end(il));
    }

    template<class Container>
    bool in(Container const& c) const 
    {
        std::cout << "container overload: ";
        return detail_in(c, associative_container_tag{});    
    }

private:
    struct sequence_container_tag {};
    struct associative_container_tag: sequence_container_tag {};

    template<class AssociativeContainer>
    auto detail_in(AssociativeContainer const& c, associative_container_tag) const 
    -> decltype(c.find(data), bool())
    {
        std::cout << "associative overload: ";
        return c.find(data) != end(c);    
    }

    template<class SequenceContainer> 
    bool detail_in(SequenceContainer const& c, sequence_container_tag) const
    {
        std::cout << "sequence overload: ";
        using std::begin; using std::end;
        return in(begin(c), end(c));    
    }
};

int main()
{
    foo f{1};
    int a1[] = { 1, 2, 3};
    int a2[] = { 2, 3, 4};

    std::cout << f.in({1, 2, 3}) << "\n";
    std::cout << f.in({2, 3, 4}) << "\n";

    std::cout << f.in(std::begin(a1), std::end(a1)) << "\n";
    std::cout << f.in(std::begin(a2), std::end(a2)) << "\n";

    std::cout << f.in(a1) << "\n";
    std::cout << f.in(a2) << "\n";

    std::cout << f.in(std::array<int, 3>{ 1, 2, 3 }) << "\n";
    std::cout << f.in(std::array<int, 3>{ 2, 3, 4 }) << "\n";

    std::cout << f.in(std::vector<int>{ 1, 2, 3 }) << "\n";
    std::cout << f.in(std::vector<int>{ 2, 3, 4 }) << "\n";

    std::cout << f.in(std::set<int>{ 1, 2, 3 }) << "\n";
    std::cout << f.in(std::set<int>{ 2, 3, 4 }) << "\n";

    std::cout << f.in(std::unordered_set<int>{ 1, 2, 3 }) << "\n";
    std::cout << f.in(std::unordered_set<int>{ 2, 3, 4 }) << "\n";    
}

مثال حي - على كل الحاويات الممكنة - يطبع 1 و 0 لكلا مجموعتي الأرقام.

حالات الاستخدام std::initializer_list الزائد std::initializer_list مخصصة لاختبار أعضاء السفينة لمجموعات صغيرة من الأرقام التي تكتبها بشكل صريح في رمز الاتصال. يحتوي على تعقيد O(N) ولكن يتجنب أي تخصيصات كومة الذاكرة المؤقتة.

لأي شيء ثقيل مثل اختبار العضوية للمجموعات الكبيرة ، يمكنك تخزين الأرقام في حاوية multi_set مثل std::set أو أبناء عمومة multi_set أو unordered_set . سينتقل هذا إلى الكومة عند تخزين هذه الأرقام ، ولكن يحتوي على بحث O(log N) أو حتى تعقيد بحث O(1) .

ولكن إذا كان لديك فقط حاوية تسلسلية مليئة بالأرقام المحيطة ، فيمكنك أيضًا رميها إلى الفصل وستحسب بحسارة العضوية لك في زمن O(N) .


إذا كانت data بالفعل عبارة عن نوع متكامل أو تعداد ، فيمكنك استخدام رمز switch :

switch (data) {
  case 1:
  case 2:
  case 2000:
  case 6000:
  case /* whatever other values you want */:
    act_on_the_group();
    break;
  default:
    act_on_not_the_group();
    break;
}

إذا كانت البيانات ، num1 ، .. num6 بين 0 و 31 ، فيمكنك استخدامها

int match = ((1<<num1) | (1<<num2) | ... | (1 << num6));
if( ( (1 << data) & match ) != 0 ) ...

إذا كانت الأرقام من 1 إلى num6 عبارة عن ثوابت ، فسوف يقوم المحول البرمجي بحساب المطابقة في وقت الترجمة.


انها ليست جميلة ، ولكن هذا يجب أن يعمل:

class foo {
    bool equals(int a) { return a == data; }
    bool equals(int a, int b) { return (a == data) || (b == data); }
    bool equals(int a, int b, int c) {...}     
    bool equals(int a, int b, int c, int d) {...} 
private:
    int data; 
}

وما إلى ذلك وهلم جرا. سوف يمنحك بناء الجملة الصحيح الذي كنت عليه بعد. لكن إذا كنت بعد العدد المتغير تمامًا من الوسائط ، فربما تكون قائمة المتجه أو std :: initalizer هي الطريقة التي يجب اتباعها:

راجع: http://en.cppreference.com/w/cpp/utility/initializer_list

يوضح هذا المثال في العمل:

#include <assert.h>
#include <initializer_list>

class foo {
public:
        foo(int d) : data(d) {}
        bool equals_one_of(std::initializer_list<int> options) {
                for (auto o: options) {
                        if (o == data) return true;
                }
                return false;
        }
private:
        int data;
};

int main() {
        foo f(10);
        assert(f.equals_one_of({1,3,5,7,8,10,14}));
        assert(!f.equals_one_of({3,6,14}));
        return 0;
}

هناك العديد من الطرق للقيام بذلك مع STL.

إذا كان لديك عدد كبير بشكل لا يصدق من العناصر وتريد اختبار ما إذا كان عنصرك المعطى عضوًا في هذه المجموعة ، فاستخدم set أو unordered_set . إنها تسمح لك بالتحقق من العضوية في log n والوقت الثابت على التوالي.

إذا احتفظت بالعناصر الموجودة في مصفوفة مرتبة ، binary_search أيضًا العضوية في log n time.

بالنسبة للصفائف الصغيرة ، فإن search الخطي قد يشكّل بشكل أسرع (حيث لا يوجد فرعي). قد يقوم البحث الخطي بإجراء مقارنات 3-8 في الوقت الذي يستغرقه البحث الثنائي "للقفز" . يقترح منشور المدونة هذا وجود نقطة التعادل عند 64 عنصر تقريبًا ، أدناه قد يكون البحث الخطي أسرع ، على الرغم من أن هذا يعتمد بشكل واضح على تطبيق STL وتحسينات برنامج التحويل البرمجي والتنبؤ بفرع الهندسة المعمارية لديك.


يعد الخيار خيارًا جيدًا ، ولكن إذا كنت ترغب حقًا في تدوين ملفك الشخصي ، فإن أداة التهيئة الأولي هي:

bool is_in( int val, initializer_list<int> lst )
{
    for( auto i : lst )
        if( i == val ) return true;
    return false;
}

استخدام تافهة:

is_in( x, { 3, 5, 7 } ) ;

انها يا (ن) ، مجموعة / غير مرتبة أسرع





comparison