سلسلة ++c للمحترفين خوارزميات المكتبة القياسية std في Cpp

std::next_permutation

المثال التالي يبدل تسلسل المجال [first, last] ويحوّله إلى التبديل التالي الأعلى في الترتيب المعجمي (lexicographically higher permutation)، ويمكن تخصيص قاعدة التبديل عبر ‎cmpFun‎.

template < class Iterator >
  bool next_permutation(Iterator first, Iterator last);
template < class Iterator, class Compare >
  bool next_permutation(Iterator first, Iterator last, Compare cmpFun);

المعاملات

• ‎first‎ - بداية المجال المُراد تبديله (مُضمّن)
• ‎last‎ - نهاية المجال المراد تبديله (غير مُضمّن)

القيمة المعادة

تعيد true إن كان التبديل موجودًا، وخلاف ذلك، يُحوّل المجال إلى أصغر تبديل معجمية (lexicographically smallest permutation)، ثم تُعاد القيمة false.

التعقيد Complexity

التعقيد يساوي O(n)‎، حيث تمثّل n المسافة من ‎first‎ إلى ‎last‎. إليك المثال التالي:

std::vector< int > v { 1, 2, 3 }; 
do {
  for (int i = 0; i < v.size(); i += 1) {
    std::cout << v[i];
  }
  std::cout << std::endl;
} while (std::next_permutation(v.begin(), v.end()));

هذا يطبع جميع تقليبات المجال 1،2،3 وفق ترتيب معجمي تصاعدي.

الخرج:

123
132
213
231
312
321

std::for_each

في الشيفرة أدناه، نطبّق الدالّة ‎f‎ على نتيجة تحصيل كلّ مُكرّر في المجال ‎[first, last)‎ بدءًا من ‎first‎ وحتى ‎last - 1‎.

template < class InputIterator, class Function >
  Function for_each(InputIterator first, InputIterator last, Function f);

المعاملات

• ‎first, last‎ - المجال الذي ستُطبّق ‎f‎ عليه.
• ‎f‎ - كائن قابل للاستدعاء يُطبّق على نتيجة تحصيل كل مكرّر في المجال [‎first, last‎).

القيمة المُعادة

تعاد ‎f‎ إن كان الإصدار أقدم من C++‎ 11، وإلّا فستُعاد std::move(f)‎.

التعقيد

تُطبّق ‎f‎ عدد ‎last - first‎ مرّة.

مثال

الإصدار ≥ C++‎ 11

std::vector<int> v { 1, 2, 4, 8, 16 };
std::for_each(v.begin(), v.end(), [](int elem) {
  std::cout << elem << " ";
});

تطبيق الدالّة المُعطاة على كل عنصر من المتجه ‎v‎ يؤدي إلى طباعة هذا العنصر في مجرى الخرج ‎stdout‎.

std::accumulate

هذه الخوارزمية مُعرّّفة في الترويسة

template < class InputIterator, class T >
  T accumulate(InputIterator first, InputIterator last, T init); // (1)

template < class InputIterator, class T, class BinaryOperation >
  T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation f); // (2)

تُجرى std::accumulate عملية الطي (fold operation) باستخدام الدالّة ‎f‎ على المجال ‎[first, last)‎ بدءا من ‎init‎ كقيمة تراكمية (accumulator value)، وهذا يكافئ:

T acc = init;
for (auto it = first; first != last; ++it)
  acc = f(acc, * it);
return acc;

في الإصدار (1)، يُستخدم ‎operator+‎ بدلًا من ‎f‎، لذا فإنّ مراكمة قيمِ حاويةٍ يعادل مجموع عناصر تلك الحاوية.

المعاملات

• ‎first, last‎ - المجال الذي ستُطبّق ‎f‎ عليه.
• ‎init‎ - القيمة الأولية للتراكم.
• ‎f‎ - دالّة الطي الثنائية (binary folding function).

القيمة المُعادة

القيمة المتراكمة الناتجة عن التطبيق المتتابع للدالّة ‎f‎.

التعقيد

التعقيد يساوي O(n × k)‎، و n هنا يمثّل المسافة من ‎first‎ إلى ‎last‎، فيما تمثّل O(k)‎ تعقيد الدالّة ‎f‎. انظر المثال البسيط التالي عن مُراكمة الجَمْع:

std::vector<int> v { 2, 3, 4 };
auto sum = std::accumulate(v.begin(), v.end(), 1);
std::cout << sum << std::endl;

الناتج سيكون:

10

تحويل الأرقام (digits) إلى عدد (number):

الإصدار<C++‎ 11

