‏C++ set: عناصر فريدة ومرتّبة باستخدام std::set

حقيبة من القيم الفريدة والمرتّبة

رأيت كيف يخزّن unordered_map أزواج المفتاح-القيمة مع بحث سريع قائم على التجزئة. أما std::set فهو ابن العمّ الأبسط: يخزّن القيم فقط دون أي بيانات مرتبطة، ويفرض قاعدتين تلقائيًا. كل عنصر فريد (تُتجاهل التكرارات بصمت)، وتبقى العناصر دائمًا بترتيب مرتّب.

هذا يجعل set الخيار الطبيعي لأسئلة مثل «هل رأيت هذا من قبل؟» أو «أعطني العناصر المتمايزة بترتيب». تُدرج دون قلق بشأن التكرارات، وتُكرّر دون الحاجة إلى الترتيب أولًا.

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s;
    s.insert(40);
    s.insert(10);
    s.insert(30);
    s.insert(10);   // مكرّر - يُتجاهل

    for (int x : s) cout << x << " ";   // 10 30 40 (مرتّب، بلا تكرار)
}

لاحظ أننا أدرجنا 10 مرتين وبترتيب غير منظّم، ومع ذلك جاء الخرج مرتّبًا وظهر 10 مرة واحدة. لقد تكفّل الـ set بكل التنظيم نيابة عنك.

الإدراج والحذف

insert يضيف قيمة إن لم تكن موجودة من قبل. يُرجع pair يكون .second فيه قيمة bool تخبرك إن كان الإدراج قد حدث فعلًا، وهو مفيد عندما تريد معرفة ما إذا كانت القيمة جديدة:

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

int main() {
    set<string> seen;

    for (string word : {"go", "rust", "go", "cpp"}) {
        auto [it, inserted] = seen.insert(word);
        if (inserted)
            cout << "First time seeing: " << word << "\n";
        else
            cout << "Already saw: " << word << "\n";
    }
}

لحذف قيمة، استدعِ erase مع القيمة نفسها؛ فهو يُرجع عدد العناصر المحذوفة (0 أو 1 في الـ set). حذف شيء غير موجود غير ضارّ ولا يُعدّ خطأً:

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {1, 2, 3, 4};

    s.erase(3);          // يحذف 3
    s.erase(99);         // لا يفعل شيئًا، ويُرجع 0

    for (int x : s) cout << x << " ";   // 1 2 4
}

التحقق من العضوية

الغرض الأساسي من الـ set هو الاختبارات السريعة لـ «هل هذا موجود هنا؟». وأوضح طريقة هي count التي تُرجع 1 أو 0:

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> primes = {2, 3, 5, 7, 11};

    if (primes.count(7))
        cout << "7 is prime\n";

    if (!primes.count(9))
        cout << "9 is not in the set\n";
}

منذ C++20 صار هناك خيار أوضح للقراءة، وهو contains، الذي يُرجع قيمة bool مباشرة:

if (primes.contains(7)) { /* ... */ }   // C++20

من الأخطاء الشائعة اللجوء إلى operator[] كما تفعل مع map. الـ set لا يملك operator[]: لا توجد قيمة لجلبها، بل وجود فقط لاختباره. استخدم count أو contains، لا s[7].

إن احتجت إلى الموضع الفعلي (لحذفه أو للنظر إلى العناصر المجاورة)، استخدم find الذي يُرجع مؤشّرًا تكراريًا أو end():

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {10, 20, 30};

    auto it = s.find(20);
    if (it != s.end()) {
        cout << "found " << *it << "\n";
        s.erase(it);   // الحذف بالمؤشّر التكراري - دون بحث ثانٍ
    }
    cout << "size now " << s.size() << "\n";
}

التكرار المرتّب واستعلامات النطاق

بما أن الـ set مرتّب، فإن التكرار يُنتج العناصر دائمًا من الأصغر إلى الأكبر، وتحصل على حِيَل الحاويات المرتّبة مجانًا. lower_bound(x) يعطي أول عنصر ليس أصغر من x، وupper_bound(x) أول عنصر أكبر تمامًا من x؛ ومعًا يتيحان لك مسح نطاق رقمي دون فحص كل عنصر:

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {5, 12, 18, 23, 31, 47};

    // اطبع كل ما يقع في النطاق [12, 31]
    auto begin = s.lower_bound(12);
    auto end = s.upper_bound(31);
    for (auto it = begin; it != end; ++it)
        cout << *it << " ";   // 12 18 23 31
}

قاعدة دقيقة لكنها مهمة: عناصر الـ set غير قابلة للتعديل. يمنحك المؤشّر التكراري مرجعًا من نوع const، لذا لا يمكنك تغيير عنصر في مكانه؛ فالقيام بذلك قد يكسر ترتيب الفرز الذي تعتمد عليه الحاوية. ولكي «تغيّر» قيمة، احذف القديمة وأدرج الجديدة.

الترتيب افتراضيًا تصاعدي (std::less). وللترتيب التنازلي، مرّر مُقارِنًا مختلفًا كوسيط القالب الثاني:

#include <iostream>
#include <functional>
#include <set>
using namespace std;

int main() {
    set<int, greater<int>> s = {5, 12, 18, 23};

    for (int x : s) cout << x << " ";   // 23 18 12 5
}

‏set و multiset و unordered_set

std::set واحد من ثلاثة أقارب متقاربين، واختيار المناسب منها أمر مهمّ:

set<int>            // قيم فريدة، مرتّبة، O(log n)
multiset<int>       // يسمح بالتكرارات، مرتّبة، O(log n)
unordered_set<int>  // قيم فريدة، بلا ترتيب، O(1) في المتوسط

ألجأ إلى unordered_set عندما تحتاج فقط إلى اختبارات عضوية ولا يهمّك الترتيب؛ فعمليات بحثه القائمة على التجزئة أسرع في المتوسط من O(log n) القائمة على الشجرة في الـ set. اختر set عندما تحتاج إلى عناصر بترتيب مرتّب، أو استعلامات نطاق بـ lower_bound/upper_bound، أو سلوك مستقرّ للمؤشّرات التكرارية. استخدم multiset فقط عندما تكون التكرارات ذات معنى (مثل مدرّج تكراري لقيم متكرّرة): ففي الـ multiset قد يُرجع count(x) أكثر من 1، ويحذف erase(x) كل النسخ ما لم تحذف عبر مؤشّر تكراري واحد.

من الاستخدامات الكلاسيكية للـ set: إزالة التكرارات من vector وترتيبه في خطوة واحدة.

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
    vector<int> data = {4, 1, 4, 2, 1, 3};
    set<int> unique(data.begin(), data.end());

    for (int x : unique) cout << x << " ";   // 1 2 3 4
}

بناء الـ set من المؤشّرات التكرارية لـ vector يُسقط كل تكرار ويرتّب الباقي، دون حلقة يدوية، ودون رقصة std::sort مع std::unique.

التالي: pair و tuple

رأيت الآن .first و.second تظهران على الـ pair الذي يُرجعه insert، ورأيت الربط البنيوي (auto [it, inserted]) يفكّكه بأناقة. هذه الأنواع الخفيفة التي «تجمع بضع قيم معًا» منتشرة في كل أنحاء الـ STL. سننظر تاليًا في pair و tuple مباشرة: كيف تبنيها، وتفكّكها، وتُرجع عدة قيم من دالة دون تعريف بنية كاملة.