איטרטורים ב-C++: begin, end וסוגי איטרטורים

מה זה בעצם איטרטור

כל מכולה סטנדרטית, vector, string, map, set, list, שומרת את האיברים שלה בצורה שונה מבפנים. vector הוא בלוק רציף, map הוא עץ מאוזן, list הוא צמתים מקושרים. ובכל זאת אפשר לעבור בלולאה על כולם באותה דרך. מה שמאפשר את זה הוא האיטרטור: אובייקט קטן ש"מצביע" על איבר אחד ויודע איך לעבור לבא.

חשבו על איטרטור כעל מצביע מוכלל. מקבלים אחד מ-begin(), קוראים את האיבר שהוא מצביע עליו עם *, ומקדמים אותו עם ++. החלקים מתחברים כך:

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

int main() {
    vector<int> v = {10, 20, 30};

    vector<int>::iterator it = v.begin();
    cout << *it << "\n";   // 10: הגישה עם * קוראת את האיבר

    ++it;                  // מתקדמים לאיבר הבא
    cout << *it << "\n";   // 20
}

v.begin() מחזיר איטרטור לאיבר הראשון, *it נותן לכם את האיבר הזה, ו-++it עובר לבא. השלישייה הזו, גישה, התקדמות והשוואה, היא כל המודל המחשבתי.

begin(), end() והטווח החצי-פתוח

החצי השני של התמונה הוא end(). וזה חשוב: end() לא מצביע על האיבר האחרון, אלא על המקום אחד אחרי האיבר האחרון. זה טווח "חצי-פתוח" מכוון [begin, end): begin כלול, ו-end הוא אות העצירה.

העיצוב הזה הופך את הלולאה הסטנדרטית לנקייה: הולכים עד שהאיטרטור שווה ל-end():

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

int main() {
    vector<int> v = {3, 1, 4, 1, 5};

    for (auto it = v.begin(); it != v.end(); ++it) {
        cout << *it << " ";
    }
    cout << "\n";
}

שימו לב ל-it != v.end(), לא it < v.end(). רוב האיטרטורים של מכולות (כמו map או list) לא תומכים ב-<, רק ב-== וב-!=, ולכן != הוא הבחירה הניידת. ו-auto חוסך מכם לכתוב ידנית vector<int>::iterator: הקומפיילר מסיק את הטיפוס.

המקרה של מכולה ריקה מסתדר מעצמו: כשמכולה ריקה, begin() == end(), ולכן גוף הלולאה לא רץ אף פעם. לא צריך טיפול מיוחד.

לעולם אל תיגשו ל-end()

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

vector<int> v = {1, 2, 3};
cout << *v.end();   // התנהגות לא מוגדרת: end() אינו איבר

אותה מלכודת פוגעת בפונקציות חיפוש. std::find מחזיר end() כשהוא לא מוצא את הערך, ולכן חייבים לבדוק לפני הגישה:

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

int main() {
    vector<int> v = {2, 4, 6, 8};

    auto it = find(v.begin(), v.end(), 5);
    if (it != v.end()) {
        cout << "Found: " << *it << "\n";
    } else {
        cout << "5 is not in the vector\n";   // זה מה שרץ
    }
}

השוו תמיד את האיטרטור שהוחזר מול end() לפני שאתם ניגשים דרכו. שכחה של ה-if הזה היא אחד המקורות הנפוצים ביותר לקריסות בקוד STL של מתחילים.

const, cbegin ואיטרטורים הפוכים

מכולות מספקות סוגים שונים של איטרטורים, לפי מה שצריך:

• begin() / end(): איטרטורים רגילים לקריאה ולכתיבה (*it = ... עובד).
• cbegin() / cend(): איטרטורי const_iterator: אפשר לקרוא דרכם אבל לא לשנות את האיבר.
• rbegin() / rend(): איטרטורים הפוכים שעוברים מהסוף להתחלה: ++ בעצם זז אחורה.

