STL Containers — C++ المتقدم

حاويات STL

اختيار الحاوية الصحيحة قرار يؤثر في سرعة البرنامج ووضوحه. القاعدة الأولى: ابدأ بـ vector ما لم يكن لديك سبب واضح لغيرها.

الحاويات التسلسلية

| الحاوية | الوصول بالفهرس | إضافة/حذف في النهاية | في البداية | في المنتصف |

|---|---|---|---|---|

| vector | O(1) | O(1) غالباً | O(n) | O(n) |

| deque | O(1) | O(1) | O(1) | O(n) |

| list | لا يوجد | O(1) | O(1) | O(1) إذا كان معك مكرِّر |

| array<T, N> | O(1) | حجم ثابت | — | — |

vector يخزن العناصر متجاورة في الذاكرة، والمعالج يحب ذلك (cache)؛ لذلك يتفوق عملياً على list حتى في حالات تبدو نظرياً لصالح list.

#include <deque>
#include <vector>
using namespace std;

vector<int> v = {1, 2, 3};
v.reserve(1000);          // احجز مسبقاً إن كنت تعرف الحجم: يمنع إعادة التخصيص المتكررة
v.push_back(4);
v.emplace_back(5);        // يبني العنصر في مكانه مباشرة

deque<int> d = {2, 3};
d.push_front(1);          // سريع في البداية والنهاية

الحاويات الترابطية (مرتبة)

set (قيم فريدة مرتبة) و map (مفتاح ← قيمة، مرتبة بالمفتاح). مبنية على شجرة متوازنة: البحث والإضافة والحذف O(log n).

الحاويات غير المرتبة (Hash)

unordered_set و unordered_map: جدول تجزئة، العمليات O(1) في المتوسط، لكن بلا ترتيب.

| تحتاج | استخدم |

|---|---|

| عناصر بالترتيب + بحث | set / map |

| بحث أسرع ولا يهم الترتيب | unordered_set / unordered_map |

| أكبر/أصغر عنصر باستمرار | priority_queue |

| مكدس / طابور | stack / queue (محوّلات فوق deque) |

فخ map::operator[]

#include <map>
#include <string>
using namespace std;

map<string, int> stock = {{"قلم", 10}};
int a = stock["دفتر"];            // ⚠️ يُنشئ "دفتر" بقيمة 0 إذا لم يوجد!
bool has = stock.contains("قلم"); // C++20: فحص بلا إنشاء
auto it = stock.find("ممحاة");    // find لا تُنشئ شيئاً
bool found = (it != stock.end());

- [] للكتابة أو عندما تريد القيمة الافتراضية فعلاً.

- find أو contains للبحث فقط، و at ترمي استثناء إذا لم يوجد المفتاح.

المرور على map بأسماء واضحة

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

int main() {
    map<string, int> ages = {{"سارة", 21}, {"عمر", 25}};
    for (const auto& [name, age] : ages)          // structured bindings (C++17)
        cout << name << ": " << age << '\n';
}

المكرِّرات (Iterators)

المكرِّر "مؤشر معمَّم" يمر على أي حاوية بنفس الطريقة: begin() أول عنصر، و end() بعد آخر عنصر. لهذا تعمل خوارزميات STL مع كل الحاويات.

⚠️ إبطال المكرِّرات: إضافة عنصر إلى vector قد تنقل كل العناصر لمكان جديد، فتصبح المكرِّرات والمؤشرات والمراجع القديمة معلّقة. لا تحتفظ بمكرِّر بعد تعديل الـ vector.

تمرين

اقرأ نصاً واحسب تكرار كل كلمة بـ unordered_map<string,int>، ثم انقل النتائج إلى vector من الأزواج ورتبها تنازلياً حسب العدد واطبع أكثر 3 كلمات.

#include <iostream>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <sstream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    // ===== vector: الخيار الافتراضي =====
    vector<int> scores;
    scores.reserve(5);                 // حجز مسبق
    for (int s : {72, 95, 88, 60, 95}) scores.push_back(s);
    cout << "vector: الحجم " << scores.size() << "، السعة " << scores.capacity() << "\n";

    // ===== deque: إضافة سريعة من الطرفين =====
    deque<string> line = {"سارة", "عمر"};
    line.push_front("مستعجل");
    line.push_back("ليلى");
    cout << "deque: أول " << line.front() << "، آخر " << line.back() << "\n";

    // ===== set: فريد ومرتب =====
    set<int> unique(scores.begin(), scores.end());
    cout << "set: ";
    for (int s : unique) cout << s << ' ';            // 60 72 88 95
    cout << "\n";

    // ===== map: مرتب بالمفتاح =====
    map<string, int> stock = {{"قلم", 10}, {"دفتر", 4}};
    stock["ممحاة"] += 3;                              // [] يُنشئ بقيمة 0 ثم يضيف
    if (auto it = stock.find("مسطرة"); it == stock.end())
        cout << "map: لا توجد مسطرة (find لم تُنشئ شيئاً)\n";
    for (const auto& [item, qty] : stock) cout << "  " << item << " = " << qty << "\n";

    // ===== unordered_map: عدّ الكلمات =====
    string text = "c++ سريعة و c++ قوية و c++ ممتعة";
    unordered_map<string, int> freq;
    istringstream in(text);
    for (string w; in >> w;) ++freq[w];

    vector<pair<string, int>> ranked(freq.begin(), freq.end());
    sort(ranked.begin(), ranked.end(), [](const auto& a, const auto& b) {
        return a.second != b.second ? a.second > b.second : a.first < b.first;
    });
    cout << "الأكثر تكراراً: " << ranked[0].first << " (" << ranked[0].second << ")\n";

    // ===== priority_queue: الأكبر أولاً =====
    priority_queue<pair<int, string>> tasks;
    tasks.push({2, "مراجعة"});
    tasks.push({5, "إصلاح عاجل"});
    tasks.push({1, "توثيق"});
    cout << "ترتيب المهام: ";
    while (!tasks.empty()) {
        cout << tasks.top().second << " ← ";
        tasks.pop();
    }
    cout << "انتهى\n";
    return 0;
}