‏C++ unordered_map: شرح البحث السريع في جدول التجزئة

عندما لا يهمّ الترتيب

لقد رأيت للتوّ std::map، الذي يبقي مفاتيحه مرتَّبة باستخدام شجرة متوازنة ويمنحك عمليات بتعقيد O(log n). لكن للترتيب كلفة، وكثيرًا ما لا يهمّك بأيّ ترتيب تخرج المفاتيح - كلّ ما تريده هو أن تسأل "هل هذا المفتاح موجود، وما قيمته؟" بأسرع ما يمكن.

لهذا وُجد std::unordered_map. إنه جدول تجزئة: يمرِّر كلّ مفتاح عبر دالة تجزئة ليقرّر مكان تخزينه، ما يجعل الإدراج والبحث والحذف بمتوسط 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 قيمته "")، ثم يُعيد مرجعًا. لذا فإنّ شيفرة تبدو كأنها بحث تُكبِّر الخريطة بهدوء:

#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 لمجرّد ذكره. لاختبار الوجود دون تعديل الخريطة، استخدم 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 (يُبلغان عن الوجود دون المساس بالخريطة). اختر الأسلوب الذي يطابق نمط فشله ما تقصده.

المرور على العناصر والحذف

تُعدّ حلقة 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 يُبطِل مكرِّر العنصر المحذوف وحده فقط، لذا استخدم القيمة المُعادة من 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 يُعيد المكرِّر الصالح التالي
        else
            ++it;
    }

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

كتابة الأسلوب wins.erase(it++) أو وضع ++it بعد erase(it) بسيط هو الفخّ الكلاسيكي للمكرِّر المعلَّق - المكرِّر المحذوف ميّت، فخذ دائمًا المكرِّر الذي يُعيده erase.

‏map أم unordered_map؟

كلاهما يخزِّن أزواج مفتاح-قيمة بواجهة متشابهة، لذا يتلخّص الاختيار في ما تحتاجه:

// std::map            -> مفاتيح مرتَّبة، O(log n)، استعلامات على نطاق (lower_bound)
// std::unordered_map  -> بلا ترتيب،     O(1) متوسط، أسرع بحث بسيط

اِلجأ إلى unordered_map عندما تحتاج فقط إلى بحث سريع بالمفتاح ويكون الترتيب غير ذي صلة (عدّ تكرارات الكلمات، التخزين المؤقت، إزالة التكرار). اختر map عندما تحتاج إلى المفاتيح بترتيب مُرتَّب، أو تريد المرور بترتيب، أو تُجري استعلامات على نطاق. تحذيران بشأن unordered_map: تعقيده O(1) هو متوسط - وقد تُدهوره دالة تجزئة سيئة - ونوع المفتاح المخصَّص يحتاج إلى تخصيص تجزئة (specialization) أو كائن دالة تجزئة (functor)، بينما لا يحتاج map إلا إلى operator<.

التالي: Set

لقد رأيت الآن كلا نوعَي حاوية المفتاح-القيمة. لكن أحيانًا لا تحتاج إلى قيمة على الإطلاق - يهمّك فقط هل الشيء موجود، مثل مجموعة من الوسوم الفريدة أو المعرّفات التي زُرتها. تاليًا سننظر في std::set (وقريبه المعتمِد على التجزئة unordered_set)، اللذين يخزّنان المفاتيح وحدها ويُبقيانها فريدة تلقائيًّا.