class Converter {
  public:
    int operator()(int a, int d) const {
      return a * 10 + d;
    }
};

ثمّ:

const int ds[3] = {1, 2, 3};
int n = std::accumulate(ds, ds + 3, 0, Converter());
std::cout << n << std::endl;

الإصدار ≥ C++‎ 11

const std::vector<int> ds = {1, 2, 3};
int n = std::accumulate(ds.begin(), ds.end(),
 0,
[](int a, int d) { return a * 10 + d; });
std::cout << n << std::endl;

الناتج سيكون:

123

std::find

تساعد std::find على العثور على أوّل ظهور لعنصر val داخل مجال ‎[first, last)‎‎‎.

template < class InputIterator, class T >
  InputIterator find (InputIterator first, InputIterator last, const T& val);

المعاملات

• ‎first‎ : يمثل مُكرّرًا يشير إلى بداية المجال.
• ‎last‎ يمثل مُكرّرًا يشير إلى نهاية المجال.
• ‎val‎ يمثل القيمة المبحوث عنها داخل المجال.

القيمة المعادة

يُعاد مكرِّر يشير إلى أوّل عنصر في المجال يساوي (==) val، أما إن لم يكن هناك عنصر يحقّق ذلك، فسيُعاد مكرّر يشير إلى last. انظر المثال التالي:

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;
int main(int argc,
  const char * argv[]) {

سننشئ متجهًا هنا:

 vector<int> intVec {4, 6, 8, 9, 10, 30, 55,100, 45, 2, 4, 7, 9, 43, 48};

ثم نعرِّف المكرِّرات:

  vector < int > ::iterator itr_9;
  vector < int > ::iterator itr_43;
  vector < int > ::iterator itr_50;

والآن نستدعي find:

  itr_9 = find(intVec.begin(), intVec.end(), 9); //occurs twice
  itr_43 = find(intVec.begin(), intVec.end(), 43); //occurs once

  // قيمة غير موجودة في المتجهة
  itr_50 = find(intVec.begin(), intVec.end(), 50); //does not occur
  cout << "first occurrence of: " << * itr_9 << endl;
  cout << "only occurrence of: " << * itr_43 << endl;

نستطيع إثبات أن itr_9 تشير إلى الظهور الأول لـ 9 عبر فحص القيمة التي تلي 9، والتي يجب أن تكون 10 وليس 43، نتابع:

  cout << "element after first 9: " << * (itr_9 + 1) << ends;

وسنلقي نظرة على العنصر الموجود قبل النهاية لتجنب تحصيل ()intVec.end:

  cout << "last element: " << * (itr_50 - 1) << endl;
  return 0;
}

يكون ناتج ذلك كله:

first occurrence of: 9
only occurrence of: 43
element after first 9: 10
last element: 48

std::min_element

تُستخدم std::min_element لإيجاد أصغر عنصر في مجال معيّن.

template < class ForwardIterator >
    ForwardIterator min_element(ForwardIterator first, ForwardIterator last);

template < class ForwardIterator, class Compare >
    ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare comp);

المعاملات

• ‎first‎ - مكرّر يشير إلى بداية المجال
• ‎last‎ - مكرّر يشير إلى نهاية المجال
• ‎comp‎ - مؤشّر دالّة أو كائن دالّة يأخذ وسيطين ويعيد إما true أو false موضحًا إذا كان الوسيط الأول أصغر من الوسيط الثاني. يُشتَرَط ألًا تعدّل هذه الدالّة المُدخلاتِ.

القيمة المعادة

يُعاد مكرّر إلى أصغر عنصر في المجال.

التعقيد

التعقيد يساوي O(1)‎ - n‎، حيث يمثل n عدد العناصر المُقارنَة. انظر المثال التالي:

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>  // make_pair لاستخدام

using namespace std;

// دالّة تقارن زوجين
bool pairLessThanFunction(const pair < string, int > & p1,
    const pair < string, int > & p2) {
    return p1.second < p2.second;
}

int main(int argc,
    const char * argv[]) {

   vector<int> intVec {30,200,167,56,75,94,10,73,52,6,39,43};

   vector> pairVector = {make_pair("y", 25), make_pair("b", 2), make_pair("z", 26), make_pair("e", 5) };

    // < العامل الافتراضي هو
    auto minInt = min_element(intVec.begin(), intVec.end());

    // pairLessThanFunction استخدام
    auto minPairFunction = min_element(pairVector.begin(), pairVector.end(), pairLessThanFunction);

    // intVector اطبع أصغر قيمة في
    cout << "min int from default: " << * minInt << endl;

    // pairVector اطبع أصغر قيمة في
    cout << "min pair from PairLessThanFunction: " << ( * minPairFunction).second << endl;

    return 0;
}

