vector ב-C++: מערכים דינמיים עם std::vector

למה vector ולא מערך גולמי

למערך גולמי יש גודל קבוע שנקבע בזמן קומפילציה, והוא שוכח מה האורך שלו ברגע שמעבירים אותו לפונקציה. std::vector פותר את שתי הבעיות: זה מערך בגודל משתנה שעוקב אחרי האורך שלו, גדל לפי הצורך ומנקה את הזיכרון של עצמו. ב-C++ מודרנית, vector הוא קונטיינר ברירת המחדל: פנו למערך גולמי רק כשיש לכם סיבה ספציפית.

כללו את <vector>, ואז הצהירו על אחד עם טיפוס האיברים בסוגריים משולשים:

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

int main() {
    vector<int> scores = {90, 75, 100, 60};

    cout << "Count: " << scores.size() << "\n";
    cout << "First: " << scores[0] << "\n";
}

scores.size() תמיד מחזיר את האורך הנוכחי: אין int n נפרד שצריך לשמור מסונכרן, ואין טריקים עם sizeof. ה-{90, 75, 100, 60} הוא brace initializer (רשימת אתחול בסוגריים מסולסלים); ה-vector מבין לבד שהוא צריך ארבעה מקומות.

יצירה ואתחול של vector

יש כמה דרכים לבנות vector, לפי מה שאתם יודעים מראש:

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

int main() {
    vector<int> empty;                 // 0 איברים
    vector<int> filled = {1, 2, 3};    // 3 איברים מרשימה
    vector<int> tens(5, 10);           // 5 איברים, כל אחד = 10
    vector<string> names(3);           // 3 מחרוזות ריקות

    cout << empty.size() << " "
         << filled.size() << " "
         << tens.size() << " "
         << names.size() << "\n";      // 0 3 5 3
}

שימו לב למלכודת של סוגריים עגולים מול מסולסלים: vector<int> tens(5, 10) יוצר חמישה עותקים של 10, ואילו vector<int> tens{5, 10} יוצר vector של שני איברים שמחזיק 5 ו-10. סוגריים עגולים אומרים "גודל וערך מילוי"; סוגריים מסולסלים אומרים "האיברים האלה בדיוק".

הוספה והסרה של איברים

כל הרעיון של vector הוא שהוא גדל. push_back מוסיף לסוף, ו-pop_back מסיר מהסוף:

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

int main() {
    vector<int> v;          // מתחילים ריק
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);

    v.pop_back();           // מסירים את ה-30

    cout << "Size: " << v.size() << "\n";   // 2
    cout << "Back: " << v.back() << "\n";    // 20
}

back() מחזיר את האיבר האחרון ו-front() את הראשון, בצורה נקייה יותר מ-v[v.size() - 1] ו-v[0]. מאז C++11 אפשר גם להשתמש ב-emplace_back(args...) כדי לבנות איבר במקום, מה שחוסך עותק זמני בטיפוסים כבדים יותר.

טעות נפוצה של מתחילים היא לקרוא ל-front() או ל-back() על vector ריק. זו התנהגות לא מוגדרת, לא שגיאה: תמיד הגנו קודם עם if (!v.empty()).

קריאת איברים: [] מול at()

ניגשים לאינדקס ב-vector בדיוק כמו במערך, עם []. אבל [] לא בודק גבולות: אינדקס מחוץ לטווח הוא undefined behavior, שיכול לקרוא זבל בשקט או לקרוס אחר כך במקום מבלבל:

vector<int> v = {1, 2, 3};
cout << v[10];   // התנהגות לא מוגדרת: בלי בדיקה, בלי שגיאה

כשרוצים בטיחות, משתמשים ב-at(). הוא בודק את האינדקס וזורק std::out_of_range בגישה לא תקינה, אחת מהחריגות של הספרייה הסטנדרטית שאפשר לתפוס, כך שמקבלים כישלון ברור במקום השחתה:

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

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

    try {
        cout << v.at(10) << "\n";   // זורק out_of_range
    } catch (const out_of_range& e) {
        cout << "Caught: " << e.what() << "\n";
    }
}

כלל אצבע: השתמשו ב-[] בלולאות צפופות שבהן כבר הוכחתם שהאינדקס תקין, וב-at() בגבולות שבהם קלט גרוע יכול לחדור.

לולאה על vector

הדרך הנקייה ביותר לעבור על vector היא לולאת for מבוססת טווח. קחו איברים כ-const auto& כדי לקרוא בלי להעתיק, או כ-auto& כדי לערוך אותם במקום:

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

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

    for (auto& n : v) {       // הפניה: עורך את האיברים האמיתיים
        n *= n;
    }

    for (const auto& n : v) { // קריאה בלבד
        cout << n << " ";     // 1 4 9 16
    }
    cout << "\n";
}

אם באמת צריך את האינדקס (למשל כדי להשוות שכנים), השתמשו בלולאת ספירה קלאסית, אבל שימו לב ש-size() מחזיר טיפוס unsigned (size_t). השוואה של int i עם סימן מולו יכולה לגרום לאזהרות מהמהדר ולגלגול מפתיע, אז העדיפו size_t i או לולאה מבוססת טווח כשאפשר:

for (size_t i = 0; i < v.size(); i++) {   // size_t, לא int
    cout << v[i];
}

size, capacity ו-reserve

vector שומר שני מספרים: size() (כמה איברים הוא מחזיק) ו-capacity() (כמה הוא יכול להחזיק לפני שהוא חייב לגדול). כש-push_back חורג מהקיבולת, ה-vector מקצה בלוק גדול יותר, מעתיק אליו כל איבר ומשחרר את הבלוק הישן. לכן push_back חוזר הוא זול בממוצע (amortized), אבל כל הקצאה מחדש בפני עצמה לא בחינם:

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

int main() {
    vector<int> v;
    v.reserve(100);          // מקצים מראש מקום ל-100

    for (int i = 0; i < 100; i++) {
        v.push_back(i);      // בלי הקצאה מחדש: הקיבולת כבר קיימת
    }

    cout << "Size: " << v.size() << ", capacity >= " << v.capacity() << "\n";
}

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

ההקצאה מחדש הזו היא גם המקור לבאג הכי מרושע של vector. מכיוון שהגדילה מזיזה את האחסון, כל מצביע, הפניה או iterator ששמרתם לתוך ה-vector הופכים לתלויים (dangling) אחרי push_back שמקצה מחדש:

vector<int> v = {1, 2, 3};
int& first = v[0];     // הפניה לתוך ה-vector
v.push_back(4);        // עלול להקצות מחדש...
cout << first;         // תלויה: עלולה להצביע על זיכרון משוחרר

אותו דבר נכון ל-iterators: אל תעשו push_back או erase בזמן מעבר עם iterator שמור. אם חייבים להסיר פריטים תוך כדי לולאה, השתמשו בערך ההחזרה של erase, או ב-erase-remove idiom עם std::remove.

הבא בתור: map

vector מושלם כשמחפשים דברים לפי מיקום: איבר 0, איבר 1 וכן הלאה. אבל לעיתים קרובות רוצים לחפש לפי מפתח: שם משתמש, מזהה מוצר, מילה. בשביל זה יש את std::map. בהמשך נכסה את map, הקונטיינר של מפתח-ערך ב-C++, כולל איך מכניסים, מחפשים ועוברים על רשומות, ואת המלכודת של [] שיוצר ערך ברירת מחדל ומכשילה כמעט את כולם.