קונטיינרים של STL

חלק מהיחידה תכנות מונחה עצמים במסלול ה-C++ של Coddy. שיעור 71 מתוך 104.

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

מכולות רצף שומרות על סדר מסוים של האיברים:

#include <vector>
#include <list>

std::vector<int> vec = {1, 2, 3};  // מערך דינמי, גישה אקראית מהירה
vec.push_back(4);                   // הוספה לסוף: O(1) בממוצע משוקלל
int x = vec[2];                     // גישה לפי אינדקס: O(1)

std::list<int> lst = {1, 2, 3};    // רשימה מקושרת דו־כיוונית
lst.push_front(0);                  // הוספה להתחלה: O(1)
lst.push_back(4);                   // הוספה לסוף: O(1)

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

#include <map>
#include <set>

std::set<int> s = {3, 1, 4, 1};    // איברים ייחודיים ממוינים: {1, 3, 4}
s.insert(2);                        // הוספה: O(log n)
bool found = s.count(3);            // בדיקת קיום: O(log n)

std::map<std::string, int> ages;   // זוגות מפתח-ערך, ממוינים לפי מפתח
ages["Alice"] = 25;                 // הוספה/עדכון: O(log n)
ages["Bob"] = 30;
std::cout << ages["Alice"];        // גישה: O(log n)

קונטיינרים לא ממוינים משתמשים בטבלאות גיבוב לחיפוש מהיר עוד יותר במקרה הממוצע:

#include <unordered_map>

std::unordered_map<std::string, int> scores;
scores["player1"] = 100;            // הוספה: O(1) בממוצע
scores["player2"] = 200;
std::cout << scores["player1"];    // גישה: O(1) בממוצע

השתמש ב־vector כשנדרשת גישה אקראית מהירה, ב־list להכנסות תכופות באמצע, ב־map/set כשנדרשים נתונים ממוינים, וב־unordered_map כשמהירות החיפוש קריטית והסדר אינו חשוב.

אתגר

קל

בואו נבנה מערכת לניהול ציונים של תלמידים, שמדגימה כיצד מכלים שונים של STL משמשים למטרות שונות. תשתמשו בכמה סוגי מכלים כדי לארגן נתוני תלמידים ביעילות, ותבחרו את המכל המתאים לכל משימה.

תיצרו שני קבצים כדי לארגן את הקוד:

GradeManager.h: הגדירו מחלקה בשם GradeManager שמשתמשת בכמה מכלים של STL כדי לנהל מידע על תלמידים.
המחלקה שלכם צריכה להשתמש ב:
- std::vector<std::string> כדי לאחסן את שמות התלמידים לפי סדר הוספתם
- std::map<std::string, int> כדי לשייך כל שם של תלמיד לציון שלו
- std::set<int> כדי לעקוב אחר כל הציונים הייחודיים שניתנו
ממשו את המתודות הבאות:
- addStudent(const std::string& name, int grade): מוסיפה תלמיד ואת הציון שלו לכל שלושת המכלים
- getGrade(const std::string& name): מחזירה את הציון של תלמיד לפי שמו, באמצעות המפה
- printRoster(): מדפיסה את שמות כל התלמידים לפי סדר הוספתם (מתוך המערך הדינמי), כל שם בשורה חדשה
- printGrades(): מדפיסה את כל התלמידים והציונים שלהם בסדר אלפביתי (המפה מטפלת בכך באופן אוטומטי), בפורמט name: grade בכל שורה
- printUniqueGrades(): מדפיסה את כל הציונים הייחודיים בסדר עולה (הקבוצה מטפלת בכך), מופרדים ברווחים ואחריהם ירידת שורה
main.cpp: קראו את הקלט והדגימו כיצד כל סוג מכל משמש למטרה אחרת.
קראו שישה ערכים (כל אחד בשורה נפרדת):
1. שם התלמיד הראשון
2. הציון של התלמיד הראשון (מספר שלם)
3. שם התלמיד השני
4. הציון של התלמיד השני (מספר שלם)
5. שם התלמיד השלישי
6. הציון של התלמיד השלישי (מספר שלם)
צרו GradeManager והוסיפו את שלושת התלמידים. לאחר מכן הדגימו את ההתנהגויות השונות של המכלים:
1. הדפיסו את Roster (insertion order): ולאחר מכן קראו למתודה printRoster()
2. הדפיסו את Grades (alphabetical): ולאחר מכן קראו למתודה printGrades()
3. הדפיסו את Unique grades: ולאחר מכן קראו למתודה printUniqueGrades()
4. חפשו את הציון של התלמיד השני והדפיסו <name>'s grade: <grade>

לדוגמה, עם הקלט Charlie, 85, Alice, 90, Bob, 85:

Roster (insertion order):
Charlie
Alice
Bob
Grades (alphabetical):
Alice: 90
Bob: 85
Charlie: 85
Unique grades:
85 90 
Alice's grade: 90

שימו לב כיצד המערך הדינמי שומר על סדר ההוספה (Charlie, Alice, Bob), המפה ממיינת אוטומטית לפי המפתח (Alice, Bob, Charlie), והקבוצה מאחסנת רק ערכים ייחודיים בסדר ממוין (85 מופיע פעם אחת, ולא פעמיים). כל סוג מכל מתאים במיוחד למשימות שונות!

נסו בעצמכם

#include <iostream>
#include <string>
#include "GradeManager.h"

using namespace std;

int main() {
    // קראו קלט עבור שלושה תלמידים
    string name1, name2, name3;
    int grade1, grade2, grade3;
    
    cin >> name1;
    cin >> grade1;
    cin >> name2;
    cin >> grade2;
    cin >> name3;
    cin >> grade3;
    
    // TODO: צרו אובייקט מסוג GradeManager
    
    // TODO: הוסיפו את כל שלושת התלמידים ל-GradeManager
    
    // TODO: הדפיסו "Roster (insertion order):" וקראו ל-printRoster()
    
    // TODO: הדפיסו "Grades (alphabetical):" וקראו ל-printGrades()
    
    // TODO: הדפיסו "Unique grades:" וקראו ל-printUniqueGrades()
    
    // TODO: מצאו את הציון של התלמיד השני והדפיסו "<name>'s grade: <grade>"
    
    return 0;
}