unordered_map ב-C++: חיפוש מהיר בטבלת hash

כשהסדר לא משנה

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

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

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

int main() {
    unordered_map<string, int> stock = {
        {"apple", 12},
        {"banana", 7},
        {"cherry", 30}
    };

    cout << "bananas: " << stock["banana"] << "\n";
    stock["apple"] += 5;
    cout << "apples now: " << stock["apple"] << "\n";
}

הממשק כמעט זהה לזה של map, בכוונה: לעיתים קרובות אפשר להחליף אחד בשני רק על ידי שינוי הטיפוס. כללו את <unordered_map> (לא את <map>), והמפתחות יוצאים לא ממוינים.

הכנסה ועדכון

יש כמה דרכים להכניס רשומות, והן לא כולן מתנהגות אותו דבר. השתיים שתשתמשו בהן הכי הרבה הן operator[] ו-insert:

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

int main() {
    unordered_map<string, int> votes;

    votes["alice"] = 3;              // יצירה או דריסה
    votes["alice"] = 5;              // דורס -> 5
    votes.insert({"bob", 2});        // מכניס רק אם "bob" לא קיים
    votes.insert({"bob", 99});       // מתעלם, "bob" כבר קיים

    cout << "alice: " << votes["alice"] << "\n";   // 5
    cout << "bob:   " << votes["bob"] << "\n";      // 2, לא 99
}

ההבדל המרכזי: operator[] דורס ערך קיים, ו-insert משאיר מפתח קיים בלי שינוי. אם אתם ב-C++17, insert_or_assign(key, value) נותן סמנטיקה של "קבע את זה בכל מקרה", ו-try_emplace(key, args...) בונה את הערך במקום רק כשהמפתח חדש: שימושי לערכים שיקר לבנות.

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

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

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

int main() {
    unordered_map<string, int> seen;
    seen["x"] = 1;

    // רצינו רק לבדוק אם "y" קיים, אבל [] הכניס אותו:
    if (seen["y"] == 0) {
        cout << "y looked missing...\n";
    }

    cout << "size is now " << seen.size() << "\n";   // 2, לא 1!
}

seen["y"] יצר רשומה "y" -> 0 רק מעצם האזכור. כדי לבדוק קיום בלי לשנות את ה-map, השתמשו ב-count (מחזיר 0 או 1) או ב-find:

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

int main() {
    unordered_map<string, int> seen{{"x", 1}};

    if (seen.count("y")) {
        cout << "found y\n";
    } else {
        cout << "no y, size still " << seen.size() << "\n";   // 1
    }

    // C++20: contains() קריא יותר מ-count()
    if (seen.contains("x")) cout << "x is here\n";
}

כלל אצבע: השתמשו ב-[] רק כשאתם מתכוונים ליצור או לעדכן. לקריאה בלבד השתמשו ב-count, ב-contains (C++20) או ב-find.

find ו-at: חיפושים בטוחים

find מחזיר iterator לרשומה, או end() אם המפתח לא קיים. הוא אף פעם לא מכניס, והוא מאפשר להגיע גם למפתח וגם לערך דרך it->first ו-it->second בחיפוש אחד:

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

int main() {
    unordered_map<string, int> prices = {{"pen", 2}, {"mug", 9}};

    auto it = prices.find("mug");
    if (it != prices.end()) {
        cout << it->first << " costs " << it->second << "\n";
    } else {
        cout << "not found\n";
    }
}

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

int p = prices.at("pen");   // בסדר
int q = prices.at("hat");   // זורק std::out_of_range: המפתח לא קיים

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

מעבר על איברים ומחיקה

לולאת for מבוססת טווח עם structured bindings היא הדרך הנקייה לעבור על כל רשומה. זכרו שהסדר שרירותי: אף פעם אל תסתמכו עליו:

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

int main() {
    unordered_map<string, int> wins = {{"red", 4}, {"blue", 7}, {"green", 2}};

    for (const auto& [team, score] : wins) {
        cout << team << ": " << score << "\n";   // הסדר לא מוגדר
    }
}

כדי להסיר רשומה, erase מקבל מפתח ישירות ומחזיר כמה רשומות הוסרו (0 או 1). מלכודת חשובה אחת: מחיקה תוך כדי מעבר מבטלת ב-unordered_map רק את ה-iterator של האיבר שנמחק, אז השתמשו בערך ההחזרה של erase(it) כדי להתקדם בבטחה:

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

int main() {
    unordered_map<string, int> wins = {{"red", 4}, {"blue", 1}, {"green", 2}};

    // מסירים כל קבוצה עם ניקוד נמוך מ-3
    for (auto it = wins.begin(); it != wins.end(); ) {
        if (it->second < 3)
            it = wins.erase(it);   // erase מחזיר את ה-iterator התקין הבא
        else
            ++it;
    }

    cout << "remaining entries: " << wins.size() << "\n";
}

כתיבה בסגנון wins.erase(it++) או ++it אחרי erase(it) רגיל היא מלכודת ה-iterator התלוי הקלאסית: ה-iterator שנמחק מת, אז תמיד קחו את ה-iterator ש-erase מחזיר.

map או unordered_map?

שניהם מאחסנים זוגות מפתח-ערך עם API דומה, אז הבחירה תלויה במה שאתם צריכים:

// std::map            -> מפתחות ממוינים, O(log n), שאילתות טווח (lower_bound)
// std::unordered_map  -> בלי סדר,        O(1) בממוצע, החיפוש הפשוט המהיר ביותר

פנו ל-unordered_map כשצריך רק חיפוש מהיר לפי מפתח והסדר לא רלוונטי (ספירת תדירות מילים, caching, הסרת כפילויות). בחרו ב-map כשצריך מפתחות בסדר ממוין, מעבר לפי הסדר, או שאילתות טווח. שתי הסתייגויות לגבי unordered_map: ה-O(1) שלו הוא ממוצע, ופונקציית hash גרועה יכולה לפגוע בו, וטיפוס מפתח מותאם אישית צריך התמחות של hash או hash functor, בעוד ש-map צריך רק operator<.

הבא בתור: Set

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