C++ / المتوسط / الدرس 9
الخوارزميات والمكررات والحاويات
ركّب خوارزميات قياسية على نطاقات مكررات صالحة، والتزم بشروطها، واختر الحاويات وفق العمليات المطلوبة.
في هذه الصفحة
أهداف الدرس
- شرح نطاقات المكررات نصف المفتوحة وموضع ما بعد النهاية.
- تطبيق الفرز والتجميع والحذف بعد remove بصورة صحيحة.
- اختيار الحاويات وفق الترتيب والبحث وثبات الوصول.
النطاق الصالح يستبعد نهايته
تقبل الخوارزمية التقليدية غالبًا نطاقًا نصف مفتوح [first, last). يشير first إلى العنصر الأول وlast إلى موضع بعد الأخير مباشرة. تتساوى نهايتا النطاق الفارغ. لا تفك مرجع مكرر ما بعد النهاية. لا تشكل مكررات حاويتين مختلفتين نطاقًا صالحًا ولو بدت عناوينها متقاربة. تصف فئات المكررات قدرات الاجتياز؛ يحتاج sort وصولًا عشوائيًا، بينما تعمل عمليات بحث كثيرة بقدرات أضعف. طابق متطلبات الخوارزمية مع الحاوية بدل افتراض دعم كل مكرر للجمع والطرح.
فصل الترتيب عن التجميع
يفرز المثال الأول متجهًا ثم يجمع قيمه. تغيّر std::sort ترتيب العناصر ولا تضمن ثبات ترتيب العناصر المتكافئة. يجب أن يحدّد مقارنها ترتيبًا ضعيفًا صارمًا، فلا تصلح أصغر من أو يساوي بدل أصغر من. تبدأ accumulate بنوع القيمة الابتدائية، ويختار الصفر حساب int هنا. للمجاميع الكبيرة اختر مجمّعًا أوسع وافحصه بوعي. لا تزيل الخوارزميات مخاطر الفيض، ولا تستنتج المكتبة القياسية الحد الأقصى الخاص بالمسألة من محتويات الحاوية.
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
int main() {
std::vector<int> values{4, 1, 3, 2};
std::sort(values.begin(), values.end());
for (int value : values) { std::cout << value << " "; }
std::cout << "sum=" << std::accumulate(values.begin(), values.end(), 0) << "\n";
}
1 2 3 4 sum=10
تصبح القيم تصاعدية ويبلغ المجموع عشرة. تتجنب المدخلات الصحيحة هنا التباس ترتيب المتكافئات والفيض.
الخوارزمية لا تغيّر حجم حاويتها
تنقل std::remove_if العناصر المحتفظ بها نحو البداية وتعيد نهاية منطقية جديدة، ولا تغيّر حجم المتجه. تبقى العناصر المتأخرة صالحة لكن قيمها غير محددة، فلا تفسّرها على أنها السجلات المحذوفة. ينجز حذف الذيل المعاد الإزالة البنيوية. يسمّي المثال الثاني النهاية المنطقية ويحذف ذلك الذيل فقط. توفر C++20 أيضًا std::erase_if لعدة حاويات، لكن فهم النمط ذي الخطوتين يفسر الشيفرة الأقدم ويميّز إعادة الترتيب الخوارزمية من تغيير الأعمار بواسطة الحاوية.
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> values{1, 2, 3, 4, 5};
const auto logical_end = std::remove_if(values.begin(), values.end(),
[](int value) { return value % 2 == 0; });
values.erase(logical_end, values.end());
for (int value : values) { std::cout << value << " "; }
std::cout << "size=" << values.size() << "\n";
}
1 3 5 size=3
يختار الشرط اثنين وأربعة للحذف. يبقى ترتيب المحتفظ بها واحدًا وثلاثة وخمسة، ويجعل حذف الذيل الحجم ثلاثة.
اختيار العمليات المطلوبة فعلًا
يصلح vector أساسًا جيدًا للاجتياز المتجاور والتخزين المدمج. يحافظ map على ترتيب المفاتيح ويدعم بحثًا لوغاريتميًا، ويتيح unordered_map بحثًا ثابت الزمن وسطياً دون ترتيب اجتياز مفيد مضمون ومع احتمال زمن خطي في أسوأ الحالات. يحافظ list على مكررات العناصر الأخرى عبر إضافات كثيرة لكنه يدفع كلفة تخصيص وضعف محلية. يصف التعقيد النمو مع حجم الإدخال ولا يرتب السرعة المقاسة. افحص الإبطال وكلفة الذاكرة والترتيب معًا. وقد يُدخل operator[] مفتاحًا مفقودًا في map، فاستخدم find للمراقبة دون تعديل.
فحص الشروط قبل الوثوق بالنتائج
يحتاج البحث الثنائي نطاقًا مرتبًا بالمقارنة نفسها المستخدمة للبحث. تعيد lower_bound أول موضع ليس أصغر من الهدف، وقد يكون end أو عنصرًا غير مساوٍ. افحص الشرطين قبل إعلان العثور. ينبغي أن تكون الشروط واضحة وألا تبطل النطاق الذي تفحصه. عند تعديل حاوية أثناء الاجتياز استخدم مكرر erase المعاد حيث تتطلب الواجهة. قد تكشف أوضاع تصحيح المكررات أخطاء كثيرة، لكنها تدعم ولا تستبدل إثبات صلاحية النطاق والعمر.
الأخطاء الشائعة وإصلاحها
remove_if لا تغيّر حجم المتجه.
- لماذا يحدث؟
- تضغط الخوارزمية النطاق المنطقي فقط.
- كيف تصلحه؟
- احذف من المكرر المعاد إلى end.
- كيف تتجنب تكراره؟
- افصل إعادة الترتيب عن التغيير البنيوي للحاوية.
مقارن يستخدم <= ويختل الفرز.
- لماذا يحدث؟
- المقارنة ليست غير انعكاسية.
- كيف تصلحه؟
- استخدم ترتيبًا صارمًا مثل < مع معالجة متسقة للتعادل.
- كيف تتجنب تكراره؟
- تحقق أن compare(x, x) خطأ وراجع قوانين الترتيب.
فك مرجع نتيجة بحث تساوي end.
- لماذا يحدث؟
- أُهملت حالة عدم العثور.
- كيف تصلحه؟
- قارن مع end قبل الوصول إلى العنصر.
- كيف تتجنب تكراره؟
- اختبر النطاق الفارغ والهدف المفقود صراحة.
اختبر فهمك
1. ابحث بـlower_bound عن ستة في القيم المرتبة 2 و5 و8. فسّر الموضع المعاد وهل يثبت العضوية.
اعرض الحل المشروح
يشير المكرر المعاد إلى ثمانية، أول عنصر ليس أصغر من ستة. يختلف عن end لكنه لا يساوي المطلوب، إذن ستة غير موجود. يحتاج فحص العضوية الكامل iterator != end و*iterator == target. ويعيد البحث عن تسعة end فلا يجوز فك مرجعه.
2. تحتاج مهمة تقارير اجتيازًا مرتبًا وقراءات متكررة لمجاميع مسماة. اختر map أو unordered_map وفسّر متى يتغير الاختيار.
اعرض الحل المشروح
يوفر map ترتيب المفاتيح مباشرة وبحثًا لوغاريتميًا فيلائم الشرطين دون فرز قائمة مفاتيح منفصلة. قد يناسب unordered_map عبئًا تطغى فيه كلفة البحث الوسطية ويمكن فرز الإخراج منفصلًا. قِس بيانات ممثلة قبل تغيير التصميم، ولا تعتبر ترتيب الاجتياز غير المرتب ترتيب تقارير حتميًا.
أهم ما تعلمته
- استخدم نطاقات نصف مفتوحة صالحة والتزم بشروط الخوارزمية.
- ميّز الإزالة المنطقية من إتلاف العناصر.
- اختر الحاويات وفق الترتيب والعمر وعبء العمل.