2.4 - מכולות כבחירה הנדסית - פתרון

פתרון - מיקום הבעלים אינו מיקום האובייקט

הגרסה בעלת אובייקטים מוקצים בנפרד יכולה להיראות כך:

#include <cassert>
#include <memory>
#include <vector>

struct Job {
    int id;
};

int main() {
    std::vector<std::unique_ptr<Job>> jobs;
    jobs.reserve(1);
    jobs.push_back(std::make_unique<Job>(Job{100}));
    Job* first = jobs.front().get();

    for (int id = 0; id < 1000; ++id) {
        jobs.push_back(std::make_unique<Job>(Job{id}));
    }

    assert(first == jobs.front().get());
    assert(first->id == 100);
}

ה־vector יכולה להזיז את ה־unique_ptrים, אבל אינה מזיזה את Job עצמו. אם נבצע reset על jobs.front או נמחק את הבעלים מן המכולה, חיי Job יסתיימו וה־pointer לא יהיה תקף.

לעומת זאת, ב־vector גדילה שדורשת reallocation מסיימת את חיי האיברים באחסון הישן ויוצרת את התכולה באחסון החדש. שמירת אינדקס במקום pointer יכולה לעזור בחלק מהפעולות, אבל מחיקה או שינוי סדר דורשים חוזה זהות נוסף.

שמירת קיבולת לעומת שינוי גודל

הקוד התקין הוא:

#include <cassert>
#include <vector>

int main() {
    std::vector<int> values;
    values.reserve(8);
    assert(values.empty());
    assert(values.capacity() >= 8);
    values.push_back(7);
    assert(values.size() == 1);
    assert(values[0] == 7);
}

אין כאן הנחה שהcapacity שווה בדיוק לשמונה. אין גישה ל־values[7], מפני שהמכולה עדיין מכילה איבר אחד בלבד.

בחירת מכולה

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

לחיפוש לפי מפתח עם מעבר ממויין, map נותנת חוזה מתאים באופן ישיר. המכולה unordered_map אינה מבטיחה סדר ממויין, ולכן הוספת מיון של התוצאות היא עלות נוספת שצריך לכלול בהחלטה.

ב־vector, reallocation פוסלת את כל ה־iteratorים וה־references לאיברים. הוספה ללא reallocation שומרת על references לאיברים קיימים, אך end משתנה. מחיקה פוסלת aliases בנקודת המחיקה ואחריה לפי חוזה הפעולה, גם אם הcapacity נשארה זהה.

הטבלה של המימוש צריכה להפריד כל פעולה ולא לכתוב רק שמכולה מסוימת יציבה. היציבות היא יחס בין סוג alias, פעולה ומצב capacity, ולא תווית כללית של הטיפוס.