‏C++ std::map: المفاتيح والقيم والبحث والإدراج

البحث عن الأشياء عبر المفتاح

تُعدّ 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> على أنها "map من مفاتيح 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>، لذا استخدم الربط البنيوي لتفكيك المفتاح والقيمة بأناقة:

#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";
    }
}

لاحظ أن المفتاح في الربط هو const: يمكنك تغيير قيمة عبر الحلقة باستخدام auto&، لكن لا يمكنك أبدًا تغيير مفتاح في مكانه (فذلك سيكسر ترتيب الفرز). يخرج الناتج مرتّبًا أبجديًا (blue، sea، sky) دون أي خطوة فرز، وهذا بالضبط هو السبب الذي يجعل الناس يختارون map بدلًا من جدول التجزئة عندما يكون المرور المرتّب مهمًا.

كما أن الصيغة 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، وما يصاحبها من مزالق التجزئة (أنواع المفاتيح المخصّصة، التصادمات في أسوأ الحالات).