איטרטורים הפוכים הם הדרך הנקייה לעבור בלולאה בסדר הפוך בלי חשבון אינדקסים מסורבל:

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

int main() {
    vector<int> v = {1, 2, 3, 4};

    for (auto it = v.rbegin(); it != v.rend(); ++it) {
        cout << *it << " ";   // 4 3 2 1
    }
    cout << "\n";
}

גם עם איטרטורים הפוכים כותבים ++it כדי להתקדם: האיטרטור מטפל בכיוון "אחורה" מבפנים. השתמשו ב-cbegin()/cend() (או בהפניית const למכולה) כשלולאה אמורה רק לקרוא, כדי שהקומפיילר יעצור אתכם מכתיבה בטעות.

איטרטורים של map מחזירים זוגות

לא כל איטרטור הוא עטיפה דקה סביב מצביע. איטרטור של std::map עובר על עץ, והגישה דרכו נותנת std::pair של המפתח והערך, שניגשים אליהם דרך ->first ו-->second (בדיוק כמו מצביע, איטרטור תומך ב-->):

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> ages = {{"Ada", 36}, {"Grace", 85}};

    for (auto it = ages.begin(); it != ages.end(); ++it) {
        cout << it->first << " -> " << it->second << "\n";
    }
}

לולאת for מבוססת טווח בנויה ישירות על begin()/end(), ולכן למעבר פשוט קדימה בדרך כלל תשתמשו בה. איטרטורים מפורשים מצדיקים את עצמם כשצריך מעבר הפוך, את המיקום של איבר, או להעביר טווח לאלגוריתם.

המלכודת הגדולה: ביטול איטרטורים

זו המלכודת שנושכת את כולם בסוף. כשמשנים את המבנה של מכולה, איטרטורים קיימים עלולים להתבטל (invalidated): הם מצביעים על זיכרון ששוחרר או הוזז. שימוש באחד כזה הוא התנהגות לא מוגדרת.

ב-vector, push_back עלול להקצות מחדש את כל החוצץ כדי להגדיל אותו, ולבטל כל איטרטור קיים. מחיקה תוך כדי לולאה ידועה לשמצה עוד יותר, וזו קריסה קלאסית:

vector<int> v = {1, 2, 3, 4};
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it % 2 == 0)
        v.erase(it);   // באג: erase מבטל את it, ואז ++it הוא UB
}

הפתרון הוא ש-erase מחזיר איטרטור תקין לאיבר שאחרי האיבר שהוסר. מתקדמים רק כשלא מחקתם:

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

int main() {
    vector<int> v = {1, 2, 3, 4, 5, 6};

    for (auto it = v.begin(); it != v.end(); ) {
        if (*it % 2 == 0)
            it = v.erase(it);   // erase מחזיר את האיטרטור התקין הבא
        else
            ++it;               // מתקדמים רק כששום דבר לא הוסר
    }

    for (int x : v) cout << x << " ";   // 1 3 5
    cout << "\n";
}

שימו לב שבכותרת ה-for אין ++it: הגוף מחליט אם להתקדם. (בקוד אמיתי, ה-idiom של erase-remove או std::erase_if של C++20 עושים את זה בשורה אחת.) הכלל שכדאי לזכור: כל פעולה שמוסיפה או מסירה איברים עלולה לבטל איטרטורים, ולכן אל תחזיקו באיטרטור ישן לאורך שינוי כזה.

הבא בתור: אלגוריתמים

עכשיו, כשאתם יודעים לתאר טווח כזוג begin/end, פתחתם את כל ספריית האלגוריתמים של ה-STL. לפונקציות כמו sort, find, count ו-accumulate לא אכפת איזו מכולה יש לכם: הן פועלות על טווחי איטרטורים, כך שאותה קריאה עובדת על vector, על מערך או על חלק מאחד מהם. בהמשך נפעיל את האיטרטורים האלה ונניח לספרייה הסטנדרטית לבצע את הלולאות בשבילכם.