std::map ב-C++: מפתחות, ערכים, חיפוש והכנסה

חיפוש לפי מפתח

vector מצוין כשניגשים לפי מיקום: איבר 0, איבר 1 וכן הלאה. אבל לעיתים קרובות אין לכם מיקום: יש לכם שם, ואתם רוצים את מה שמשויך אליו: שם משתמש והניקוד שלו, מילה ומספר ההופעות שלה, קוד מדינה והבירה שלה. סריקה של vector כדי למצוא התאמה היא O(n), והיא נעשית איטית מהר.

std::map פותר את זה. הוא שומר זוגות מפתח-ערך, מחזיק אותם ממוינים לפי המפתח ומאפשר לחפש ערך לפי המפתח שלו בזמן O(log n). כללו את <map> כדי להשתמש בו:

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

int main() {
    map<string, int> scores;

    scores["Ada"] = 90;
    scores["Grace"] = 100;
    scores["Linus"] = 75;

    cout << "Grace scored " << scores["Grace"] << "\n";
}

את map<string, int> קוראים כ"מיפוי ממפתחות string לערכים int". מפתחות הם ייחודיים: השימו לאותו מפתח פעמיים והערך השני ינצח. מבפנים map הוא עץ חיפוש בינארי מאוזן, ולכן הכול נשאר ממוין והחיפושים לוגריתמיים ולא בזמן קבוע.

הכנסת איברים

יש כמה דרכים להכניס רשומות, וההבדל ביניהן חשוב. הנפוצה ביותר היא operator[], שיוצר את המפתח אם הוא לא קיים ומחזיר הפניה שאפשר להשים אליה:

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

int main() {
    map<string, int> inventory;

    inventory["apples"] = 12;     // יצירה + השמה
    inventory["apples"] += 3;     // קריאה, שינוי וכתיבה: עכשיו 15

    cout << "apples: " << inventory["apples"] << "\n";
}

אם רוצים הכנסה שמסרבת לדרוס מפתח קיים, משתמשים ב-insert או ב-emplace. שניהם מחזירים pair שה-.second שלו הוא bool שאומר אם ההכנסה באמת קרתה:

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

int main() {
    map<string, int> ages;
    ages["Ada"] = 36;

    auto result = ages.insert({"Ada", 99});   // Ada כבר קיימת
    cout << "inserted? " << result.second << "\n";   // 0 (false)
    cout << "Ada is still " << ages["Ada"] << "\n";  // 36, ללא שינוי
}

השתמשו ב-[] כשאתם רוצים ש"הכתיבה האחרונה תנצח", וב-insert/emplace כשמפתח קיים צריך להישאר בלי שינוי.

המלכודת של operator[]: הוא מכניס בזמן קריאה

זה באג ה-map הנפוץ ביותר. operator[] אינו קריאה טהורה: אם המפתח חסר, הוא מכניס אותו בשקט עם ערך שנבנה כברירת מחדל (0 ל-int, "" ל-string וכן הלאה) ומחזיר הפניה אליו. כך שעצם הבדיקה של מפתח עם [] משנה את ה-map:

map<string, int> m;
if (m["maybe"] == 0) {   // באג: זה עתה יצר את "maybe" -> 0
    // ...
}
cout << m.size();        // 1, לא 0: הכנסתם מפתח בטעות

זה נושך אתכם גם עם const map, שבו operator[] אפילו לא יתקמפל כי ייתכן שיצטרך להכניס. כדי לקרוא בלי להכניס, השתמשו ב-find, ב-count/contains או ב-at (שזורק חריגה במקום להכניס כשהמפתח חסר):

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

int main() {
    map<string, int> m = {{"a", 1}, {"b", 2}};

    // find: מחזיר איטרטור, ששווה ל-end() אם המפתח חסר
    auto it = m.find("c");
    cout << "found c? " << (it != m.end()) << "\n";   // 0

    // contains (C++20) או count (כל גרסה)
    cout << "has a? " << m.contains("a") << "\n";      // 1
    cout << "count z: " << m.count("z") << "\n";       // 0

    // at: זורק std::out_of_range אם חסר, אף פעם לא מכניס
    cout << "a = " << m.at("a") << "\n";
}

כלל אצבע: אם אתם מתכוונים לקרוא, לעולם אל תשתמשו ב-[]. השתמשו ב-at כשהמפתח חייב להתקיים, וב-find/contains כשייתכן שלא.

מעבר בסדר ממוין

מכיוון ש-map מבוסס עץ, מעבר עליו מבקר במפתחות בסדר עולה ממוין, תמיד ובחינם. כל איבר הוא pair<const Key, Value>, ולכן השתמשו ב-structured binding כדי לפרק בצורה נקייה את המפתח ואת הערך:

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

int main() {
    map<string, int> wordCount;
    for (const string& w : {"sky", "blue", "sky", "sea", "blue", "sky"}) {
        wordCount[w]++;   // מפתחות חסרים מתחילים ב-0, ואז ++
    }

    for (const auto& [word, count] : wordCount) {
        cout << word << ": " << count << "\n";
    }
}

שימו לב שהמפתח ב-binding הוא const: אפשר לשנות ערך דרך הלולאה עם auto&, אבל אי אפשר לשנות מפתח במקומו (זה היה שובר את סדר המיון). הפלט יוצא בסדר אלפביתי (blue, sea, sky) בלי שום שלב מיון, וזו בדיוק הסיבה שאנשים בוחרים ב-map על פני טבלת גיבוב כשמעבר מסודר חשוב.

ה-idiom של wordCount[w]++ הוא גם השימוש הקנוני בהתנהגות של הכנסה בזמן גישה: כאן אתם רוצים שמפתח חסר יתחיל ב-0, ולכן [] הוא הכלי הנכון.

הסרת איברים וגודל

מוחקים לפי מפתח עם erase, שמחזיר כמה איברים הוסרו (0 או 1 ב-map). אפשר גם למחוק דרך איטרטור מ-find. בודקים את מצב המכולה עם size() ו-empty():

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

int main() {
    map<string, int> m = {{"x", 1}, {"y", 2}, {"z", 3}};

    cout << "removed: " << m.erase("y") << "\n";   // 1
    cout << "removed: " << m.erase("q") << "\n";   // 0 (לא היה קיים)

    cout << "size: " << m.size() << "\n";          // 2
    cout << "empty? " << m.empty() << "\n";        // 0

    for (const auto& [k, v] : m) cout << k << " ";  // x z
    cout << "\n";
}

מלכודת אחת כשמוחקים בתוך לולאה: m.erase(it) מבטל את האיטרטור it, ולכן אי אפשר לעשות אחר כך ++it. הדפוס הבטוח מאז C++11 הוא it = m.erase(it), שמחזיר איטרטור לאיבר הבא. להסרה מותנית חד-פעמית לאורך כל ה-map, std::erase_if(m, predicate) (C++20) נקי יותר.

הבא בתור: unordered_map

std::map נותן לכם מפתחות ממוינים ופעולות O(log n) צפויות, אבל משלמים על הסדר הזה בכל חיפוש. כשלא אכפת לכם מסדר המפתחות ורק רוצים את החיפושים המהירים ביותר, unordered_map מחליף את העץ הממוין בטבלת גיבוב: גישה של O(1) בממוצע. בהמשך נראה איך הוא עובד, מתי הממוצע בזמן קבוע שלו מנצח את הלוגריתם של map, ואת מלכודות הגיבוב (טיפוסי מפתח מותאמים, התנגשויות במקרה הגרוע) שמגיעות איתו.