الناتج سيكون:

min int from default: 6
min pair from PairLessThanFunction: 2

std::find_if

تُستخدم std::find_if لإيجاد أوّل عنصر في المجال يحقّق دالّة شرطية ‎pred‎.

template < class InputIterator, class UnaryPredicate >
    InputIterator find_if(InputIterator first, InputIterator last, UnaryPredicate pred);

المُعاملات

• ‎first‎ => مكرّر يشير إلى بداية المجال
• ‎last‎ => مكرّر يشير إلى نهاية المجال
• ‎pred‎ => دالّة شرطية - predicate - (تعيد إمّا true أو false)

القيمة المعادة

يُعاد مكرّر يشير إلى أول عنصر في المجال يحقّق الدالّة الشرطية، وسيُعاد مكرّر إلى last في حال لم يكن هناك أيّ عنصر يحقّق ذلك. انظر المثال التالي:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
/*
عرِّف بعض الدوالّ الشرطية
*/
// يساوي 10 x إن كان true إعادة

bool multOf10(int x) {
    return x % 10 == 0;
}

// إن كان العنصر أكبر من القيمة الممرّرة true إعادة 
class Greater {
    int _than;
    public:
        Greater(int th): _than(th) {

        }
    bool operator()(int data) const {
        return data > _than;
    }
};

int main() {

 vector myvec {2, 5, 6, 10, 56, 7, 48, 89, 850, 7, 456}; 

    // lambda مع دالّة 
    vector < int > ::iterator gt10 = find_if(myvec.begin(), myvec.end(), [](int x) {
        return x > 10;
    }); // >=

    // مع مؤشّر دالّة
    vector < int > ::iterator pow10 = find_if(myvec.begin(), myvec.end(), multOf10);

     // مع كائن دالّي
    vector < int > ::iterator gt5 = find_if(myvec.begin(), myvec.end(), Greater(5));

    // غير موجود
    vector < int > ::iterator nf = find_if(myvec.begin(), myvec.end(), Greater(1000)); // nf points to
    myvec.end();

 // myvec.end() التحقّق مما إذا كان المؤشّر يشير إلى
    if (nf != myvec.end()) {
        cout << "nf points to: " << * nf << endl;
    } else {
        cout << "item not found" << endl;
    }

    cout << "First item >   10: " << * gt10 << endl;
    cout << "First Item n * 10: " << * pow10 << endl;
    cout << "First Item >    5: " << * gt5 << endl;

    return 0;
}

الناتج سيكون:

item not found
First item > 10: 56
First Item n * 10: 10
First Item > 5: 6

استخدام std::nth_element لإيجاد الوسيط

تأخذ خوارزمية ‎std::nth_element‎ ثلاثة مُكرِّرات: مكرّر يشير إلى البداية، وآخر يشير إلى الموضع n، وآخر يشير إلى النهاية. وبمجرد عودة الدالّة، سيكون العنصر رقم n (في الترتيب وليس في الموضع) هو أصغر n عنصر. تحتوي الدالّة على تحميلات زائدة أكثر تفصيلًا، على سبيل المثال، بعضها تأخذ كائنات دالّية للموازنة.

ملاحظة: هذه الدالّة فعّالة للغاية - إذ أنّ تعقيدها خطّي.

في المثال التالي، سنُعرّف الوسيط median، وهو القيمة التي تفصل النصف الأعلى من التسلسل عن النصف الأصغر بحيث يتساوى على طرفيه عدد القيم بعد ترتيبها تصاعديًا، أي أنه العنصر الأوسط في الترتيب. للتّبسيط، سنُعرّف وسيط تسلسل مكوّن من n عنصر على أنّه العنصر الموجود في الموضع ⌈ n / 2 ⌉ حسب الترتيب. مثلًا، سيكون وسيط تسلسل طوله 5 هو العنصر الأصغر الثالث، وكذلك وسيط تسلسل بطول 6 عناصر.

لاستخدام هذه الدالّة لإيجاد الوسيط، يمكننا استخدام ما يلي، لنبدأ بــ:

std::vector v{5, 1, 2, 3, 4};  

std::vector < int > ::iterator b = v.begin();
std::vector < int > ::iterator e = v.end();

std::vector < int > ::iterator med = b;
std::advance(med, v.size() / 2);

// الوسيط موجود في الموضع الثاني
std::nth_element(b, med, e);

// v[2] الوسيط الآن هو

ولإيجاد نقطة تجزئة من الدرجة p ‏‏(p-th quantile‏‏)، سنغيّر بعض السطور أعلاه:

const std::size_t pos = p * std::distance(b, e);
std::advance(nth, pos);

ستكون نقطة التجزئة في الموضع ‎pos‎.

std::count

تحسُب std::count عدد العناصر التي تساوي قيمةً معيّنة val:

template < class InputIterator, class T >
    typename iterator_traits < InputIterator > ::difference_type
count(InputIterator first, InputIterator last,
    const T & val);

المعاملات

• ‎first‎ - مكرّر يشير إلى بداية المجال. *‎last‎ => مكرّر يشير إلى نهاية المجال.
• ‎val‎ - القيمة المراد حساب تكرار حدوثها في المجال.

القيمة المعادة

عدد العناصر التي تساوي (==) val في المجال. انظر المثال التالي:

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int main(int argc,
    const char * argv[]) {

    // إنشاء متجهة
    vector intVec{4,6,8,9,10,30,55,100,45,2,4,7,9,43,48}; 

    //9, 55, 101 حساب مرات حدوث
    size_t count_9 = count(intVec.begin(), intVec.end(), 9); //occurs twice
    size_t count_55 = count(intVec.begin(), intVec.end(), 55); //occurs once
    size_t count_101 = count(intVec.begin(), intVec.end(), 101); //occurs once

    // اطبع النتيجة
    cout << "There are " << count_9 << " 9s" << endl;
    cout << "There is " << count_55 << " 55" << endl;
    cout << "There is " << count_101 << " 101" << ends;

  // 4 ابحث عن أول عنصر في المتجهة يساوي
    vector < int > ::iterator itr_4 = find(intVec.begin(), intVec.end(), 4);

   // حساب مرات حدوثه في المتجه
    size_t count_4 = count(itr_4, intVec.end(), * itr_4); // should be 2
    cout << "There are " << count_4 << " " << * itr_4 << endl;
    return 0;
}

الناتج سيكون:

There are 2 9s
There is 1 55
There is 0 101
There are 2 4

std::count_if

تحسب std::count_if عدد العناصر في المجال التي تحقّق شرطًا معينًا.

template < class InputIterator, class UnaryPredicate >
    typename iterator_traits < InputIterator > ::difference_type
count_if(InputIterator first, InputIterator last, UnaryPredicate red);

المعاملات

• ‎first‎ - مكرّر يشير إلى بداية المجال.
• ‎last‎ - مكرّر يشير إلى نهاية المجال.
• ‎red‎ - دالّة شرطية (تعيد إما true أو false).

القيمة المعادة

عدد العناصر في المجال التي تحقّق الشرط. انظر المثال التالي:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
/*
عرِّف بعض الدوال لاستخدامها كشروط
*/

// فرديا number إن كان true إعادة 
bool isOdd(int i) {
    return i % 2 == 1;
}

// أكبر من قيمة وسيط المنشِئ number  إن كان true كائن دالي يعيد
provided
class Greater {
    int _than;
    public:
        Greater(int th): _than(th) {}
    bool operator()(int i) {
        return i > _than;
    }
};

int main(int argc,
    const char * argv[]) {

    // أنشئ متجهًا
   vector myvec = {1,5,8,0,7,6,4,5,2,1,5,0,6,9,7}; 

    // لحساب عدد العناصر الزوجية lambda استخدام دالّة
    size_t evenCount = count_if(myvec.begin(), myvec.end(), [](int i) {
        return i % 2 == 0;
    }); // >=  C++11

    // استخدام مؤشّر دالّة لحساب عدد الأعداد الفردية في النصف الأول من المتجهة
    size_t oddCount = count_if(myvec.begin(), myvec.end() - myvec.size() / 2, isOdd);

    // استخدام كائن دالّي لحساب عدد العناصر الأصغر من 5
    size_t greaterCount = count_if(myvec.begin(), myvec.end(), Greater(5));
    cout << "vector size: " << myvec.size() << endl;
    cout << "even numbers: " << evenCount << " found" << endl;
    cout << "odd numbers: " << oddCount << " found" << endl;
    cout << "numbers > 5: " << greaterCount << " found" << endl;

    return 0;
}

الناتج سيكون:

vector size: 15
even numbers: 7 found
odd numbers: 4 found
numbers > 5: 6 found

هذا الدرس جزء من سلسلة دروس عن C++‎.

ترجمة -بتصرّف- للفصل Chapter 62: Standard Library Algorithms من كتاب C++ Notes for Professionals