لوحة المتصدرين

نبدأ بدايةً بسرد بعض الأمور المتعلقة بالقاموس أو النوع std::map: لاستخدام أحد الصنفين ‎std::map‎ (القواميس) أو ‎std::multimap‎ (القواميس المتعدّدة)، يجب تضمين الترويسة. تُبقي القواميس والقواميس المتعدّدة عناصرها مرتّبة تصاعديًا وفقًا للمفاتيح، وفي حالة القواميس المتعدّدة (‎std::multimap‎) فإن القيم التي لها نفس المفتاح لا تُرتّب. الاختلاف الأساسي بين القواميس والقواميس المتعدّدة هو أنّ القواميس لا تسمح بأن تكون هناك أكثر من قيمة واحدة مرتبطة بالمفتاح نفسه، وذلك على خلاف القواميس المتعدّدة. تُقدَّم القواميس كأشجار بحث ثنائية (binary search trees). لذا تستغرق دوالّّ ‎search()‎ و ‎insert()‎ و ‎erase()‎ وقتًا لوغاريتميًا يساوي Θ(log n)‎ في المتوسط. إن أردت عمليات تأخذ وقتًا ثابتًا، فاستخدم ‎std::unordered_map‎. تعقيد الدالّتين ‎size()‎ و ‎empty()‎ يساوي (Θ(1، إذ يُخزّن عدد العُقَد مؤقتًا لتجنّب المرور عبر الشجرة في كل مرّة تُستدعى فيه هاتان الدالتان. الوصول إلى العناصر تأخذ القواميس أزواجًا قيمة-مفتاح ‎(key, value)‎ كمُدخلات. يوضح المثال التالي كيفية تهيئة std::map: std::map < std::string, int > ranking { std::make_pair("stackoverflow", 2), std::make_pair("docs-beta", 1) }; يمكن إدراج العناصر في القواميس على النحو التالي: ranking["stackoverflow"]=2; ranking["docs-beta"]=1; في المثال أعلاه، إذا كان المفتاح ‎stackoverflow‎ موجودًا من قبل، فستُحدّث قيمته إلى 2. وإن لم يكن موجودًا، فسيُنشأ مدخل جديد. يمكن الوصول إلى عناصر القاموس std::map مباشرةً عن طريق تمرير المفتاح كفهرس: std::cout << ranking[ "stackoverflow" ] << std::endl; لاحظ أنّ استخدام عامل الفهرسة ‎operator[]‎ على القاموس سيؤدّي إلى إدراج قيمة جديدة باستخدام المفتاح الذي تمّ الاستعلام عنه في القاموس. هذا يعني أنّه لا يمكنك استخدامه على القواميس الثابتة ‎const std::map‎، حتى لو كان المفتاح مخزّنًا سلفًا في القاموس. ولمنع هذا الإدراج، تحقق من وجود العنصر (مثلًا باستخدام ‎find()‎) أو استخدم ‎at()‎ كما هو موضّح أدناه. الإصدار ≥ C++‎ 11 يمكن الوصول إلى عناصر القواميس باستخدام التابع ‎at()‎: std::cout << ranking.at("stackoverflow") << std::endl; لاحظ أنّ التابع ‎at()‎ سيرفع اعتراض ‎std::out_of_range‎ إن لم تحتوي الحاوية على العنصر المطلوب. يمكن الوصول في القواميس والقواميس المتعدّدة إلى العناصر باستخدام المُكرّرات: الإصدار ≥ C++‎ 11 // begin() مثال على استخدام std::multimap < int, std::string > mmp { std::make_pair(2, "stackoverflow"), std::make_pair(1, "docs-beta"), std::make_pair(2, "stackexchange") }; auto it = mmp.begin(); std::cout << it -> first << " : " << it -> second << std::endl; // "1 : docs-beta" it++; std::cout << it -> first << " : " << it -> second << std::endl; // "2 : stackoverflow" it++; std::cout << it -> first << " : " << it -> second << std::endl; // "2 : stackexchange" // rbegin() مثال على استخدام std::map < int, std::string > mp { std::make_pair(2, "stackoverflow"), std::make_pair(1, "docs-beta"), std::make_pair(2, "stackexchange") }; auto it2 = mp.rbegin(); std::cout << it2 -> first << " : " << it2 -> second << std::endl; // "2 : stackoverflow" it2++; std::cout << it2 -> first << " : " << it2 -> second << std::endl; // "1 : docs-beta" إدراج عناصر في القواميس لا يمكن إدراج عنصر في قاموس إلّا إن كان مفتاحه غير موجود من قبل في القاموس. على سبيل المثال: std::map< std::string, size_t > fruits_count; يمكن إدراج زوج قيمة-مفتاح (key-value) في قاموس عبر التابع ‎insert()‎، والذي يتطلب زوجًا (‎pair‎) كوسيط: fruits_count.insert({"grapes", 20}); fruits_count.insert(make_pair("orange", 30)); fruits_count.insert(pair<std::string, size_t>("banana", 40)); fruits_count.insert(map<std::string, size_t>::value_type("cherry", 50)); تعيد الدالّة ‎insert()‎ زوجًا مؤلّفًا من مُكرّر وقيمة بوليانية ‎bool‎: إن نجحت عملية الإدراج فإنّ المكرّر يشير إلى العنصر المُدرج حديثًا، وستكون القيمة البوليانية ‎bool‎ المعادة صحيحة (‎true‎). إن كان في القاموس مدخل له نفس المفتاح ‎key‎ فستفشل عملية الإدراج. وحينها سيشير المكرّر إلى العنصر الذي له ذلك المفتاح، وستسَاوي ‎bool‎ القيمة ‎false‎ يمكن استخدام الطريقة التالية لدَمج عمليتي الإدراج والبحث معًا: auto success = fruits_count.insert({"grapes", 20}); if (!success.second) { // موجود سلفا في القاموس 'grapes' success.first -> second += 20; // الدخول إلى المكرر لتحديث القيمة } يُستخدم عامل الفهرسة للوصول إلى العناصر الموجودة في القاموس، أو إدراج عناصر جديدة في حال لم تكن موجودة: fruits_count["apple"] = 10; المشكلة في هذا العامل أنه يمنع المستخدم من التحقّق مما إذا كان العنصر موجودًا بالفعل. وفي حال لم يكن العنصر موجودًا، فسيُنشئه العامل std::map::operator[]‎ ضمنيًا، إذ سيهيِّئه باستخدام المُنشئ الافتراضي قبل إعادة كتابته بالقيمة المعطاة.. يمكن استخدام التابع ‎insert()‎ لإضافة عدّة عناصر دفعة واحدة عبر تمرير قائمة من الأزواج، يعيد هذا الإصدار من ‎insert()‎ القيمة الفارغة void: fruits_count.insert({{"apricot", 1}, {"jackfruit", 1}, {"lime", 1}, {"mango", 7}}); يمكن أيضًا استخدام ‎insert()‎ لإضافة عدّة عناصر باستخدام مُكرّرات تشير إلى بداية ونهاية ‎value_type‎: std::map< std::string, size_t > fruit_list{ {"lemon", 0}, {"olive", 0}, {"plum", 0}}; fruits_count.insert(fruit_list.begin(), fruit_list.end()); مثال: سنضيف عنصرًا يساوي مفتاحه fruit وقيمته 1، وإن المفتاح موجودًا فلن تفعل fruit_count أي شيء. std::map < std::string, size_t > fruits_count; std::string fruit; while (std::cin >> fruit) { auto ret = fruits_count.insert({ fruit, 1 }); if (!ret.second) { // موجود سلفا 'fruit' ++ret.first -> second; // زيادة العداد } } التعقيد الزمني لعملية الإدراج هو O(log n)‎، ذلك أنّ القواميس تُنفَّذ على هيئة أشجار. الإصدار ≥ C++‎ 11 يمكن إنشاء زوج (‎pair‎) بشكل صريح باستخدام ‎make_pair()‎ و ‎emplace()‎: std::map< std::string , int > runs; runs.emplace("Babe Ruth", 714); runs.insert(make_pair("Barry Bonds", 762)); يمكننا استخدام ‎emplace_hint()‎ إذا علمنا أين سيُدرج العنصر الجديد من أجل تحديد مكرّر ‎hint‎. إذا استطعنا إدراج العنصر الجديد قبل ‎hint‎ مباشرة فيمكن إجراء الإدراج في وقت ثابت، وإلا فإنّه سيتصرف مثل التابع ‎emplace()‎. انظر المثال التالي حيث نطلب الحصول على مكرر يشير إلى العنصر المُدرَج، ويكون العنصر التالي قبل Barry Bonds لذا سيُدرَج قبل it: std::map < std::string, int > runs; auto it = runs.emplace("Barry Bonds", 762); runs.emplace_hint(it, "Babe Ruth", 714); البحث في القواميس والقواميس المتعدّدة هناك عدّة طرق للبحث عن مفتاح في قاموس أو قاموس متعدّد . للحصول على مُكرّر يشير إلى أوّل ظهور لمفتاح معيّن، استخدم الدالّة ‎find()‎ التي تعيد ‎end()‎ إن لم يكن المفتاح موجودًا. std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} }; auto it = mmp.find(6); if (it != mmp.end()) std::cout << it -> first << ", " << it -> second << std::endl; // 6, 5 else std::cout << "Value does not exist!" << std::endl; it = mmp.find(66); if (it != mmp.end()) std::cout << it -> first << ", " << it -> second << std::endl; else std::cout << "Value does not exist!" << std::endl; // سيتم تنفيذ هذا السطر هناك طريقة أخرى لمعرفة ما إذا كان قاموس أو قاموس متعدّد يحتوي على مدخَل معيّن، وهي استخدام الدالّة ‎count()‎، والتي تحسب عدد القيم المرتبطة بمفتاح معين، وبما أن القواميس لا تربط إلا قيمة واحدة فقط بكلّ مفتاح، فإنّ الدالّة ‎count()‎ ستُعيد إمّا 0 -إن كان المفتاح غير موجود-، أو 1 -إن كان موجودًا-، أما بالنسبة إلى القواميس المتعدّدة فيمكن أن تعيد الدالّةُ ‎count()‎ قيمًا أكبر من 1 لأنّها تُجيز ربط عدّة قيم بنفس المفتاح. std::map< int , int > mp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} }; if (mp.count(3) > 0) // المفتاح 3 موجود في القاموس std::cout << "The key exists!" << std::endl; // سيتم تنفيذ هذا السطر else std::cout << "The key does not exist!" << std::endl; إن كان كل ما تريده هو التحقق من وجود عنصر ما، فإنّ ‎find‎ أفضل بلا شكّ: فعملُها واضح من اسمها، وبالنسبة للقواميس المتعدّدة ‎multimaps‎، فإنّها تتوقف بمجرّد العثور على أول عنصر مطابِق. يمكن أن ترتبط عدّة عناصر بنفس المفتاح في حالة القواميس المتعدّدة، وللحصول على تلك العناصر، يمكن استخدام الدالّة ‎equal_range()‎ التي تُعيد زوجًا يحتوي مُكرّر الحدّ الأدنى - iterator lower bound - (مُضمّن) ومُكرّر الحدّ الأعلى - iterator upper bound - (غير مُضمّن) على التوالي. إذا لم يكن المفتاح موجودًا، فسيُشير كلا المُكرّرين إلى ‎end()‎. auto eqr = mmp.equal_range(6); auto st = eqr.first, en = eqr.second; for (auto it = st; it != en; ++it) { std::cout << it -> first << ", " << it -> second << std::endl; } // 6, 7 تهيئة القواميس والقواميس المتعددة يمكن تهيئة قاموس أو قاموس متعدّد عبر توفير أزواج قيمة-مفتاح مفصولة بفاصلة ,، ويمكن توفير أزواج قيمة-مفتاح وفق الصيغة ‎{key, value}‎ أو إنشاؤها بشكل صريح بواسطة الدالّة ‎std::make_pair(key, value)‎. ولأنّ القواميس لا تسمح بالمفاتيح المكرّرة ولأن عامل الفاصلة (comma operator) يعمل من اليمين إلى اليسار، فسَتتم الكتابة على الزوج الموجود على اليمين باستخدام الزوج ذي المفتاح نفسه والمَوجود على اليسار. std::multimap < int, std::string > mmp { std::make_pair(2, "stackoverflow"), std::make_pair(1, "docs-beta"), std::make_pair(2, "stackexchange") }; // 1 docs-beta // 2 stackoverflow // 2 stackexchange std::map < int, std::string > mp { std::make_pair(2, "stackoverflow"), std::make_pair(1, "docs-beta"), std::make_pair(2, "stackexchange") }; // 1 docs-beta // 2 stackoverflow كلاهما يمكن تهِيئتهما عبر المكرّرات. انظر: من مكرر std::map أو std::multimap: std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {6, 8}, {3, 4}, {6, 7} }; // {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 8}, {6, 7}, {8, 9} auto it = mmp.begin(); std::advance(it,3); // {6, 5} حرك المؤشر على أول std::map< int, int > mp(it, mmp.end()); // {6, 5}, {8, 9} من مصفوفة الأزواج: std::pair< int, int > arr[10]; arr[0] = {1, 3}; arr[1] = {1, 5}; arr[2] = {2, 5}; arr[3] = {0, 1}; std::map< int, int > mp(arr,arr+4); //{0 , 1}, {1, 3}, {2, 5} من متجه std::vector من الأزواج std::pair: std::vector< std::pair<int, int> > v{ {1, 5}, {5, 1}, {3, 6}, {3, 2} }; std::multimap< int, int > mp(v.begin(), v.end()); // {1, 5}, {3, 6}, {3, 2}, {5, 1} التحقق من عدد العناصر حاوية std::map بها الدالة التابعة ‎empty()‎، التي تعيد إحدى القيمتين ‎true‎ أو ‎false‎ حسب حالة القاموس هل فارغ أم لا، بينما تعيد ‎size()‎ عدد العناصر المخزّنة في القاموس: std::map<std::string , int> rank {{"facebook.com", 1} ,{"google.com", 2}, {"youtube.com", 3}}; if(!rank.empty()){ std::cout << "Number of elements in the rank map: " << rank.size() << std::endl; } else{ std::cout << "The rank map is empty" << std::endl; } أنواع القواميس القواميس العادية القاموس عبارة عن حاوية ترابطية (associative container) تحتوي على أزواج "قيمة-مفتاح". #include <string> #include <map> std::map<std::string, size_t> fruits_count; في المثال أعلاه، تمثّل ‎std::string‎ نوع المفتاح، وتمثل ‎size_t‎ القيمة. يتصرّف المفتاح كفهرس في القاموس، ويجب أن يكون كل مفتاح فريدًا، ومُرتّبًا. إذا كنت بحاجة إلى قاموس يسمح بأن ترتبط عدّة قيم بنفس المفتاح، فعليك استخدام قاموس متعدّد ‎multimap‎ كما هو موضّح أدناه. إذا لم يكن هناك أيّ ترتيب مرتبط بنوع القيمة، أو إذا كنت تريد تجاوز الترتيب الافتراضي، فيمكنك إنشاء ترتيب خاصّ بك عبر: #include <string> #include <map> #include <cstring> struct StrLess { bool operator()(const std::string & a, const std::string & b) { return strncmp(a.c_str(), b.c_str(), 8) < 0; // قارن الأحرف الثمانية الأولى فقط } } std::map < std::string, size_t, StrLess > fruits_count2; إن أعادت دالّة الموازنة ‎StrLess‎ القيمة ‎false‎، فيكون المفتَاحان متساويَين، حتى لو كانت محتوياتهما مختلفة. القواميس المتعددة تسمح القواميس المتعدّدة بتخزين عدّة أزواج لها نفس المفتاح في القاموس، وإلا فإنّ واجهتها وطريقة إنشائها ستشبه القواميس العادية. #include <string> #include <map> std::multimap<std::string, size_t> fruits_count; std::multimap<std::string, size_t, StrLess> fruits_count2; قواميس التجزئة (القواميس غير المرتبة) تُخزِّن قواميس التجزئة (hash maps) أزواج "المفتاح-القيمة" بطريقة مشابهة للقواميس العادية، إلا أنها لا ترتّب العناصر وفقًا للمفاتيح، وإنما تُستخدم قيمة التجزئة (hash value) الخاصة بالمفتاح للوصول بسرعة إلى الأزواج قيمة-مفتاح المطلوبة. #include <string> #include <unordered_map> std::unordered_map<std::string, size_t> fruits_count; القواميس غير المرتّبة أسرع عادةً، بيْد أنه لا يمكن توقّع ترتيب عناصرها. على سبيل المثال، يكون التكرار على عناصر قاموس غير مرتب ‎unordered_map‎ بترتيب عشوائي. حذف العناصر إزالة جميع العناصر: std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} }; mmp.clear(); // أصبح القاموس المتعدّد فارغا إزالة عنصر ما باستخدام مكرّر: std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} }; // {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 7}, {8, 9} auto it = mmp.begin(); std::advance(it,3); // {6, 5} إزاحة المؤشّر إلى أول mmp.erase(it); // {1, 2}, {3, 4}, {3, 4}, {6, 7}, {8, 9} إزالة جميع العناصر في نطاق معيّن: std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} }; // {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 7}, {8, 9} auto it = mmp.begin(); auto it2 = it; it++; // {3, 4} إزاحة المؤشّر إلى أول std::advance(it2,3); // {6, 5} إزاحة المؤشّر الثاني إلى أول mmp.erase(it,it2); // {1, 2}, {6, 5}, {6, 7}, {8, 9} إزالة جميع العناصر التي لها مفتاح معيّن: std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} }; // {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 7}, {8, 9} mmp.erase(6); // {1, 2}, {3, 4}, {3, 4}, {8, 9} إزالة العناصر التي تحقق شرطًا ‎pred‎ معيّنا: std::map < int, int > m; auto it = m.begin(); while (it != m.end()) { if (pred( *it)) it = m.erase(it); else ++it; } التكرار على القواميس والقواميس المتعددة يمكن التكرار على القواميس والقواميس المتعدّدة بالطرق التالية: std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} }; // C++11 حلقة نطاقية - منذ for (const auto & x: mmp) std::cout << x.first << ":" << x.second << std::endl; //أمامي، سيمرُّ على العناصر من الأول حتى الأخير for مكرّر // std::map< int, int >::iterator سيكون من النوع for (auto it = mmp.begin(); it != mmp.end(); ++it) std::cout << it -> first << ":" << it -> second << std::endl; //افعل شيئا ما بالمكرر // عكسي، سيمُرّ على العناصر من الأخير إلى الأول for مكرر // std::map< int, int >::reverse_iterator سيكون من النوع for (auto it = mmp.rbegin(); it != mmp.rend(); ++it) std::cout << it -> first << " " << it -> second << std::endl; // افعل شيئا ما بالمكرّر يُفضّل أثناء التكرار على قاموس أو قاموس متعدّد استخدام ‎auto‎ لتجنّب التحويلات الضمنية غير المفيدة (راجع هذه الإجابة في موقع StackOverFlow لمزيد من التفاصيل). إنشاء قاموس باستخدام الأنواع المُعرَّفة من المستخدم كمفتاح لكي تكون قادرًا على استخدام صنف كمفتاح في القاموس، ينبغي أن يكون المفتاح قابلًا للنسخ ‎copiable‎ والإسناد ‎assignable‎. يُحدَّد الترتيب داخل القاموس من قِبل الوسيط الثالث المُمرّر إلى القالب (والوسيط الممرّر إلى المُنشئ، في حال استخدامه) ويساوي افتراضيًا ‎std::less<KeyType>‎، والذي يساوي (افتراضيًا) عامل المقارنة ‎<‎. لكن لا يلزم استخدام عامل المقارنة الافتراضي إذ يمكنك كتابة معامل مقارنة خاصّ بك (يفضل أن يكون كائنًا داليًا - functional object): struct CmpMyType { bool operator()( MyType const& lhs, MyType const& rhs ) const { // ... } }; في C++‎، يجب أن يكون شرط "المقارنة" (compare predicate) ترتيبًا ضعيفًا صارمًا (strict weak ordering)، ويجب أن يعيد تعبيرُ ‎compare(X,X)‎ القيمة ‎false‎ مهما كانت قيمة ‎X‎، فإن أعاد التعبير ‎CmpMyType()(a, b)‎ القيمة true، فإنّ التعبيرَ ‎CmpMyType()(b, a)‎ ينبغي أن يعيد false، وفي حال أعاد كلاهما القيمة false، فسيُعدُّ العنصران a و b متساويين. الترتيب الضعيف الصارم هذا مصطلح رياضيّاتي لتعريف العلاقة بين كائنين. ويعني: في C++‎، هذا يعني أنه إن كان لديك كائنان من نوع معيّن، فيجب أن يتحقّق الجدول التالي عند مقارنتهما بواسطة المُعامل ‎<‎. X a; X b; Condition: Test: Result a is equivalent to b: a < b false a is equivalent to b b < a false a is less than b a < b true a is less than b b < a false b is less than a a < b false b is less than a b < a true تعتمد الطريقة التي تعرِّف بها مفهوم التكافؤ كليًا على نوع الكائن. القواميس غير المرتبة القواميس غير المُرتّبة std::unordered_map تشبه القواميس العادية، فهي حاوية ترابطية (Associative Container) تعمل على المفاتيح وقواميسها، فالمفاتيح تحقق التفرد في القاموس لعناصره، بينما تكون قيمة القاموس "map" مجرد محتوى مرتبط بالمفتاح، وأنواع البيانات الخاصة بهذا المفتاح والقاموس يمكن أن تكون أي نوع بيانات معرَّف مسبقًا أو عرَّفه المستخدم. كيفية التصريح والاستخدام يمكن التصريح عن قاموس غير مرتّب من أيّ نوع كما أوضحنا، وسنعرّف قاموسًا غير مرتّب في المثال التالي، يحمل الاسم first باستخدام النوعين string و integer. unordered_map < string, int > first; // إعلان القاموس first["One"] = 1; // [] استخدام العامل first["Two"] = 2; first["Three"] = 3; first["Four"] = 4; first["Five"] = 5; pair < string, int > bar = make_pair("Nine", 9); // إنشاء زوج من نفس النوع first.insert(bar); بعض الدوال الأساسية للتعامل مع القواميس هذه بعض الدوال الأساسية الخاصة بالقواميس غير المرتبة: unordered_map<data_type, data_type> variable_name; // التصريح variable_name[key_value] = mapped_value; // إدراج العناصر variable_name.find(key_value); // إعادة مكرّر إلى قيمة المفتاح variable_name.begin(); // مكرّر إلى العنصر الأول variable_name.end(); // مكرر إلى العنصر الأخير + 1 هذا الدرس جزء من سلسلة مقالات عن C++‎. ترجمة -بتصرّف- للفصلين Chapter 50: std::map و Chapter 61: Using std::unordered_map من كتاب C++ Notes for Professionals