אלגוריתמים של 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() לפני שאתם ניגשים לתוצאה דרך dereference: dereference של end() הוא undefined behavior.

ספירה ובדיקה עם פרדיקטים

אלגוריתמים רבים מקבלים פרדיקט: פונקציה (בדרך כלל lambda) שמחזירה 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);.

איטרטורים שחיים מעבר לתוקף שלהם הם סכנה

מכיוון שאלגוריתמים מחזירים איטרטורים, האיטרטורים האלה כפופים לאותם כללי פסילה (invalidation) שפגשתם בעמוד הקודם. שמירת איטרטור ואז שינוי המכל, push_back שגורם להקצאה מחדש או erase, עלולים להשאיר את האיטרטור השמור תלוי באוויר (dangling), ושימוש בו הוא undefined behavior.

auto it = find(v.begin(), v.end(), 16);
v.push_back(99);   // עלול להקצות מחדש את האחסון של v
cout << *it;       // באג: `it` עשוי להצביע עכשיו על זיכרון משוחרר

ההרגל הבטוח: השתמשו באיטרטור שאלגוריתם מחזיר מיד, לפני כל פעולה שעלולה לשנות גודל או להקצות מחדש את המכל. אם צריך לשנות את המכל על סמך תוצאה, שמרו במקום זאת אינדקס (it - v.begin()), כי אינדקסים שורדים הקצאה מחדש.

הבא בתור: מיון

ראיתם עכשיו חיפוש, ספירה, המרה וצמצום, אבל אלגוריתם אחד חשוב מספיק כדי לקבל עמוד משלו. std::sort מסדר מחדש טווח במקום, וברגע שהנתונים ממוינים נפתחת משפחה שלמה של אלגוריתמים מהירים יותר שעובדים רק על נתונים ממוינים (binary_search, lower_bound, equal_range). בהמשך נצלול למיון: איך מספקים comparator מותאם אישית, מה ההבדל בין sort ל-stable_sort, ואילו כללים פונקציית ההשוואה שלכם חייבת לקיים כדי להימנע מ-undefined behavior.