مكتبة القوالب المعيارية Set في لغة ++C

اقرأ في هذا المقال


ما هي حاوية Set في لغة ++C؟

(set) هي عبارة عن حاوية ترابطية (أي ترتبط كل قيمة بمفتاح)، وتحتوي (set) على مجموعة مرتبة من العناصر الفريدة وتكون من نوع المفتاح، يظهر كل عنصر مرة واحدة فقط، لذلك فهي لا تسمح بالتكرارات، و إذا أُدخل عنصر إلى حاوية (set) لا يمكن التعديل على قيمته، أي أن العناصر دائمًا ثابتة (const)، ولكن يمكن إدخالها أو إزالتها من الحاوية، وتكون حاويات (set) بشكل عام أبطأ من (unordered_set)، في الوصول إلى العناصر بشكل فردي عن طريق مفتاحه.

أهم الدوال في الـ Set:

 الدالةاستخدامهاتعقيد الوقت
1- ()beginيُرجع (Return) مؤشر يشير إلى موقع أول عنصر في (set)، وتستطيع من خلاله التنقل عبر محتويات (set).(1)O
2- ()endيُرجع مؤشر يشير إلى موقع الذي يتبع العنصر الأخير في (set)، بالتالي لا يشير إلى أي عنصر في (set).O(1)
3- ()rbeginيرجع مؤشر يشير إلى موقع العنصر الأخير في (set)، ويعني (reverse begin) أي بداية عكسية.O(1)
4- ()rendيرجع مؤشر يشير إلى موقع الذي يسبق أول عنصر في (set)، بالتالي لا يشير إلى أي عنصر في (set)، ويعني (reverse end) أي نهاية عكسية.O(1)
5- (Val)insert

توسيع حاوية (set)،عن طريق إدخال عناصر جديدة، نظرًا لأن العناصر الموجودة في (set) يجب أن تكون فريدة، فإن عملية الإدراج تتحقق مما إذا كان كل العنصر مدرج مكافئًا لعنصر موجود بالفعل في الحاوية، وإذا كان الأمر كذلك، فلن يتم إدراج العنصر.

داخليًا، تُبقي هذه الدالة جميع العناصر داخل (set) مرتبة، وفقًا للمعيار المحدد بواسطة، ويتم دائمًا إدراج العناصر في موضعها الخاص بعد هذا الترتيب.

(O(N*log(N)

حيث أن (N) هي عدد العناصر المُدخلة ل (set)

6- (x)swap

يستبدل محتوى (set) التي يتم الاستدعاء بها بمحتوى (x)، وهي (set) أخرى، ويجب أن تكون من نفس النوع، وقد تختلف الأحجام.

بعد استدعاء هذه الدالة، تكون العناصر الموجودة في (set) التي تم الاستدعاء بها، هي العناصر التي كانت موجودة في (x) قبل الاستدعاء، وعناصر الموجودة في (x) هي العناصر التي كانت الموجودة في (set) التي تم الاستدعاء بها.

O(1)
7- ()clearيزيل جميع العناصر من الحاوية، فيصبح حجم الحاوية (0).O(N)
8- ()emptyتختبر ما إذا كانت الحاوية فارغة أم لا،
إذا كانت حاوية فارغة (أي ما إذا كان حجمها 0)، تُرجع (true)،غير ذلك ترجع (false).
O(1)
9- ()sizeتُرجع عدد العناصر في حاوية (set).O(1)
10- ()max_sizeتُرجع الحد الأقصى لعدد العناصر التي يمكن أن تحتويها حاوية (set).O(1)
11- (Val)findيبحث في الحاوية عن عنصر مكافئ لـ (Val) ويعيد مؤشر يشير لموقع العنصر إذا تم العثور عليه، وإلا فإنه يعيد مؤشر يشير لموقع “()set :: end”، أي موقع الذي يتبع العنصر الأخير في (set).(O(log(N)

تطبيق عملي على حاوية Set:

احتاج شخص يدعى “بوب” إلى أن يعثر على إحصائيات “الدرجة الثانية” لسلسلة من الأرقام الصحيحة، ويريد أن يختار رقم من السلسلة مرة واحدة بالضبط ثم يفرزها، إحصائيات “الدرجة الثانية” هي القيمة في الموقع الثاني لسلسلة أرقام المحددة. بمعنى آخر، هو أصغر عنصر أكبر من الحد الأدنى، وهنا سوف نساعد “بوب” في حل هذه المشكلة، كما يلي:

المدخلات:

يحتوي سطر الإدخال الأول على عدد صحيح (n ≤ 100)، حيث أن (n) هو عدد الأرقام في السلسلة، ويحتوي السطر الثاني على أعداد صحيحة مفصولة بمسافات، وهي عناصر السلسلة، هذه الأرقام لا تتجاوز 100 في القيمة المطلقة.

المخرجات:

إذا كان التسلسل المحدد يحتوي على إحصائيات الدرجة الثانية، فقم بإخراج إحصائيات الطلب هذه، وإلا فقم بإخراج (NO).

الحل: (مقترح)

Screenshot-2021-02-18-144307

المصدر: std::set::set(Set in C++ Standard Template Library (STLSet insert() in C++ STL


شارك المقالة: