خوارزميات STL في C++: دليل عملي مع أمثلة

حلقات لا تضطر إلى كتابتها

في الصفحة السابقة رأيت أن كل حاوية تُسلِّم مُكرِّرات - مؤشرات خفيفة مزوَّدة بـ begin() وend(). هذا التجريد هو السبب الكامل لوجود الخوارزميات القياسية. فبدلًا من كتابة حلقة for خام في كل مرة تريد فيها البحث أو العدّ أو تحويل البيانات، تستدعي دالة باسمها من <algorithm> وتُمرِّر إليها نطاقًا.

النطاق ليس سوى مُكرِّرَين: من أين تبدأ، وموضعٌ واحد بعد حيث تتوقف. ولأن كل خوارزمية تتحدث لغة المُكرِّرات نفسها، يعمل find نفسه على vector أو string أو مصفوفة عادية.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {4, 8, 15, 16, 23, 42};

    // هل العدد 16 ضمن النطاق [begin, end)؟
    auto it = find(v.begin(), v.end(), 16);

    if (it != v.end())
        cout << "found " << *it << " at index " << (it - v.begin()) << "\n";
    else
        cout << "not found\n";
    return 0;
}

النمط الذي ينبغي استيعابه: الخوارزمية التي تبحث تُعيد المُكرِّر end() لتعني "لم يُعثَر على شيء". قارن دائمًا بـ end() قبل أن تفكّ مرجعية النتيجة - فكّ مرجعية end() هو سلوك غير معرَّف.

العدّ والاختبار باستخدام المُسنِدات

كثير من الخوارزميات تأخذ مُسنِدًا - دالة (غالبًا تعبير لامدا) تُعيد bool لكل عنصر. يَعُدّ count_if المطابقات؛ بينما يُجيب all_of وany_of وnone_of عن أسئلة نعم/لا حول النطاق بأكمله.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> scores = {42, 88, 17, 95, 63, 71};

    int passed = count_if(scores.begin(), scores.end(),
                          [](int s) { return s >= 60; });

    bool allPositive = all_of(scores.begin(), scores.end(),
                              [](int s) { return s > 0; });

    bool anyPerfect = any_of(scores.begin(), scores.end(),
                             [](int s) { return s == 100; });

    cout << passed << " passed\n";          // اجتاز 4
    cout << "all positive? " << allPositive << "\n";  // 1
    cout << "any perfect? " << anyPerfect << "\n";    // 0
    return 0;
}

std::count (من دون _if) هو القريب الأبسط الذي يَعُدّ قيمة محددة بدلًا من شرط. الجأ إلى النسخ ذات المُسنِد فور أن يصبح اختبارك "أي شيء يطابق قاعدة" بدلًا من "هذه القيمة بالذات".

تحويل نطاق واختزاله

حصانان للعمل يغطّيان معظم معالجة البيانات: يُطبِّق std::transform دالة على كل عنصر، بينما يطوي std::accumulate (من <numeric> لا من <algorithm>) نطاقًا إلى قيمة واحدة.

يكتب transform نتائجه عبر مُكرِّر إخراج. والخطأ الشائع والخطير هو توجيه الإخراج إلى vector فارغ - إذ تفترض الخوارزمية أن المساحة موجودة فعلًا فتكتب بعد النهاية. إمّا أن تُحدِّد حجم الوجهة أولًا، أو تستخدم back_inserter كي تُضاف كل نتيجة عبر push_back.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 3, 4};
    vector<int> squares;   // فارغ - لا مساحة بعد

    // back_inserter يُنمّي `squares` كلما وصلت النتائج
    transform(nums.begin(), nums.end(), back_inserter(squares),
              [](int n) { return n * n; });

    for (int s : squares) cout << s << " ";  // 1 4 9 16
    cout << "\n";
    return 0;
}

يبدأ accumulate من قيمة ابتدائية ويجمع العناصر من البداية إلى النهاية. نوع القيمة الابتدائية مهم: مرِّر 0 (وهو int) فيُحسَب المجموع ضمن int، ما قد يؤدي إلى طفحان أو اقتطاع.

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main() {
    vector<double> prices = {9.99, 4.50, 19.95};

    // ابدأ بـ 0.0 (double) كي يبقى المجموع الجاري من نوع double.
    double total = accumulate(prices.begin(), prices.end(), 0.0);

    cout << "total: " << total << "\n";  // total: 34.44
    return 0;
}

لو كتبت accumulate(prices.begin(), prices.end(), 0) ببذرة من نوع int، لتمّت كل عملية جمع ضمن int ولاختفت الكسور. نوع البذرة يحدّد نوع النتيجة في صمت.

مصطلح erase-remove

ها هو المزلق الذي يُفاجئ الجميع. std::remove لا يحذف أي شيء من الحاوية. الخوارزميات لا تملك سوى مُكرِّرات، لذا لا تستطيع تغيير حجم الحاوية - بل لا تعلم أصلًا بوجود حاوية. ما يفعله remove حقًا هو نقل كل العناصر المُحتفَظ بها إلى المقدمة، وترك الذيل في حالة غير محددة، وإعادة مُكرِّر يشير إلى النهاية المنطقية الجديدة.

// remove وحده يترك الحجم دون تغيير - هذا هو الخطأ:
remove(v.begin(), v.end(), 0);  // يُعيد مُكرِّرًا تجاهلته
// v ما زال بحجمه الأصلي؛ والذيل قمامة

لحذف العناصر فعلًا تُقرِن remove مع erase الخاص بالحاوية، ولهذا يُسمّى مصطلح erase-remove:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {3, 0, 7, 0, 1, 0, 9};

    // 1. remove ينقل القيم غير الصفرية إلى الأمام، ويُعيد النهاية الجديدة
    // 2. erase يقتطع كل شيء من هناك حتى النهاية الحقيقية
    v.erase(remove(v.begin(), v.end(), 0), v.end());

    for (int n : v) cout << n << " ";  // 3 7 1 9
    cout << "\n";
    return 0;
}

استخدم remove_if لمُسنِد بدلًا من قيمة محددة. وفي C++20 يمكنك تجاوز هذه الرقصة بالكامل بالدالتين الحرّتين std::erase / std::erase_if، اللتين تُنفِّذان الخطوتين نيابةً عنك: erase(v, 0);.

المُكرِّرات تتجاوز صلاحيتها على مسؤوليتك

لأن الخوارزميات تُعيد مُكرِّرات، تخضع تلك المُكرِّرات لقواعد الإبطال نفسها التي صادفتها في الصفحة السابقة. تخزين مُكرِّر ثم تعديل الحاوية - push_back يُطلِق إعادة تخصيص، أو erase - قد يترك المُكرِّر المخزَّن معلَّقًا، واستخدامه سلوك غير معرَّف.

auto it = find(v.begin(), v.end(), 16);
v.push_back(99);   // قد يُعيد تخصيص مساحة تخزين v
cout << *it;       // BUG: قد يشير `it` الآن إلى ذاكرة محرَّرة

العادة الآمنة: استخدم المُكرِّر الذي تُعيده الخوارزمية فورًا، قبل أي عملية قد تُغيِّر حجم الحاوية أو تُعيد تخصيصها. وإذا احتجت إلى تعديل الحاوية بناءً على نتيجة، فالتقط فهرسًا (it - v.begin()) بدلًا من ذلك، لأن الفهارس تبقى صالحة رغم إعادة التخصيص.

التالي: الفرز

لقد رأيت الآن البحث والعدّ والتحويل والاختزال - لكن خوارزمية واحدة على قدر من الأهمية يستحق صفحة خاصة به. يُعيد std::sort ترتيب نطاق في مكانه، وما إن تُفرَز البيانات حتى تنفتح عائلة كاملة من الخوارزميات الأسرع المخصصة للبيانات المفروزة (binary_search وlower_bound وequal_range). تاليًا سنتعمّق في الفرز: كيف تُوفِّر مُقارِنًا مخصصًا، والفرق بين sort وstable_sort، والقواعد التي يجب أن تلتزم بها دالة المقارنة لتجنّب السلوك غير المعرَّف.